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)
--
http://mail.python.org/mailman/listinfo/python-list
