# Generate a number by using a given list of numbers and arithmetic operators

You are given a list of numbers L = [17, 5, 9, 17, 59, 14], a bag of operators O = {+:7, -:3, *:5, /:1} and a number N = 569.

Output an equation that uses all numbers in L on the left-hand side and only the number N on the right-hand side. If this is not possible, output False. Example solution:

59*(17-5)-9*17+14 = 569


## Limitations and Clarification

• You may not concatenate numbers ([13,37] may not be used as 1337)
• Only natural numbers and zero will appear in L.
• The order in L doesn't matter.
• You must use all numbers in L.
• Only the operators +,-,*,/ will appear in O.
• O can have more operators than you need, but at least |L|-1 operators
• You may use each operator any number of times up to the value in O.
• All four operations in O are the standard mathematical operations; in particular, / is normal division with exact fractions.

## Points

• The less points, the better
• Every character of your code gives you one point

You have to provide an un-golfed version that is easy to read.

## Background

A similar question was asked on Stack Overflow. I thought it might be an interesting code-golf challenge.

## Computational Complexity

As Peter Taylor said in the comments, you can solve subset sum with this:

1. You have an instance of subset sum (hence a set S of integers and a number x)
2. L := S + [0, ..., 0] (|S| times a zero), N := x, O := {+:|S|-1, *: |S| - 1, /:0, -: 0}
3. Now solve this instance of my problem
4. The solution for subset sum is the numbers of S that don't get multiplied with zero.

If you find an Algorithm that is better than O(2^n), you prove that P=NP. As P vs NP is a Millennium Prize Problem and hence worth 1,000,000 US-Dollar, it is very unlikely that somebody finds a solution for this. So I removed this part of the ranking.

## Test cases

The following are not the only valid answers, other solutions exist, and are permitted:

• ([17,5,9,17,59,14], {+:7, -:3, *:5, /:1}, 569)
=> 59 * (17-5)- 9 * 17 + 14 = 569
• ([2,2], {'+':3, '-':3, '*':3, '/':3}, 1)
=> 2/2 = 1
• ([2,3,5,7,10,0,0,0,0,0,0,0], {'+':20, '-':20, '*':20, '/':20}, 16)
=> 5+10-2*3+7+0+0+0+0+0+0+0 = 16
• ([2,3,5,7,10,0,0,0,0,0,0,0], {'+':20, '-':20, '*':20, '/':20}, 15)
=> 5+10+0*(2+3+7)+0+0+0+0+0+0 = 15
• Is m = |L|? If yes, how can you expect the runtime to not depend on the size of that list? For example, [2,2],[+,+,...,+,/],1. In fact, since n is O(m), you might just write it all in terms of m. – boothby Feb 26 '13 at 9:31
• What kind of arithmetic is this to use – exact fractionals, integer (/div), just floating-point and hope-for-no-rounding-errors, ...? – ceased to turn counterclockwis Feb 26 '13 at 12:02
• Why the complicated scoring rules for computational complexity? There's an easy reduction from subset-sum, so anything better than O(2^n) is worth a million USD. – Peter Taylor Feb 26 '13 at 13:14
• – Dr. belisarius Feb 27 '13 at 11:51
• 3rd test case is not False... 5+10+2*3+7*0+0... – Shmiddty Feb 27 '13 at 18:36

# Python 2.7 / 478 chars

L=[17,5,9,17,59,14]
O={'+':7,'-':3,'*':5,'/':1}
N=569
P=eval("{'+l+y,'-l-y,'*l*y,'/l/y}".replace('l',"':lambda x,y:x"))
def S(R,T):
if len(T)>1:
c,d=y=T.pop();a,b=x=T.pop()
for o in O:
if O[o]>0 and(o!='/'or y):
T+=[(P[o](a, c),'('+b+o+d+')')];O[o]-=1
if S(R,T):return 1
O[o]+=1;T.pop()
T+=[x,y]
elif not R:
v,r=T
if v==N:print r
return v==N
for x in R[:]:
R.remove(x);T+=[x]
if S(R,T):return 1
T.pop();R+=[x]
S([(x,x)for x in L],[])


The main idea is to use postfix form of an expression to search. For example, 2*(3+4) in postfix form will be 234+*. So the problem become finding a partly permutation of L+O that evalates to N.

The following version is the ungolfed version. The stack stk looks like [(5, '5'), (2, '5-3', (10, ((4+2)+(2*(4/2))))].

L = [17, 5, 9, 17, 59, 14]
O = {'+':7, '-':3, '*':5, '/':1}
N = 569

P = {'+':lambda x,y:x+y,
'-':lambda x,y:x-y,
'*':lambda x,y:x*y,
'/':lambda x,y:x/y}

def postfix_search(rest, stk):
if len(stk) >= 2:
y = (v2, r2) = stk.pop()
x = (v1, r1) = stk.pop()
for opr in O:
if O[opr] > 0 and not (opr == '/' and v2 == 0):
stk += [(P[opr](v1, v2), '('+r1+opr+r2+')')]
O[opr] -= 1
if postfix_search(rest, stk): return 1
O[opr] += 1
stk.pop()
stk += [x, y]
elif not rest:
v, r = stk
if v == N: print(r)
return v == N
for x in list(rest):
rest.remove(x)
stk += [x]
if postfix_search(rest, stk):
return True
stk.pop()
rest += [x]
postfix_search(list(zip(L, map(str, L))), [])

• Wow, that's shorter than I've expected. I have scribbled an algorithm which included a conversion postfix<=>infix, but my scribble wasn't much shorter than your implementation. Impressing. And thanks for the construction P[opr](v1, v2). I never thought of combining lambdas and dictionaries like this, although it seems obvious now. – Martin Thoma Feb 27 '13 at 8:33
• I've tried to test your solution with my 4rd testcase. After 2h, I stopped the execution. – Martin Thoma Feb 27 '13 at 10:52
• @moose I'll try to add some heuristic to make it faster. But after that the code length may double. – Ray Feb 27 '13 at 13:46
• Using Fraction like I did here fixes a problem in your answer. Just try it for the given instance on the link I've provided. Your current code doesn't find an answer, but when you use fraction it does. – Martin Thoma Jun 13 '13 at 6:38