In Part 3, I have completed the Numbers Game. The

There is an imperfection in

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:

`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:

- they evaluate into the same result
- they have the same list of integers
- 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:

Post a Comment