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:

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:

- generate all combinations of the numbers to be put into the tree
- generate all combinations of the operators to be put into the tree
- 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*.- 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
- generate all combinations and permutations of the operators (which are repeatable) into arrays of different sizes (from 1 to 5) - e.g. ['+'], ['-'], ['*'], ['/'], ['+', '+'], ['+', '-'], ... ['/', '/', '/', '/', '/']
- 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, ...
- 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:

So with the

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

- 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

There are also plenty of permutations code, I prefer this one from crl:

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

## No comments:

Post a Comment