# 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`

.`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:

- 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)`

- 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
```

- 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
```

- 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