During the summer vacation , There are often children in the office who have to follow their parents to work because they are unattended . If you're not busy , I'll play with them , They also like to play with me . We all like to play number games . see , A child gave me a difficult problem : Three 5 And a 1, Only add, subtract, multiply and divide four operations , Each number can only and must be used once , How to make the result equal to 24?
This is not the classic 24 Any questions ? We are good at this , I've been playing since I was a kid , How can children's games defeat Lao Xu ! But , For this question , I tried for a long time , But still can't find the answer .
“ This question , Is there no solution ?” I tried to ask the children .
“ Is not! , There is an answer to this question , And it's very simple .” The children are serious .
“ good , Give me 5 minute .” I slipped into my office , shut the door , Turn on the computer . no need Python, I don't think we can live in town .
When there is no way out , Exhaustion may be the best choice .4 A digital ,4 There are three kinds of operation symbols , Parentheses , How to exhaust all the formulas ? Let's break down the problem .
4 A digital , Each number can only and must be used once , It's a matter of permutation , share 4 × 3 × 2 = 24 4\times3\times2=24 4×3×2=24 Sort of permutation .
Python Built-in module itertools Provides permutation functions permutations(), You can give all the permutations . If you use ABCD Express 4 A digital , So the whole arrangement is as follows .
>>> from itertools import permutations
>>> for item in permutations('ABCD'):
print(item)
('A', 'B', 'C', 'D')
('A', 'B', 'D', 'C')
('A', 'C', 'B', 'D')
('A', 'C', 'D', 'B')
('A', 'D', 'B', 'C')
('A', 'D', 'C', 'B')
('B', 'A', 'C', 'D')
('B', 'A', 'D', 'C')
('B', 'C', 'A', 'D')
('B', 'C', 'D', 'A')
('B', 'D', 'A', 'C')
('B', 'D', 'C', 'A')
('C', 'A', 'B', 'D')
('C', 'A', 'D', 'B')
('C', 'B', 'A', 'D')
('C', 'B', 'D', 'A')
('C', 'D', 'A', 'B')
('C', 'D', 'B', 'A')
('D', 'A', 'B', 'C')
('D', 'A', 'C', 'B')
('D', 'B', 'A', 'C')
('D', 'B', 'C', 'A')
('D', 'C', 'A', 'B')
('D', 'C', 'B', 'A')
For each number arrangement , We need to go from 4 It is allowed to take out repeatedly from the operation symbols 3 individual , Form a formula . The problem becomes the following description : Yes 3 Baskets , There's... In every basket 4 Operator , Take from each basket 1 Symbols , How many possibilities are there ? This is a Cartesian product problem , The answer is 4 × 4 × 4 = 64 4\times4\times4=64 4×4×4=64 Maybe .
Python Built-in module itertools The Cartesian product function is provided product(), You can give the whole plan .
>>> from itertools import product
>>> for item in product('+-*/', '+-*/', '+-*/'):
print(item)
('+', '+', '+')
('+', '+', '-')
('+', '+', '*')
('+', '+', '/')
('+', '-', '+')
('+', '-', '-')
('+', '-', '*')
('+', '-', '/')
('+', '*', '+')
('+', '*', '-')
('+', '*', '*')
('+', '*', '/')
('+', '/', '+')
('+', '/', '-')
('+', '/', '*')
('+', '/', '/')
('-', '+', '+')
('-', '+', '-')
('-', '+', '*')
('-', '+', '/')
('-', '-', '+')
('-', '-', '-')
('-', '-', '*')
('-', '-', '/')
('-', '*', '+')
('-', '*', '-')
('-', '*', '*')
('-', '*', '/')
('-', '/', '+')
('-', '/', '-')
('-', '/', '*')
('-', '/', '/')
('*', '+', '+')
('*', '+', '-')
('*', '+', '*')
('*', '+', '/')
('*', '-', '+')
('*', '-', '-')
('*', '-', '*')
('*', '-', '/')
('*', '*', '+')
('*', '*', '-')
('*', '*', '*')
('*', '*', '/')
('*', '/', '+')
('*', '/', '-')
('*', '/', '*')
('*', '/', '/')
('/', '+', '+')
('/', '+', '-')
('/', '+', '*')
('/', '+', '/')
('/', '-', '+')
('/', '-', '-')
('/', '-', '*')
('/', '-', '/')
('/', '*', '+')
('/', '*', '-')
('/', '*', '*')
('/', '*', '/')
('/', '/', '+')
('/', '/', '-')
('/', '/', '*')
('/', '/', '/')
For a formula , Enumerate all possible parentheses , There seems to be no regularity . A little analysis , It's also easy to find solutions . We use it N Representation number , use # Representation operator , The possible situations are as follows 11 Types ( Some of them are equivalent , For the sake of simplicity , We don't continue to optimize ).
The numbers are 24 Sort of arrangement , The operation symbols are 64 Kind of plan , Add brackets with 11 Maybe , Then all possible formulas are 24 × 64 × 11 = 16896 24\times64\times11=16896 24×64×11=16896 individual . We just need to put each string form of the formula ( expression ) use eval() The result of function calculation , You can find that the result is equal to 24 The formula of . Of course , Some formulas may be meaningless , For example, the divisor is 0 The situation of . For meaningless formulas ,eval() It throws an exception , We just need to catch and ignore exceptions .
With the above analysis , Writing code is a natural thing 、 It's a light hearted thing .
>>> from itertools import permutations, product
>>> def game24(n1,n2,n3,n4):
for a,b,c,d in permutations((n1,n2,n3,n4),4):
for o1,o2,o3 in product(['+','-','*','/'], repeat=3): # Another way to write Cartesian product
cases = list()
cases.append('%d%s%d%s%d%s%d'%(a,o1,b,o2,c,o3,d))
cases.append('(%d%s%d)%s%d%s%d'%(a,o1,b,o2,c,o3,d))
cases.append('%d%s%d%s(%d%s%d)'%(a,o1,b,o2,c,o3,d))
cases.append('%d%s(%d%s%d)%s%d'%(a,o1,b,o2,c,o3,d))
cases.append('(%d%s%d)%s(%d%s%d)'%(a,o1,b,o2,c,o3,d))
cases.append('(%d%s%d%s%d)%s%d'%(a,o1,b,o2,c,o3,d))
cases.append('((%d%s%d)%s%d)%s%d'%(a,o1,b,o2,c,o3,d))
cases.append('(%d%s(%d%s%d))%s%d'%(a,o1,b,o2,c,o3,d))
cases.append('%d%s(%d%s%d%s%d)'%(a,o1,b,o2,c,o3,d))
cases.append('%d%s((%d%s%d)%s%d)'%(a,o1,b,o2,c,o3,d))
cases.append('%d%s(%d%s(%d%s%d))'%(a,o1,b,o2,c,o3,d))
for expression in cases:
try: # The denominator in the capture expression is 0 It's abnormal
if eval(expression) == 24:
print(' answer :%s = 24'%expression)
return
except:
pass
print(' unsolvable !')
>>> game24(5,5,5,1)
answer :5*(5-1/5) = 24
>>> game24(1,3,4,6)
answer :6/(1-3/4) = 24
>>> game24(10,10,4,4)
answer :(10*10-4)/4 = 24
>>> game24(7,7,3,3)
answer :7*(3/7+3) = 24
>>> game24(1,5,7,10)
answer :(1+7/5)*10 = 24
>>> game24(15,25,37,80)
unsolvable !
Exhaust all the changes , How about the speed ? Plus the time measure , Test with the same questions above , The fastest 5 millisecond , The slowest ( All the formulas are exhausted )146 millisecond .
>>> game24(5,5,5,1)
answer :5*(5-1/5) = 24, Time consuming 0.011
>>> game24(1,3,4,6)
answer :6/(1-3/4) = 24, Time consuming 0.117
>>> game24(10,10,4,4)
answer :(10*10-4)/4 = 24, Time consuming 0.005
>>> game24(7,7,3,3)
answer :7*(3/7+3) = 24, Time consuming 0.017
>>> game24(1,5,7,10)
answer :(1+7/5)*10 = 24, Time consuming 0.014
>>> game24(15,25,37,80)
unsolvable ! Time consuming 0.146
After verification , all OK 了 . Next , It's time for me to brag in front of the children , You can imagine . Ha ha ha .