Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

Task

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
share|improve this question
    
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
3  
What kind of arithmetic is this to use – exact fractionals, integer (/div), just floating-point and hope-for-no-rounding-errors, ...? –  leftaroundabout Feb 26 '13 at 12:02
3  
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
1  
Related: stackoverflow.com/questions/3947937/… –  belisarius Feb 27 '13 at 11:51
1  
3rd test case is not False... 5+10+2*3+7*0+0... –  Shmiddty Feb 27 '13 at 18:36

1 Answer 1

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))), [])
share|improve this answer
1  
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. –  moose Feb 27 '13 at 8:33
    
I've tried to test your solution with my 4rd testcase. After 2h, I stopped the execution. –  moose 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. –  moose Jun 13 '13 at 6:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.