πŸŽ₯ Raku challenge review week 70

In this article, my review of the Raku solutions to the Weekly Challenge 70. The tasks are: 1) Character swapping, and 2) Generating Gray code. As a regular part of the review, there are two video covering all solutions that were sent by the participants.

This text is written for The Perl Weekly Challenge and was originally published at perlweeklychallenge.org/blog/p6-review-challenge-070.

Task 1. Character swapping

Swapping

In this task, you need to swap a few characters in the given string. The swapping range is controlled by a couple of integer parameters: the number of swappings and the offset.

The task of swapping two characters is mostly solved using one of the two forms of assigning two items at the same time. Either individually:

my @s = $s.comb;
(@s[0], @s[7]) = @s[7], @s[0];

Or using an array slice:

my @s = $s.comb;
@s[0, 7] = @s[7, 0];

A few of the solutions offer an interesting alternative and use the built-in substr-rw method (or function):

my $t = $s.substr(0, 1);
$s.substr-rw(0, 1) = $s.substr(7, 1);
$s.substr-rw(7, 1) = $t;

It is not possible to subscript a string in Raku (actually, why?), so Laurent Rosenfeld created his own version of the operator [ ]:

multi sub postcircumfix:<[ ]> (Str $s, Int $n) {
    substr-rw $s, $n, 1;
}

Checkout that solution in the repository and watch the video to see how it can be made even more powerful.

Input restrictions

The choice of the input parameters ($C and $O) makes inposbile to get index overflow when subscripting the arrays of characters, so it looks like we never need to use modulo in the solution:

$S[ 1 % $N ] <=> $S[ (1 + $O) % $N ]
. . .
$S[ $C % $N ] <=> $S[ ($C + $O) % $N ]

Indeed, if 1 <= $C <= $O >= 1 and $C + $O <= $N, then the maximum possible value of $C is $N - 1, so $S[$C % $N] is equivalent to $S[$C].

Similarly, in $S[($C + $O) % $N], the value of $C + $O does not exceed $N by definition, but if $C + $O == $N, then we get $S[0], so the modulo operation is still needed here.

Taking the above consideration into account, we can simplify the task:

$S[ 1 ] <=> $S[ (1 + $O) % $N ]
. . .
$S[ $C ] <=> $S[ ($C + $O) % $N ]

Note that the character at position 0 can still be swapped, even if you do not see it from the left side of the above formulae.

To loop or not to loop

The main swapping loop is most often organised with a for loop over the range 1..$C. In the solution by Mark Anderson, the loop is indirectly run via map:

map { @S[$_ % $N, ($_ + $O) % $N] = @S[($_ + $O) % $N, $_ % $N] }, 1..$C;

But you can solve the task even without loops! Myoungjin Jeon demonstrates how:

$N = $S.chars;
my $K = $C > $O;

my $result;
with $S {
    $result  = .substr( 0, 1 ) # 1
    ~ .substr( $C+2 .. $C+$O ) # 2
    ~ .substr( $K ?? $C-$O .. $C !! $C+1 .. $O ) # 3
    ~ .substr( 1 .. ( $C + $K*($O+1) ) ) # 4
    ~ .substr( ( $C+$O+1+$K) .. $N -1 );
}

The final string here is a concatenation of several parts. The initial conditions makes sure the is no overlapping, so you can take the part of the string before the first swapping (p), the second part of the characters (ndr), which go as a whole, so we can immediately take the substring of three characters, then the characters between the swapped parts (a), then another substring from the beginning of the string (erl), and, finally, the rest of the string (aku).

Video review

Task 2. Gray code sequence

The second task is to generate an N-bit sequence of Gray code. The task definition has an example of how to do it using some list manipulations, and that was the most popular approach. Although, there is another algorithm that manipulates bits directly and you don’t need to work with lists or create tricky loops to organise them. This week, we have solutions with both of these approaches.

Loop, or recursion, or bitwise operation

Here is the minimum solution brought by Andrew Shitov that uses bit operations:

put map {$_ +^ ($_ div 2)}, ^2**@*ARGS[0];

This is the whole program and it prints the sequence for the given input number of bits.

A number of solutions use recursion. As you may notice, the first half of the N-bit sequence fully repeats the (N-1)-bit sequence. For example, here is the solution demonstrated by Noud Aldenhoven:

sub gray-code-sequence($n) {
    if ($n == 1) {
        return [0, 1];
    }
    my $seq1 = gray-code-sequence($n - 1);
    my $seq2 = [2**($n - 1) + $_ for $seq1.reverse];
    return [|($seq1), |($seq2)];
}

Flattening

A number of solutions use the so-called flattening, in the form of either calling the method flat or by using the | prefix that creates a slip.

Flattening is often used when the two parts of the current sequence are joined, for example:

my @gray-seq = |@s1, |@s2;

In such a case, you can simply call append and join the lists using a cleaner Raku code.

Examine the following example and its output to see the difference:

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

my @c = @a, @b;
dd @c; # Array @c = [[3, 4, 5], [10, 20, 30]]

my @d = @a, @b;
dd @d; # Array @d = [3, 4, 5, 10, 20, 30]

my @e = @a.append(@b);
dd @e; # Array @e = [3, 4, 5, 10, 20, 30]

Binary ↔ decimal

The majority of solutions use strings with characters 0 and 1 to keep and manipulate the β€˜bits’.

There is more than one way to convert a string with a binary representation of a number to its decimal value. Let me list a few of them that were used in the solutions.

In the first group, the parse-based routine is used:

@sequence.map( *.parse-base( 2 ) )

my @result = map { .parse-base(2) },  @gray-seq;

The second group uses the adverbal form :2<1010>:

@A.map({ ":2<$_>".Int })

return ":2<$binary>".Int;

And in the third group, we create a 0b-prefixed string and coerce it to an integer by calling a method on the string:

@S1 = @S1.map({ "0b$_".Int });

my UInt @gray-codes = 
    gray-codes-binary($N).map: { "0b$_".UInt };

Video review

Leave a Reply

Your email address will not be published. Required fields are marked *