Andrew Shitov Weekly Review: Challenge - 075

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


This was a tough week, and the tasks appeared to be not that simple as they might seem from the beginning. Among the submitted solutions, there are three types of programs: straightforward solutions that implement a more or less language-independent algorithms, Raku-specific solutions where you can see the beauty of the language and its features, and the solutions that are unnecessarily complicated as to my opinion.


Task 1. Coins Sum

In the first task, you need to form a collection of coins so that they add up to the required amount. Of course, nowadays, in the era of electronic payments, we do not do such exercises often enough, so it was a good skill to train.

Combinations

One of the possible ways to solve the task is to generate all possible combinations from the given set of coin types, and then select those that form the correct answer.

My solution falls into this group. First, I fill the wallet so that I can reach an amount with a single type of coins:

my @wallet;
@wallet.append: $_ xx ($sum div $_) for @coins;

Then, just combine everything with everything and filter:

.say for @wallet.combinations.unique(:as(*.Str)).grep({$sum == [+] $_});

An interesting thing to look at is how different participants filter unique lists:

.unique(:as(*.Str))

Or:

.unique(:with(&[eqv]))

Or:

.unique: with => &[~~]

Or via a similar code with parentheses:

.unique( with => &[~~] )

Recursion and friends

Another group of solutions includes recursive gathering the coins for the change. For example, take the biggest or the smallest coin, then repeat the procedure for the remaining amount, and so on. A special case in this group of solutions is when the amount is representable by a single type of coins.

Let me demonstrate a part of the solution by Javier Luque where you can clearly see the recursive nature of the algorithm:

    sub coin-combinations(@C, $S, @bag is copy) {
        for (@C) -> $coin {
            @bag.push($coin);
            if (@bag.sum < $S) {
                    coin-combinations(@C, $S, @bag);
            }
            . . .

Or, examine the snippet of Athanasius’s solution, where the next iteration happens for the new target amount, which is smaller than the current amount by $i * $coin.

    sub count-coin-combinations(. . .) {
        . . .
        my UInt $new-target = $target - ($i * $coin);

        . . .

        $sum += count-coin-combinations($new-target, $coins.clone);
        . . .
    }

Video review

There are more interesting moments in the solutions, which I highligted in the video review. The full review of the solutions to the Task 1 is available on YouTube:

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

Please refer to a separate video for the review of the solutions of Shahed Nooshmand.

Task 2. Largest Rectangle Histogram

In the second task, you are given a histogram with integer heights of the cells, and you need to find the biggest rectangle that you can find in it. One thing that was not clear from the definition is whether you can treat a single histogram bin as a rectangle or you need at least two cells to form a shape. Different solutions treat this differently.

My personal winner in the category of the most Raku-ish solution is the program by Markus Holzer. Here is the complete solution:

    my @A = (3, 2, 3, 5, 7, 5);
    say ( 1..@A ).map({ |@A.rotor($_ => 1 - $_) }).max({ .min * .elems });

We already saw a similar use of rotor in the previous weeks, and it still demonstrates its power. Another thing to note is how you can employ the code block in the max method to use your own definition of what maximum is. In this case, we are looking for the maximum area, and you can immediately express it in the code: .max({ .min * .elems }).

The straigtforward solution is to scan the rectangle of the possible widths at every possible position. For example, here is an example of such approach in the solution by Noud Aldenhoven.

    sub largest-rec-hist(@A) {
        my @largest-sub-rec = [];
        for 0..(@A.elems - 1) -> $i {
            for ($i + 1)..(@A.elems - 1) -> $j {
                @largest-sub-rec.push(($j - $i + 1) * @A[$i..$j].min);
            }
        }
        return @largest-sub-rec.max;
    }

Shahed Nooshmand is using a very inventive way to generate the ranges of the rectangles to test:

    my @indices = |(0..(@A − $length) Z.. ($length − 1)..^@A).max: { @A[|$_].min }

Notice the three range operators (..) here including the operator inside the zip metaoperator: Z...

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:

Please refer to a separate video for the review of the solutions of Shahed Nooshmand.

BLOGS


Andrew Shitov: BLOG #1, BLOG #2, BLOG #3

Arne Sommer, Colin Crain, Javier Luque, Laurent Rosenfeld, Luca Ferrari, 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