« Dont be cheap | Main | Phrasing it right »

September 16, 2004

TechTip: Google Labs Aptitude Test (GLAT)

Ever since I posted this article about the Google Labs Aptitude Test puzzle (wwwdot - google = dotcom), I have been getting a trickle of emails that are either along the lines of "I solved it" or "I need a hint". Most of those who solved it were somewhat bemused about my comments about the two different ways to solve it - basically they chose to bat for one method or the other as being the most "obvious" way of getting an answer.

Well here is a hint about how to tackle it logically (which took me longer than the programmatic solution). Imagine a similar puzzle that looks like:

ABC -

DEF =

GHI

This consists of three sub equations of which the most complex is the middle one (with B, E and H in it). There are four possible permutations for this single entry. The first and most obvious is simply that B-E=H. The second happens if C<F which would mean that C had to 'borrow' and there is a carry attached to E which gives us: B-(E+1)=H. The third possibility happens if B<E in which case we need to include a 'borrow' and the equation becomes: (B+10)-E=H. Finally we could have the second and third equations both happening at the same time: (B+10)-(E+1)=H. Note that the end equations (C,F,I and A,D,G) are simpler because there are less possibilities to consider.

In the Google question, the most interesting pair of equations involve W,O,T and W,O,O. A quick think about this makes it clear that there are some constraints about borrows because the two get different results. Also note the O,L,O triple which sort of suggests that L could be zero. If you only care about finding an answer (i.e. any answer), you could start by making L=0 and trying to solve from that point.

Interestingly, ignoring the actual values in the equation, this could be expressed in terms of a tree of possible solutions where the first fork has a choice of 2 and the next four have 4 choices and the last has two again (from the permutations above). That means exploring a tree with 2 x 4 x 4 x 4 x 4 x 2 nodes (2^10 = 1024 possible combinations). Some of the branches can be eliminated quickly, others take more effort.

Next time I will describe one way to tackle the problem using brute force and a computer.

Posted by Ozguru at September 16, 2004 06:00 AM