Google Code Jam 2020 in Lisp—Round 1B

Although I had quite a bit of trouble surviving this year's qualification round, I was allowed to participate in online round 1, which, as usual, is held as three different sub-rounds to accommodate participants from various time zones.  The first (1A) was in the middle of the night in my time zone, so I skipped it and didn't even get around to reading the problems.  But today I attempted  round 1B.  The problems were again very cute and interesting, and while I struggled with the limited time, I ended up being quite satisfied, even though I missed qualification this time.

Problem 1: Expogo

I wrote a relatively simple implementation using search with memoization (caching) and a bit of pruning of implausible search regions, and that was sufficient for all three data sets.  According to the after-round summary, there's also a constructive solution.  I had suspected so, but couldn't find it.

Problem 2: Blindfolded Bullseye

This is a nice search problem that involves some geometry.  I think I started with a reasonable search strategy, but then ran out of time when it came to doing the geometry... So I gave up trying to find a "good" solution, and coded the trivial brute-force solution for solving the easiest data set.  That was worth only 3 points, but those 3 points improved my final ranking by more than 1'000.

Problem 3: Join the Ranks

This didn't look too impossible, but given the high amounts of points awarded for this, I suspected that this would be beyond my skills and decided to focus on the other two problems.

Conclusion

With a full solution for problem 1, a half(?)-done good solution for problem 2, and the few extra points for the trivial data set of problem 2, I finally ranked #1996 [edited for final result].  As only the first 1500 contestants qualify for round 2, this was not sufficient.  But I'm quite happy with how it went, and am looking forward to round 1C, about two weeks from now.  And unlike during the qualification round, I didn't run into any issues with coding in Lisp—even though I haven't been using it professionally for several years now.

Google Code Jam 2020 in Lisp—Qualification Round

This year I registered for Google Code Jam again. The new platform supports Common Lisp (SBCL) again, so I started writing my solutions for the Qualification Round in SBCL. Although I managed to qualify for Online Round 1, it didn't work as well as I'd hoped.
The Qualification Round this year had five problems, which took me a while to notice—I had to scroll horizontally to see the fifth problem. I attempted all five, but only managed to write working solutions for three of them.

Problem 1: Vestigium

That was an easy one, but for some reason I didn't manage to code it correctly in Common Lisp. Even though my code looked totally straightforward, it only produced an RE (Runtime Error) when run against the data set. Finally I rewrote the solution in C++, and that worked on first try.

Problem 2: Nesting Depth

The task was to generate appropriate numbers of correctly nested parentheses. Obviously this type of problem is familiar to Lispers, and this time my straightforward code actually worked. My sloppiness resulted in an invalid attempt, as I initially left out the (solve) call at the end of the script.

Problem 3: Parenting Partnering Returns

It occurred to me relatively early that the problem maps to the problem of partitioning (two-coloring) the interval graph. However, all my attempts of coding this simple graph traversal algorithm in Common Lisp ended in REs (Runtime Exceptions) again. Very frustrating!

Problem 4: ESAb ATAd

This was my favorite problem, and I came up with a simple and near-optimal solution pretty quickly. It would have worked the first time, had I not (again) forgotten to add the correct (solve) call after the development phase.

Problem 5: Indicium

That one was definitely too hard for me! After the deadline, I read the analysis and took it up again. I managed to code a super-efficient method to generate latin squares with arbitrary possible traces at will, based on "circulating" matrices. The only cases that I cannot solve in this way are odd-sized with traces of is n+2 or n²-2.

Conclusion

Finally I advanced with 49 points (from 100, with 30 required), and ranked #6318 of about 44000 participants. My Lisp development and graph algorithm skills have become a bit rusty, and I'm not very optimistic about being able to survive Online Round 1.