Andrew Shitov Weekly Review: Challenge - 078

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


This week, both tasks gave some possibilities to literate programming in Raku. Indeed, in the first task, we have to find an array items which are bigger than all of the items to its right. Just use a built-in all routine: say @a[$_] if @a[$_] > all(@a[$_ ^.. *]). In the second task, we need to rotate an array. So, just use rotate which is a part of the language: say @a.rotate($_) for @b. Isn’t Raku amazing?

Task 1. Leader Element

There are three main approaches to the solution here.

Built-in all

In the first approach, we compare the current element with the elements following it. In this case, the closer the item is to the end of the array, the more often we check it. It is a bit inefficient but is completely fine for small data sets.

Let me show my program as an example of the first approach:

    my @a = 9, 10, 7, 5, 6, 1;

    for @a.kv -> $i, $v {
        say $v if $v > all(@a[$i^..*]);
    }

Maximums from the end

It is still interesting to implement a more efficient algorithm. All you need to do that is to walk from right to left and find the maximums on your way.

Kang-min Liu demonstrates an example of the this approach:

    sub leaders(@A) {
        my $max = -Inf;
        return @A.reverse.grep(-> $v { ($v > $max) ?? ( $max = $v ; True ) !! False }).reverse();
    }

    say leaders(@*ARGS);

Other approaches

Julio de Castro offered an attractive program written in a functional style:

    sub get-leaders {
        my \A          = ( 9, 10, 7, 5, 6, 1 );
        sub is-last    { $^i == A.elems - 1 }
        sub current    { A[$^i] }
        sub following  { A[$^i + 1] }
        sub is-leading { current($^i) > following($^i) }
        sub is-leader  { is-last($^i) || is-leading($^i) }
        sub if-leader  { is-leader($^i) ?? current($^i) !! () }
        sub add-leader { ($^list.flat, if-leader($^pos)).flat }

        A.elems == 0 ?? (0) !! [[&add-leader]] ((), |^A)
    }

    say get-leaders;

There is a tiny mistake there and you can watch the video review below to see how you can fix the solution. Nevertheless, enjoy the beauty of decomposing the task into clearly defined simple steps.

Markus Holzer created an additional solution that uses recursion:

    sub leader-elements-recursive( @stuff ) {
        sub find( $that, *@the-rest ) {
            take $that      if $that > all @the-rest;
            find |@the-rest if @the-rest }

        +@stuff ?? gather find |@stuff !! 0
    }

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. Left Rotation

In the second task, we need to rotate an array.

Built-in rotate

The simplest possible solution in Raku is to use the built-in rotate routine, as, for example, in my solution:

    my @a = 10, 20, 30, 40, 50;
    my @b = 3, 4;

    say @a.rotate($_) for @b;

The way you scan the values in @b can be different. For instance, with the help of map as in the solution by Jan Krňávek:

    sub left-rotate ( @a, @b ) {
        @b.map: { @a.rotate: $_ }
    }

Collecting the result pieces can be done with gather and take. Actually, this is one of the most favourite features of Raku among the participants of The Weekly Challenge. Look, for example, at how it is used in the program submitted by Jason Messer:

    sub rotate-array-by(:@array, :@indices) {
        gather for @indices {
            take @array.rotate: $_;
        }
    }

Swapping the parts

Another approach to the problem is to swap the source data @a around the pivot positions from @b. Here is the essence of it demonstrated in the program by Kang-min Liu:

    sub rot($n, @A) {
        return @A[ $n .. *, 0 .. $n-1 ].flat;
    }

The two ranges $n .. * and 0 .. $n-1 define the two slices of the source array, which we swap to get the result.

Modulo

Another way to rotate the data is to subscript it with the index that is first incremented and then corrected by the modulo operation. In this case, the index loops to the beginning of the array. The solution by Julio de Castro demonstrates this approach:

    sub rotate {
        my \A = (7, 4, 2, 6, 3);
        my \B = (1, 3, 4);
        for B -> \rotation {
            say (|^A).map: { A[ ($^index + rotation) % A.elems ] }
        }
    }

    rotate;

Also notice the usage of sigilless variables.

Markus Holzer also gives a solution with the modulo operator as one of the possible variants:

    sub rotate-array-concise( @a, $i ) {
        ( @a + $i ) % @a andthen [ |@a[ $_..* ], |@a[ ^$_ ] ] }

Markus also noticed that rotation values which are bigger than the length of the source data should be corrected before real rotation to avoid redundant loops:

    multi rotate-array-multi( @a, $i where $i >= @a ) {
        rotate-array-multi( @a, $i % @a ) }

Double and cut

Another interesting idea (well, formally it can be classified to the previous group) is proposed by Roger Bell_West. The array is first doubled so that it contains two copies of itself, and then you take its middle part starting from the given rotation position:

    sub leftrot(@a,@b) {
        my $l=@a.end;
        my @t=(@a,@a).flat;
        my @o;
        for @b -> $c {
            push @o,[@t[$c..$c+$l]];
        }
        return @o;
    }

Additional reading

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