# Perl Weekly Challenge 086

Another week, another challenge and chance to practice Perl and Python programming skills.

#### Challenge 1 - Pair Difference:

You are given an array of integers `@N` and an integer `\$A`.

Write a script to find find if there exists a pair of elements in the array whose difference is `\$A`.

Print `1` if exists otherwise `0`.

This task got me refactoring it 3 times.

First my line of thought was - OK, generate all pairs of numbers in the list via some combinatorics module, or create two nested loops checking the same.

But something did not sound right - in facts, I do not need the pairs themselves. I need just check if there is a number satisfying the condition for another number.

So I wrote code storing the whole array to a hash - keys are the numbers and values are just 1 to see they exist.

And then loop through the array, check if a corresponding hash exists and stop, if so.

I submitted the solution and happy.

Then I woke up literally in the middle of the night (does it happen to you that a solution wakes you up too?) - thinking, why am I storing the whole array first if I can stop when finding a match?

Time to refactor again... final solution stores the value and then checks, if we already have seen a number in the right distance (plus or minus).

Perl:

``````my %h;
for (@\$arr) {
\$h{\$_} = 1;

return 1 if (\$h{\$_ + \$\$data{a}}) or (\$h{\$_ - \$\$data{a}});
}``````

After so many years I’m still not happy with the way Perl passes parameters to functions, having to write things like \$\$data...

Python:

``````hash_keys = {}
for number in n:
hash_keys[number] = 1

if hash_keys.get(number+a, 0) or hash_keys.get(number-a, 0):
return 1``````

A bit cleaner syntax... could be even more simplified using defaultdict.

#### Challenge 2: Sudoku Puzzle Solver

You are given Sudoku puzzle (9x9).

Write a script to complete the puzzle.

Wow, what a task - writing a Sudoku solver.

My mind started to go to recursive overflow, as it does always when solving recursive or Dynamic programming tasks.

Let’s get to it... I had two lines of thought:

First I was thinking about writing a backtracking algorithm, simply finding first empty spot, try to find a valid number, put it there... and then just send it to the function again as a new puzzle.

Then I thought to make it more interesting and a bit heuristic - why not start putting random numbers and see if they fit. As strange as it sounds, I started to write the second option - only to find out that when I implemented a validity checking, I was - in facts - writing the first solution.

So at the end I implemented the expected backtracking.

From the code:

1. I was struggling a bit to get a true copy of the puzzle for each iteration, as it is passed as a reference. This got it working:

Perl:

``my \$next_puzzle = dclone( \$puzzle );``

Python:

``next_puzzle = deepcopy(puzzle_input)``
1. Then just loop trough the array/list and see what needs to be filled in. I loaded the input the way that empty positions are coded as 0.

Perl:

``````for my \$row (0..scalar @\$next_puzzle -1) {
for my \$col (0..scalar @\$next_puzzle -1) {

# find the next empty position
next if \$\$next_puzzle[\$row][\$col];``````

Python... why there is no enumerator in Perl?

``````for row, row_data in enumerate(next_puzzle):
for col, item in enumerate(row_data):

if item != 0:
continue``````
1. Then just loop trough the array/list and see what needs to be filled in. I loaded the input the way Get a list of valid numbers for the position. This is done by looping through the respective rows, columns and quadrants. If there are none, check if the solution is complete.

Perl:

``````my \$valid_options = get_valid_options( { puzzle => \$next_puzzle, row => \$row, col => \$col } );

unless (keys %\$valid_options) {
# nothing left to try, check if the solution is complete

return unless is_complete(\$next_puzzle);
return \$next_puzzle;
}``````

Python... was playing first with the any() operator, finally decided to write the old-fashioned way.

``````valid_options = get_valid_options(puzzle=next_puzzle, row=row, col=col)

if not valid_options:
# nothing left to try, check if the solution is complete

for test_row in next_puzzle:
for test_item in test_row:
if item == 0:
return

return next_puzzle``````
1. Finally loop through the valid options, creating a new puzzle to be passed back to the function.

Perl:

``````my @hash_keys = keys %\$valid_options;

# iterate through the candidate numbers

for my \$next_key (@hash_keys) {
\$\$next_puzzle[\$row][\$col] = \$next_key;

my \$next_iteration = solve_position(\$next_puzzle);
return \$next_iteration if \$next_iteration;
}``````

Python...

``````for next_key in valid_options:
next_puzzle[row][col] = next_key

next_iteration = solve_position(deepcopy(next_puzzle))

if next_iteration:
return next_iteration``````

Test cases were added to both exercises to make sure it passes the requirements.

Complete code in Github: https://github.com/LubosKolouch/perlweeklychallenge-club/tree/master/challenge-086/lubos-kolouch