1. problem

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 .

2. analysis

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 .

2.1 Numbers

4 A digital , Each number can only and must be used once , It's a matter of permutation , share $4\times 3\times 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')

2.2 Operation symbol

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\times 4\times 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)
('+', '+', '+')
('+', '+', '-')
('+', '+', '*')
('+', '+', '/')
('+', '-', '+')
('+', '-', '-')
('+', '-', '*')
('+', '-', '/')
('+', '*', '+')
('+', '*', '-')
('+', '*', '*')
('+', '*', '/')
('+', '/', '+')
('+', '/', '-')
('+', '/', '*')
('+', '/', '/')
('-', '+', '+')
('-', '+', '-')
('-', '+', '*')
('-', '+', '/')
('-', '-', '+')
('-', '-', '-')
('-', '-', '*')
('-', '-', '/')
('-', '*', '+')
('-', '*', '-')
('-', '*', '*')
('-', '*', '/')
('-', '/', '+')
('-', '/', '-')
('-', '/', '*')
('-', '/', '/')
('*', '+', '+')
('*', '+', '-')
('*', '+', '*')
('*', '+', '/')
('*', '-', '+')
('*', '-', '-')
('*', '-', '*')
('*', '-', '/')
('*', '*', '+')
('*', '*', '-')
('*', '*', '*')
('*', '*', '/')
('*', '/', '+')
('*', '/', '-')
('*', '/', '*')
('*', '/', '/')
('/', '+', '+')
('/', '+', '-')
('/', '+', '*')
('/', '+', '/')
('/', '-', '+')
('/', '-', '-')
('/', '-', '*')
('/', '-', '/')
('/', '*', '+')
('/', '*', '-')
('/', '*', '*')
('/', '*', '/')
('/', '/', '+')
('/', '/', '-')
('/', '/', '*')
('/', '/', '/')

2.3 Brackets

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 ）.

1. N # N # N # N
2. (N # N ) # N # N
3. N # N # (N # N)
4. N # (N # N) # N
5. (N # N) # (N # N)
6. (N # N # N) # N
7. ((N # N) # N) # N
8. (N # (N # N)) # N
9. N # (N # N # N)
10. N # ((N # N) # N)
11. N # (N # (N # N))

2.4 Calculation

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\times 64\times 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 .

3. answer

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 .