Always Turn Left

This is with reference to the Google Code Jam practice problem.

SPOILER WARNING: DISCUSSION ON THE SOLUTION BELOW

This problem initially seemed vexing. After a little bit of thought about using bit twiddling to represent directions, generating the right codes was easy.

If you have any experience with hexadecimal numbers, it should strike you that the direction table with 4 directions each of which can be yes or no, is a big hint that bit twiddles are exactly what is needed. Which means powers of two

N, S, W, E = 1, 2, 4, 8

Now I'm not going to show how you combine them, but here is how you get the code directly in Python ( somewhat similar in C ):

def code(dirs):
return '%x'%dirs

After this I scribbled a lot on paper, mapping the small input to the maze. It was easy to figure out that the problem could easily be solved by going both ways because always turn left means that you will visit every part of the maze if you go both ways. I wasted a lot of time thinking how to orient the grid, until I read the specification that the entrace is always at the north.

But there was another problem, how to generate a perfect size grid for a dynamic problem like that. I didn't want a 10000*10000 grid all the time, that would be very inelegant. First I tried using links for each Cell, but the problem is resolving W-E or N-S relationships would involve backtracking to find the adjacent Cell. This flummoxed me for a LONG time. Then I read João's idea [perfect maze size] and it hit me like a rock. This problem really requires you to break some preconceived notions, like a multidimensional array being the best representation for a Grid. A dictionary with coordinates as keys turned out to be perfect for this problem. After this the solution was dead simple, walk forward, preserving the right coordinates, then turn around and walk back, overlaying existing directions with new ones you find.

Write a simple comparator function for coordinates, and use it to sort the grid and print it, and you have the solution in Python

In general the practice problems are creative, all they require a bit of common sense, some unconventional thinking and perhaps a few years of experience. Mainly it's about how elegant your code can be. I'm just hoping the real ones will be easy too. But irrespective of that, I'm not qualified to receive even a T-shirt, since I'm under age.