PWC 046 › Cryptic Message

This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)

Challenge #1 this week is the following:

The communication system of an office is broken and message received are not completely reliable. To send message Hello, it ended up sending these following:

H x l 4 !
c e - l o
z e 6 l g
H W l v R
q 9 m # o

Similarly another day we received a message repeatedly like below:

P + 2 l ! a t o
1 e 8 0 R $ 4 u
5 - r ] + a > /
P x w l b 3 k \
2 e 3 5 R 8 y u
< ! r ^ ( ) k 0

Write a script to decrypt the above repeated message (one message repeated 6 times).

This turns out to sort of be a challenge in frequency analysis, or counting how many times letters occur in the “ciphertext,” which in this case, is just plaintext that appears to have been repeatedly typed by someone in the office who has had way, way too many cups of coffee already and may, in fact, require medical attention.

The good news is, the correct letter in each column is simply the letter that appears most often. So our decaffeinator, as it were, simply has to pull out the most frequent letter from each column and return that.

Raku

#| Decode extremely unreliable transmission
sub decode( @strings ) {
    my @col-count;
    for @strings».split: ' ' -> $row {
        @col-count[.key]{.value}++ for |$row.pairs;
    }
    @col-count».sort(-*.value)».first».key.join;
}

Our decode function accepts an array of @strings like the ones from the problem description, above. We split each into a $row that looks like (H x l 4 !), and then loop over the pairs (i.e., the index and the value).

The inner loop tallies the frequency of each letter in each column. @col-count[0]{H} is therefore the number of times H occurred in the 1st column.

The last line iterates over every row (thanks again to the hyperoperator, »), and sorts the hash pairs in reverse numerical order by value. We then grab the .first.key, which is our most frequent letter, and .join everything together into a string.

Perl

sub decode {
    my @r = map y/ //dr, @_;
    join '',   map { reduce { $_->{$a} > $_->{$b} ? $a : $b } keys %$_ }
       reverse map { { frequency map chop, @r } } 1..length $r[0];
}

That’s all we need.

The implementation here differs slightly from the Raku version. First, I remove spaces from all the strings, making a copy in @r. Then, we can read that two-line compound statement from the bottom up:

reverse map { 
    { frequency map chop, @r } 
} 1..length $r[0];

We loop once for the number of columns. The inner map chop, @r chops the last character off of each string in @r and feeds them all to frequency from List::MoreUtils^†. For example, frequency(H c z H q) would return (H => 2, c => 1, q => 1, z => 1). The extra { curly braces } turn this hash into a hash ref. All of those hash refs are then sent to the next step in reverse order, since we used chop to work from right-to-left.

map { 
    reduce { $_->{$a} > $_->{$b} ? $a : $b } keys %$_
}

Remembering that the input to this map is a list of hash refs, for each one, we loop over the keys and use reduce to pull out the key that has the maximum value. In other words, we obtain the most frequent character. Finally, we join together our list of characters into a string. Et voilà!

† I usually avoid non-code module dependencies in these challenges, but just about everyone has List::MoreUtils anyway. frequency is an extremely simple function that every Perl programmer has probably implemented in some form or another, multiple times.