5 numbers equal 23

Question

How can I check whether 5 given numbers and mathematical operations (+, -, *)could be arranged to get the result of 23?

For instance:

1 1 1 1 1 –– Impossible

1 2 3 4 5 –– Possible

Specifications:

All the operations have the same priority and performed from left to right (not in mathematically correct order).

Answer 1

While you can use brute force to try out every possible combination, i would suggest a slightly more elegant solution:

The last digit as well as multiplication is the key. If the result (23) isn't divisible by the last digit, then the last operator can't be "*". Then you can try out the same for the result +- the last digit, as it is either added or subtracted. Iterating backwards this way should save quite a few iterations.

Pseudo-Code Example:

var digits = [1, 2, 3, 4, 5];
var expected = 23;
var combinatoric =  function(digits, expected) {
    var result = false;
    var digit = digits[digits.length -1];
    var nDigits = digits.removeLast();
    // If we are at the last digit...
    if(nDigits.isEmpty() && Math.abs(digit) == Math.abs(expected)) {
        //Last digit must be added or substracted, as its the starting digit.
        result = true;
    } else if(!nDigits.isEmpty()) {
        //Only if divisible is "*" an option.
        if(expected % digit == 0) {
            if(combinatoric(nDigits, expected / digit) {
                result = true;
            }
        }
        // "+" and "-" are always options.
        if(combinatoric(nDigits, expected - digit) {
            result = true;
        }
        if(combinatoric(nDigits, expected + digit) {
            result = true;
        }
    }
    return result;
}

This approach saves at least a few iterations, as you dont try to multiply if it won't resolve to a natural number anyway. And by going backwards you can make this calculation recursive, as the modified expected result is passed on to every iteration.