Modify a given number to find the required sum?

Question

A friend of mine sent me this question. I haven't really been able to come up with any kind of algorithm to solve this problem.

You are provided with a no. say 123456789 and two operators * and +. Now without changing the sequence of the provided no. and using these operators as many times as you wish, evaluate the given value:

eg: given value 2097
Solution: 1+2+345*6+7+8+9

Any ideas on how to approach problems like these?

Answer 1

One of the easiest ways to do it is using shell expansion in BASH:

#!/bin/sh

for i in 1{,+,*}2{,+,*}3{,+,*}4{,+,*}5{,+,*}6{,+,*}7{,+,*}8{,+,*}9; do
    if [ $(( $i )) == 2097 ]; then
        echo $i = 2097
    fi
done

which gives:

$ sh -c '. ./testequation.sh'
12*34+5*6*7*8+9 = 2097
12*3*45+6*78+9 = 2097
1+2+345*6+7+8+9 = 2097

Answer 2

There are not that many solutions - this python program takes under a second to bruteforce them all

from itertools import product

for q in product(("","+","*"), repeat=8):
    e = ''.join(i+j for i,j in zip('12345678',q))+'9'
    print e,'=',eval(e)

Here is a sample run through grep

$ python sums.py | grep 2097
12*34+5*6*7*8+9 = 2097
12*3*45+6*78+9 = 2097
1+2+345*6+7+8+9 = 2097

General solution is a simple modification

from itertools import product

def f(seq):
    for q in product(("","+","*"), repeat=len(seq)-1):
        e = ''.join(i+j for i,j in zip(seq[:-1],q))+seq[-1]
        print e,'=',eval(e)