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

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: