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

You have a list of numbers `L = [17, 5, 9, 17, 59, 14]`, a dictionary 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.

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

## Limitations and Clarification

• You may not concatinate 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 have to 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 take each operator a number of times equal to its value in `O`.
• All four operations in `O` are the basic operations you know from math. Especially `/` 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 StackOverflow. I thought it might be an interesting codegolf-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 subsetsum is the numbers of S that don't get multiplied with zero.

When you would find an Algorithm that is better than O(2^n), you would 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.

## Testcases

• ([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
• ([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
-
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[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. – 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