Andrew Shitov Weekly Review: Challenge - 079

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


Task 1. Count Set Bits

This week, the participants were solving a variation of the classical problem of counting bits in a range of numbers. There are different approaches ranging from straightforward bit-by-bit testing to using formulae, and we have a variety of solutions submitted.

Counting the bits

The most direct method is to check all the bits in the number and repeat the procedure for all the numbers from 1 to $N. Here is a possible way to do that that we see in the solution by Kang-min Liu:

    $c += ($n % 2);
    $n div= 2;

Another way is to use bitwise operations, as Roger Bell_West did it:

    $bits += $k +& 1;
    $k +>= 1;

Jan Krnavek used the polymod method to get all the remainders after dividing a number by modulo 2:

1 .. $n
andthen .map: |*.polymod(2 xx *)
andthen .sum

Binary representation

In Raku, you can easily convert any number to a string with its binary representation by calling the base method on it: $n.base(2). Alternatively, you can use a formatting string, for example: $n.fmt('%b'). Having such a string, you can count all 1s in it. Again, there is more than one way to do it. Let us briefly look at the examples found in the submitted programs.

My solution with a regex:

    [+] ((.base(2) ~~ m:g/1/).elems for 1..$n)

Mark Anderson with a non-default argument to comb:

    (1..$N).map(*.base(2)).comb(/1/).elems

Simon Proctor:

    [+] (1..$N).race.map( *.base(2).comb ).flat

Notice a good idea to use race here, as we can make the computations faster and we don’t care about the order.

Arne Sommer:

    (1..$N).map({ $_.fmt('%b') })>>.comb.flat.sum

Colin Crain:

    my $tot += .base(2).comb.sum for ^$input;

Once again, let me point out how easily Raku switches between the string and numeric representations. The topic variable in this for loop is a number which is then converted to a string and is split into separate characters, which then are treated as numbers in the final summation.

Jaldhar H. Vyas:

    my $total = [+] (1 .. $N).map({ sprintf("%b", $_) ~~ m:g/ 1 /; });

Laurent Rosenfeld:

    [+] map { .fmt("%b").comb.sum }, 1..@*ARGS[0]

Mohammad S Anwar:

    (1..$n).map( -> $i { $c += [+] $i.base(2).comb; });

A pointy block -> $i { . . . } often helps to introduce a named variable instead of $_, but you can always use a placeholder variable such as $^n.

Myoungjin Jeon:

    [+] (.base(2).indices(1).elems for ^$_[0]+1)

All these methods are good for small numbers and for prototyping. You can also use them as a mean to get the test answer if you want to implement a more sophisticated algorithm and check its correctness.

Using formulae or observations

There is a sequence known under its number A000788: Total number of 1’s in binary expansions of 0, …, n, which is exactly the sequence what we use in this task. Well, except for the final modulo operation. On the website of The OEIS Foundation, you can find quite a few different algorithms, both recursive and not, which give the result without the need to test each and every bit in all the numbers.

You can also notice that in the sequence of numbers, the least significant bit (20) flips every two numbers. The next bit (21) flips every four times, the third bit (22) flips every eight numbers, and so on. I used this fact in my main solution.

Julio de Castro used the built-in method called msb for detecting the most significant bit and to count its flips:

    sub ms-flips(UInt:D \number) returns UInt:D {
        number == 1 ?? 1 !! 1 + number.msb * 2 ** (number.msb - 1)
    }

Such programs are much more efficient comparing to those using bare bit testing, but of course, it is not always clear how they achieve the result :-)

Let me show the complete text of the program by Markus Holzer that also uses sigil-less variables to speed it up:

    unit sub MAIN( Int \N );

    my Int \t = 2;
    my Int \r = 0;
    my Int \n = N;

    while n {
        my Int \a = t +> 1;
        my Int \s = N +& ( t - 1 );
        my Int \d = N div t;

        r := r +  d * a;
        r := r +  1 + s - a if 1 + s > a;
        t := t +< 1;
        n := n +> 1;
    }

    say r % 1000000007;

Notice that we do not loop over the whole range between 1 and N but only over the list of powers of two not exceeding N.

Another interesting solution has been submitted by Athanasius, here is it’s main part:

    my UInt $total-count-set-bit = 0;

    loop (my UInt $bit = 1; $bit <= $N; $bit +<= 1)
    {
        $total-count-set-bit += ($N +> 1) +& +^($bit - 1);

        $total-count-set-bit += ($N +& (($bit +< 1) - 1)) - ($bit - 1)
            if $N +& $bit;
    }

If you want to explore the different approaches and compare there properties, I would recommend you to examine the file bench.raku where Markus Holzer collected different implementations.

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. Trapped rain water

The participants showed a number of inventive approaches to the problem. To test the solution, you not only have to work on one of the sample set but also try to create a histogram where one of its sides is open and cannot keep water. For example, 2, 1, 4, 1, 2, 2. Some of the submitted solutions print incorrect results for such inputs.

In one of the methods, you scan the histogram along its horizontal coordinate and look left and right to find the smallest wall that is visible from that position. That level is the maximum level that can be filled with water. Now just subtract the height at the current position, and here you are, you know the height of the water pole at this position.

Jan Krnavek’s solution demonstrates this approach extremely clearly:

sub trapped-rain-water ( +@n ) {
    @n.pairs
    andthen .map: { (@n[0.. .key].max min @n[.key..*].max) - .value }\
    andthen .sum
}

Mark Andreson uses regexes to find those unit cells that can keep water.

    while @ints.join ~~ m:c($pos)/ (\d)(\d+)(\d) <?{ $0 > $1.comb.all < $2 }> / {
        $sum += (($0, $2).min <<->> $1.comb).sum;
        $pos = $/.to - 1;
    }

Water can be trapped within those areas where there are higher walls on the right and left sides. Using the language of regexes, Mark formulates it in the following way: / (\d)(\d+)(\d) <?{ $0 > $1.comb.all < $2 }> /. The sequence of brick piles \d+ must be surrounded by two walls which are higher than all of the inner blocks: $0 > $1.comb.all < $2. (This solution works for the hights not bigger than 9, but you can probably modify the program to use Unicode one-characters digits such as ⑪. Raku is great in its ability to correctly evaluate constructions such as ⑪.Int.)

Colin Crain finds the peaks inside the histogram and then computes the free area between them:

    for (@input.min..@input.max).reverse -> $level {
        my @peaks = @input.keys.grep({ @input[$_] >= $level });
        $vol += ($_[1] - $_[0] - 1) for @peaks.rotor(2=>-1);

        . . .
    }

Let me stop here as all the solutions are really interesting this week, and I would have to repeat the whole review from the video below to describe their best features.

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