## October 13, 2004

### TechTip: Google Labs Aptitude Test (GLAT)

Yesterday we reduced the number of possible solutions from 1,000,000,000 to 3,628,800. Today we are going to further restrict the solution set by adding the individual equations from the formula. Each of these need to be added to the outermost loop which contains all of the variables involved.

If we start on the right, we have T/E/M and we know (from algebra) that there are two possibilities, either: `(T - E) = M` because T is larger than E or: `(10 + T - E) = M` when T is smaller than E. This limitation is placed just inside the T loop after the 'not identical' test we created last time. The T loop now looks like this:

```
...

foreach \$T (@Values)

{

next if \$T == \$O or \$T == \$M

or \$T == \$L or \$T == \$G

or \$T == \$E or \$T == \$D

or \$T == \$C ;

next unless ((\$T - \$E) == \$M)

or ((10 + \$T - \$E) == \$M) ;

foreach \$W (@Values)

{

...

```

Out of interest, this rule alone chops the number of possible solutions by an order of magnitude:

`\$ time perl ./glat3.pl`

``` There were 362880 solutions real 0m36.330s user 0m14.558s sys 0m0.270s ```

The next equation is a bit more complicated and it is worth noting that this first pass is deliberately simplified. The base equation is `O - L = O` and there are four variations to consider which we can code like this:

```
...

foreach \$O (@Values)

{

next if \$O == \$M or \$O == \$L or \$O == \$G

or \$O == \$E or \$O == \$D or \$O == \$C ;

next unless ((\$O - \$L) == \$O) or

((10 + \$O - \$L) == \$O) or

((\$O - \$L) - 1 == \$O) or

((10 + \$O - \$L) - 1 == \$O) ;

foreach \$T (@Values)

{

...

```

Interestingly, even though this option is not quite right, it has the desired effect and reduces the number of options:

`\$ time perl ./glat3.pl`

``` There were 80640 solutions real 0m12.120s user 0m5.964s sys 0m0.105s ```

Now we do the same for `D - G = C` (17,280 solutions), `W - O = T` (3,460) `W - O = O` (360) and finally `W - G = D`. Note that this last equation only has two choices, not four because there is no longer any 'borrow' option. The resulting code now gives us:

`\$ time perl ./glat3.pl`

``` There were 30 solutions real 0m2.527s user 0m1.298s sys 0m0.035s ```

Can anyone spot the simplification that was used (and is the reason why we have too many solutions)?

Can anyone spot a better equation to use?

Posted by Ozguru at October 13, 2004 06:00 AM