Coding Countdown: The Numbers Round

Okay, this one was a little trickier than the letters.

The objective of the Countdown numbers game is to make a target number (a randomly generated integer between 100 and 999) from six other pseudo-randomly selected numbers in the set [100, 75, 50, 25, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]. The numbers 1-10 may appear more than once, and contestants have some say in their distribution, for example ‘one large (i.e. in the 25-100 group) and five small (i.e. in the 1-10 group)’.

The following rules apply:

  • Only the operations +, -, x and / (plus, minus, times, divide) are allowed.
  • Brackets may be used, e.g. (1+3) x 10 = 40.
  • All intermediately calculated numbers must be positive integers, e.g. (5 / 2) * 10 = 25 is not permissible as 5 / 2 = 2.5; however, (5 * 10) / 2 = 25 is fine. Similarly, (5 – 10) + 50 = 45 is unacceptable as 5 – 10 = -5; however, (5 + 50) – 10 is fine.
  • A number may only be used as many times as it appears in the initial set of six.
  • It is not necessary to use all of the numbers.

This article is about using efficient Python code to quickly calculate all possible ways of reaching a target number (not necessarily between 100 and 999) from a group of smaller numbers (not necessarily 6), adhering to the Countdown rules described above. Along the way we’ll look at tree construction and search based on Python dictionaries.

n.b. the rule concerning not having to use all of the numbers is glossed over until the very end of the article for the sake of simplicity in explanation.

First Thoughts

I thought I had cracked this one in double-quick time. I considered the option of running through every possible permutation of the numbers and, for each permutation, slotting in every possible permutation of the operators, then evaluating left-to-right. If, at any stage, the rules were violated, that particular permutation would be abandoned. Given that there are 6! = 720 ways of permuting 6 numbers without replacement, and 1020 ways of permuting four operators five times with replacement, this gives a maximum of 734400 expressions to evaluate, which, to a computer, is no big deal. Bingo!

But, as a trivial example can show, this algorithm does not generate every possible solution. Consider the case of target number 144 with working numbers [11, 11, 11, 11, 11, 11].

The only way of doing this is ((11/11) + 11) * ((11/11) + 11) = 144. The brackets are crucial. No possible arrangement of left-to-right operations can give 144. Back to the drawing board.

Trees and Pairs

I like to go about solving complicated problems by solving simpler ones first. So, rather than throwing myself straight into the James Martin 952 problem, I tried to make 6 from [1, 2, 3].

To establish all of the different ways of making 6, I drew something like this:

2014-03-25 18.54.28

What’s going on here is that I’m considering pairs of numbers (let’s call them A and B) in turn. I consider every way of reducing [1, 2, 3] into [x, 3], [x, 2] and [x, 1]. It turns out that there are between two and four values for x in the general case:

  • Addition and multiplication will never violate the rules. They are commutative operations, so there is no need to consider A + B and B + A separately.
  • Subtraction is not commutative; however, if A is greater than B, then A – B will always give a positive integer. Conversely, if A is less than or equal to B, A – B will never give a positive integer.
  • Division is not commutative; however, if A is less than B, then A / B will never give a positive integer. We will accept A / B if A is greater than or equal to B and the result is an integer.

To start us off in Python, here is some code that returns all of the possible values of x from A and B. It also returns a string representation of the operation, so we can retrace how each x was constructed later. The code requires A <= B to be valid, which we will address later. Note the use of the ‘yield’ statement, which should be interpreted by non-Python programmers as ‘return x and keep going’.

def all_results_from(a, b):
    '''
    Yield all of the possible positive integer results
    from applying +, -, * and / to a and b as tuples.
    The first element is a string representation of the
    operation. The second is an integer.
    We assume b > a. Depending on a and b,
    there may be 2 - 4 possible results.
    '''
    # Addition and multiplication are commutative.
    yield '+', a + b
    yield 'x', a * b
    # Subtraction and division are not commutative.
    c = b - a
    if c > 0:
        yield '-', c
    if b % a == 0:
        yield '/', b / a

The diagram continues to reduce the tree in this way until the ‘leaves’ are single integers. These ‘leaves’ can be shown to be every possible outcome from the original numbers, as each pair combination is effectively a ‘bracketed’ operation. A bit of thought will tell you that we could make 144 from the [11, 11, 11, 11, 11, 11] example with this method.

Constructing the Tree Graph

The tree can be constructed with a bit of recursive code. This article about Python graphs represents a graph as a dict of lists; however, I used a dict of dicts as I needed to store information on the ‘connecting lines’, i.e. how x was made from A and B. The dictionary keys are tuples of numbers available for selection, henceforth referred to as nodes. My first stab went something like this:

def solve(numbers, target):

    numbers = tuple(sorted(numbers))
    graph = defaultdict(dict)

    def r(numbers):
        l = len(numbers)
        for pair, rejects in pairs_and_rejects(l):
            a, b = numbers[pair[0]], numbers[pair[1]]
            rejects = [numbers[i] for i in rejects]
            for op, c in all_results_from(a, b):
                node = tuple(sorted(rejects + [ c ]))
                graph[node][numbers] = ((a, b), op, c)
                r(node)

    r(numbers)

