# 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. Feb 26, 2013 at 9:31
• What kind of arithmetic is this to use – exact fractionals, integer (/div), just floating-point and hope-for-no-rounding-errors, ...? Feb 26, 2013 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. Feb 26, 2013 at 13:14
• Feb 27, 2013 at 11:51
• 3rd test case is not False... 5+10+2*3+7*0+0... Feb 27, 2013 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[0]):
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[0]
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[0]
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. Feb 27, 2013 at 8:33
• I've tried to test your solution with my 4rd testcase. After 2h, I stopped the execution. Feb 27, 2013 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, 2013 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. Jun 13, 2013 at 6:38