I grew up with Countdown as part of my diet. I had a crush on Carol Vorderman (before she went all advertisey and weird). I loved the numbers game, obviously – although I still have some slight resentment that Ian Scarrott was class champion rather than me. A few years back, I implemented a numbers game solver and thought no more about it.
Until the estimable @PlaneMirrorArt tweeted:
For some reason I decided to write a proggy to simulate 100,000 @c4countdown letters rounds (using 3-5 vowels) to find out which are the most useful words to know. Might try for 1,000,000 at some point but my code needs to be much more efficient. As it stands it's a bit ‘thick’. pic.twitter.com/ausYN9Ngb9
— Andrew Bradley (@PlaneMirrorArt) March 31, 2018
… and I remembered about an interesting connection between words and the Fundamental Theorem of Arithmetic, and thought I’d have a go at that, too.
The Fundamental Theorem of Arithmetic is the one that says every positive integer1 is the product of a unique set of prime factors. You can write the factors in any order you like, and the number of each particular factor is important.
So how is that helpful? Well, you can create a one-to-one mapping between letters of the alphabet and a subset of the prime numbers - so, perhaps, A corresponds to 2, B to 3, C to 5 and so on up to Z <=> 101. Then you can represent any string of letters by the product of the corresponding prime numbers: for example, DAB would correspond to $7 \times 2 \times 3 = 42$. BAD would correspond to… 42 as well.
That looks like a bad thing - but in fact it’s good: the order of the letters in a word, as far as the game is concerned, is not important. If the same letters come out in a different order, the same words are available; and if DAB is available as a word on the board, then so is BAD.
But the kicker is better yet: DAB and BAD are possible answers to a board of letters if and only if 42 is a factor of the number corresponding to the board! Or, in general:
The Fundamental Theorem Of Countdown: let $w$ be a word, $b$ a board of letters, and $P(s)$ the product of the primes corresponding to the letters of $s$. Then $w$ can be made from $b$ if and only if $P(w)$ is a factor of $P(b)$.
If, like Andrew, you want to find the most useful Countdown words to know, it’s a pain to search through all of the possible combinations of letters and match them against all of the possible words.
If you use the FTC, and especially if you index the words up front, so the computer knows that 42 corresponds to BAD and DAB, you can save yourself a lot of time.
Here’s how my code works:
(In fact, I work with the sum of the logs of the corresponding primes rather than the product of the primes themselves – I’m not sure that it’s any quicker in the long run, but I like it.)
And that’s about it!
Oh! The word that’s most likely to be a winner on a random Countdown board, under the assumptions I’ve made, is GOITRE (6). The most likely nine-letter word to be available is ORIGINATE, while the four most common eight-letter words are two pairs of anagrams: SENORITA and NOTARISE, and RELATION and ORIENTAL.
The Python code and results are available at GitHub. Let me know if you use and/or improve it!
* Many thanks to @PlaneMirrorArt for the challenge, for useful discussions, and for pointing out a bug.
* Corrected 2019-06-24 to fix a typo and assign a category.