帮助小胖计算24点。

问题描述

给定四个数,四个基本运算符+,-,*,/,计算二十四点。可以添加括号。

分析

对于具体的一组形如a op1 b op2 c op3 d的算式,其添加括号就相当于指定三个操作符的顺序。例如,(a op1 b) op2 (c op3 d)可看成先执行op1op3再执行op2
故理论上遍历4!种数字排列*(4*4*4)种操作符排列*3!种操作符调用顺序即可,实际代码中优化避免重复计算。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
const cal=(a,op,b)=>{
if(op==='+'){
return {
val:a.val+b.val,
exp:`(${a.exp}${op}${b.exp})`
}
}
else if(op==='-'){
return {
val:a.val-b.val,
exp:`(${a.exp}${op}${b.exp})`
}
}
else if(op==='*'){
return {
val:a.val*b.val,
exp:`(${a.exp}${op}${b.exp})`
}
}
else if(op==='/'){
return {
val:a.val/b.val,
exp:`(${a.exp}${op}${b.exp})`
}
}
else{
throw new Error('unknow op')
}
}

const schemeFrom=(a,opi,b,opj,c,opk,d)=>mode=>{
if(mode===123){
return cal(cal(cal(a,opi,b),opj,c),opk,d)
}
else if(mode===132){
return cal(cal(a,opi,b),opj,cal(c,opk,d))
}
else if(mode===213){
return cal(cal(a,opi,cal(b,opj,c)),opk,d)
}
else if(mode===231){
return cal(a,opi,cal(cal(b,opj,c),opk,d))
}
else if(mode===312){
return cal(cal(a,opi,b),opj,cal(c,opk,d))
}
else if(mode===321){
return cal(a,opi,cal(b,opj,cal(c,opk,d)))
}
else{
throw new Error('unknow mode')
}
}

const isAddOrSub=op=>op==='+'||op==='-'

const mode=(opi,opj,opk)=>{
let i=isAddOrSub(opi)?0:1
let j=isAddOrSub(opj)?0:1
let k=isAddOrSub(opk)?0:1
return [i,j,k].join('')
}

const mathEqual=(a,b)=>Math.abs(a-b)<1e-10

const solve=target=>{
return function*(a,b,c,d){
const ops=['+','-','*','/']
for(let i=0;i<4;i++){
for(let j=0;j<4;j++){
for(let k=0;k<4;k++){
let opi=ops[i]
let opj=ops[j]
let opk=ops[k]
let md=mode(opi,opj,opk)
let scheme
let schemeBy=schemeFrom({
val:a,
exp:a.toString()
},
opi,{
val:b,
exp:b.toString()
},
opj,{
val:c,
exp:c.toString()
},
opk,{
val:d,
exp:d.toString()
})
if(md==='001'||md==='110'){
scheme=schemeBy(123)
if(mathEqual(scheme.val,target)){
yield scheme
}
scheme=schemeBy(132)
if(mathEqual(scheme.val,target)){
yield scheme
}
scheme=schemeBy(231)
if(mathEqual(scheme.val,target)){
yield scheme
}
}
else if(md==='010'||md==='101'){
scheme=schemeBy(123)
if(mathEqual(scheme.val,target)){
yield scheme
}
scheme=schemeBy(132)
if(mathEqual(scheme.val,target)){
yield scheme
}
scheme=schemeBy(213)
if(mathEqual(scheme.val,target)){
yield scheme
}
scheme=schemeBy(321)
if(mathEqual(scheme.val,target)){
yield scheme
}
}
else if(md==='100'||md==='011'){
scheme=schemeBy(123)
if(mathEqual(scheme.val,target)){
yield scheme
}
scheme=schemeBy(213)
if(mathEqual(scheme.val,target)){
yield scheme
}
scheme=schemeBy(231)
if(mathEqual(scheme.val,target)){
yield scheme
}
}
else if(md==='111'||md==='000'){
scheme=schemeBy(123)
if(mathEqual(scheme.val,target)){
yield scheme
}
}
else{
throw Error('unknow mode')
}
}
}
}
}
}

const solveOneOrder=target=>(a,b,c,d)=>{
const schemeGenerator=solve(target)(a,b,c,d)
const one=schemeGenerator.next()
return one.done?-1:one.value
}

const solveAllOrder=target=>(a,b,c,d)=>{
const schemeGenerator=solve(target)(a,b,c,d)
const schemes=[]
for(let scheme of schemeGenerator){
schemes.push(scheme)
}
return schemes
}

const next_perm=arr=>{
if(arr.length===1){
return false
}
else{
let cp=arr.slice()
let l=cp.length-2
while(l && cp[l]>=cp[l+1]){
l--
}
if(cp[l]>=cp[l+1]){
return false
}
else{
let r=l+1
while(cp[r+1]>cp[l]){
r++
}
let t=cp[l]
cp[l]=cp[r]
cp[r]=t
let tail=cp.splice(l+1).reverse()
cp=cp.concat(tail)
}
return cp
}

}

const perm=arr=>{
let curr=arr.slice().sort((a,b)=>a-b)
let ret=[]
while(curr){
ret.push(curr)
curr=next_perm(curr)
}
return ret
}

const solveOneGenerator=target=>function*(a,b,c,d){
const perms=perm([a,b,c,d])
for(let currPerm of perms){
yield*solve(target)(...currPerm)
}
}

const solveOne=target=>(a,b,c,d)=>{
const schemeGenerator=solveOneGenerator(target)(a,b,c,d)
const one=schemeGenerator.next()
return one.done?-1:one.value
}

const solveAll=target=>(a,b,c,d)=>{
const perms=perm([a,b,c,d])
const allSchemes=perms.reduce((allS,currPerm)=>{
const currScheme=solveAllOrder(target)(...currPerm)
return allS.concat(currScheme)
},[])
return allSchemes
}

console.log(solveOne(24)(11,9,5,7))
/*
[ { val: 24, exp: '((5+7)*(11-9))' },
{ val: 24, exp: '((7+5)*(11-9))' },
{ val: 24, exp: '((11-9)*(5+7))' },
{ val: 24, exp: '((11-9)*(7+5))' } ]
*/