#### 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**.