Algorithm for placing plus and minus signs between digits so that the result is 100

Yesterday I found the following programming problem:
Write a program that outputs all possibilities to put + or – or nothing between the numbers 1,2,…,9 (in this order) such that the result is 100.

This problem has 11 solutions and they are demonstrated here: Fun with numbers: place plus/minus signs between the digits.
1 + 2 + 34 – 5 + 67 – 8 + 9 = 100
12 + 3 – 4 + 5 + 67 + 8 + 9 = 100
123 – 4 – 5 – 6 – 7 + 8 – 9 = 100
123 + 4 – 5 + 67 – 89 = 100
123 + 45 – 67 + 8 – 9 = 100
123 – 45 – 67 + 89 = 100
12 – 3 – 4 + 5 – 6 + 7 + 89 = 100
12 + 3 + 4 + 5 – 6 – 7 + 89 = 100
1 + 23 – 4 + 5 + 6 + 78 – 9 = 100
1 + 23 – 4 + 56 + 7 + 8 + 9 = 100
1 + 2 + 3 – 4 + 5 + 6 + 78 + 9 = 100

But the page in the link provides only answers without an algorithm, that’s why I decided to write it myself.

At first let’s simplify the problem and use only ‘+’ and ‘-‘ operations, without concatenation of numbers. Then we will have some kind of a tree with 2 branches for each node, the left branch is ‘+’ operation, the right branch is ‘-‘ operation. For numbers [1 2 3 4] and sum=6 the tree will look like this:

tree_for_1234

Then we should modify the algorithm so that besides ‘+’ and ‘-‘ we can put ‘nothing’ between numbers. We will have the tree above, but with 3 child nodes for each node instead of 2. Also the ‘nothing’ operator will build slightly different nodes. Here is their comparison:

  • ‘+’ operator: [1 2 3 4] sum 100 -> [2 3 4] sum 99
  • ‘-‘ operator: [1 2 3 4] sum 100 -> [-2 3 4] sum 99
  • ‘nothing’ operator: [1 2 3 4] sum 100 -> [12 3 4] sum 100

For the ‘+’ operator we call “findPaths(99, 2, index+1)”, for nothing operator we will call “findPaths(100, 12, index+1)”. Here is the updated algorithm:

var digits = [1,2,3,4,5,6,7,8,9];
var searchSum = 100;

function concatPrefix(prefix, paths) {
    return paths
        .filter(function(p) { return p.length > 0; })
        .map(function(p) { return prefix.concat(p); });
}

function findPaths(sum, previousNumber, index) {
    var previousDigit = Math.abs(previousNumber%10);
    if (index >= digits.length) {
        return sum == previousNumber ? [[previousDigit]] : [];
    }
    
    var currentDigit = digits[index];
    var concatenatedNumber = previousNumber >= 0 ? 10*previousNumber + currentDigit : 10*previousNumber - currentDigit;
 
    var plusPaths = findPaths(sum-previousNumber, currentDigit, index+1);
    var minusPaths = findPaths(sum-previousNumber, -currentDigit, index+1);
    var concatPaths = findPaths(sum, concatenatedNumber, index+1);
    
    var paths = [];
    Array.prototype.push.apply(paths, concatPrefix([previousDigit, '+'], plusPaths));
    Array.prototype.push.apply(paths, concatPrefix([previousDigit, '-'], minusPaths));
    Array.prototype.push.apply(paths, concatPrefix([previousDigit, '&'], concatPaths));
    return paths;
}

var foundPaths = findPaths(searchSum, digits[0], 1);

if (foundPaths.length == 0) {
    console.log("no paths were found");
} else {
    for (var i = 0; i < foundPaths.length; i++) {
        console.log(foundPaths[i].join("").replace(/&/g, ""));
    }
}

Also there is another algorithm: to generate an array with all possible combinations, then parse each row and check its sum.
It is quite slower, but it is more generic and can work for other operations:

var numbers = [1,2,3,4,5,6,7,8,9];
var sum = 100;
var signs = ['+', '-', '&'];
var numbersInnerLength = numbers.length-1;
var cLength = Math.pow(signs.length, numbersInnerLength);
var combinations = [];

for (var i = 0; i < cLength; i++) {
    var newArray = [];
    for (var j = 0; j < numbers.length; j++) {
        newArray[j*2] = numbers[j];
    }
    combinations.push(newArray);
    
}

for (var k = 0; k < numbersInnerLength; k++) {
    var periodLength = cLength / Math.pow(signs.length, k+1);
    var signIndex = 0;
    for (var i = 0; i < cLength; i+=periodLength) {
        for (var j = 0; j < periodLength && i+j < cLength; j++) {
            combinations[i+j][k*2+1] = signs[signIndex];
        }
        signIndex = (signIndex+1)%signs.length;
    }
}

for (var i = 0; i < combinations.length; i++) {
    var combination = combinations[i];
    var cstr = combination.join("").replace(/&/g, "");
    if (eval(cstr) == sum) {
        console.log(cstr);
    }
}

Recursion algorithm example on jsFiddle: http://jsfiddle.net/2CxQC/
Eval algorithm example: http://jsfiddle.net/ek3p2/

This algorithm has a high complexity and requires 3^8 (=6561) comparisons. But I can’t find a better algorithm so checking all combinations seems to be the best way to solve it.

Advertisements

One Response to Algorithm for placing plus and minus signs between digits so that the result is 100

  1. Darren says:

    Hello. What language did you use for this programs?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: