The Weekly Challenge 046

Garbled Message and 500 Rooms

Solutions on GitHub

Task 1: Garbled Message / Cryptokitty

You are given a list of equal-length strings representing a garbled message sent over a noisy channel. Write a script to reconstruct the original message by selecting the most common character at each index.

Example Output

Input: "P + 2 l ! a t o", "1 e 8 0 R $ 4 u", ... Output: Perl weekly challenge (reconstructed string)

Logic

For each index i from 0 to the message length, iterate through all input lines, extract the character at index i, and count occurrences. The character with the highest count is chosen for the reconstructed message.

Perl Solution

ch-1.pl

sub decrypt_message { my @lines = @_; my $message_length = length($lines[0]); my $decrypted_message = ""; for (my $i = 0; $i < $message_length; $i++) { my %counter; foreach my $line (@lines) { my $char = substr($line, $i, 1); $counter{$char}++; } my $most_common_char = reduce { $counter{$a} > $counter{$b} ? $a : $b } keys %counter; $decrypted_message .= $most_common_char; } return $decrypted_message; }

Python Solution

ch-1.py

from collections import Counter def decrypt_message(lines: [str]) -> str: message_length = len(lines[0]) decrypted_message = "" for i in range(message_length): column_chars = [line[i] for line in lines] most_common_char = Counter(column_chars).most_common(1)[0][0] decrypted_message += most_common_char return decrypted_message

Task 2: 500 Rooms Puzzle

There are 500 rooms. At first, all are closed. In the first pass, toggle every room. In the second pass, toggle every second room, and so on. Find which rooms are open after 500 passes.

Example Output

Open rooms: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441, 484

Logic

This is the classic Locker Problem. A locker is toggled once for each divisor it has. Only numbers with an odd number of divisors will end up open (True). These are exactly the perfect squares.

Perl Solution

ch-2.pl

sub find_open_rooms { my $rooms_count = 500; my @rooms = (0) x ($rooms_count + 1); for (my $i = 1; $i <= $rooms_count; $i++) { for (my $j = $i; $j <= $rooms_count; $j += $i) { $rooms[$j] = !$rooms[$j]; } } my @open_rooms = grep { $rooms[$_] } (1 .. $rooms_count); return \@open_rooms; }

Python Solution

ch-2.py

def find_open_rooms() -> [int]: rooms_count = 500 rooms = [False] * (rooms_count + 1) for i in range(1, rooms_count + 1): for j in range(i, rooms_count + 1, i): rooms[j] = not rooms[j] open_rooms = [i for i in range(1, rooms_count + 1) if rooms[i]] return open_rooms