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.

Note that this algorithm is flawed:

• it results in false positives: (25-5)+((75+50)+5)*7 and (((7+75)-50)+5)*25+5
• it results in false negatives: 5-(2-1) and 5-2+1

Alas, but it's still better than having too many duplicates in the result.

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;
}