Given an array of number, how to calculate to a target value

algorithmsdynamic programming

Chatting with a friend about a game we used to play, and thinking how to implement it in code.

Here are the rules:

Given a list of number e.g. {1,2,3,4}
Try to use all the numbers from the list to perform +,-,*,/ operations to reach a target number (e.g. 2).
The numbers can be used only once, the operators can be used more than once.

So one solution would be (1+3)*2/4 = 2

Any ideas for an algorithm to get at the answer(s)?

Best Answer

The easiest way is brute force. Generate all the ways to order the numbers and apply the operators, then see if any matches the target value. This will scale very badly, but can be improved with heuristics.

Using your example, we can notice that we only need to try division when it will come out to an integer (assuming you don't mean / as truncating integer division). So when we start with 3, we don't need to try dividing by anything but 1.

Memoization could also help, but unless you're planning on a large list of targets or expensive operations it probably won't be worth it. If you do go with memoization, I would recommend thinking carefully about what you expect to repeat. If the same target can come up many times, memoizing target => (numbers, operators) would make sense. If the numbers can be repeated, you could try memoizing each operator, (operator, operands) => value. Either way, I would profile any options here before making a decision.

Also, if your language has any way to reference functions (closures, function pointers, functors) it will probably be clearest to use those for the operators. Definitely avoid string parsing or evaling expressions.

Some ruby-ish pseudocode:

numbers = [1, 2, 3, 4]
operators = [+, -, *, /]
target = 2

numbers.permutation(4).each do |p|
  operators.permutation(3).each do |o|
    x = o[0](p[0], p[1])
    x = o[1](x, p[2])
    x = o[2](x, p[3])
    if (x == target)
      return p, o
    end
  end
end
Related Topic