Google Code Jam 2023 in Lisp

Since 2009, I have occasionally participated in Google's Code Jam competitions, usually programming in Lisp. Google decided to discontinue it along with their other coding competitions. So this year there was a "Farewell Round" held on a single day (yesterday), actually four rounds (A, B, C, D) held during the same long (four-hour) timeslot. Because I didn't feel very competitive or confident, I mainly tackled the problems from the "A" round, assuming that those were the easiest ones.

Thanks to the generous timeslot, I managed to solve all five problems in Round A.  You can find them on the gcj2023 project on my personal GitLab server.

Colliding Encoding: The task is to check whether there are collisions (duplicates) in a list of word after encoding with a lossy cipher function (mapping 26 alphabetic letters to 10 decimal digits). I map the strings, sort them, and walk through the result comparing neighboring entries—iff there's a match, then there are collisions. Code: a/1.lisp

Illumination Optimization: Given a set of lampposts at positions X_i along a road, how many lightbulbs of illumination radius R are needed to light the entire stretch of road from 0 to M? You go through the lamppost positions in order and skip those that are already illuminated by the previous lamp. My solution (a/2.lisp) tries both directions, in case one is "more optimal" than the other :-)

Rainbow Sort: On first read, I found it a bit confusing, because it talks about colors, card positions, and ordering numbers, all represented as integers; so I put it off until after the others. In the end it turned out to be quite easy. My solution (a/3.lisp) is a simple recursive function using a hash table to store colors that have already been seen.

ASCII Art: I quickly figured out that there must be a solution that involves just computation and no searching or construction. But it took me quite a bit of time (easily more than an hour) and trial/error until I removed all off-by-one errors. The solution (a/4.lisp) ended up simple enough, and solved all sets on the first attempt.

Untie: Here again, I quickly figured out that I can simply ignore all sub-sequences that have no repetitions. For every repeated sequences of length N, you can always fix the tie by flipping ⌊N/2⌋ symbols. I convinced myself that this is always possible without creating additional collision, thanks to the fact that you have two symbols to choose from. The trickiest part is that we're dealing with a circle rather than a sequence with start and end. My approach was to start at a point where the symbol changes—if there is no such point, then this is a special situation of a circular sequence of the total length of the sequence, and in this case actually you need to flip ⌈N/2⌉ symbols. Other than that, my recursive solution (a/5.lisp) looks relatively simple, and solved all cases on the first attempt.

By solving all problem sets in time, I ended up in rank 734 for that round, which made me quite happy! With some (but too little) time remaining, I tried my hand at two problems from more difficult rounds, but didn't manage to solve either of them in time.

Game Sort (Round C): This didn't look that hard, but my code consistently solved only the tiny sample set, and failed at even the small set on all my attempts. Maybe I take my broken code (c/1.lisp) up and try to find and fix what's wrong with it—or probably rather with my initial understanding of the problem and its possible solution.

Spacious Sets (Round B): My first iteration of code solved the small set, but ran into a timeout on the large set. I had to revise it to avoid quadratic complexity. I first thought of "memoization" to optimize away repeated iterations; in the process of implementing that, I discovered a nice linear initial pass (which has to be done in both directions—the problem has some structural similarities with Illumination Optimization above) that allowed the computation for a given pivot element to be done in constant time (adding two pre-computed numbers and 1). To my surprise, even with this probably very close to optimal solution, my program ran out of time! It turned out that I had another O(N²) issue in an innocuous part of the code that simply constructs a mapping from indexes in the original unordered sequence to the position in the sorted sequence that I use for the computation. I had to replace the trivial code using POSITION with my own FAST-POSITION trivially implementing binary search on the sorted output vector. The code (b/3.lisp) doesn't look great, but it works! I only really started after the end of the competition, though; otherwise I might have gotten four points for the small set...

So that was Google Code Jam's Farewell Round! Thanks a lot to Google for organizing those events over twenty years, and especially to the many Googlers for coming up with great problems, ironing them out, and providing tons of challenging data sets! I had a lot of fun—along with quite a bit of frustration; but that goes along with the challenge, I guess.