Sunday 17 January 2016

Numbers Game - Part 3 - Putting Things Right

Continuing from Part 2.

I am really unhappy about how the operators are generated as shown in part 2 because the algorithm is not well thought through and the performance is terrible. So following Agile principle of Continuous attention to technical excellence and good design, I decided to rewrite this part.

This time, instead of generating all the possible operators combinations and permutations up front, I do it on the fly when processing each numbers array.
/*
 * generate and test nums array using all possible operators 
 * returns either -1 (no solution) or expression string
 * For example, to check numbers [n1, n2, n3, n4] against answer a,
 * pass the parameters as so:
 * checkNumbers([n2, n3, n4], a, n1, 'n1');
 */
function checkNumbers(nums, answer, currAnswer, currExpr) {
 var length=nums.length, num=nums[0], tail=nums.slice(1);

 if(length<1) return -1;
  
 if(length==1){
  if(currExpr.length==0)
   return num;
  // else
  if((currAnswer+num)===answer) {
   return currExpr+'+'+num;
  } else if ((currAnswer-num)===answer) {
   return currExpr+'-'+num;
  } else if ((currAnswer*num)===answer) {
   return currExpr+'*'+num;
  } else if ((currAnswer/num)===answer) {
   return currExpr+'/'+num;
  } else
   return -1;
 } 
 // try +, -, *, / one by one
 // could use eval() but chose not to due to performance concern
 var a=currAnswer+num
 if(a===answer)
  return currExpr+'+'+num;
 else {
  var result = checkNumbers(tail, answer, a, '('+currExpr+'+'+num+')');
  if(result!=-1)
   return result;
 }
 
 a=currAnswer-num; 
 if(a===answer)
  return currExpr+'-'+num;
 else {
  var result = checkNumbers(tail, answer, a, '('+currExpr+'-'+num+')');
  if(result!=-1)
   return result;
 }
 
 a=currAnswer*num;
 if(a===answer)
  return currExpr+'*'+num;
 else {
  var result = checkNumbers(tail, answer, a, currExpr+'*'+num);
  if(result!=-1)
   return result;
 }

 a=currAnswer/num;
 if(a%1 !=0)
  return -1;
 if(a===answer)
  return currExpr+'/'+num;
 else {
  var result = checkNumbers(tail, answer, a, currExpr+'/'+num);
  if(result!=-1)
   return result;
 }
 return -1;
}
Now the solveGame() becomes:
function solveGame (nums, answer) {
 if(nums.indexOf(answer)>0)
  return answer;
 if(nums.length<2)
  return -1;

 for(var i=2; i<=nums.length; i++) {
  var numbers=k_combinations(nums, i);
  for(var n of numbers) {
   var permus=permutations(n);
   for(var p of permus) {
    var expr=checkNumbers(p.slice(1), answer, p[0], ''+p[0]);
    if(expr!=-1) {
     console.log("Solved: "+expr);
     return expr;
    }
   }
  } 
 }
 console.log("Problem has no solution.")
 return -1;
}

To find all possible solutions:
function solveAllGames (nums, answer) {
 var solutions=[];
 if(nums.indexOf(answer)>0)
  solutions.push(answer);
 else if(nums.length<2)
  return [];

 for(var i=2; i<=nums.length; i++) {
  var numbers=k_combinations(nums, i);
  for(var n of numbers) {
   var permus=permutations(n);
   for(var p of permus) {
    var expr=checkNumbers(p.slice(1), answer, p[0], ''+p[0]);
    if(expr!=-1) {
     solutions.push(expr);
    }
   }
  } 
 }
 return solutions;
}
An unsolvable game (i.e. traversing all possible combinations and permutations of all numbers of all sizes using all operators) used to take about 12 seconds on V8 now takes 250ms:

c:\temp>node numsGame.js
Sun Jan 17 2016 15:23:47 GMT+1100 (AUS Eastern Daylight Time)
solving [75,25,100,50,10,10] targetting 883
Problem has no solution.
-1
Sun Jan 17 2016 15:23:48 GMT+1100 (AUS Eastern Daylight Time)
Duration: 250ms

No comments: