HomeBlogAbout UsWorkContentContact Us
 
 Advertisement 

Countdown Game Show

When I was growing up in the UK we had just three TV stations. These were BBC1, BBC2 and ITV.

Then, when I was 15, a new station was launched with imaginative name of Channel 4. The first program to air on this new channel was a game show called Countdown. Countdown is still shown today and is one of the longest running game shows in the World. At the time of writing this article, over 5,000 episodes have been broadcast.

The show was not entirely original in concept, being based on a slightly earlier game shown in France called Des chiffres et des lettres (Numbers and Letters).

The Countdown game tests contestants' numeracy and word-making skills. In the ‘letters’ rounds of the game, players have to create the longest word possible from a random selection of letters (a little bit like Scrabble) picked from vowels and consonants.

In the ‘numbers’ round of the game, players have to combine six selected numbers (using just the four basic arithmetic operators) to get as close as possible to a randomly generated total. It’s is the numbers game that I’m going to talk about in this post.

Numbers Game

All games require rules, here are the rules for the numbers game of Countdown:

*There is some speculation as to whether 100 is a possible target number generated by the computer. Some say that only numbers range 101-999 are generated (which are the rules in the French variant), and other say that any three digit numbers is possible. I’m going to assume the latter in my calculations and say that a target of 100 is possible.

From the way the numbers are selected it’s clear that there can never be more than two of the same number. Also, there can only be one each of the larger numbers. If all four of the large numbers are taken then it’s assured that { 25 , 50 , 75 , 100 } will occur.

Example

Here's an example of the game in action. In this instance, one number was selected from the large set, and the rest from the small set.

{ 50 , 8 , 3 , 7 , 2 , 10 }

The randomly selected target was 556.

There are multiple ways to solve this. The smallest solution requires just four numbers:

(50 × 10) + (8 × 7) = 556

A example of a more complicated solution is this:

(((50 - 7) × 3) + 10) × 8) ÷ 2 = 556

Numbers Geek

On the show, contestants' declared solutions are confirmed by one of the hosts (who then goes on to reveal a better/alternate solution if one of the contestants does not get an exact solution). For 26 years, this host role was performed by the talented Carol Vorderman.

Being a numbers geek, I wanted to know many things:

  • Are all problems solvable for a perfect score? Does there exist a three digit number that is not achievable by any combination of digits? If not, what is the hardest number to achieve?

  • Is there a perfect set of numbers that allows the solving of any target 100-999?

  • What is the best strategy? Is it better to take 0,1,2,3 or 4 large numbers?

  • What is the ‘simplest’ solution to every problem (If there are multiple ways to solve any particular problem, what is the solution that requires the smallest number of donor numbers)

  • What is the distribution of the solutions?

  • Are there some interesting pieces of trivia found from analysing the problem?


Carol Vorderman - Countdown Numbers Host
Image: ITV

Code

This was a fun piece of code to write. I elected to use a brute-force approach. I worked out all possible combinations of ways the numbers/symbols could be arranged and, if they gave a valid solution, what that solution was.

First of all I needed to generate all unique combinations/subsets of numbers from the starting tiles. There are 13,243 distinct ways of picking the numbers following the rules. Then, for each of these distinct subsets, the number of distinct ways these numbers can be arranged in order was determined.

For each of these, all combinations of the operators (five in total) of + - × ÷ needed to be inserted between each number. The most obvious way to process these was to use Reverse Polish Notation to store the calculation (postfix) as opposed to the more traditional (infix).

InfixPostfixSolution
10-(7-2)10 7 2 - -= 5
(10-7)-210 7 - 2 -= 1
(10×4)-210 4 × 2 -= 38
10×(4-2)10 4 2 - ×= 20
1+(((5×(100-5))-9)+10)1 5 100 5 - × 9 - 10 + += 477

A trap that needs to be avoided is the ordering the operators should be applied. For example 10-(7-2) gives a very different solution to (10-7)-2, just as (10×4)-2 is very different from 10×(4-2). In RPN notation these distinctions are obvious (See table).

