A couple days ago, when watching the Letters and Numbers show on SBS, I used my Javascript program to check some of the numbers games. To my embarrassment, I found a serious flaw in my algorithm - the
Looking at an array of numbers - e.g. [n1, n2, n3, n4, n5, n6], they can be broken down to left and right sub-arrays using various lengths combinations - e.g. 2 elements in array 1, 4 elements in array 2; 3 elements each;, etc. So it's a matter of iterating the different array lengths to generate all possible 'brackets' scenarios.
This function generates all possible expressions with different brackets groups. It returns an array of expressions in the form of strings. So in order to check which expressions have the right answer I would have to use
checkNumbers() function only checks expressions that are strictly from left to right - i.e. it does not cover scenarios like '(a+b)*(c-d)'. Notice that the calculation is not strictly left to right due to the brackets. So today, I set out to fix the problem.Looking at an array of numbers - e.g. [n1, n2, n3, n4, n5, n6], they can be broken down to left and right sub-arrays using various lengths combinations - e.g. 2 elements in array 1, 4 elements in array 2; 3 elements each;, etc. So it's a matter of iterating the different array lengths to generate all possible 'brackets' scenarios.
function genExprs(numbers) {
var len=numbers.length, exprs=[];
if(len==1)
exprs.push(numbers[0]);
else if(len==2) {
var n1=numbers[0], n2=numbers[1];
exprs.push('('+n1+'+'+n2+')');
exprs.push('('+n1+'-'+n2+')');
exprs.push('('+n1+'*'+n2+')');
if(n1/n2%1==0)
exprs.push('('+n1+'/'+n2+')');
} else {
len=numbers.length-1;
for(var i=2; i<=len; i++){
var left=genExprs(numbers.slice(0,i));
var right=genExprs(numbers.slice(i));
for(lexpr of left) {
for (rexpr of right) {
exprs.push('('+lexpr+'+'+rexpr+')');
exprs.push('('+lexpr+'-'+rexpr+')');
exprs.push('('+lexpr+'*'+rexpr+')');
var expr='('+lexpr+'/'+rexpr+')';
if(eval(expr)%1===0)
exprs.push(expr);
}
}
}
}
//console.log("genExprs returning: "+exprs);
return exprs;
}
This function generates all possible expressions with different brackets groups. It returns an array of expressions in the form of strings. So in order to check which expressions have the right answer I would have to use
eval() to evaluate each expression. Because eval() has to process strings, it makes it at least 10 times slower than calculating directly. To fix this, I need to return the expression string as well as the evaluation result of the expression. A JSON object with 2 fields will suffice - one to contain the expression string; the other to store the current answer (i.e. the evaluation) of the expression. An improved version of genExprs() was born.function genExprs2(numbers) {
var len=numbers.length, results=[];
if(len==1)
results.push({expr:numbers[0], currAnswer:numbers[0]});
else if(len==2) {
var n1=numbers[0], n2=numbers[1];
results.push({expr:'('+n1+'+'+n2+')', currAnswer: n1+n2});
results.push({expr:'('+n1+'-'+n2+')', currAnswer: n1-n2});
results.push({expr:'('+n1+'*'+n2+')', currAnswer: n1*n2});
var currAnswer=n1/n2;
if(currAnswer%1==0)
results.push({expr:'('+n1+'/'+n2+')', currAnswer: currAnswer});
} else {
len=numbers.length-1;
for(var i=2; i<=len; i++){
var left=genExprs2(numbers.slice(0,i));
var right=genExprs2(numbers.slice(i));
for(lexpr of left) {
for (rexpr of right) {
results.push({ expr:'('+lexpr.expr+'+'+rexpr.expr+')', currAnswer: lexpr.currAnswer+rexpr.currAnswer});
results.push({ expr:'('+lexpr.expr+'-'+rexpr.expr+')', currAnswer: lexpr.currAnswer-rexpr.currAnswer});
results.push({ expr:'('+lexpr.expr+'*'+rexpr.expr+')', currAnswer: lexpr.currAnswer*rexpr.currAnswer});
var currAnswer=lexpr.currAnswer/rexpr.currAnswer;
if(currAnswer%1===0)
results.push({ expr:'('+lexpr.expr+'/'+rexpr.expr+')', currAnswer: currAnswer});
}
}
}
}
//console.log("genExprs returning: "+exprs);
return results;
}
/*
* length of numbers array must be greater than 3
*/
function checkNumberArray(numbers, answer) {
var solutions=[];
if(numbers.length<4)
return checkNumbers(numbers.slice(1), answer, numbers[0], numbers[0]+'');
for(expr of genExprs2(numbers)) {
//console.log("expression="+expr);
var currAnswer=expr.currAnswer;
if(currAnswer===answer && !checkDup(solutions, expr.expr))
solutions.push(expr.expr.slice(1, expr.expr.length-1)); // strip the first (open) and last (close) brackets
}
//console.log("checkNumberArray solutions="+solutions);
return solutions;
}
eval() version took 50 seconds or more.See also:
No comments:
Post a Comment