# Just for fun: Countdown numbers game solver

david.hotham at blueyonder.co.uk david.hotham at blueyonder.co.uk
Mon Jan 28 22:31:05 CET 2008

```I also had a go at this problem for a bit of python practice, about 6
months ago.  I tried a few optimizations and my experience was that
with only 6 seeds, a hash table was very effective.  So effective, in
fact, that it made all other optimizations more or less pointless.

Code below.  Arguments are seeds first, then targets.  Like this:

C:\utils>countdown.py 7 8 50 8 1 3 923
50 * 8 = 400
400 - 1 = 399
399 / 3 = 133
133 * 7 = 931
931 - 8 = 923

Took 0.421 seconds

from time import time
from bisect import insort
from sys import argv

#------------------------------------------------------------------------------
# Hash table is a global variable
#------------------------------------------------------------------------------
global hash_table

#------------------------------------------------------------------------------
# countdown.py
#
# Python script to solve the Countdown numbers game
#
# Remarks on optimization:
#
# -  Without the hash table, the following all proved beneficial:
#    -  Keep a list of numbers used so far, and never create a number
that
#    -  Make sure only to return unique pairs from the generate_pairs
function
#    -  Don't ever perform two consecutive substractions
#    -  (Don't ever perform two consecutive divisions would also be
valid,
#       though it's not something that happens a lot so the benefit is
small)
#
# -  These tricks work by avoiding performing the same search more
than once
#
# -  With only six seeds, it's possible to implement a perfect hash
table that
#    remembers every list that we try to solve (and indeed this is
what the
#    implementation here does)
#
# -  With that hash table, the optimizations above become largely
redundant, so
#    for the sake of simplicity I've removed them
#
# -  Solving for larger numbers of seeds would require a smarter
approach, as
#    it would soon become infeasible to maintain a complete hash
table.  Then
#    the tricks above might be useful again.
#
#------------------------------------------------------------------------------

#------------------------------------------------------------------------------
# Returns all useful combinations of two numbers, and a string
representing
# the operation used to get there.
#------------------------------------------------------------------------------
def generate_combinations(higher_number, lower_number):

#--------------------------------------------------------------------------
# Useful operations are:
# - subtraction (of the lower number from the higher number, so
long as
#   they are not equal)
# - multiplication (so long as not multiplying by one)
# - division (if it's exact, and not by one)

#--------------------------------------------------------------------------
yield "+", higher_number + lower_number
if (higher_number != lower_number):
yield "-", higher_number - lower_number
if (lower_number != 1):
yield "*", higher_number * lower_number
if ((higher_number % lower_number) == 0):
yield "/", higher_number / lower_number

#------------------------------------------------------------------------------
# Returns all pairs from a list of seeds.
#
# Pairs always have the first number lower than or equal to the second
number,
# provided that the list is ordered on entry (as it should be).
#------------------------------------------------------------------------------
def generate_pairs(seeds):
for ii in xrange(len(seeds)):
for higher_num in seeds[ii+1:]:
yield seeds[ii], higher_num

#------------------------------------------------------------------------------
# Solves a seed list.  Takes pairs, combines them, and recursively
calls
# solve_list again with the new shorter list.
#
# Seeds should be sorted on entry.
#------------------------------------------------------------------------------
def solve_list(seeds, target, depth, solution_so_far):

#--------------------------------------------------------------------------
# Loop through possible pairs.

#--------------------------------------------------------------------------
for lower_num, higher_num in generate_pairs(seeds):

#----------------------------------------------------------------------
# Make a copy of the list, and remove this pair.
#
# Taking a copy appears to be quicker than using the original
list and
# then reinstating the chosen pair later.

#----------------------------------------------------------------------
new_seeds = seeds[:]
new_seeds.remove(lower_num)
new_seeds.remove(higher_num)

#----------------------------------------------------------------------
# Try out all possible combinations of our pair.

#----------------------------------------------------------------------
for operation, combination in
generate_combinations(higher_num,

lower_num):

#------------------------------------------------------------------
# If we hit our target, we're happy.
#
# Else if the list has gotten too short already, move on.
#
# Else make a new, shorter, list containing our new value.
#
# If we've already tried to solve the new list, there's no
point in
# trying again.
#
# Else try to solve the shorter list.

#------------------------------------------------------------------
if combination == target:
print "%s%d %s %d = %d\n" % (solution_so_far,
higher_num,
operation,
lower_num,
combination)
return(0)
elif (depth > 0):
insort(new_seeds, combination)
seeds_tuple = tuple(new_seeds)
if (seeds_tuple in hash_table):
pass
else:
hash_table[seeds_tuple] = 1
new_soln_so_far = ("%s%d %s %d = %d\n" %
(solution_so_far,

higher_num,

operation,

lower_num,

combination))
if (solve_list(new_seeds,
target,
depth - 1,
new_soln_so_far) == 0):

#------------------------------------------------------
# Success!

#------------------------------------------------------
return(0)

#--------------------------------------------------------------
# Remove the value that we made out of our number
pair, in
# preparation for the next try.

#--------------------------------------------------------------
new_seeds.remove(combination)

#--------------------------------------------------------------------------
# Didn't solve it.

#--------------------------------------------------------------------------
return(1)

#------------------------------------------------------------------------------
# OK, let's go.  Get the puzzle, and solve it.  The last argument is
the target
# and the others are the seeds.
#------------------------------------------------------------------------------
original_seeds = map(int, argv[1:-1])
target = int(argv[-1])
start_time = time()
failed = 1;
if target in original_seeds:
print "Target is amongst seeds!"
else:
original_seeds.sort()

#--------------------------------------------------------------------------
# First look for one-step solutions, then for two-step solutions,
etc.
# That way we always get a shortest solution first.

#--------------------------------------------------------------------------
for depth in xrange(len(original_seeds)):
hash_table = {}
failed = solve_list(original_seeds, target, depth, "")
if (failed == 0):
break
if (failed != 0):
print "No solution!"
print "Took %.3f seconds" % (time() - start_time)

```