Just for fun: Countdown numbers game solver

[david.hotham]

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)

 

[Arnaud Delobelle]

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.

My strategy was to walk through each solution "only once" (for a
certain definition of "only once , thus I was hoping not to need a
hashtable.

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

Did you pick these numbers at random? Interestingly, the solution is
unique:

[0.27424502372741699]

list(test(nums=[7, 8, 50, 8, 1, 3], target=923, method=divide, countdown=print_countdown)) (50*8-1)*7/3-8

(50*8-1)*7/3-8
[0.2748568058013916]

To find just one solution:

list(test(nums=[7, 8, 50, 8, 1, 3], target=923, countdown=first_countdown)) [0.11860203742980957]

(list returned contains time taken to reach solution. By comparison
your code takes 0.264s on my machine. Mine is faster on this example,
but one example is not representative!)

 

[david.hotham]

My strategy was to walk through each solution "only once" (for a
certain definition of "only once , thus I was hoping not to need a
hashtable.

Yes, that seems like it should be preferable (and indeed necessary for
a more general problem with larger numbers of seeds). But I wasn't
smart enough to figure out how to do it ;-)

Did you pick these numbers at random? Interestingly, the solution is
unique:

Not at random - this particular puzzle came out of the first post in
this thread.

Mine is faster on this example, but one example is not representative!

If you've found an efficient way to walk through the possible
solutions only once, then
- I expect that yours will be faster
- and well done!

I guess I should try to understand your code...

 

[Arnaud Delobelle]

If you've found an efficient way to walk through the possible
solutions only once

As discussed earlier in this thread, the definition of 'only once' is
not as clear cut as one would first think (see Terry's thoughts on
this).

 

[Arnaud Delobelle]

On Jan 29, 9:02 am, (e-mail address removed) wrote:

Oops I sent too quickly...

If you've found an efficient way to walk through the possible
solutions only once, then
-  I expect that yours will be faster
-  and well done!

I guess I should try to understand your code...

My code is quite naive and I suspect that combining your caching and
the tree pruning discussed in this thread would yield faster results.
Not sure if I'll have time to try this though...

 

[wolfram.hinderer]

So anyone got an answer to which set of numbers gives the most targets
from 100 onwards say (or from 0 onwards)? IsPythonupto the task?

It's (5, 8, 9, 50, 75, 100): 47561 targets altogether (including
negative ones), 25814 targets >= 100.
(BTW, 1226 sets of numbers give all 900 3-digit targets, but the above
one doesn't; 954 and 981 are missing.)

The following (mostly) straightforward program needed about 30 min for
the calculation. I tried to keep all (intermediate) results in a dict
(which turned out later to need too much memory). I wanted to use the
same dict for memoization. So I let the dict fill itself on access.
The disadvantage of this method is that the function needs to know
that it's being memoized. The advantage is that it's easier (I think)
to manipulate/control the dict.


class AutoFillDict(dict):
""" Values for missing keys are computed on-the-fly """

def __init__(self, func, *args, **kwargs):
self.func = func
super(AutoFillDict, self).__init__(*args, **kwargs)

def __missing__(self, key):
self[key] = self.func(self, key)
return self[key]


def subs_k(dic, (nums, k)):
""" Return k-subsets of tuple nums, using dic as cache """
if k == 1:
return [(i,) for i in nums]
if k == len(nums):
return [nums]
a = nums[:1]
b = nums[1:]
return [a + i for i in dic[b, k-1]] + dic[b, k]


def subs_and_complements(dic, nums):
""" Return subsets and complements of tuple nums, using dic as
cache """
if not nums:
return set([((), ())])
a = nums[:1]
b = nums[1:]
res = set([(s, a + c) for s, c in dic])
res.update([(a + s, c) for s, c in dic])
return res


subs_and_comps = AutoFillDict(subs_and_complements)


def countdown(dic, nums, sac_dict=subs_and_comps):
"""Return all possible goals for input nums, using dic as cache

All numbers in nums must be used.

"""
if len(nums) == 1:
return nums
ret = set()
for s, c in sac_dict[nums]:
if s and c:
xs = dic
ys = dic[c]
ret.update([x + y for x in xs for y in ys])
ret.update([x - y for x in xs for y in ys])
ret.update([x * y for x in xs for y in ys])
ret.update([x // y for x in xs for y in ys if y != 0 and x
% y == 0])
return ret


def print_max(results):
max_goals = max(results.values())
max_nums = [n for (n, g) in results.items() if g == max_goals]
max_nums.sort()
print "Maximal number of reachable goals: %d" % max_goals
print "Number of tuples: %d" % len(max_nums)
for n in max_nums:
print n


if __name__ == "__main__":

all_nums = range(1, 11)*2 + [25, 50, 75, 100]
all_nums = tuple(sorted(all_nums))

subsets_k = AutoFillDict(subs_k)
d = AutoFillDict(countdown)

results = {}
results100 = {}
for i, nums in enumerate(sorted(set(subsets_k[all_nums, 6]))):
# result is the union of reachable goals for all subsets
result = set()
for s, c in subs_and_comps[nums]:
result.update(d)
results[nums] = len(result)
results100[nums] = len([x for x in result if x >= 100])
# Prevent MemoryError
if i % 200 == 0:
d.clear()

print "Goals: all integers"
print_max(results)
print
print "Goals: integers >= 100"
print_max(results100)