Countdown (dada dada dada-dada, dum)

Countdown is a TV show that frustrates me as a maths/engineering person... The numbers game is great but I have to sit through four rounds of anagrams to get one maths puzzle (consider what that says about how society values technical skills vs literary skills...). Fortunately here I make the rules, so we're just doing the numbers game!

Pick up to four "big" numbers (but usually 1, sometimes 2  rarely more), then make that up up 6 selections using small numbers. Then a random number between 100 and 999 is generated. Now in 30 seconds use your mental arithmetic skills to derive the big number from the small number.

It turns out this has some real merit as a game: As this Real Maths analysis shows provided you pick 1 big number the statistics fall in a sweet spot that the solution is almost always possible, but only rarely obvious.

I fancied writing a program to solve Countdown puzzles in Sniff, so here's my first go at it.

make N list of numbers
make target number

make sourceN list of numberswhen pickNumbers
.make index number
.delete all of N
.delete all of sourceN
.
.add 25 to sourceN
.add 50 to sourceN
.add 75 to sourceN
.add 100 to sourceN
.
.set index to pick random 1 to 4
.add item index of sourceN to N
.delete item index of sourceN
.if pick random 1 to 5 = 1
..set index to pick random 1 to 3
..add item index of sourceN to N
..delete item index of sourceN
.
.delete all of sourceN
.repeat 10 using index
..add index to sourceN
..add index to sourceN
.
.repeat until length of N = 6
..set index to pick random 1 to length of sourceN
..add item index of sourceN to N
..delete item index of sourceN

