« From a science exam | Main | Chemistry »

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