Monday, 18 January 2016

Numbers Game - Part 4 - De-duplicate Mathematically Equivalent Expressions

In Part 3, I have completed the Numbers Game. The solveGame() function finds the shortest answer; the solveAllGames() function finds all possible solutions, if any.

There is an imperfection in solveAllGames(): it returns mathematically equivalent expressions. For example, 1+2 and 2+1 are equivalent, so we should only return one of them, not both. Therefore, in solveAllGames(), I need to check whether an equivalent expression already exists in solutions array before I append it to the array.

To check whether two expressions are mathematically equivalent is worthy of a PhD thesis and an entire math library to do. Fortunately, my problem at hand is a lot simpler since it only involves a tiny fraction of the whole mathematical expressions. Namely: my expressions are arithmetic ones only - involving only integers and four operators (+, -, *, /). By observation, I see that equivalent expressions have these properties:
  1. they evaluate into the same result
  2. they have the same list of integers
  3. they have the same list of operators
For example, consider these expressions: 2*(1+5), (5+1)*2. They both have the same three numbers: 1, 2 and 5; they both have the same operators: + and *. 

So it's simply a matter of adding the above checks to the expression before inserting into the solutions array as highlighted lines below. I cheated a little here - since I am comparing two arrays of integers/strings only, instead of checking for deep equality (or using Node.js Assert#deepEqual() or JSON.stringify()) I just used Array#toString() to compare the two strings.
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) {
     // check if equivalant expression already in solutions
     var found=false;
     for(var sol of solutions) {
      var e1=sol.replace(/\(|\)/g, '');
      var e2=expr.replace(/\(|\)/g, '');
      if(e1.length != e2.length)
       continue;
      if(e1.split(/(\+|\-|\*|\/)/).sort().toString()==e2.split(/(\+|\-|\*|\/)/).sort().toString()) { 
       found=true;
       break;
      }
       
     }
     if(!found)
      solutions.push(expr);
    }
   }
  } 
 }
 return solutions;
}



No comments: