Gragh Gragh - 2 months ago 9
Javascript Question

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

Answer

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>

Comments