Numbers Game - Part 1 - The Journey Begins

I am a fan of the Letters and Numbers game on SBS channel of Australian TV. So today I decided to try and write a javascript program to solve the games. To keep the program simple, brute force is the way to go!

Letters games should be easy. It's just a matter of generating all the combinations and permutations of the nine letters and check against a work list from MacQuarie dictionary. So I will leave this to a later date.

The numbers game is a lot trickier. The orthodox way would be to generate binary trees and put numbers into the tree leaves in different permutations. The non-leaf nodes of the tree would be permutations of five operators: plus, minus, multiply, divide and null operator (since not all numbers have to be used to get to the answer).

So the numbers game is reduced to the following main problems:

1. generate all combinations of the numbers to be put into the tree
2. generate all combinations of the operators to be put into the tree
3. evaluate the generated tree

However, I feel that implementing binary trees and arithmetic operators for such a small program are too much effort. So I decided to use arrays instead and take the lazy way out... I mean the Agile way by following one of the principles: Simplicity--the art of maximizing the amount of work not done--is essential.

1. generate all combinations and permutations of the numbers (which are non-repeatable) into arrays of different sizes (from 2 to 6) - e.g. [n1, n2], [n2, n1], [n1, n3]...[n1, n2, n3, n4, n5] and permutate each of them
2. generate all combinations and permutations of the operators (which are repeatable) into arrays of different sizes (from 1 to 5) - e.g. ['+'], ['-'], ['*'], ['/'], ['+', '+'], ['+', '-'], ... ['/', '/', '/', '/', '/']
3. walk-through all the number arrays and for each weave with the operators array of the correct size - e.g. [n1, n2] combined with ['+'], ['-'], ['*'], ['/'] to produce strings: n1+n2, n1-n2, n1*n2, n1/n2, ...
4. use eval() to evaluate the generated arithmetic expression strings and check against the answer until matched.

There is a rule in the numbers game saying that throughout all the steps of the calculation, no fractions are allowed. For example, to get 431 from [75, 25, 50, 100, 8, 2]:

Arithmetically (75/100+50)*8+25=431. However, this is not a correct answer in the game because the step 75/100 produces fraction.

Generating Numbers List

Basically, from the array of 6 integers, say [5,6,7,8,9,0], I need to generate all its combinations into arrays of size 2, 3, 4, 5, 6:

• size 2 (with 15(=6! / (2! (6-4)!)) combinations): [[5,6],[5,7],[5,8],[5,9],[5,0],[6,7],[6,8],[6,9],[6,0],[7,8],[7,9],[7,0],[8,9],[8,0],[9,0]]
• size 3 (with 20(=6! / (3! (6-3)!)) combinations): [[5,6,7],[5,6,8],[5,6,9],[5,6,0],[5,7,8],[5,7,9],[5,7,0],[5,8,9],[5,8,0],[5,9,0],[6,7,8],[6,7,9],[6,7,0],[6,8,9],[6,8,0],[6,9,0],[7,8,9],[7,8,0],[7,9,0],[8,9,0]]
• size 4 (with 15(=6!/(4! (6-4)!)) combinations): [[5,6,7,8],[5,6,7,9],[5,6,7,0],[5,6,8,9],[5,6,8,0],[5,6,9,0],[5,7,8,9],[5,7,8,0],[5,7,9,0],[5,8,9,0],[6,7,8,9],[6,7,8,0],[6,7,9,0],[6,8,9,0],[7,8,9,0]] 
• size 5 (with 6(=6!/(5! (6-5)!)) combinations): [[5,6,7,8,9],[5,6,7,8,0],[5,6,7,9,0],[5,6,8,9,0],[5,7,8,9,0],[6,7,8,9,0]]

For each of the above arrays, we can try putting different operators between each two numbers and compute them. Note that each array also needs to be permutated - e.g. [5,6] becomes [5,6] and [6,5] so that we can try 5-6, as well as 6-5, and so on.

There is a nice little Javascript that generates combinations and k-combinations found here.
There are also plenty of permutations code, I prefer this one from crl:

function permutations(xs){
 var r=[];
 if (!xs.length)
  return [[]];
 for (var i=0;i<xs.length;i++){
  var xs_ = xs.slice();
  var x = xs_.splice(i, 1);
  var ps = permutations(xs_);
  r.splice(r.length, 0,...ps.map(psi=>x.concat(psi)))
 }
 return r;
}

So with the combinations(), k_combinations() and permutations() functions, I am well on my way to process the numbers.

Now I must stop as Letters and Numbers show is on right now! Stay tuned for Part 2.