…Exhibiting Gray Areas in Character

Wherein we explore the idea that the steady development of an plan can evolve through the smallest of changes, from either standing in place to focus on the next step or packing up and moving over large distances…

THE WEEKLY CHALLENGE – PERL & RAKU #70

---

TASK #1 › Character Swapping

Submitted by: Mohammad S Anwar

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.

• UPDATE: 2020-07-20 16:10:00
  Pete Houston suggested to put additional constraint i.e. $C <= $O. He presented the use case $S = ‘abcd’, $C = 2, $O = 1.

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

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

Method

Such was the case when confronted with the quite specific directions to this challenge. Constraints are defined, and an algorithm for a sequence of actions is well described, but as written it leaves me wondering what the intent is behind all this moving and shuffling.

When used as directed, each action swaps a character earlier in the string with one later. As the next subsequent action swaps the next letter pair, the net result is to switch a block of characters starting at index 1 of length C with an equivalent block of characters from later in the string spaced O characters away. Well, almost. There is the question of that pesky modulo operator. What exactly is it doing there?

If C + O ≤ N, then the modulo never even come into play, right? Oh wait. Less than or equal to N. So in the one case where C + O = N, the modulo sets the index to 0. Huh. How about that. So it is possible that at the end of a sequence of swaps, the switch is from later in the string to the 0 position. The limits on C and O will never allow switching to continue past 0, only for this one, last swap in a run.

Were it not for this oddity, the action of all the swapping could be done with a single complicated substring statement. We could use a first substr() to chop out the later character block (starting at Offset + 1 with length C), and use a second substr() to exchange it, replacing the earlier block (starting at index 1 with length C). The characters overwritten are returned by that operation and, because substr() can be used as an lvalue, we can then assign that text to overwrite the later block. Here is the code:

        substr( $str, 1+$O, $C) =                   ## 3. the new later block
            substr( $str, 1, $C,                    ## 2. the earlier block, which becomes ↰
                substr( $str, 1+$O, $C) );          ## 1. the later block replaces ↰

If you start reading from the end, the replacement overwrites the original which in turns overwrites the replacement, all in-place without a temporary variable. But as substr() only works on contiguous sets of characters, it is not to be.

We can still use this basic construction to swap individual characters, however, so all is not lost. It’s a great little trick. We’ll just have to loop over the individual swaps instead.

We can only speculate as to the meaning behind circling around to move position 0. It seems out of place with the rest of the operation, especially so once we’ve disallowed the Count being greater than the Offset. If we do allow that, the later swaps will begin to re-swap characters already swapped once, creating a churning effect similar to a cat playing Jenga with a Scrabble game. Other options to tweak the rules could be to start indexing at the first character instead of the second, or changing the constraint to C + O < N. I ended up building a pair of nested loops and tried examining the way altering the parameters changes the outcome. Each has its virtues, but none suggests itself to be somehow the “correct” variation. I think the contiguous block move, changing the start point to 0 and the sum to less than the length (thus keeping the swap range the same but making the modulo superfluous), is perhaps the most aesthetically pleasing, but now are getting rather far afield from the problem given. With all of the variations, at some point it seems we always return to the carnage of that darn cat, requiring careful parsing of the results just to make sure the logic is sound. Sometimes the puzzle can be more of a puzzle than the solution.

I don’t see a satisfactory explanation forthcoming, but that is no mind. It’s a puzzle and can be solved as laid out, whatever the reasoning.

Perl Solution

[colincrain:~/PWC]$  perl 70_1_chrswp.pl 
Count   3
Offset  4
Start   p e r l a n d r a k u
Result  p n d r a e r l a k u

use warnings;
use strict;
use feature ":5.26";

## ## ## ## ## MAIN:


my ($str, $C, $O) = @ARGV;

$str //= 'perlandraku';
$C   //= 3;
$O   //= 4;

say "Count   $C";
say "Offset  $O";
say "Start   ", $str =~ s/\B/ /gr;       ## easier to see if we spread things out a bit

$str = swap( $str, $C, $O );
say "Result  ", $str =~ s/\B/ /gr;    

## ## ## ## ## SUBS:

sub swap {
    my ($str, $C, $O ) = @_;
    my $N = length $str;

    for my $i (1..$C) {
        substr( $str, ($i+$O) % $N, 1) = 
            substr( $str, $i % $N, 1, 
                substr( $str, ($i+$O) % $N, 1));
    }
    return $str;
}