I’ve already shown you the ‘all_results_from’ function, so the only thing new here is ‘pairs_and_rejects’. ‘Pairs’ here refers to the A and B we have set aside to operate on. ‘Rejects’ is a list of what’s left over. Note the use of the built-in ‘sorted’ function, which allows us to guarantee A <= B, and avoids the code interpreting (3, 2) as being different from (2, 3). Also, the function is called ‘solve’, and accepts ‘target’ as an argument, but we haven’t done any solving yet.

This code works OK, but there are two problems, both caused by the dictionary keys (i.e. node names) not being unique in the current system.

  • The code does not consider the possibility of two DIFFERENT parent nodes ((3, 3) and (2, 3)) arriving at the same node (6). This is a serious problem as, when we retrace our steps later and enquire how many ways of making 6 were found, we will be told ’1′. We’re also wasting computational effort if the common node has a subtree of its own to calculate.
  • Referring to my hand-drawn tree, you will see that there are multiple ways of arriving at (2, 3) from the SAME parent node (i.e. (1, 2, 3)) and the code above overwrites old ones as as it goes. This is a less serious problem that will normally only manifest itself when 1s and 2s are involved, e.g. 2 x 1 = 2 / 1 = 2. You may be able to think of other special cases.

To counter the first problem, we need to ask whether or not a node already exists in the graph. To counter the second problem, we need to allow the facility to store multiple paths between two nodes. We will use a set to guarantee the uniqueness of these paths.

Finally, for reasons of efficiency, let’s add a conditional statement when we get down to just two numbers, A and B, at a node. If A x B is less than our target, or B / A (remember, A <= B) is greater than our target, then it’s not worth bothering trying + and -.

Here is the finished graph construction function:

def solve(numbers, target):

    numbers = tuple(sorted(numbers))
    graph = {}

    def r(numbers):
        l = len(numbers)
        if l == 2:
            a, b = numbers[0], numbers[1]
            if b / a > target or a * b < target:
                return
        for pair, rejects in pairs_and_rejects(l):
            a, b = numbers[pair[0]], numbers[pair[1]]
            rejects = [numbers[i] for i in rejects]
            for op, c in all_results_from(a, b):
                node = tuple(sorted(rejects + [ c ]))
                if node in graph:
                    graph[node][numbers].add(((a, b), op, c))
                else:
                    graph[node] = defaultdict(set)
                    graph[node][numbers].add(((a, b), op, c))
                    r(node)

    r(numbers)

Considering All Combinations

So far, we’ve glossed over the fact that we don’t have to use all of the numbers. This can be overcome by using the itertools.combinations function to extend the graph such that all possibilities are included, like so:

for i in xrange(len(numbers)):
        for numbers_combination in combinations(numbers, i+1):
            r(numbers_combination)

Retracing Our Steps

Now we’ve constructed our tree, we need to work backwards to find all of the paths from our target to the original numbers (both the full set and subsets thereof). Fortunately, the hard labour has already been done for us, and a simple copy-paste of an official Python example function called find_all_paths will do the trick nicely.

From there, it’s a matter of formatting the output, which is a fairly unglamourous process. One detail to be aware of is that, in terms of tree traversal, the following solutions will be considered unique:

‘Make 750 from [25, 5, 3, 2]‘:

1:
25 x 2 = 50
5 x 3 = 15
50 x 15 = 750

2:
5 x 3 = 15
25 x 2 = 50
50 x 15 = 750

Of course, they are not, so we only show solutions whose intermediate numbers are different. This doesn’t preclude (2 x 3 = 6, 6 x 4 = 24) being interpreted as different to (3 x 4 = 12, 12 x 2 = 24). Some people may disagree; however, I would argue that these solutions are in fact unique.

952

Let’s set our code loose on James Martin’s 952 game. We learn that there are, in fact, seven possible solutions! (James picked option 3). Perhaps he’s not such a genius after all!

Blakes-iMac:countdown_math Blake$ time python maths.py

SOLUTION 1 FROM (3, 6, 25, 50, 75, 100)

100 + 6 = 106
106 x 75 = 7950
7950 x 3 = 23850
23850 - 50 = 23800
23800 / 25 = 952

SOLUTION 2 FROM (3, 6, 25, 50, 75, 100)

75 x 3 = 225
100 + 6 = 106
225 x 106 = 23850
23850 - 50 = 23800
23800 / 25 = 952

SOLUTION 3 FROM (3, 6, 25, 50, 75, 100)

100 + 6 = 106
106 x 3 = 318
318 x 75 = 23850
23850 - 50 = 23800
23800 / 25 = 952

SOLUTION 4 FROM (3, 6, 25, 50, 75, 100)

100 + 3 = 103
103 x 75 = 7725
7725 x 6 = 46350
46350 / 50 = 927
927 + 25 = 952

SOLUTION 5 FROM (3, 6, 25, 50, 75, 100)

100 + 3 = 103
103 x 6 = 618
618 x 75 = 46350
46350 / 50 = 927
927 + 25 = 952

SOLUTION 6 FROM (3, 6, 25, 50, 75, 100)

100 + 3 = 103
75 x 6 = 450
450 x 103 = 46350
46350 / 50 = 927
927 + 25 = 952

SOLUTION 7 FROM (3, 6, 25, 50, 75, 100)

75 x 6 = 450
450 / 50 = 9
100 + 3 = 103
103 x 9 = 927
927 + 25 = 952

real	0m1.492s
user	0m1.307s
sys	0m0.107s

I don’t think 1.5 seconds is too bad for this! I feel as if, though, someone might be able to do better. Do you have any ideas? Let me know!

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>