laurent_r

These are some answers to the Week 70 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Task 1: Character Swapping

You are given a string $S of size $N.

You are also given swap count $C and offset $O such that $C >= 1, $O >= 1, $C <= $O and $C + $O <= $N.

Write a script to perform character swapping like below:

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

Example 1:

Input:
    $S = 'perlandraku'
    $C = 3
    $O = 4

Character Swapping:
    swap 1: e <=> n = pnrlaedraku
    swap 2: r <=> d = pndlaerraku
    swap 3: l <=> r = pndraerlaku

Output:
    pndraerlaku

Character Swapping in Raku

To access the individual characters of a string, Raku offers two basic mechanisms: the substr function, or the ability to split a string into an array of individual characters, using the split or comb built-in routines.

However, since this task is fairly easy, I thought there would be more fun to create a postcircumfix [ ] operator for indexing strings with subscripts the way it is done, for example, in C or in Python. We even built this multi operator also for slices, used with ranges, although it is not used in this program. Note that the way it is defined, it is not possible to use it on the left-hand side of an assignment (in other words you can read the character at a given position in a string, but you cannot modify a character in the string).

use v6;
subset Non0 of Int where * > 0;

# For fun, indexing strings with subscripts
multi sub postcircumfix:<[ ]> (Str $s, Int $n) {
    substr-rw $s, $n, 1;
}
# Not used here, but more fun
multi sub postcircumfix:<[ ]> (Str $s, Range $r) {
    substr-rw $s, $r;
}

sub MAIN ($s is copy, Non0 $c = 3, Non0 $o = 4) {
    my $n = $s.chars;
    die "Invalid values" if $c + $o > $n;
    for 1..$c -> $i {
        my $tmp = $s[$i % $n];
        substr-rw($s, $i % $n, 1) = $s[($i + $o) % $n];
        substr-rw($s, ($i + $o) % $n, 1) = $tmp;
    }
    say $s
}

Running it using the default values displays the following output:

$ raku char-swap.raku PerlAndRaku
PndRAerlaku

Character Swapping in Perl

With Perl, we can’t really create a new operator as in Raku . So we’ll use the substr built-in.

use strict;
use warnings;
use feature qw /say/;

my ($s, $c, $o) = @ARGV;
my $n = length $s;
die "Invalid values" if $c < 1 or $o < 1 or $c + $o > $n;
for my $i (1..$c) {
    my $tmp = substr $s, $i % $n, 1;
    substr($s, $i % $n, 1) = substr $s, ($i + $o) % $n, 1;
    substr($s, ($i + $o) % $n, 1) = $tmp;
}
say $s;

This program displays the following output:

$ perl char-swap.pl PerlAndRaku 3 4
PndRAerlaku

Task 2: Gray Code Sequence

You are given an integer 2 <= $N <= 5.

Write a script to generate $N-bit gray code sequence.

2-bit Gray Code Sequence

[0, 1, 3, 2]

To generate the 3-bit Gray code sequence from the 2-bit Gray code sequence, follow the step below:

2-bit Gray Code sequence
[0, 1, 3, 2]

Binary form of the sequence
a) S1 = [00, 01, 11, 10]

Reverse of S1
b) S2 = [10, 11, 01, 00]

Prefix all entries of S1 with '0'
c) S1 = [000, 001, 011, 010]

Prefix all entries of S2 with '1'
d) S2 = [110, 111, 101, 100]

Concatenate S1 and S2 gives 3-bit Gray Code sequence
e) [000, 001, 011, 010, 110, 111, 101, 100]

3-bit Gray Code sequence
[0, 1, 3, 2, 6, 7, 5, 4]

Example:

Input: $N = 4

Output: [0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8]

I don’t see any compelling reason to start with a two-bit Gray code sequence, we can start with a one bit sequence: [0, 1], and thus make the program slightly more general.

Gray Codes in Raku

We just follow the steps described in the task specification.

use v6;
my @gray = [0], [0, 1]; # No need to have [1, 2, 4, 3] here

sub next-gray (Int $in) {
    my $fmt = "%0" ~ $in ~ "s"; # build the formatting string
    my @s1 = map { .fmt('%b').fmt($fmt) }, | @gray[$in];
    my @s2 = reverse map { '1' ~ $_ }, @s1;
    @s1 = map { '0' ~ $_ }, @s1;
    my @gray-seq = |@s1, |@s2;
    my @result = map { .parse-base(2) },  @gray-seq;
}

sub MAIN ($n where 1 <= * <= 5) { # we can start at 1
    for 1..^$n -> $i {
        @gray[$i+1] = next-gray $i;
    }
    say @gray[$n];
    say @gray;
}

This program displays the expected result:

$ raku gray.raku 4
[0 1 3 2 6 7 5 4 12 13 15 14 10 11 9 8]

I’m late and don’t have time to do the equivalent Perl program, although it should really not be a big deal to port the above program to Perl (except possibly the mildly difficult binary to decimal conversion, but I already know how to do that, having done that before with the unpack built-in).

Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on Sunday, August 2, 2020. And, please, also spread the word about the Perl Weekly Challenge if you can.