Over christmas we had a look at the GCHQ christmas quiz [1]. The idea is that you solve a set of small puzzles, each producing a letter, which then become label

Over christmas we had a look at the GCHQ christmas quiz [1]. The idea is that you solve a set of small puzzles, each producing a letter, which then become labels of the nodes of a directed graph, and you have to find a Eulerian path through the graph (visiting some nodes multiple times) which spells out a festive word or phrase. We solved two or three of the small puzzles, but couldn't get the rest. I wondered if we could solve the overall puzzle without knowing the letters, by exploiting the structure of the graph: perhaps there are simply not many words or phases which could be produced by the graph. Enumerating the possible paths through the graph was straightforward (there are a few hundred, i think). Matching those paths against individual words, if you have a word list, is easy. But where i was stumped was matching them against phrases containing multiple words. Trying every possible sequence of words, even lazily assembled, felt like it would be a combinatorial explosion that i would never be able to get through. Using a corpus of phrases from wikipedia is absolute genius. [1] https://www.gchq.gov.uk/news/christmas-card-2020 https://www.gchq.gov.uk/news/christmas-card-2020 - note that the edge with a double arrow is really two edges, one in each direction