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