Andrew Shitov Weekly Review: Challenge - 084

Thursday, Nov 19, 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 084 of The Weekly Challenge!. For a quick overview, go through the original tasks and recap of the weekly challenge.

Task 1. Reverse Integer

In the first problem, the task is to take a number and print it backwards. A couple of additional requirements are: 1) to keep the sign and 2) to print 0 if the flipped number exceeds the size of a 32-bit integer.

Obviously, the most Rakuish solution is to use the flip method. It works with strings, but Raku will implicitly translate numbers to it. To keep the sign, you can use the sign method that returns +1 for positive numbers, -1 for negative numbers and 0 for 0. Try it in the REPL shell:

    $ raku
    > 0.sign
    0
    > -20.sign
    -1
    > 20.sign
    1

So, here is a possible solution:

    my $r = $n.sign * $n.abs.flip;
    say -2147483648 <= $r <= 2147483647 ?? $r !! 0;

Feng Chang split the task into the four clear options:

    given $n {
        when (0)             { put 0 }
        when (0 < $n ≤ imax) { put $n.flip; }
        when (imin ≤ $n < 0) { put '-', (-$n).flip; }
        default              { put 0; }
    }

Jan Krnavek used a combination of the above-mentioned methods:

    with $n.abs.flip * $n.sign {
        when -2³¹ ..^ 2³¹ { $_ };
        default           { 0  };
    }

Mark Anderson uses smartmatch directly (without the given block):

    $N = $N.abs.flip * $N.sign;
    my \MAX = 2**31;
    say $N ~~ -MAX .. MAX-1 ?? $N !! 0;

Markus Holzer decided to use the subst method to replace the digits in the number and thus to keep the minus sign in place:

    say -2³¹ <= $i <= 2³¹
        ?? $i.subst( / \d+ /, + *.flip )
        !! 0;

Notice how Stuart Little keeps the sign by removing the last character from what sign returns:

    return ($nr >= 2**31) ?? (0)
    !! ($nr.sign.chop ~ $nr.abs.flip);

Of course, nobody stops you from determining the sign by comparing the number with 0, as Arne Sommer, Colin Crain, and Kang-min Liu did it:

    my $sign = $N < 0
        ?? "-"
        !! "";

    my $new = $sign ~ $N.abs.flip;

    . . .

    my $sign = $num < 0 ?? -1 !! 1 ;
    my $out  = $sign * $num.abs.flip ;

    . . .

    my $o = ($n < 0 ?? -1 !! 1) * flip abs $n;
    return (-2³¹ ≤ $o < 2³¹) ?? $o !! 0;

Roger Bell_West and Ulrich Rieke used regexes to extract the digits and the sign from the number:

    my $r=$s.comb.reverse.join('');
    if ($r ~~ /(<[0..9]>+)\-$/) {
        $r="-$0";
    }

    . . .

    $N ~~ /(<[+-]>*)(\d+)/ ;
    my $maximum = 2147483647 ;
    if ( $N.Int <= $maximum ) {
        say ($0.Str ~ $1.Str.flip) ;
    }
    else {
        say 0 ;
    }

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. Find Square

In the second task, you take a matrix with 1s and 0s and have to find the number of all possible squares, whose corners keep 1s.

To solve the task, you can scan each and every cell of the matrix, and from there ‘blow’ the squares of different sizes before you reach one of the edges. Here is an example of how you do it with three nested loops:

    for ^$w -> $x {
        for ^$h -> $y {
            for 1..* -> $z {
                last if $x + $z >= $w || $y + $z >= $h;

                . . .

To test and count the squares, just check the values at the corresponding coordinates:

    $count++ if all(
        @m[$x; $y     ], @m[$x + $z; $y     ],
        @m[$x; $y + $z], @m[$x + $z; $y + $z]
    );

A number of participants noted that you could optimise this approach by skipping the entire third loop if you see that the cell at coordinates ($x, $y) is 0. Indeed, all further checks will fail with such a corner.

Instead of nesting loops, you can use Raku’s cross operator X to make the table of cell coordinates:

    for 0..^@N[0].elems-1 X 0..^@N.elems-1 -> ($i, $j) {
        . . .

Or:

    multi find-square ( @n, ) {
        my $rows     = @n.elems;
        my $columns  = @n[0].elems;
        ^$rows X ^$columns
        andthen .grep: -> ($x, $y) { @n[$x;$y]==1 }\
        andthen .map:  { find-square @n, :topleft($_)  }\
        andthen .sum
    }

Another interesting approach is to — again! — use combinations to test different square sizes. This fragment also uses the above-mentioned optimisation to skip the squares with 0 in the corner:

    for ^@matrix.end -> $i {
        my @indices = @matrix[$i].grep(1, :k);

        next unless @indices.elems >= 2;

        for @indices.combinations(2) -> [$h, $t] {
            my $skip = $i + $t - $h;
            next if $skip > @matrix.end;
            $count++ if all @matrix[$skip][$h, $t];
        }
    }

There are more interesting bits both in the algorithms and in language usage, so I invite you to watch the video review and to look at the code more precisely.

Video review

The full review of Task 2 is available on YouTube:

The timestamps to the reviews of the individual solutions:


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