Andrew Shitov Weekly Review: Challenge - 077

Sunday, Sep 20, 2020| Tags: Raku

Raku Solutions Weekly Review

Getting in Touch

Email › Email me (Andrew) with any feedback about this review.

GitHub › Submit a pull request for any issues you may find with this page.

Twitter › Join the discussion on Twitter!

We’d greatly appreciate any feedback you’d like to give.


Welcome to the Raku Review for Week 077 of The Weekly Challenge!. For a quick overview, go through the original tasks and recap of the weekly challenge.


The tasks this week required some additional thinking before the actual implementation. The first task, in particular, can be solved in just a few lines of code. But let’s move on directly to them.

Task 1. Fibonacci Sum

In this task, we need to find the combinations of non-repeating Fibonacci numbers that add up to the given number $N. In the ‘official’ Fibonacci sequence, there are only two equal items; those are 1 and 1 at the very beginning of it. So, it is quite practical to use a shifted sequence that starts with 1, 2.

Most of the participants employed the sequence operator of Raku to generate Fibonacci numbers below and including $N:

    my @fib = 1, 2, * + * ...^ * > $N;

The next steps fall into two groups.

In the first, brute force is applied to find the valid result by filtering all the combinations that you can make with the given list of Fibonacci numbers. For example, a self-explanatory code in Laurent Rosenfeld’s program:

    for @fib.combinations -> $s {
        say $s if $n == [+] $s;
    }

In Colin Crane’s solution, there’s an exciting addition to speed up the computations:

    my @output = @fib.combinations.race:8degree:200batch.grep( *.sum == $target );

The race method together with its degree and batch parameters instructs the compiler to perform operations in parallel.

A more traditional method call can replace the non-standard syntax with colons:

    @fib.combinations.race(degree => 8, batch => 200)

The second approach is to build the representation of the number directly, and there is some theoretical support to that via the so-called Zeckendorf representation.

For example, for the input number 1001, the biggest Fibonacci number is 987, so we take it. The remainder is 14, for which the biggest Fibonacci number is 13. So, 1001 equals 987 + 13 + 1, and it is the shortest sum. To get all possible representations of the original number, you need to repeat the procedure for all of the numbers 987, 13, and 1 and take only those combinations where you have no repeated numbers.

Markus Holzer did an incredible job to not only implement the algorithm but also to make it extremely fast. His program finds the result for a big enough number 123456789 within 10 seconds, which is an unbeatable result among the other solutions.

Additional reading

Video review

The full review of Task 1 is available on YouTube:

The timestamps for quick access to the review of each solution.

Task 2. Lonely X

In the second task, for the given matrix, each cell of which only keeps X or O, we need to find the so-called lonely Xs which are surrounded only by Os.

The general approach is to scan the source matrix so that we visit all of its cells, and then to visit all the neighbours that surround the cell. As a lonely X can appear on the border or in the corner, you should ignore the missing neighbours.

A straightforward pair of nested loops can be used to scan the cells. As in Arne Sommer’s solution, for example:

    for ^$rows -> $row
    {
        for ^$cols -> $col
        {
            . . .
            $is_lonely++ if is_lonely(@matrix, $row, $col);
        }
    }

Visiting the neighbours is equivalent to changing one or both of the coordinates to ±1 and checking the contents of the cell:

    for (-1, 0, 1) -> $r
    {
        for (-1, 0, 1) -> $c
        {
            next if $r == $c == 0;
            next unless @matrix[$row + $r][$col + $c].defined;

            return False if @matrix[$row + $r][$col + $c] eq 'X';
        }
    }

A very attractive and useful feature of Raku that help to simplify the code is a junction. There are different forms of it, in particular, the any- and all-junctions. Just look at the program submitted by Feng Chang to see the advantage immediately:

    for 1..$rows -> $i {
        for 1..$width -> $j {
            my $junc = all(@a[$i-1;$j-1], @a[$i-1;$j], @a[$i-1;$j+1],
                        @a[$i;$j-1],                @a[$i;$j+1],
                        @a[$i+1;$j-1], @a[$i+1;$j], @a[$i+1;$j+1]
                    );
            ++$cnt if @a[$i;$j] eq 'X' and $junc eq 'O';
        }
    }

In the body of the inner loop, the $junc variable encloses all eight neighbours in a single variable, which is later compared with the value: $junc eq 'O'.

In the same solution, we can also see a step to prepare the input data to surround the whole matrix with ‘good neighbours‘:

    @a.push($line.comb.Array.unshift('O').push('O'));

    . . .

    @a.unshift(['O' xx $width + 2]);
    @a.push(['O' xx $width + 2]);

By doing that, you do not have to check if the neighbour exists when visiting it.

But checking if we are withing the borders is another delightful small task that you can solve differently. For example, Mark Anderson uses the defined-or operator // to substitute an empty string for the non-existing cells:

    take [$r, $c] unless any((@matrix[$r-1][$c-1] // q{}),
                             (@matrix[$r-1][$c  ] // q{}),
                             (@matrix[$r-1][$c+1] // q{}),
                             (@matrix[$r  ][$c-1] // q{}),
                             (@matrix[$r  ][$c+1] // q{}),
                             (@matrix[$r+1][$c+1] // q{}),
                             (@matrix[$r+1][$c  ] // q{}),
                             (@matrix[$r+1][$c-1] // q{})) eq "X";

(Also don’t miss the use of the any-junction.)

Markus Holzer uses andthen to go on only with defined cells:

    $matrix[ $x + $c[0]; $y + $c[1] ] andthen $_ eq "X"

To build the ‘guest map’ of the local neighbours, we can use different tricks. For example, the following construct gives the deltas such as (-1, 1) or (0, 1) that you can add to the coordinates of the current cell:

    <1 0 -1> X <1 0 -1>

Of course, nobody stops you from hard-coding the list of relative coordinates:

    state @maybe-neighbours = (-1,-1), (-1,0), (-1,1), (0,-1), (0, 1), (1,-1), (1,0), (1,1);

When computing the absolute coordinates, you can even use it with a cute hyper-operator:

    @neighbours.map(* <<+>> @coord))

Additional reading

Video review

There are much more smart coding bits that the participants used in their solutions. Enjoy the full review on YouTube.

The timestamps to the reviews of the individual solutions:


BLOGS


Andrew Shitov BLOG #1 and BLOG #2

Arne Sommer, Colin Crain, Laurent Rosenfeld, Mohammad S Anwar, Roger Bell_West and Shahed Nooshmand.


If you want to participate in The Weekly Challenge, please contact us at perlweeklychallenge@yahoo.com.

SO WHAT DO YOU THINK ?

If you have any suggestions or ideas then please do share with us.

Contact with me