G'day Mate (Mk III)

« Schools | Main | From a science exam »

October 12, 2004

TechTip: Google Labs Aptitude Test (GLAT)

A couple of weeks back, I posted the logical solution to the Google Labs Aptitude Test (wwwdot - google = dotcom). I also mentioned that there was a programatic solution which proved that there were only two possible answers for the given criteria. Since that post I have had about 40 emails asking for the source code (which may explain why I have been a little slow responding to other email) and I figured I may as well post the whole solution on-line.

Rather than just throw a bunch of strange looking perl code at you, I decided to step through the design of the program and how I developed it. This is important because if you understand why and how then you should be able to implement the solution in a language of your choice (instead of perl).

I don't promise that the code is perfect (or even good) but as with many programs it was written to solve a particular problem and having solved it, the code will not be reused.

Basically we write the program by trying to establish the rules from the competition. To make the rules more obvious, we use 9 variables which correspond to the 9 letters in the puzzle:

#!/usr/bin/perl

#

my ($C, $D, $E, $G, $L, $M, $O, $T, $W) ;

We also need to keep track of just how many solutions we have found. In fact it is sort of fun to see how each additional rule restricts the number of answers:

my $Solutions = 0 ;

To make some alternative scenarios easier, we also declare an array of possible values (you may want to try limiting this to the values 1..9 to see if you can find a solution):

my @Values = (0..9) ;

Now for the first cut of the body, we are going to make a series of nested loops. This is not very efficient but it makes the rule encoding much easier:

foreach $C (@Values)

{

	foreach $D (@Values)

	{

		foreach $E (@Values)

		{

			foreach $G (@Values)

			{

				foreach $L (@Values)

				{

					foreach $M (@Values)

					{

						foreach $O (@Values)

						{

							foreach $T (@Values)

							{

								foreach $W (@Values)

								{

									$Solutions++ ;

								}

							}

						}

					}

				}

			}

		}

	}

}

print "There were $Solutions solutions found.n" ;

Note that at this stage, we are not interested in what the solutions are, just how many of them can be found. Running the program on my laptop (while running off battery :-() gives me the following:

$ time perl ./glat1.pl

There were 1000000000 solutions

real 46m31.469s

user 17m0.175s

sys 0m11.492s

The first improvement we can make is to enforce the no-duplicate rule (i.e. we don't allow two letters to stand for the same number). This is done inside each loop with a next statement. For example the $M loop will now look like:

...

foreach $M (@Values)

{

	next if $M == $L or $M == $G or $M == $E

		or $M == $D or $M == $C ;

	foreach $O (@Values)

	{

		...

Note that there is a comparison for each variable that appears to the left of $M in the initial variable list. Do not include $O, $T, $W at this point! Filling in all the conditions is left as an exercise for the reader. Note that we have reduced the number of possible solutions quite dramatically:

$ time perl ./glat2.pl

There were 3628800 solutions

real 3m24.680s

user 1m12.115s

sys 0m0.944s

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