11
\$\begingroup\$

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.

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. 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
Improve this question
\$\endgroup\$
12
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Feb 26, 2013 at 9:31
  • 3
    \$\begingroup\$ What kind of arithmetic is this to use – exact fractionals, integer (/ ≡ div), just floating-point and hope-for-no-rounding-errors, ...? \$\endgroup\$ Commented Feb 26, 2013 at 12:02
  • 4
    \$\begingroup\$ 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. \$\endgroup\$ Commented Feb 26, 2013 at 13:14
  • 1
    \$\begingroup\$ Related: stackoverflow.com/questions/3947937/… \$\endgroup\$ Commented Feb 27, 2013 at 11:51
  • 1
    \$\begingroup\$ 3rd test case is not False... 5+10+2*3+7*0+0... \$\endgroup\$ Commented Feb 27, 2013 at 18:36

1 Answer 1

Reset to default
3
\$\begingroup\$

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))), [])
Improve this answer
\$\endgroup\$
4
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Commented Feb 27, 2013 at 8:33
  • \$\begingroup\$ I've tried to test your solution with my 4rd testcase. After 2h, I stopped the execution. \$\endgroup\$ Commented Feb 27, 2013 at 10:52
  • \$\begingroup\$ @moose I'll try to add some heuristic to make it faster. But after that the code length may double. \$\endgroup\$ Commented Feb 27, 2013 at 13:46
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Jun 13, 2013 at 6:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.