Just for fun: Countdown numbers game solver

[david.hotham at blueyonder.co.uk]

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
made target!
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
#       you've already used
#    -  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:
    # - addition (always)
    # - 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 "made 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)