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.)
The second of the challenges this week poses the following question (paraphrased):
Suppose we have 500 doors, and 500 employees. The first employee opens all the doors. The second employee closes every 2nd door (doors 2, 4, 6, … 500). The third employee closes every third door if it is open, or opens it if closed. And so on. Which doors are open after all 500 employees have been through?
I remembered toying with a very similar problem a few years ago. At the time, I actually wrote a terminal-based visualizer for it, which you can see in action below (the animated GIF is 1.7MiB, so it may take a few seconds to load on slower connections):
Have you spotted the pattern yet? Once the animation is finished, only the square numbers are lit up: 1, 4, 9, 16, etc. Let’s explore a purely programmatic approach to generating those numbers first:
Solution 1 › Literal Interpretation
The most obvious way to write up the solution is to do exactly what the challenge tells us to do: loop 500 times, and for each iteration $i, toggle every $ith door. I’m using logical XOR (exclusive-or) to toggle the values:
Raku
my %doors;
for 1..$doors -> $m {
%doors{$m*$_} ^^= 1 for 1..$doors/$m;
}
And now we just need to pull out and print the hash keys we want (all the doors that are “open”, which means the hash value equal to 1, which in this case is equivalent to .value being defined):
say %doors.grep({ .value })».key».Int.sort;
Perl
my %door;
for my $m (1..$doors) {
$door{$m*$_} ^= 1 for 1..$doors/$m;
}
say join ' ', grep { $door{$_} }
sort { $a <=> $b } keys %door;
As you can see, the solutions are very similar.
Solution 2 › Pure Math
The solution is the easy part. You don’t need a doctorate in mathematics to spot the pattern of square numbers in the solution, and writing the code is extremely easy:
say join ' ', map { $_ * $_ } 1..int sqrt $doors; # Perl
say (1..$doors.sqrt.Int) »**» 2; # Raku
Informal Correctness “Proof”
The hard part is proving that your solution will always be correct, whether $doors is 500, 501, or any other positive integer. Your code isn’t much use if you can’t prove its correctness. I will explain informally, but the full proof is straightforward.
(1) If a door is initially closed and you toggle it an even number of times, it will be closed. But with an odd number of toggles, it will be open.
(2) Notice that every time we toggle a door, we are working with a factor of that door number. The number 12, for example, has factors of 1, 2, 3, 4, 6, and 12. In the language of the challenge, only those six employees will open or close door 12. 12 has six factors (even), so door number 12 will be closed.
What about 16, a square number? 16 has factors 1, 2, 4, 4, 8, and 16. But employee 4 is still only going to come around once! (In other words, we only care about unique factors.) Since 16 has an odd number of unique factors (five), door 16 will be open.
Finally, we need only demonstrate now that square numbers always have an odd number of unique factors, whereas non-square numbers will always have an even number of unique factors. All factors come in pairs (because you have to multiply a factor by another factor, e.g.: 1 × 16, 2 × 8, 4 × 4), therefore every number has an even number of factors. But in the unique case of square numbers, the square root is multiplied by itself, but we only count it as a unique factor once, thus only square numbers have an odd number of unique factors, thus only the square numbered doors are open (thus, this hotel could cut over 95% of its staff).
And that’s it! Or, if you prefer: ∎