Find the minimum number of operations required to compute a number using a specified range of numbers

Question

Let me start with an example - I have a range of numbers from 1 to 9. And let's say the target number that I want is 29. In this case the minimum number of operations that are required would be (9*3)+2 = 2 operations. Similarly for 18 the minimum number of operations is 1 (9*2=18). I can use any of the 4 arithmetic operators - +, -, / and *.

How can I programmatically find out the minimum number of operations required? Thanks in advance for any help provided.

clarification: integers only, no decimals allowed mid-calculation. i.e. the following is not valid (from comments below): ((9/2) + 1) * 4 == 22 I must admit I didn't think about this thoroughly, but for my purpose it doesn't matter if decimal numbers appear mid-calculation. ((9/2) + 1) * 4 == 22 is valid. Sorry for the confusion.

Answer 1

For the special case where set Y = [1..9] and n > 0:

• n <= 9 : 0 operations
• n <=18 : 1 operation (+)
• otherwise : Remove any divisor found in Y. If this is not enough, do a recursion on the remainder for all offsets -9 .. +9. Offset 0 can be skipped as it has already been tried.

Notice how division is not needed in this case. For other Y this does not hold.

This algorithm is exponential in log(n). The exact analysis is a job for somebody with more knowledge about algebra than I.

For more speed, add pruning to eliminate some of the search for larger numbers.

Sample code:

def findop(n, maxlen=9999):
    # Return a short postfix list of numbers and operations

    # Simple solution to small numbers
    if n<=9: return [n]
    if n<=18: return [9,n-9,'+']

    # Find direct multiply
    x = divlist(n)
    if len(x) > 1:
        mults = len(x)-1
        x[-1:] = findop(x[-1], maxlen-2*mults)
        x.extend(['*'] * mults)
        return x

    shortest = 0

    for o in range(1,10) + range(-1,-10,-1):
        x = divlist(n-o)
        if len(x) == 1: continue
        mults = len(x)-1

        # We spent len(divlist) + mults + 2 fields for offset. 
        # The last number is expanded by the recursion, so it doesn't count. 
        recursion_maxlen = maxlen - len(x) - mults - 2 + 1

        if recursion_maxlen < 1: continue
        x[-1:] = findop(x[-1], recursion_maxlen)
        x.extend(['*'] * mults)
        if o > 0:
            x.extend([o, '+'])
        else:
            x.extend([-o, '-'])
        if shortest == 0 or len(x) < shortest:
            shortest = len(x)
            maxlen = shortest - 1
            solution = x[:]

    if shortest == 0:
        # Fake solution, it will be discarded
        return '#' * (maxlen+1)
    return solution

def divlist(n):
    l = []
    for d in range(9,1,-1):
        while n%d == 0:
            l.append(d)
            n = n/d
    if n>1: l.append(n)
    return l

Answer 2

The basic idea is to test all possibilities with k operations, for k starting from 0. Imagine you create a tree of height k that branches for every possible new operation with operand (4*9 branches per level). You need to traverse and evaluate the leaves of the tree for each k before moving to the next k.

I didn't test this pseudo-code:

for every k from 0 to infinity
  for every n from 1 to 9
    if compute(n,0,k):
      return k


boolean compute(n,j,k):
  if (j == k):
    return (n == target)
  else:
    for each operator in {+,-,*,/}:
       for every i from 1 to 9:
         if compute((n operator i),j+1,k):
           return true
    return false

It doesn't take into account arithmetic operators precedence and braces, that would require some rework.

Answer 3

Really cool question :)

Notice that you can start from the end! From your example (9*3)+2 = 29 is equivalent to saying (29-2)/3=9. That way we can avoid the double loop in cyborg's answer. This suggests the following algorithm for set Y and result r:

nextleaves = {r}
nops = 0
while(true):
   nops = nops+1
   leaves = nextleaves
   nextleaves = {}
   for leaf in leaves:
      for y in Y:
         if (leaf+y) or (leaf-y) or (leaf*y) or (leaf/y) is in X:
             return(nops)
         else:
             add (leaf+y) and (leaf-y) and (leaf*y) and (leaf/y) to nextleaves

This is the basic idea, performance can be certainly be improved, for instance by avoiding "backtracks", such as r+a-a or r*a*b/a.

Answer 4

I guess my idea is similar to the one of Peer Sommerlund:

For big numbers, you advance fast, by multiplication with big ciphers.

Is Y=29 prime? If not, divide it by the maximum divider of (2 to 9). Else you could subtract a number, to reach a dividable number. 27 is fine, since it is dividable by 9, so

(29-2)/9=3 => 
3*9+2 = 29 

So maybe - I didn't think about this to the end: Search the next divisible by 9 number below Y. If you don't reach a number which is a digit, repeat.

The formula is the steps reversed.

(I'll try it for some numbers. :) )

I tried with 2551, which is

echo $((((3*9+4)*9+4)*9+4))

But I didn't test every intermediate result whether it is prime. But

echo $((8*8*8*5-9)) 

is 2 operations less. Maybe I can investigate this later.