As has been noted elsewhere, a set of 2 large + 4 small or 1 large + 5 small typically covers a large proportion of target numbers (101 to 999), and there are typically many ways of expressing each target using some or all of the 6 numbers.
These sets each cover all targets from 101 to 999. The lists of solutions (
) contain all targets from 0 until a gap above 999 is reached:5 6 7 8 9 75 (five consecutive numbers)6 7 7 9 9 100 is perhaps more noteworthy, covering every target number except the number 367
2 5 7 8 9 10 (six small numbers)
4 7 7 10 25 100 (a repeated number)
8 9 25 50 75 100 is the best set containing all four large numbers, covering 885 targets
The code constructs solutions for a few games that have appeared on the TV show:
- 3 6 25 50 75 100 with a target of 952 , the James Martin 952 game, which has 2 solutions, (3×75×(6+100)-50)÷25 which was found by the contestant, and 25+(6×75×(3+100))÷50.
- 1 4 8 9 10 50 with a target of 500 ,possibly the easiset game ever? for which my program finds 21 distinct solutions .
- Some games solved by George Ford , one of the best countdown contestants.
e.g. (((((6)+(7))-(9))×(7))×(9))-(100)=(6+7-9)×7×9-100
and avoiding solutions that are essentially the same, e.g. 152=(6+7-9)×7×9-100=7×(7-9+6)×9-100.
The program also excludes "frivolous" solutions that contain an expression that equates to zero, e.g. 500 = (9-8-1)×4+50×100, solutions that involve multiplying or dividing by 1, e.g. 500 = (9-8)×50×100 or 500 = 50×100÷1 and solutions that have other redundancies, e.g. 500 = 9+10×50-1-8.
# -*- coding: cp1252 -*- from itertools import combinations def wrap(t, condition=True): return ''.join(["(",t,")"]) if condition else t def expressions( A, processed=set() ): """ initially, A is an array of numbers In recursive calls, A is an array of tuples (n,t,o,x,y,h) where n is a number, t is a text expression of n, o is the last operation applied to x,y to produce n = xoy h is the history of the expression, containing all the numbers produced in the construction of the expression """ if type(A[0])==int: # inital call, so convert to array of tuples A = [ (A[i],str(A[i]),"",0,0, frozenset((A[i],)) ) for i in xrange(len(A))] processed=set() else: # recursive call, so return the expression formed in the parent n,t,o,x,y,h = A[0] if (n,t) not in processed: yield A[0] processed.add( (n,t) ) A.sort() tA=tuple(A) if tA in processed: return processed.add(tA) if A[0][0]==0: return for p1, p2 in combinations(range(len(A)),2): p1,p2 = sorted((p1,p2)) n1,t1,o1,x1,y1,h1 = A[p1] n2,t2,o2,x2,y2,h2 = A[p2] history=h1|h2 B= A[:] B.pop(p2) B.pop(p1) # don't process x/(y/z) as (x*z)/y produces the same answer # don't process x/(y*z) as x/y/z produces the same answer if n2 <> 0 and n1%n2==0 and o2 not in ('*','/') and n1/n2 not in history: C=[(n1/n2, wrap(t1,o1 not in ('',))+ u'÷' +wrap(t2,o2<>''),"/",n1,n2, frozenset(history|set((n1/n2,))) )] for x in expressions(C+B, processed): yield x if n1 <> 0 and n2%n1==0 and o1 not in ('*','/') and n1<>1 and n2/n1 not in history: C=[(n2/n1, wrap(t2,o2 not in ('',))+u'÷'+wrap(t1, o1<>''),"/",n2,n1, frozenset(history|set((n2/n1,))) )] for x in expressions(C+B, processed): yield x # don't process x*(y/z), as (x*y)/z produces the same answer # don't process (x/y)*z as (x*z)/y produces the same answer if o2<>'/' and o1<>'/' and n2<>1 and n1<>1: # don't process x*(y*z) if (x>y or x>z) if not(o2=='*' and (n1>x2 or n1>y2)) and n1*n2 not in history: C= [(n1*n2,wrap(t1,o1 not in ('','*'))+u'×'+wrap(t2,o2 not in ('','*')),"*",n1,n2, frozenset(history|set((n1*n2,))) )] for x in expressions(C+B, processed): yield x # don't process x-(y-z), as x+y-z produces the same answer # don't process x-(y+z), as x-y-z produces the same answer # don't process (x-y)-z if y>z. x-z-y produces the same answer if n1>=n2: if o2 not in ('+','-'): if not( o1=='-' and y1>n2) and n1-n2 not in history: C=[(n1-n2,wrap(t1,False)+"-"+wrap(t2,o2 not in ('','*','/')),"-",n1,n2, frozenset(history|set((n1-n2,))) )] for x in expressions(C+B, processed): yield x if n2>=n1: if o1 not in ('+','-'): if not( o2=='-' and y2>n1) and n2-n1 not in history: C= [(n2-n1,wrap(t2,False)+"-"+wrap(t1,o1 not in ('','*','/')),"-",n2,n1, frozenset(history|set((n2-n1,))) )] for x in expressions(C+B, processed): yield x # don't process x+(y-z), as (x+y)-z produces the same answer # don't process (x-z)+y, as (x+y)-z produces the same answer if o1<>'-' and o2<>'-': # don't process x+(y+z) if (x>z or x>y) if not( o2=='+' and (n1>x2 or n1>y2)) and n1+n2 not in history: C=[(n1+n2,wrap(t1,False)+"+"+wrap(t2,False),"+",n1,n2, frozenset(history|set((n1+n2,))) )] for x in expressions(C+B, processed): yield x #--------------------------------------------------------------------- # find all the solutions matching a target def allsolutions(A,target): print "\n", A, "target =",target for (x,t,o,a,b,h) in expressions(A): if x==target: print x,"=",t # find how many targets in the range 101..999 are covered def numtargets(A): results=set() for (x,t,o,a,b,h) in expressions(A): results.add(x) return len(results & set(range(101,1000))) # write expressions for all targets for a set of numbers A, until a gap above 1000 is found def alltargets(A): filename = "Countdown numbers game coverage for "+ ",".join(str(i) for i in sorted(A)) +".txt" f=open(filename,'w') lastx=-1 for (x,t) in sorted( (x,t) for (x,t,o,a,b,h) in expressions(A) ): if x>lastx: if x >1000 and x<>lastx+1: break f.write( (str(x) + "=" + t + "\n").encode('utf8') ) lastx=x f.close() if __name__=='__main__': from random import randint as RI print "\nThe James Martin 952 game, https://www.youtube.com/watch?v=6mCgiaAFCu8" allsolutions([100,75,50,25,6,3], 952) print "\nGeorge Ford, https://www.youtube.com/watch?v=DYW1c41Aw0U" allsolutions([100,75,50,25,8,2], 318) allsolutions([100,75,50,25,1,3], 974) allsolutions([100,75,50,25,1,8], 278) allsolutions([100,75,50,25,1,2], 940) allsolutions([50,75,8,5,4,1], 937) allsolutions([100,75,50,25,4,1], 189) allsolutions([100,75,50,25,5,6], 814) print "\nThe easiset game ever? https://www.youtube.com/watch?v=d3I2lafp9LY" allsolutions([1,4,8,9,10,50], 500) for i in xrange (5): target=RI(101,999) print "\nA game with 7,7,8,8,9,9, target",target allsolutions([7,7,8,8,9,9], target) print "\nThese only have a few solutions each" allsolutions([50,25,1,7,10,10], 976) allsolutions([100,75,1,1,3,5], 862) allsolutions([50,75,2,5,5,6], 977) allsolutions([100,50,10,10,7,1], 284) allsolutions([75,25,1,4,6,10], 632) print "\nTest random combinations of 2 top + 4 bottom" print "until a combination is found that covers all targets 101 to 999" top2 = [ x for x in combinations([25,50,75,100],2)] bottom4 = [ x for x in combinations(range(1,11)+range(1,11),4)] while True: A= list(top2[RI(0,len(top2)-1)] + bottom4[RI(0,len(bottom4)-1)]) n = numtargets(A) print A,"covers", n ,"targets" if n==899: break print "\nTest random combinations of 1 top + 5 bottom" print "until a combination is found that covers all targets 101 to 999" bottom5 = [ x for x in combinations(range(1,11)+range(1,11),5)] while True: A=[RI(1,4)*25]+ list(bottom5[RI(0,len(bottom5)-1)]) n = numtargets(A) print A,"covers", n ,"targets" if n==899: break # these cover all targets 101..999 alltargets([75,5,6,7,8,9]) alltargets([25, 100, 4, 7, 10, 7]) # these are useful for school game of noughts and crosses alltargets([2,3,4,5]) alltargets([3,4,5,6])
No comments:
Post a Comment