To start with we need to generate a random puzzle to solve: a target number (Easy), and a set of numbers to make it from (not so easy). To generate a typical set of cards, we create a list sourceN which initially we fill with the big cards. 1 time in 5 we take two of those, otherwise we take 1. We then fill sourceN with 2 of each of the numbers 1 to 10, and fill up N with randomly selected cards (remembering to delete them from sournceN when they're picked).

We're going to need to generate solutions  and check it to see if they work. Which raises the critical  question of what does a solution look like?

The solution is obviously an equation. For example to make  796 from 50 3 4 3 7 10 we can do

(50+7+4)*(3+10)+3. Thats a pretty neat solution (if you know what 61*13 is!), but the problem is that regular maths notation is just too messy. For a start we need to remember that we * before we +, and when we don't want to do that we have to put brackets in to make sure everything works properly. Writing code to understand that is pretty hard. We can make things a bit easier if we always put brackets in:(((50+(7+4))*(3+10))+3). Now we don't have to worry about what order to do things in, but its still tricky.

Regular maths notation is great for representing equations, but not great for helping you do calculations. What we want is a notation that actually gives us a set of instructions for doing the maths. The way we generally do that is using "Reverse Polish" notation :RPN (that's as in the country, not the cleaning product). Instead of writing 1+2 we write 1 2 +. To evaluate an expression you just work from left to right. When you see a number you append it to the end of a list of numbers called the "stack". When you see an operator (+) you use the last two numbers in the list, remove them from that list and put the result back at the end of the list. So here we "push" 1 and 2 onto the stack, the perform a "+" which removes those, adds them, and puts the resulting 3 onto the stack.

If we want to evaluate 1+2*3 we could write in in RPN as 1 2 3 * +. Push 1, push 2, push 3 now multiply the top two (2 and 3) so that leaves 1 and 6 on the stack. Now add, to leave 7.

If we actually wanted (1+2)*3 we would write it as 1 2 + 3 *. Push 1 and 2, add them to leave 3. push another 3, multiply them to get 9.

Doing maths like rearranging equations on paper in RPN would be strange and tricky, but here we want to do calculations, so its exactly what we need. If we can generate equations in RNM then we can write some code to evaluate them pretty easily:

make stack list of numbers
make eval number
when evalCandidate
.make val number
.make index number
.make l string
.delete all of stack
.repeat length of candidate using index
..set l to letter index of candidate
..if l = "+"
...set val to item last of stack
...delete item last of stack
...set val to val + item last of stack
...delete item last of stack
...add val to stack
..if l = "*"
...set val to item last of stack
...delete item last of stack
...set val to val * item last of stack
...delete item last of stack
...add val to stack
..if l = "/"
...set val to item last of stack
...delete item last of stack
...set val to val / item last of stack
...delete item last of stack
...add val to stack
..if l = "-"
...set val to item last of stack
...delete item last of stack
...set val to val - item last of stack
...delete item last of stack
...add val to stack
..if not value of l = 0
...set val to value of l
...add item val of N to stack
.set eval to item 1 of stack

To evaluate a candidate string we simply go through one letter at a time and "follow the instructions". When we see an operator we perform the operation. When we see a number we treat it as a card number, get that card from the deck, and put it on the stack. As there are only six cards, we'll use the numbers 1 to 6 to represent the 6 cards, so we know that 25 means card 2 then card 5, rather than having the potential to confuse 2, 5 and 25. So our rules are going to look something like: 34*2+56++ (Card 3 *Card 4)+Card2+Card5+Card6.

Now we can evaluate a candidate, we can set about making some:

when makeCandidate
.make index number
.make balance number
.make r number
.delete all of sourceN
.repeat 6 using index
..add index to sourceN
.
.set balance to 0
.set candidate to ""
.repeat until balance=1 and length of candidate>5
..set r to pick random 1 to 2
..if length of sourceN>0 and (balance<2 or (balance<4 and r=1))
...set index to pick random 1 to length of sourceN
...set candidate to join candidate  [item index of sourceN]
...delete item index of sourceN
...change balance by 1
..else
...set r to pick random 1 to 9
...if r < 4
....set candidate to join candidate "*"
...else
....if r <7
.....set candidate to join candidate "+"
....else
.....if r <9
......set candidate to join candidate "-"
.....else
......set candidate to join candidate "/"

...change balance by -1

We put the numbers 1 to 6 to represent the 6 cards into sourceN and we remove them as we use them to that we don't use each card more than once.

We then generate a string one l letter at a time - each letter being either a card number or an operator. Nominally we pick a random number and choose each equally, but there are restrictions. We can't pick a number if there are no cards left. We can't pick an operator if there are no numbers on the stack to use. We keep track of how many numbers are on the stack using "balance". Initially it starts of as 0. When we add a card it increases by 1. When we add an operator it decreases by 1. If balance <2 then we can't perform any operators. If balance becomes large we probably shouldn't add any more numbers. We keep going until we have a string longer than 5 characters with a balance 1 (the answer we hope!).

Most solutions use * and + a lot, - a occasionally, and / almost never, so if we choose to select an operator then we bias the selection towards the more common operators. It would be interesting to see if in fact there are large numbers of solutions that could use division but simply don't because its "less obvious". However the danger is that division takes us out of the Natural numbers. We strictly shouldn't use fractions or negative numbers, but I've allowed them because they'd complicate the code, and I think that almost any solution which uses them would have an obviously equivalent solution that uses just Natural numbers.

Now we can generate a random puzzle, a random solution and see how good that solution is:

when start
.set target to pick random 101 to 999
.say join "Target:"[target]
.
.broadcast pickNumbers and wait
.say join "Numbers:" [ N ]
.broadcast makeCandidate and wait
.say candidate
..broadcast evalCandidate and wait
.say join "=" [eval]
.say join "err:" [abs of (eval - target)]

So to find a good solution we can just do that thousands of times and pick the best:

when start
.ask "ready?" and wait
.set target to pick random 101 to 999
.say join "Target:"[target]
.set bestErr to target
.
.broadcast pickNumbers and wait
.say join "Numbers:" [ N ]
.repeat 10000
..broadcast makeCandidate and wait
..broadcast evalCandidate and wait
..if  abs of (eval - target) < bestErr
...set best to candidate
...set bestEval to eval
...set bestErr to abs of (eval - target)
.
.say ""
.say best
.say [bestEval]
.set candidate to best
.broadcast prettyPrintCandidate and wait
.say pretty

As a final trick, I wrote another script "prettyPrintCandidate". This operates pretty much the same as evaluateCandidate, but instead of calculating the result of the calculation it calculates the regular string representation of the expression so 12+ becomes (1+2).

The code works supprisingly well, and actually performs similarly to a human player - with 10,000 tests it gets most smaller targets, and does pretty well on targer targets, sometimes getting them, and often being 1 or 2 off. One quirk, because we don't disallow fractions is that it produces non-integer "close" answers - occasionally being off by 2/3's.

The brute force solution runs in only a fraction of a second, so its pretty effective. However the next question is can we do better? I think we can, but I'll save that for another post...