Google's Geek Aptitude Tests
Home
Google's Geek Aptitude Tests
Google's highly-publicized Geek aptitude tests have created quite a bit of buzz in Silicon Valley and other places where geeks congregate. The MathWorld website has a nice writeup on some of the problems as well as Mathematica-based ways of solving them. A typical (if you can apply the term to such an eclectic mix of puzzles) example is:
Solve this cryptic equation, realizing of course that values for M and E could be interchanged. No leading zeros are allowed.
WWWDOT - GOOGLE = DOTCOM
i.e. one needs to find a distinct decimal digit corresponding to each distinct alphabetic letter in the puzzle such that the resulting numbers satisfy the given equality. MathWorld gives several Mathematica-based algorithms for solving the problem, each one running faster than the previous one. This is an interesting optimization problem - here is a simple (only lightly optimized in the purely arithmetic sense, e.g. it needs no integer multiplies) C program that uses a brute-force approach to solving the problem:
#include "stdio.h"
int main()
{
/* Brute-force code for solving the cryptogram "wwwdot - google = dotcom" */
int w,d,o,t,g,l,e,c,m,wwwdot,google,dotcom;
wwwdot = google = dotcom = 0;
for(w=0;w<10;++w){
for(d=0;d<10;++d){
for(o=0;o<10;++o){
for(t=0;t<10;++t){
for(g=0;g<10;++g){
for(l=0;l<10;++l){
for(e=0;e<10;++e){
for(c=0;c<10;++c){
for(m=0;m<10;++m){
if(wwwdot - google == dotcom)
{
/* Make sure distinct letters all correspond to distinct digits: */
if(!(
w==d||w==o||w==t||w==g||w==l||w==e||w==c||w==m
||d==o||d==t||d==g||d==l||d==e||d==c||d==m
||o==t||o==g||o==l||o==e||o==c||o==m
||t==g||t==l||t==e||t==c||t==m
||g==l||g==e||g==c||g==m
||l==e||l==c||l==m
||e==c||e==m
||c==m
))
printf("%6d - %6d = %6d\n",wwwdot,google,dotcom);
}
dotcom++;
}
dotcom += 90;
}
dotcom -= 1000;
google += 1;
}
}
google += 100000;
}
wwwdot++;
google -= 1001000;
dotcom += 1000;
}
google += 11000;
dotcom += 10;
}
google -= 110000;
dotcom -= 100;
}
dotcom -= 1000000;
wwwdot += 110000;
}
return 0;
}
777589 - 188103 = 589486 777589 - 188106 = 589483We can clearly cut a bit of runtime off this by restricting W, G and D to be strictly greater than zero, but what we really want is an asymptotically faster algorithm than exhaustive search. The obvious one that presents itself is to restrict the 9 parameters W,D,O,T,G,L,E,C,M to all possible permutations of the numbers 0,1,2,3,4,5,6,7,8,9, and where we discard the last element of each permutation, since we have only 9 parameters to assign to. Here is some simple example code that implements this:
#include "stdio.h"
void nPerm(int a[], int ncurr, int ndim, int *count);
void dumpCurrPerm(int a[], int ncurr, int ndim);
void swap2int(int a[], int pos1, int pos2);
void checkGoogEq(int a[]);
int main()
{
const int n = 10;
int a[n];
int count = 0;
// Init the permutation array:
for(int i = 0; i < n; ++i)
{
a[i] = i;
}
// ...and generate the n! permutations:
nPerm(a, n, n, &count);
printf("Generated %d permutations.\n", count);
return 0;
}
/* Recursive function to generate all possible permutations of the integers {0, 1, 2, ... , n-1} */
void nPerm(int a[], int ncurr, int ndim, int *count)
{
/* Recursion terminates when ncurr = 1: */
if(ncurr == 1)
{
/* dumpCurrPerm(a, ndim); Uncomment this to see the actual permutations */
++(*count);
checkGoogEq(a);
}
else
{
/* Swap a[ncurr-1] with each of a[0], ... , a[ncurr-2] in turn and recurse: */
for(int i = 0; i < ncurr; ++i)
{
swap2int(a, i, ncurr-1);
nPerm(a, ncurr-1, ndim, count);
/* Undo the swap in preparation for the next one: */
swap2int(a, i, ncurr-1);
}
}
}
void dumpCurrPerm(int a[], int ncurr, int ndim)
{
for(int i = 0; i < ndim; ++i)
{
printf(" %d", a[i]);
}
printf("\n");
}
void swap2int(int a[], int pos1, int pos2)
{
int tmp;
tmp=a[pos1]; a[pos1]=a[pos2]; a[pos2]=tmp;
}
void checkGoogEq(int a[])
{
int w,d,o,t,g,l,e,c,m,wwwdot,google,dotcom;
/* Discard the last element of the permutation here: */
w = a[0];
d = a[1];
o = a[2];
t = a[3];
g = a[4];
l = a[5];
e = a[6];
c = a[7];
m = a[8];
wwwdot = w*111000 + d*100 + o*10 + t;
google = g*100100 + o*11000 + l*10 + e;
dotcom = d*100000 + o*10010 + t*1000 + c*100 + m;
if(wwwdot - google == dotcom)
printf("%6d - %6d = %6d\n",wwwdot,google,dotcom);
}
This needs less than a half-second to run through all possible 10-permutations and find the 2 solutions on the aforementioned hardware,
compared with nearly 3 seconds for the fastest Mathematica-based algorithm posted on the MathWorld website (they didn't say what hardware
they ran on, but mention that it was a "relatively fast machine.") The above code is arguably simpler than the best-of-breed Mathematica code.
Of course there are further straightforward optimizations one could do within the permutation code - one could attempt to implement a nonrecursive
permutation generator to eliminate the computational overhead associated with the recursion, for instance - but those would at best give modest improvements.
More interesting (albeit not asymptotically faster) would be a version of the permutation algorithm that only changes some minimum number of elements of the permutation between iterates, i.e. an N-permutational analog of a binary Gray code. That would minimize the amount of arithmetic needing to be performed in each call to the above checkGoogEq function - one would simply modify that function to take added arguments that key which permutation elements have changed in the latest iterate, and then use an incremental-update scheme to appropriately modify the variable(s) affected by the change. At this moment I don't know if such a "Gray permutation" algorithm exists - I haven't been able to find any references in my (admittedly not very deep) literature searches. If anyone knows of such an algorithm, I would appreciate it if you would be kind enough to send me a reference.