Calculating all possible solutions is easy using RPN by permuting the order operators and operands (within the constraints of a stack, so some combination as not possible; you can't operate on numbers if there are none in the stack!)

An added benefit of using RPN is that, at the end of any operation you can check the stack and that will give you a possible intermediate solution (remember not all numbers need to be used for a valid solution).

As an example of this, in the example on the last line of the table, the first intermediate result is (100-5)=95. This is not a valid answer, as it is less than a hundred (the lowest possible target). However the next operation is multiplication by 5. This gives a result of 475, which is valid. So, we already have a short (efficient) solution for 475 which is 5×(100-5). We also have an intermediate solution of 466 for the next step (5×(100-5))-9 …

Optimisations and Gotchas

There are some obvious optimisations that can be made in the algorithm (plus a couple of things to watch out for):

  • There is no benefit in multiply by 1 at any stage. This just makes a longer solution.

  • Similarly, there is no benefit of dividing by 1 at any stage.

  • If at any time the intermediate solution becomes negative, we can instantly bail on that solution.

  • Similarly if the intermediate solution becomes non-integer.

  • Slightly more subtly, if there is an intermediate calculation where a÷b=b then this is redundant because this is just a longer form of using b.

  • Likewise for a-b=b.

  • You need to make sure you catch any potential divide by zero calculation that might happen as you test for possible solutions.

  • It's very tempting to think about using 16 bit Integers to store intermediate but this is wrong for a couple of reasons. The highest possible intermediate accumulator total encountered is 100×75×50×25×10×10 = 937,500,000. This would cause an overflow.

  • Notwithstanding the above, the highest intermediate total seen in a valid solution is 99,600 which happens when trying to obtain a total of 996 from the set {3,3,25,50,75,100}.

    The solution for this, and it is a unique solution for this total, is ((((50+3)×25)+3)×75)÷100=996 If this came up on the show, and you'd managed to work this out, I'm sure you'd be proud!

    The most convoluted I've heard about in the history of the show is this one for 952, followed closely by 821 (from an Australian version of the show). Pretty impressive!

I find it easier to interpret infix rather than postfix equations, so I wrote a function to convert these back and insert the appropriate parenthesis after the calculations were over.

Results

  • The 13,243 possible combinations that the tiles can be selected can be combined to make 10,871,986 distinct solutions of tiles and target numbers.

  • There is no target number that it is impossible to make, given the correct numbers.

  • Only one set of number {1,1,2,2,3,3} cannot make any target solution (as it’s not possible to make any three digit number from this set of numbers).

    If you were unlucky enough to draw these numbers there is nothing you could do. The hight possible total achievable from these six numbers is 81 = (2+1)×(2+1)×3×3. Even the lowest target of 100 is more than 10 away from this, so no score is possible.

  • The ‘hardest’ total to make is 947. Just 9,017 of the 13,243 combinations can make it (68.09%).

  • There are four target numbers that are the ‘easiest’ total to make. These are: 100, 102, 104 and 108 both of these can be made by 13,240 of the possible 13,243 tile combinations (99.98%). Of the three solutions missing, one should not be a surprise, we’ve already discussed it, and this is {1,1,2,2,3,3}. Since it’s not possible to make any target number from this set, it has to be missing by definition! Related to this is the set {1,1,2,2,3,4} which can only can one possible total, which is 108 (1+2)×((1+2)×(3×4)). Finally numbers in the set {1,7,7,8,8,9} cannot be combined to make 100.

    For 102 and 104, the impossible sets are {1,1,2,2,3,3} {1,1,2,2,3,4} {1,1,2,2,3,5}

    For 108, the impossible sets are {1,1,2,2,3,3} {1,1,5,5,50,75} {1,1,10,10,50,75}

  • Out of the 13,243 possible combinations, a surprising 1,226 of them can solve any problem from 100-999 inclusive (9.26%). Below are the first few resutls of a set that can make all 900 possible target numbers. It is the set {2,7,9,10,25,50}. The first few solutions are shown below (click link after for complete list):


100 = 2×50 101 = (2×(7×9))-25 102 = ((2+9)×7)+25 103 = ((2+9)×10)-7
104 = (2×7)+(9×10) 105 = 7×(25-10) 106 = 2×((7×9)-10) 107 = (2×50)+7
108 = (2+10)×9 109 = (2×50)+9 110 = (2+9)×10 111 = (2×(9+50))-7
112 = 7×(25-9) 113 = (7×9)+50 114 = 2×(7+50) 115 = (9×10)+25
116 = (2×(7×9))-10 117 = ((2+9)×10)+7 118 = 2×(9+50) 119 = 7×((9-2)+10)
120 = 2×(10+50) 121 = (2×((7×9)+10))-25 122 = 2×((7×10)-9) 123 = (2×(7+50))+9
124 = (2×(7+50))+10 125 = (7-2)×25 126 = 2×(7×9) 127 = ((2+9)×7)+50
128 = (7+9)×(10-2) 129 = (2×(10+50))+9 130 = 2×((9×10)-25) 131 = ((2+7)×9)+50
132 = 2×(7+(9+50)) 133 = 7×(9+10) 134 = ((7-2)×25)+9 135 = 9×(25-10)
136 = (2×(7×9))+10 137 = 2+(9×(25-10)) 138 = 2×(9+(10+50)) 139 = (2×(7+50))+25
140 = 2×(7×10) 141 = (2×(25+50))-9 142 = 2+((9×10)+50) 143 = (2×(9+50))+25
144 = (2+7)×(25-9) 145 = (2×(10+50))+25 146 = 2×((7×9)+10) 147 = (2+(9+10))×7
148 = ((10-7)×50)-2 149 = (2×(7×10))+9 150 = 2×(25+50) 151 = (2×(7×9))+25
152 = (7×(25-2))-9 153 = (7+10)×9 154 = (2×7)+((9×10)+50) 155 = 2+((7+10)×9)
156 = (2+50)×(10-7) 157 = (7×25)-(2×9) 158 = 2×((7×10)+9) 159 = (2×(25+50))+9
160 = (7+9)×10 161 = 7×(25-2) 162 = 9×(25-7) 163 = (2×50)+(7×9)
164 = 2+(9×(25-7)) 165 = (7×25)-10 166 = (7×25)-9 167 = 2+((7×25)-10)
168 = 2+((7×25)-9) 169 = (2×(7+(9×10)))-25 170 = (7-2)×(9+25) 171 = (2+7)×(9+10)
172 = (9×(25-7))+10 173 = (7×25)-2 174 = ((7×25)+9)-10 175 = 7×25
176 = 2×((7×9)+25) 177 = 2+(7×25) 178 = ((7+10)×9)+25 179 = ((2+25)×7)-10
180 = 2×(9×10) 181 = ((2×(7×10))-9)+50 182 = 7+((9-2)×25) 183 = (7×(9+10))+50
184 = (7×25)+9 185 = (7×25)+10 186 = 2+((7×25)+9) 187 = (2+9)×(7+10)
188 = (7×(9+25))-50 189 = (2+25)×7 190 = 2×((7×10)+25) 191 = ((10-2)×25)-9
192 = (2+10)×(7+9) 193 = (2×9)+(7×25) 194 = 2×(7+(9×10)) 195 = (2×10)+(7×25)
196 = ((2×9)+10)×7 197 = (9×(25-2))-10 198 = (2+9)×(25-7) 199 = ((2+25)×7)+10

You can view the entire results here. (Link opens in a new window).

Here is a list of all the sets, like {2,7,9,10,25,50} that can make every single target number from 100-999 (Link opens in a new window).


# BigCount
05
1614
2603
34

Of the 1,226 perfect solution sets (sets of numbers that can solve any problem), only five of them contain no large number (for the shortest solution). There is no perfect number set that contains all four large numbers. If you select just one large number, you marginally increase your chances of getting a set of numbers that can solve any problem (cf. selecting two large numbers).

The table on the left shows the distribution of large number counts in all the perfect solutions (for the shortest possible solution).

Pivoting this data the other way, the percentage of problems that are solvable changes with the target number. As the target number gets larger, the percentage of times a random selection of tiles will be able to solve gets smaller. (This is not a surprise. As the target gets larger, it's more likely that the multiplication operator is used more. This will leave gaps in between targets that are not reachable).

All totals below 316 are solvable by >95% of all possible sets.

Trivia

Other misc pieces of trivia:

Try it out yourself

Try your hand at solving Countdown numbers problems. If you want to find out solutions, I've put a solver online.

The solver allows you to input the selected tiles (in any order), the requested target, and gives the simplest (smallest number of numbers used) solution to the target number (if an exact solution is possible). If no exact solution is possible the three nearest solutions are given. Have fun!

 

You can find a complete list of all the articles here.      Click here to receive email alerts on new articles.

© 2009-2014 DataGenetics    Privacy Policy