Just for fun: Countdown numbers game solver

[david.hotham at blueyonder.co.uk]

I see I don't have as many columns as I'd expected.  Here's a
reformatted listing.



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)