by Anders Kaseorg
The puzzle is an infinite string of letters, presented in pages of
2000 letters at a
time. Page
1 begins:
AEOLOMWSUOYCMKBSXNSKFSMDYBCSOBBKAEOLOMSXNSKCSOBBKVSWKCSOBBKHBKISXNSKZKZKAEOLOMWS…
We’ll call this level 0. It decodes with Caesar shift key K to:
QUEBECMIKEOSCARINDIAVICTORSIERRAQUEBECINDIASIERRALIMASIERRAXRAYINDIAPAPAQUEBECMI…
which is the phonetic alphabet spelling of level 1:
QMOIVSQISLSXIPQMOIIGLSXERKSIGLSXERKSIGLSKSPJPMQEIGLSZMGXSVTETEQMOIMRHMEDYPYQMOIK…
This now decodes with Caesar shift key E to:
MIKEROMEOHOTELMIKEECHOTANGOECHOTANGOECHOGOLFLIMAECHOVICTORPAPAMIKEINDIAZULUMIKEG…
which is the phonetic alphabet spelling of level 2:
MRHMETETEGLEVPMIZMGXSVHIPXEQMOIKSPJTETERSZIQFIVALMWOICHIPXEMRHMEXERKSEPTLEXERKSV…
This now decodes with Caesar shift key E to:
INDIAPAPACHARLIEVICTORDELTAMIKEGOLFPAPANOVEMBERWHISKEYDELTAINDIATANGOALPHATANGOR…
That’s about as much as we can get from just page 1, so we add on
pages 2–5 to read more of level 3:
IPCVDMGPNWDITATRWDWDITAUDMIGDIEPEPAXBPCDKTBQTGWDITAGDBTDKXRIDGUDMIGDISTAIPJCXUDG…
As we continue like this, the Caesar shift keys will spell out the clue phrase, but by the time we’ve gotten through KEEP DECODING, the first letter at level 12 is spelled by 386634276 letters at level 0. Clearly a more efficient strategy is required.
Let \(a_{n,l}\) be the length of an encoded letter \(l\) at the \(n\)th level. By writing these lengths in terms of the lengths at the previous level: \begin{align*} a_{0,l} &= 1, \\ a_{3,\mathtt I} &= a_{2,e_{\mathbf E}(\mathtt I)} + a_{2,e_{\mathbf E}(\mathtt N)} + a_{2,e_{\mathbf E}(\mathtt D)} + a_{2,e_{\mathbf E}(\mathtt I)} + a_{2,e_{\mathbf E}(\mathtt A)} \\ &= a_{2,\mathtt M} + a_{2,\mathtt R} + a_{2,\mathtt H} + a_{2,\mathtt M} + a_{2,\mathtt E}, \end{align*} we can compute a table of \(a_{n,l}\):
| \(n\) | \(a_{n,\mathtt A}\) | \(a_{n,\mathtt B}\) | \(a_{n,\mathtt C}\) | \(a_{n,\mathtt D}\) | \(a_{n,\mathtt E}\) | \(a_{n,\mathtt F}\) | \(a_{n,\mathtt G}\) | \(a_{n,\mathtt H}\) | \(a_{n,\mathtt I}\) | \(a_{n,\mathtt J}\) | \(a_{n,\mathtt K}\) | \(a_{n,\mathtt L}\) | \(a_{n,\mathtt M}\) | \(a_{n,\mathtt N}\) | \(a_{n,\mathtt O}\) | \(a_{n,\mathtt P}\) | \(a_{n,\mathtt Q}\) | \(a_{n,\mathtt R}\) | \(a_{n,\mathtt S}\) | \(a_{n,\mathtt T}\) | \(a_{n,\mathtt U}\) | \(a_{n,\mathtt X}\) | \(a_{n,\mathtt W}\) | \(a_{n,\mathtt X}\) | \(a_{n,\mathtt Y}\) | \(a_{n,\mathtt Z}\) | key |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | K |
| 1 | 5 | 5 | 7 | 5 | 4 | 7 | 4 | 5 | 5 | 6 | 4 | 4 | 4 | 8 | 5 | 4 | 6 | 5 | 6 | 5 | 7 | 6 | 7 | 4 | 6 | 4 | E |
| 2 | 21 | 27 | 31 | 22 | 19 | 37 | 20 | 23 | 22 | 31 | 19 | 18 | 20 | 44 | 27 | 18 | 34 | 29 | 32 | 23 | 39 | 28 | 37 | 22 | 31 | 21 | E |
| 3 | 97 | 137 | 145 | 104 | 92 | 194 | 100 | 112 | 111 | 157 | 97 | 91 | 103 | 225 | 136 | 84 | 171 | 148 | 154 | 121 | 205 | 143 | 176 | 105 | 150 | 102 | P |
| 4 | 533 | 556 | 831 | 567 | 549 | 838 | 549 | 609 | 593 | 741 | 408 | 423 | 465 | 996 | 548 | 352 | 912 | 566 | 622 | 587 | 953 | 665 | 932 | 512 | 798 | 547 | D |
| 5 | 2712 | 3433 | 4346 | 3205 | 2421 | 5075 | 2448 | 3063 | 2874 | 3489 | 2533 | 1890 | 2380 | 5348 | 3589 | 2378 | 3704 | 3046 | 4170 | 3718 | 4311 | 4510 | 4204 | 2609 | 4249 | 2403 | E |
| ⋮ | ⋮ | ⋮ | |||||||||||||||||||||||||
We can now use these encoded lengths to skip ahead to the necessary pages while decoding each successive level. This gets us as far as KEEP DECODING THIS DIG DUG PAC MA…, but once we get to about the nine quadrillionth page, we notice that the server has a “bug”: it starts redirecting our requests to round the page numbers to the nearest 64-bit double-precision floating point number.
In order to continue decoding with only the pages that the server will give us, we need the ability to predict the contents of an arbitrary page given guesses for a prefix of the clue phrase. Let \(e_{n,l}(i)\) be the \(i\)th letter of the encoding of an \(n\)th level letter \(l\). Using the lengths \(a_{n,l}\) from the table above, we can compute \(e_{n,l}(i)\) recursively. For example: \begin{align*} e_{0,l}(0) &= l, \\ e_{3,\mathtt I}(i) &= \begin{cases} e_{2,\mathtt M}(i), & 0 \le i < a_{2,\mathtt M}, \\ e_{2,\mathtt R}(i - a_{2,\mathtt M}), & a_{2,\mathtt M} \le i < a_{2,\mathtt M} + a_{2,\mathtt R}, \\ e_{2,\mathtt H}(i - a_{2,\mathtt M} - a_{2,\mathtt R}), & a_{2,\mathtt M} + a_{2,\mathtt R} \le i < a_{2,\mathtt M} + a_{2,\mathtt R} + a_{2,\mathtt H}, \\ e_{2,\mathtt M}(i - a_{2,\mathtt M} - a_{2,\mathtt R} - a_{2,\mathtt H}), & a_{2,\mathtt M} + a_{2,\mathtt R} + a_{2,\mathtt H} \le i < a_{2,\mathtt M} + a_{2,\mathtt R} + a_{2,\mathtt H} + a_{2,\mathtt M}, \\ e_{2,\mathtt E}(i - a_{2,\mathtt M} - a_{2,\mathtt R} - a_{2,\mathtt H} - a_{2,\mathtt M}), & a_{2,\mathtt M} + a_{2,\mathtt R} + a_{2,\mathtt H} + a_{2,\mathtt M} \le i < e_{3,\mathtt I}. \end{cases} \end{align*} Using the server to check various predictions based on the 26 possible guesses for the first letter of level \(n\) (and the corresponding level \(n - 1\) key), we work out more of the clue phrase:
KEEP DECODING THIS DIG DUG PACMAN GALAGA LEGIONS GALAGA XEVIOUS PACMAN CHAMPIONSHIP EDITION NEW RALLYX MS PACMAN MR DRILLER ONLINE GROBDA MOTOS THE TOWER OF DRUAGA METROCROSS GALAXIAN RALLYX KING AND BALLOON BOSCONIAN PAC AND PAL SUPER PACMAN DIG DUG II MAPPY DRAGON BUSTER SKY KID BARADUKE ROLLING THUNDER SKY KID DELUXE PACMANIA GALAGA EIGHTY EIGHT DRAGON SPIRIT POLE POSITION POLE POSITION II GALAGA ARRANGEMENT PACMAN ARRANGEMENT DIG DUG ARRANGEMENT DIG DUG PAC MAN GALAGA LEGIONS GALAGA XEVIOUS PACMAN CHAMP…
Now we really can’t go any farther—we’ve reached the last page, having exhausted the range of a 64-bit double. Fortunately the clue phrase has started repeating itself. The repeated part lists the games of the Namco Museum Virtual Arcade collection (arranged by their order in the collection’s menu screens). The answer is NAMCO MUSEUM VIRTUAL ARCADE.