Do do-do do do-do, do-do do-do do-do da-do.

Countdown is a very long-running UK quiz show¹, based on word and number puzzles. There are three parts to parts to each game: i) ten letter rounds, where the contestants try to make the longest possible words from nine random letters; ii) four number rounds, where the contestants try to make a target number from six other numbers using simple arithmetic, iii) a nine-letter anagram round.

During lockdown I ended up watching a fair bit of Countdown, and given that I had a lot of time on my hands I decided to write some code to play the game.

Letters round

For the letters round we get nine random letters, where we get the choice of how many are vowels and how many are consonants. Also, letters aren’t chosen uniformly at random, they are stratified with respect to their frequency of use in English. Let’s say we’ve got:

How can we find the longest word from this set of letters? The way that I’ve done it is by computing the letter set for each word - the sorted set of letters in the word - and constructing a dictionary mapping letter sets to the list of words that share that letter set. An example might be helpful here, take the word cats. The letter set of cats is acst, and this letter set can also be used to make three other words, so the entry in our dictionary is

'acst' : ['acts', 'cast', 'cats', 'scat']

The letter set map is made like this, where WORDS is the contents of /usr/share/dict/british-english

WORD_MAP = defaultdict(list)

join = "".join
def key(x): return join(sorted(x))

for w in WORDS:
    WORD_MAP[key(w)] += [w]

Then to find all of the words for a given board we just need to get all of the letter sets (of different lengths) from our nine letters, look them up in the dictionary and pick the longest words that result.

def lettersets(letters: Letters) -> Set[Word]:
    return {key(l) for i in range(4, 9) for l in combinations(letters, i)}

def best_words(letters: Letters, n: int = 5) -> Words:
    poss = [WORD_MAP[s] for s in lettersets(letters) if s in WORD_MAP]
    return sorted(sum(poss, []), key=len, reverse=True)[:n]

Simple as.

For the letters given above we get,

best_words("arioeklnn")
['lankier', 'aileron', 'alienor', 'oarlike', 'kaoline']

Numbers round

The numbers round is a tougher problem. Here we get 6 random numbers, where we can chose how many are small ($\le 10$) and how many are large ($(25, 50, 75, 100)$). We’re then given a target between $100$ and $1,000$. The goal is to get as close as possible to the target using the four basic operations (addition, subtraction, multiplication, and division). We don’t have to use all six numbers, and we can’t at any point use a non-natural number (a fraction or negative number).

Let’s have an example.

Is it possible to make the target by doing simple arithmetic operations to the numbers given?

There are lots of clever ways of doing this (I’m sure) but I’m going to do it the simple way,by brute-force checking all of the possible equations we can make from those numbers. To do this I’ll encode the equations using Reverse Polish Notation², which makes life easier because it means we don’t have to worry about placing parentheses to denote the order of operations. In RPN an equation is just a list of $N$ numbers and $N - 1$ operators:

All we need to do it take the product of all length $N$ permutations of numbers and length $N-1$ permutations of operators, and check if any evaluate to the number we want. Generating the equations isn’t too hard:³

def eqn_nums(nums: Numbers) -> Equation:
    ops = combinations_with_replacement("+-/*", len(nums) - 1)
    op_perms = mapcat(permutations, ops)
    num_perms = set(permutations(nums))

    eqns = product(num_perms, op_perms)
    return (list(p) + list(o) for p, o in eqns)


def all_eqn(nums: Numbers) -> Equations:
    for i in range(4, len(nums) + 1):
        for n in combinations(nums, i):
            yield from eqn_nums(n)

Now to evaluate the equations we just need an RPN calculator. I won’t show that here (see footnote 2), but it’s quite a simple piece of code. And one nice thing about is that we can enforce our natural numbers only rule.

Now we can just use a bit of code to rewrite our RPN in infix for display and we’re done.⁴

def is_solution(nums: Numbers, t: int) -> bool:
    try:
        return calc(nums) == t
    except NotValidEqnError:
        return False


def solution(nums: Numbers, t: int) -> Numbers:
    return next(filter(lambda x: is_solution(x, t), all_eqn(nums)), [''])


def to_infix(expr: Expression) -> str:
    stack = []
    for s in expr:
        if s not in ops:
            stack = [s] + stack
        else:
            subexpr = f"({stack.pop(0)} {s} {stack.pop(0)})"
            stack= [subexpr] + stack

    return stack[0]

to_infix(solution([1, 8, 9, 6, 50, 100], 836))

Giving

Conundrum

The final part of the game is the Countdown Conundrum, which is a nine-letter anagram. To solve this anagram we can just use the code from our letters round. The real fun is making the conundrum, the nine-letter anagram is always made up of one four and one five-letter word. To do this we get all the nine-letter words (but only if you can’t make any other nine-letter words from those letters, to avoid confusion), we get all of the four and five-letter words, and then return a triple of (four, five, nine)-letter words once we find a four and five-letter word pair that share letter with a nine-letter word. Probably clearer in code

def conundrum():

    uniq9s = {k: v for k, v in WORD_MAP.items() if len(v) is 1 and len(k) is 9}
    fours = shuffled(w for w in WORDS if len(w) is 4)
    fives = shuffled(w for w in WORDS if len(w) is 5)

    for fr, fv in product(fours, fives):
        k = key(fr + fv)
        if k in uniq9s:
            yield fr, fv, uniq9s[k][0]

Running this gives us something like,

So there we go, that’s all we need play Countdown. The code is here, a nice way to spend lockdown.