Sunday, April 10, 2016

Google Code Jam 2016 Qualification Round in Lisp

This year I registered for Google Code Jam again. The qualification round was this weekend, and I submitted solutions in Lisp.  This time I used SBCL with GNU Emacs and SLIME as the IDE, rather than Allegro Common Lisp with GNU Emacs and Franz Inc's emacs-lisp interface.
The puzzles were lots of fun, as usual.  A (Counting Sheep) and B (Revenge of the Pancakes) were easy.  When I looked at C (Coin Jam), I found it tricky, so I put that aside and did D (Fractiles) next.  Explaining the problem to my 19-year-old son helped me find a good approach.  After implementing it and submitting the solutions, I turned back to puzzle C.  My solution looked complex, and I suspected that there would be a more elegant way.  Still I was happy with the solution as it produced a result for the large set very quickly, so I submitted the results and was done. My solutions can be found here.

So how did I fare?

The round went on for 27 hours, and I started somewhere in the middle due to timezone.  So after I was done with my solutions, I had to wait until the next day to see the final score.  The "small" problem datasets are checked immediately after submission, so I already knew I had all of those right before I went to bed.  Since they already accounted for 37 points, and I needed 40 to advance to the next round, I could be pretty optimistic that I had passed—having any large dataset correct would get me more than the three missing points.
The intermediate scoreboard put me on rank #1189; this is assuming (for everybody) that all the "large" solutions that were submitted would be correct.  I was pretty sure that mine were all correct, so I had hopes that my final rank would be even higher.
But my final rank was #2748, because it turned out that my "large" solution for D (Fractiles) was incorrect.  This was a big disappointment, because I was very confident in my solution approach.  And it turned out that my error was a stupid one in one of the "easy" parts of the implementation; the decision whether the number of grad students (S) is sufficient to clean enough tiles in the base-length-K and complexity C artwork to detect whether there's any gold tile.  The correct test would be
  (if (< (* s c) k)
...but I used:
  (let ((min-s (truncate k c)))
    (if (< s min-s)
My test was too lax, and I sometimes output a "solution" when I should have printed IMPOSSIBLE.  This stupid mistake cost me >2000 ranks.  It would be nice if I managed to avoid this in the next round.  But realistically I'll make even more of these mistakes because the problems will be harder and the time pressure much higher.

How did the other Lispers do?

On there are statistics about GCJ participants and submissions, and it's easy to find all submissions for this round that used Lisp.  We Lispers were quite successful this weekend, with 26 out of 27 proceeding to the next round, a success rate of 96% compared to 81.5% for the entire population.
The highest ranking Lisper was Ipetru at #594 with all solutions in Lisp (and of course all correct).  I looked at his solutions for C and D, and they are so incredibly compact that I couldn't believe my eyes.  D used the same approach as I had, just very elegantly written—the code proper is about two lines; much harder to hide stupid mistakes in there! C used a completely different approach, deterministically generating Jamcoins rather than checking candidates as I had.
The second-ranking Lisper was DarkKnight. at #720.  He only wrote one solution in Lisp.  In fact he used different languages for all solutions, and I mean all 8 solutions, not all 4 puzzles! bc, OCaml, Lisp, Racket, Lua, Perl, Octave, R.  Impressive! :-)

No comments: