« Chemistry | Main | Programmer's drinking song »
October 14, 2004
TechTip: Google Labs Aptitude Test (GLAT)
The final entry in the on-going saga.
Brownie points to anyone who spotted the simplification from yesterday. By treating each equation in isolation we actually allowed combinations to occur that should not have. For example, we allowed for four possibilities in the second equation O - L = O but in reality there were only two possibilities depending on which of the two options was selected for the previous equation. Think about it, if we have already determined which choice was made at the previous step then that precludes us from making some choices at this step.
There are two options here, one is to continue to explore the interaction of the equations and the other is to rethink the whole program. The rethink requires us to introduce some sort of communication between one layer and the next. This communication is about whether a borrow has happened and hence there should be a carry included. This can be done using a collection of variables that is set or cleared depending on the choice.
Our first equation (T - E) = M now needs to be written like this:
# Add this near the start
my @Borrow = () ;
...
# Replace the old "foreach $T" code
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 ;
if (($T - $E) == $M)
{
# Note that the '1' is for the 'first' or leftmost equation
$Borrow[1] = 0 ;
}
elsif ((10 + $T - $E) == $M)
{
$Borrow[1] = 1 ;
}
else
{
next ;
}
foreach $W (@Values)
{
Note that at this point we have not actually changed the program in a way that would affect the results. To have an impact on our current set of 30 solutions, we need to use the borrow array in the next equation. This in turn introduces another minor problem. We have moved the equation tests as close to outside the loop as possible (which improves performance) - now we have to ensure that we do not test the second equation until after the first one and so on. This will migrate code deeper into the loop which will slow the program down.
Here are the results after modifying the first equation:
$ time perl ./glat4.pl
There were 30 solutions
real 0m1.616s
user 0m1.297s
sys 0m0.010s
Now the second equation needs to move from the O loop into the T loop after the first equation. Without otherwise modifying the code:
$ time perl ./glat4.pl
There were 30 solutions
real 0m2.798s
user 0m2.698s
sys 0m0.033s
Ouch. As a programmer of the old school, I like my programs to get faster and tighter not larger and slower.* Let's add in the borrowing code and see if it helps at all. Note that there is both the code to set the next borrow and also use the previous borrow. Laying it out as a series of if/then statements is OK because perlmagic will happen...
This code appears just after the previous code and before the foreach $W:
if (!$Borrow[1] and ($O - $L) == $O)
{
$Borrow[2] = 0 ;
}
elsif (!$Borrow[1] and (10 + $O - $L) == $O)
{
$Borrow[2] = 1 ;
}
elsif ($Borrow[1] and ($O - $L) - 1 == $O)
{
$Borrow[2] = 0 ;
}
elsif ($Borrow[1] and (10 + $O - $L) - 1 == $O)
{
$Borrow[2] = 1 ;
}
else
{
next ;
}
Now the reduced number of cases helps to compensate for the relocation of the code:
$ time perl ./glat4.pl
There were 20 solutions
real 0m2.894s
user 0m2.665s
sys 0m0.025s
Finish off the code and you should get the right results:
$ time perl ./glat4.pl
(4, 5, 3, 1, 0, 6, 8, 9, 7) (0, 0, 0, 1, 1, 0)
(4, 5, 6, 1, 0, 3, 8, 9, 7) (0, 0, 0, 1, 1, 0)
There were 2 solutions
real 0m16.425s
user 0m12.823s
sys 0m0.114s
I did mention that there was another way to tackle it and that is to put one equation in the innermost look and drop the other equations (except for the uniqueness test). The innermost loop would contain:
next unless ($T + 10*$O + 100*$D + 1000*$W + 10000*$W + 100000*$W) -
($E + 10*$L + 100*$G + 1000*$O + 10000*$O + 100000*$G) ==
($M + 10*$O + 100*$C + 1000*$T + 10000*$O + 100000*$D) ;
Programatically, this is very inefficient but nevertheless gives us the right answer:
$ time perl ./glat5.pl
(4, 5, 3, 1, 0, 6, 8, 9, 7)
(4, 5, 6, 1, 0, 3, 8, 9, 7)
There were 2 solutions
real 1m27.429s
user 0m55.602s
sys 0m0.649s
I hope you enjoyed the puzzle, if you have any questions, drop me a line or leave a comment...
[* Larger and slower is the Microsoft school of coding...]
Posted by Ozguru at October 14, 2004 06:00 AM
