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

Many thanks for the challenges this week, looking forward to the next ones!