Rafraîchissoir

By Shahed Nooshmand

Perl Weekly Challenge: week 70

Task #1

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 ]

Shouldn’t be too hard:

my @s = $S.comb;
@s[$_, ($_ + $O) % $N] = @s[($_ + $O) % $N, $_] for 1..$C;
say @s.join;

Since we know $C ≤ $N, we don’t need % for the $_.

Task #2

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

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

The general solution for generating a Gray code sequence, by definition of “reflected binary”, is to recursively reverse and concatenate. Here’s how that might go:

[""], { |.map(0 ~ *), |.reverse.map(1 ~ *) } … ∞

Subscripting the above with .[$N] would give a sequence of $N-bit binary numbers, so to see the sequence in decimal form you’d have to call .map: *.parse-base: 2 on it.

We can do this a lot shorter, however, if we cheat. Instead of generating a sequence, we can convert from every number (or index, rather) to its corresponding Gray code:

^∞ Z+^ (^∞ X+> 1)

This is basically the old “Kth Gray code is K^(K>>1)” algorithm on a diet. To get the $N-bit sequence, subscript it with .[^2**$N].