Countdown letters game solver
version 4B, 2024-07-26

Introduction

A Letters Game contestant in the UK TV Channel 4 show Countdown has 30 seconds to find the longest word in the Oxford English Dictionary (the OED) that can be made from a partially random set of nine letters.

Solving the letters game automatically is quite simple in principle if you have a list of allowed words. No program is provided yet because of the need to ensure word list copyrights are respected and the need to prepare a special version of the list. But this page covers the principles.

Similarly to the number game solver, this started as a 1988 summer break project under Xenix on an Intel 80286 with probably no more than 40 MBytes of disk space. The key issue with the technology of the day was file access speed and file size. This is no longer a problem and the convoluted but compact and fast dictionary file format of version 1 was abandoned in favour of something simpler in the modern Linux version.

The solver in principle

To understand the principle, start by automatically solving a nine-letter anagram. Re-arrange the nine given letters into alphabetical order and compare that to a similarly re-arranged copy of each word in the word list. A match means an anagram has been found.

That’s a lot of work but computers are good at that. In computing terms the list of allowed words is a database and the alphabetized copy of each word is a key to use in looking up that word. The database comprises records each containing a word and its alphabetised key.

Solving the letters game extends this idea. It starts by taking the contestant’s nine letters and doing the above. A match means that there is a nine-letter solution. Next the nine possible eight-letter sub-sets of the contestant’s letters are generated and the same search is done nine times for eight-letter anagrams. Then all of the seven-letter possibilities are generated and checked. And so on until the solver has found sufficient potential solutions from which the user may choose. If the word list happened to be the OED itself then a single match would suffice. If not, it seems like a good idea to have several candidates from which to choose a word that might also be on the OED.

The solver in practice (part 1)

The letters game solver uses a dictionary file with allowed words organized into alphabetical order of their keys. The keys being just the letters of the word in alphabetical order as above. The keys are not stored in the file since they are easy to generate from the word. It is the ordering of the words in the file that matters most.

The words file is accessed through an Application Programming Interface (API) which provides a lookup function which will find all of the anagrams in its word list of a given set of letters, and perform a given action with each word it finds (e.g. display it).

The lookup function generates an index file whenever the dictionary file does not already have one or re-generates it when the dictionary file has been updated. That index file contains a list of keys and for each an index which is the place in the dictionary file where the corresponding word can be found. The keys in the index file are a small sub-set of the keys for the entire dictionary file. A word with a key that lies alphabetically between two index file keys will be in the dictionary file somewhere between the two indices in the index file. Usually 64 words lie between each index. That means just a short dictionary file search for each set of letters that is looked up.