#!/usr/bin/env python # Not exhaustive. Just a quick hack. # Doesn't solve 25 50 75 100 3 6 952 for example # http://www.youtube.com/watch?v=pfa3MHLLSWI import sys from operator import add, sub, mul, div ops=[mul,add,sub,div] repr_ops={mul:'*', add:'+', sub:'-', div:'/'} random_prob=0 if len(sys.argv) == 1: random_prob=1 import random allnums=range(1,11)*2+[25,50,75,100] random.shuffle(allnums) nums = allnums[:6] target = int(random.random()*1000) elif len(sys.argv) != 8: print "Usage:", sys.argv[0], "[1 2 3 4 5 6 123]" sys.exit(1) else: nums=map(int,sys.argv[1:7]) target=int(sys.argv[7]) solution=[] nums.sort() nums.reverse() #start with largest nums def calculate(num1, op, num2): ans = op(float(num1),num2) ians = int(ans) if ans==num1 or ans==num2: return 0 elif ians != ans: return 0 elif ians < 0: #could abs this and handle simply below for speed return 0 return ians times=0 def solve(target): global times times+=1 for inum1 in range(len(nums)-1): num1=nums[inum1] if num1 != 0: for inum2 in range(inum1+1, len(nums)): num2=nums[inum2] if num2 != 0: for op in ops: total=calculate(num1, op, num2) if total and total!=target: #could check levels here to get best solution nums[inum1]=0 #don't use nums[inum2]=total #check other nums in combo with this result = solve(target) nums[inum1]=num1 nums[inum2]=num2 if result: solution.insert(0,(num1, op, num2)) return 1 elif total == target: solution.insert(0,(num1, op, num2)) return 1 return 0 solve(target) print >> sys.stderr, "%d combinations checked" % times if random_prob: print >> sys.stderr, nums, target # OK have a graph now and would like to represent # this as a Directed Acyclical Graph (tree) with # the original numbers as nodes and the operations as edges. # This would be very easily achieved using a dictionary # if there were unique nodes (original and intermediary numbers), # but is a little more involved as this isn't the case. if len(solution) != 0: #flag origonal numbers as string solution2=[] for num1, op, num2 in solution: if num1 in nums: try: nums.remove(num1) num1=str(num1) except: pass if num2 in nums: try: nums.remove(num2) num2=str(num2) except: pass solution2.append((num1,repr_ops[op],num2)) import types def printanswer(ans): print "(", for num1, op, num2 in solution2: nextans=eval(str(num1)+op+str(num2)) if nextans == ans: solution2.remove((num1,op,num2)) break else: print "the sky is falling", ans, ")", return if type(num1) != types.StringType: printanswer(num1) else: print num1, print op, if type(num2) != types.StringType: printanswer(num2) else: print num2, print ")", printanswer(target) else: sys.exit(1)