Google Code Jam 2016 in Lisp: Round 1B/1C

After failing to qualify in round 1A in this year's Google Code Jam, I had two more chances to advance to round 2.

Round 1B

In round 1B, I only managed to solve the first problem, Getting The Digits.  It took me quite some time, but eventually I found the recommended approach to count letters that are specific to a single digit (e.g. Z occurs in no other digits than ZERO), then eliminate those digits; initially all the even digits have unique characters (0:Z, 2:W, 4:U, 6:X, 8:G), but after those have been eliminated, this holds for other digits as well: (1:O, 3:T, 5:F, 7:S) and finally (9:I).  The program is ugly in that this sequence of letter/digit combinations is hard-coded; a good program would extract the letters by itself so that it could be ported more easily to other languages etc.  My Lisp code is here.

Anyway, both of the other problems resisted my analysis.  I should have been able to solve Close Match, but I couldn't decide whether it should be solved from left to right or right to left, and ended up spinning in circles.  The final problem, Technobabble, is beyond my current capabilities: I neither succeeded in mapping the problem description to the correct graph problem (minimum edge cover on a bipartite graph), nor would I have been able to code an efficient solution to that problem.  As an undergraduate I was good at these kinds of things, but lacked practice over the past 20 years or so.

With only one problem set solved, I ranked #4259 and was very far from qualifying.  The other Lispers didn't fare much better in this round, except for orivej, who advanced by ranking #847.  He or she only used Lisp for the first problem, and Python for the third.

Round 1C

Again I was able to solve the first (and easiest) problem, Senate Evacuation.  There are many viable approaches, and it took me a bit too long to find one.  Here's my slightly embellished A.lisp (raw submission).

After 35 minutes, I attacked the second problem, Slides! After lots of scribbling of graphs and diagonal matrices, I found a method to construct slides for an arbitrary M below the maximum that maps nicely to binary numbers.  The resulting code (B.lisp, cleaned up from the actual submission) is short and sweet and even turns out to work.  But again it has taken me much too long to get there.

With only 16 minutes left, I looked at the final problem, Fashion Police.  I knew I didn't have the slightest chance to solve the problem properly, so I started coding a brute-force algorithm that might solve the small dataset.  But that was not as small as it looked, and the problem not as simple as I thought, so I failed.  Well, anything else would have been a miracle.

My final rank was in this round #1326.  I didn't qualify, but I was quite happy with this honorable (for me) result.  To qualify, I would have had to finished my two working programs in 1h39'30" instead of 2h13'46".  Maybe with more practice I'd be able to save those 34 minutes somewhere—but it looks like a long shot!

Looking at the other Lispers in the contest: This round saw an awesome result from lpetru, who handed in a perfect score (100 points, all problem sets solved), landing him or her on rank #98.  And so far he or she submitted all solutions in Lisp.  I know whom to root for in round 2!

Final remarks

Again it was lots of fun to participate in Google Code Jam.  It was exhausting and sometimes frustrating (especially in round 1B).  But it's good to have those old brain cells work outside their comfort zone.  So I'll probably try again and hope that I'll eventually manage to reach round 2.  See you next year!