Andrew Shitov Weekly Review: Challenge - 074

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


Task 1. Majority Element

The first task this week was to find the majority element in the array of integers. The majority element is the item that occupies more than half of positions in the array. It is worth noting that while it is not explicitly said in the task, you cannot have more than one such element. Indeed, if more than the half seats are occupied, there is simply not enough space for any other majority one. But it may happen that there is no such item, in which case the program must print -1.

Bags (not bugs)

In this task, the most useful tool of Raku is the Bag datatype. If you convert an array to a bag, you immediately get its elements counted. Here is an example that you can reproduce in Rakudo’s REPL to see what happens:

> my @a = 3, 4, 5, 3, 3, 5;
[3 4 5 3 3 5]
> @a.Bag;
Bag(3(3), 4, 5(2))

We see that in the source array, the value 3 appears three times, 5 happens twice, and 4 occurs only once. This principle is the main engine in many submitted solutions.

Outside of the bags

So, the simplest way to count the characters is to use a bag:

@a.Bag

In Raku, you can also use the classify method to make the classification of the elements, which is letter counting in our case.

my %count = @A.classify({ $_; });

An example with map seems to be an interesting one too:

@A.map({ %count{$_}++ });

There are also other ways to do that via more traditional (read as Perlish) approaches.

my %counting;
%counting{ $_ }++ for @array;

Floor

Another thing probably worth noting is that there is no need to compute the floor of the half-length. When we compare the number of occurrences of a character with size_of_list/2, we always compare an integer with either another integer or with an integer plus 0.5. If you use < for comparison, there is no difference between comparing, say, 4 with 5 or with 5.5. Also, we can use integer division and type @a.elems div 2 instead of @a.elems / 2.

Nevertheless, there is a very interesting approach demonstrated by Colin Crane to modify the grammar and introduce a mathematical notation for taking the floor:

sub circumfix:<⎣ ⎦>( Numeric $n ) {
    $n.floor ;
}

Having this user-defined circumfix operator, you can use its parts to surround the value that you need to round downwards:

⎣@A.elems/2⎦

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.

Additional material

Task 2. FNR Character

The second task was to find the first non-repeating character in the series of substrings of the given string. The task left some room for questions as it was not completely clear that you either need to scan the substring from right to left, or to take into account the partial result that was computed on the previous step. Nevertheless, the majority of the solutions produce the output that agrees with the example given in the task description.

Preparing substrings

So, say, we’ve got the string ababc, and we need to make a series of substrings a, ab, aba, abab, and ababc. The solutions demonstrate the following ways.

Using a simple loop and taking an explicit substring:

for 1..$s.chars -> $pos {
    my $substr = $s.substr(0, $pos).join;
    . . .
}

Filling the array of characters in a loop:

my @left;
gather BUILD: for $s.comb -> $strch {
    @left.unshift($strch)
    . . .
}

Using the triangular version of a reduction operator around the list creation operator:

[\,] $S.comb

Raku-specific solutions

There are a couple of solutions that I want to accentuate.

One of them, by Jan Krňávek , introduces a user-defined infix operator, which is then used in a triangular reduction operation, whose result parts are then concatenated using another reduction operator. Just browse for the code to enjoy it.

sub infix:<FNR> (+@a) is assoc<list> {
    @a.first: * ∉ @a.repeated, :end orelse '#'
}

sub FNR-charakter ( $s ) {
    [~] [\FNR] $s.comb
}

Myoungjin Jeon used a role to inject the new method to a string:

role fnr {
    method sayLNR ( Str:D $str = self.Str ) {
        . . .
    }
    . . .
}

my $fnr-string = $sample does fnr;
. . .
$fnr-string.sayLNR;

The compact winners

One of the most compact solution, which is also a very idiomatic Raku code, is proposed by Markus Holzer:

my $S = ‘ababc’;
.say for ( [\,] $S.comb ).map( -> $L {
    my $B = $L.Bag;
    $L.reverse.first({ $B{ $_ } == 1 }) || "#"
});

Here, we have non-ASCII quotes, topicalizing the result, triangular reduction operator, the .comb method, a pointy block with a signature, and a Bag.

Another one-liner solution which, actually, needs some tuning before you can run it, is submitted by Shahed Nooshmand. Here it is:

my $S = 'ababc';
([\,] $S.comb).map({ .grep({ .grep($^c) == 1 })[*-1] // '#' }).join.say

In it, we see another cool feature of Raku — placeholder variables and a typical Raku thing — taking the last element of an array by subscripting it as [*-1].

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, 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