CODEWITHSUNDEEP
javascriptrecursion
Gragh
Gragh

Reputation: 39

Why does this recursive function skip numbers?

I'm trying to find the various possibilities to equal 100 with digits 1-9. This function produces the desired results, but also others which I had not intended. The other results add up to 100, but without some of these digits, like leaving out 3 or 6. Why are these other results included? 

    var nums = [1, 2, 3, 4, 5, 6, 7, 8, 9];
    var signs = ["+", "-", "N"];
    var results = [];
    find100("1");
    function find100(expr) {
       if (eval(expr.replace(/N/g, "")) === 100) {
          results.push(expr);
       } else {
          for (var i = eval(expr.substring(expr.length - 1, expr.length)) + 1; i <=    
          nums.length; i++) {
             signs.forEach(function(sign) {
                var expr2 = expr;
                find100(expr2 += sign + i);
             });
          }
       }
    }

Desired output: 

1+2+3-4+5+6+78+9, 
1+2+34-5+67-8+9, 
1+23-4+5+6+78-9, 
1+23-4+56+7+8+9, 
12+3+4+5-6-7+89, 
12+3-4+5+67+8+9, 
12-3-4+5-6+7+89, 
123+4-5+67-89, 
123+45-67+8-9, 
123-4-5-6-7+8-9, 
123-45-67+89

Upvotes: 1

Views: 204

Answers (2)

trincot
trincot

Reputation: 350345

The reason that some digits are skipped is in this loop:

for (var i = eval(expr.substring(expr.length - 1, expr.length)) + 1; i <=    
      nums.length; i++) {

On the second iteration it will increment that last digit in the expression, which will therefore create a gap in the continued recursion. In short, that loop should not be there.

I would suggest a solution without using eval, not because it would be somehow dangerous, but because it is responsible for a major performance hit.

Instead you could keep a numerical variable updated to what the expression represents. In fact, I suggest to use two such variables, one for the sum of the previous terms, and another for the last term, because that one might need to still be extended with more digits.

To facilitate the different way the signs influence the expression, I have defined a function per sign: it takes the above mentioned numerical values, and also the last digit, and returns the updated values.

Here is a working snippet (ES6 syntax) using that idea, and you'll notice the dramatic performance improvement:

function find100(digits, signs) {
    const loop = (expr, i, [sum, value]) =>
        // Not yet all digits used?
        i < digits.length ?
            // Apply each of the signs in turn:
            Object.keys(signs).reduce( (results, sign) =>
                // Recurse, passing on the modified expression, the sum of the 
                // preceding terms, and the value of the last term. As '+' is
                // not any different than '' before the first digit, skip '+':
                sign != '+' || i ?
                    results.concat(loop(expr+sign+digits[i], i+1, 
                                        signs[sign](sum, value, digits[i]))) :
                    results,
                [] ) :
        // All digits were used. Did it match?
        sum+value == 100 ? [expr] : [];
    // Start recursion
    return loop('', 0, [0, 0]); 
}

var nums = [1, 2, 3, 4, 5, 6, 7, 8, 9];
// define how each sign should modify the expression value:
var signs = {
    '+': (sum, value, digit) => [sum+value, digit],
    '-': (sum, value, digit) => [sum+value, -digit],
    '' : (sum, value, digit) => [sum, value*10 + (value<0 ? -digit : digit)]
};
var results = find100(nums, signs);

console.log(results);

Note that this also outputs the following expression:

-1+2-3+4+5+6+78+9

This is because the code also tries the signs before the first digit. I thought it would be relevant to have this also included in the output.

Upvotes: 1

Tibrogargan
Tibrogargan

Reputation: 4603

It's adding undesired results because your first loop iterates through each of the remaining numbers and adds ANY results that evaluate to 100, even if it has skipped a number to do so. If the method finds a solution for a number it adds the solution to results - which is correct, however if it doesn't find a solution it moves onto the next number anyway. This is the source of the skipped numbers. If there was no solution for a number it should have not continued to the next number.

As to how to fix it, that's a different question (but why not ...)

The difference here is that you can ONLY get a result if for any number there exists an expression that uses all remaining numbers.

var results = [];
var operations = [ "+", "-", "" ];
var expected = 100;
var limit = 10;

function findExpression(expr, next) {
    if (next === limit) {
        eval(expr) === expected && results.push(expr);
    } else {
        operations.forEach(function(operation) {
            findExpression(expr + operation + next, next + 1);
        });
    }
}

$(document).ready(function() {
    findExpression("1", 2);
    for(var i=0; i<results.length; i++) {
        $("#foo").append(results[i]+"<br />");
    }
});
<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.12.0/jquery.min.js"></script>
<body>
<div id="foo"></div>
</body>

Upvotes: 2

Related Questions