I competed in Google Code Jam for the first time this year and really had fun with it. Some of the puzzles can seem challenging at first glance but usually break down into a main algorithm with a few checks for outliers and limits. It’s a pretty good test of how quickly you can translate a problem into code.

I used C++ primarily and Go language in one case since I knew it had a handy string.Map function. My solutions can be found on github.

One of the problems, named Kingdom Rush, provided a game scenario as input and required a result indicating the shortest number of turns to complete it.

On my 1st pass I implemented the obvious naive solution:

1
2
3
4
5

Search for any eligible 2-star ratings.
  If found, mark it done, update score, and start over.

If none found, search for any eligible 1-star ratings.
  If found, mark it done, update score, and start over.

It passed the given samples, so I submitted and it failed. The grader doesn’t say why or give errors, so I had to find a case that broke the code. This is where pencil and paper are invaluable since at this point you have to simulate instances. Turns out, you can shorten your game by doing 2-star ratings where the 1-star rating is unlikely to be completed until late. I resubmitted with this modification and it passed.

What I learned:

• Have a pencil and paper handy; this is largely a math contest. Doodling tends to provide insight. As I was working on Hall of Mirrors my sketch reminded me of the Fly and Spider problem, which revealed a very reasonable approach.
• Hurry. Readability and elegance are for teams and longevity; this is an intense individual exercise where you only need 1 good run. Write the quickest thing that might work.
• Remember any initial assumptions. In this problem, I assumed that order did not matter. When the solution I had coded worked exactly as intended, but was still wrong, it took me valuable minutes to work back and realize that turns could be minimized with a deliberate selection order. Don’t mistake this for advice about not making assumptions; you should (see “Hurry”). Just remember what you glossed over when things don’t work.
• Break it down. The idea behind this is trite, yet why do large problems always daunt us as if they were monoliths that can only be tackled in one piece? While not being gimmicky, these problems often break down into known solveable chunks. At its core is usually something familiar.