Andrew Shitov Weekly Review: Challenge - 073

Sunday, Aug 23, 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 073 of The Weekly Challenge!. For a quick overview, go through the original tasks and recap of the weekly challenge.


Task 1. Min Sliding Window

The task was to scan the array of integers @A with a window of the given size $S and print the minimum value on each step.

The submitted solutions demonstrated that that was one of the simplest tasks during the last few weeks of the Weekly Challenge. Nevertheless, there are several interesting moments that I would like to cover here in this review.

Using rotor

The first group of solutions includes those that used the built-in rotor routine. One of the ways to work with it is to pass a pair, in which case you get the groups of overlapping lists with the given width. The key of the pair defines the width; the value stands for the gap between the series. If the gap is negative and its absolute value is 1 unit smaller than the width, we get exactly what we want in the task.

For instance, for the sample array and the window width of 3:

my @a = 1, 5, 0, 2, 9, 3, 7, 6, 4, 8;
say @a.rotor(3 => -2);

This program produces the following sequence of lists:

((1 5 0) (5 0 2) (0 2 9) (2 9 3) (9 3 7) (3 7 6) (7 6 4) (6 4 8))

Now, just find the minimum and print the result.

Using array slices

Another group is taking the sub-arrays using trivial computations of the indices of the first and the last elements within the window.

For example, in a loop using an array slice, as Noud Aldenhoven did it.

    gather for 0..@A.elems-$S -> $i {
        take min(@A[$i..$i+$S-1]);
    }

Using maps

There is a cluster of solutions where scanning is done using the map routine. For example, look at the nice one-liner by Ben Davies:

    say (0...@array - $s).map({ @array.skip($_).head($s).min });

Finding the minimum

Not a surprise that the built-in min routine was used widely. But its usage differs from one solution to another.

For example, Colin Crain used it in a WhateverCode block inside a map:

    my @windows = @A.rotor($S=>-$S+1);
    my @output = @windows.map( *.min );

A similar solution is proposed by Markus Holzer:

    say join ' ', @A.rotor( $S => -($S - 1) ).map: *.min;

In my solution, I am using for and calling .min on a topicalized variable:

    .min.say for @a.rotor($s => 1 - $s);

Collecting the results

In those solutions where the result is not printed immediately, the resulting values are usually collected in an array, and there are two main approaches to it. First, by pushing the newly computed item. Look at Roger Bell_West’s variant for the reference:

    my @out;
    for (0..(@a.elems-$s)) -> $i {
        push @out,min(@a[$i..$i+$s-1]);
    }

Second, by using a gather and take pair, for example, as in Laurent Rosendeld’s code:

    my @result = gather {
        for 0..@a.elems - $s  -> $i {
            take min @a[$i..^$i + $s];
        }
    }

Bonus track

An outstanding solution is demonstrated by Jan Krnavek, where all the main steps of the algorithm are connected together using the andthen infix:

    sub min-sliding-window (@a, $s) {
        @a
        andthen .rotor: $s => - $s.pred
        andthen .map: *.min
    }

Video review

The full review of the solutions to the Task 1 is available on YouTube:

Starting from this week, I’ll be publishing the timestamps for quick access to the review of each solution.

Additional materials

Task 2. Smallest Neighbour

In the second task, you are also working with an array of integers and for each of the items, you need to find the minimum item among the elements prior to the current one. If the current one is bigger than that minimum or if it is the first item in the array, print 0.

To understand the task, you needed to examine the examples, but most of the participants dit it well; there is only one solution that missed that additional requirement.

Excerpts from the solutions

In the solutions, we again see similar ways of finding the minimum values of a part of an array. Collecting the result is done via gather and take or by pushing or appending the elements to the end of the array.

To simplify finding the minimum, some participants used grep to ignore all the items which are bigger than the current one. For example, you can see it in a solution by Mark Andreson:

    @A.kv.map(-> $k,$v {(@A.head($k+1).grep(* < $v) or 0).min}).join(", ").List.say;

Or as Markus Holzer did it in his compact solution:

    say join ' ', 0, gather for 1 .. +@A - 1 -> $i {
        take .min with @A[ 0..$i-1 ].grep( * < @A[$i] ) or 0 };

By the way, Roger Bell_West demonstrated the method of computing the minumum without using any explicit comparisons. Just add the current minimum value to the new data set, and find the minimum again:

    $wm=min($wm,@a[$i-1]);

Myoungjin Jeon reminds us how to mixin a role in Raku with but:

    role zero { method raku { "0" } }

    . . .

    $smallest < $c ?? $smallest !! $c but zero

Later, when you call the raku method on a value, the role’s method is used for the elements where that role was applied:

    say "Output: {@answer.map( *.raku ).map( *.Int ).Array.raku}"

Bonus track

As a side story, watch the deparsing and modifying the regular expression that Mohammad S Anwar used in his solution, where he takes the input data as a string:

    sub MAIN(Str $list = "7, 8, 3, 12, 10") {
        say $list;
        smallest-neighbour($list).join(', ').say;
    }

    sub smallest-neighbour(Str $list is copy) {

        die "ERROR: Invalid list [$list].\n"
            unless $list ~~ /^[\s?\-?\d\,?\s?]+$/;
        . . .
    }

Video review

The full review of the solutions to the Task 2 is available on YouTube:

The timestamps to the reviews of the individual solutions:

Additional materials


BLOGS


Andrew Shitov, Arne Sommer, Colin Crain, Jaldhar H. Vyas, Javier Luque, Luca Ferrari, Laurent Rosenfeld, Mohammad S Anwar and Roger Bell_West.


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