Re: Just for fun: Countdown numbers game solver
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)
Re: Just for fun: Countdown numbers game solver
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 #
Re: Just for fun: Countdown numbers game solver
On Jan 28, 10:11 pm, Arnaud Delobelle <[EMAIL PROTECTED]> wrote: > 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 -- http://mail.python.org/mailman/listinfo/python-list