Raku Solution

In Raku there does not seem to be a way to install a replacement string using substr while returning the code replaced, so we must resort to using a temporary container to hold it. I still feel there must be a better way to do this, and must figure out how.

sub MAIN ( Str $str is copy = 'abcdefgh', Int $C = 1, Int $O = 7) {


    ## easier to see the results if we spread things out a bit
    say "Count   $C";
    say "Offset  $O";
    say "Start   ",  $str.comb.join: ' ';  

    swap( $str, $C, $O );

    say "Result  ", $str.comb.join: ' ';   

}


## ## ## ## ## SUBS:

sub swap ($str is rw, $C, $O) {
    my $n = $str.chars;
    for 1..$C -> $i {
        my $tmp = $str.substr(($i+$O) % $n, 1);
        $str.substr-rw(($i+$O) % $n, 1) = $str.substr-rw( $i % $n, 1 );
        $str.substr-rw( $i % $n, 1 ) = $tmp;          
    }
    return $str;
}

---

---

TASK #2 › Gray Code Sequence

Submitted by: Mohammad S Anwar

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]

Method

In electromechanical systems, states often change in a highly ordered manner, progressing for one to the next. Clocks cycle, elevators move up and down one floor, countdowns keep sequenced operations orderly. Outboard sensor systems need to communicate with central computing to transmit that information, to be the system’s eyes and ears. Computers work with binary data, so it seems reasonable to communicate the state data using that means.

Problems arise when generating binary data because the binary numbers, viewed as a stream of bit sequences, is discontinuous with respect to bit changes. Consider a machine with 16 states, switching from state 7 to 8: encoded as a 4-digit binary number, 0111 → 1000. All four bits switch at once. In a clock regulated computer this is no problem, but if those bits are realized with relays there is no telling *exactly* when the switching will occur. If the central brain polls the data line at the wrong instant, the update may not be complete, leading to wildly incorrect values. Likewise an electromechanical counter caught updating its register. If the connection between the sensor and control is unsophisticated, it can be impossible to distinguish spurious data from real. Enter Gray Codes.

Gray Codes, also known as reflected binary codes, are a reordering of the binary sequence such that the progression of one number to the next only changes a single digit. On the one hand, it’s somewhat remarkable and non-obvious that for a given set of digits on length n that this is even possible to construct, more so it’s quite interesting that this rearrangement can be derived algorithmically.

With a Gray Code, the switch between state 7 to 8 becomes 0101 → 0100. Yes the progression does appear to go down, because of the reordering, but only one digit changes. Polling the data line at any time around the transition will always result in 7 or 8.

The algorithm for creating G_n+1 from G_n is well defined in the challenge description. Implementing it is short work.

I’ve been working on refining my functional programming game with quite pleasing results. Here I’m repeatedly employing map to apply functions over lists of data. We use two nested map functions to prefix the forward or reversed versions of the recursively gathered pervious sequence with either 0 or 1, respectively. An edge case of G₁ stops the recursion, providing the kernel [0,1]. Two more mappings are required to transform the strings in an out of binary format as we are asked for the decimal representations of the numbers for output, bringing the total up to four. Well then. Well done.

Perl Solution

[colincrain:~/PWC]$  perl 70_2_gray_area.pl 4
[ 0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8 ]

use warnings;
use strict;
use feature ":5.26";

## ## ## ## ## MAIN:

my $bits = shift @ARGV // 3;

say "[ ", (join ', ', grey_code($bits)->@*), " ]";

## ## ## ## ## SUBS:

sub grey_code {
    my $s = shift;
    return [0, 1] if $s == 1;       ## edge case    
    return [ map { oct("0b".$_) } map { 
        my $n = $_;
        my $fmt = '%0' . ($s-1) . "b";
        my @gc = map {sprintf $fmt, $_} grey_code($s-1)->@*;
        map { $n . $_ } $_ ? reverse @gc : @gc;
    } (0,1)  ];
}

Raku Solution

sub MAIN ( Int $bits where {$bits > 1} = 8) {

    grey_code( $bits ).put;

}

sub grey_code ( $bits ) {
    return (0,1) when $bits == 1;
        
    return (0,1).map({ 
        my $n = $_;
        my @gc  = grey_code($bits-1).map: {$_.fmt('%0' ~ ($bits-1) ~ 'b')};
        ($_ ?? reverse @gc !! @gc).map:{ $n ~ $_ };
    }).flat.map:{ :2($_ )} 
}