Having survived (like 96% of all Lispers and 81.5% of the wider population) the Qualification Round, I'm trying to pass the first "real" round. As expected, things are getting much more serious now! Round 1 is held in three sub-rounds, and you can participate in each, or until you advance to round 2. In each sub-round, the 1'000 highest-ranking contestants advance to round 2.
Where the qualification round had consisted of four problems (subjectively, two easy and two somewhat tricky) with 27 hours time to solve them, round 1 is three problems (an easier one and two quite tricky ones) that have to be solved within 2h30. From previous participations I knew that I would likely run into the time limit.
Getting off to a good start
Although the first sub-round, Round 1A, started at 3AM in my time zone, I decided to give it a try. I went to bed somewhat early and asked one of my sons, who was going out, to wake me up a bit before three, which he dutifully did. (Thank you!)
The first puzzle (The Last Word) went quite well. Somehow I convinced myself quickly that it is sufficient to put the next letter in front if it is greater than or equal to the first letter of the current substring, and at the end if it is smaller. My straightforward Lisp implementation can be found here.
The second task (Rank and File) was cute. After a bit of scribbling and thinking, I suddenly realized that it's sufficient to look for numbers that occur an odd number of times, sort those numbers and be done with it. I coded this up fairly quickly as well (Lisp source here).
So I was done with the first two problems after 44'22" with no penalties. I was also reasonably certain that I got both the large input sets right as well. (In the Qualification Round I had wrongly believed so as well, but in the critical case of problem C, the difference between small and large input was qualitative rather than quantitative.)
Problem C: close, but no cigar
With 1h45 left, I attacked the last problem, BFFs. This is a great problem—very simple in its formulation, yet requiring good (but not impossible) analysis, and also a bit of programming skills. It would be a nice recruitment interview problem.
This is pretty clearly a graph problem. The input set is a rather special set of directed graph with out-degree 1 (the BFF function). This must somehow be mapped to another kind of graph that represents a circle with some constraints. But this mapping is not that straightforward. Studying the sample inputs on the problem page, I quickly found that there are two different types of circle: One is a complete cyclic sub-graph of the input—that's easy to find given the simple type of input graph. The other possibility is to have a "core" circular graph of two nodes (a "couple" of mutual BFFs), with "extensions" of other nodes (kids) that (BFF-) point towards the nodes of the core. I wrote the code for both cases and tested it successfully against the tiny example on the problem page. My code looked for the maximum cycle, and the maximum graph of the second type, and would return the size of the bigger one.
To my great disappointment, the system told me that my solution for the small input set was incorrect. I couldn't figure out what was wrong, and time ran out on me. It was 5h30, and I had finished at rank #2137, with correct solutions for the first two problems and none for the third.
I went to bed slightly frustrated, and of course couldn't sleep right away but continued to think about the problem... what if the entire class consists of happy couples, i.e. mutual BFFs? Then I could put everybody in the circle. Hmmm... that's a case I had somehow missed! In fact the second type of graph (couple with "inbound" extensions) can occur arbitrarily often in the circle. Having understood my error, I could finally sleep.
In the next morning I had to write the code, although the contest was over. Although I had coded (correctly, I think) a good part of the necessary logic the night before, it took me several hours to get the algorithm right for the actual solution. I was too ambitious and wanted to write a really efficient solution ("early optimization..."), although a stupid O(N2) approach would probably have worked even for the maximum problem size of a 1'000 kids class. Probably I was also tired. Also, I saw that I don't know how to do proper debugging in SBCL, and had written the code in a way that made debugging somewhat hard. Finally I got the code right, see C.lisp here. Although the code is not particularly compact, I'm happy with it because at least I can read and understand it (for how long is another question), and it is O(N) with a pretty low constant factor for what that is worth—it runs in 20 milliseconds on the large practice set including I/O.
What about the other Lispers?
The per-language dashboard for Lisp on go-hero.net shows that none of us advanced in sub-round 1A. A very honorable mention goes to vii, who ended up on rank #1019 with correct solutions for all problems and input sets, but with a few penalties landing him or her 2'33" above the qualifying threshold. Good job & better luck next time! I'm sure he or she has what it takes.
Will I continue to use Lisp (and SBCL)?
While coding the last problem (BFFs), I sometimes thought that the program would have been easier to write in another language, even in C. I couldn't find an elegant recursive approach, and I always found writing iterative code in Lisp a bit awkward; I never really mastered loop or any of the other "modern" iteration constructs—why learn them when do will do? But the primary reason why I would have preferred another language was data structures. I built my graph from "node" objects (expressed as defstructs) with pointers, which was natural enough and worked well. But in another language I would have used a convenient vector representation... in Lisp the syntax for dereferencing vectors is so verbose and awkward that I was worried getting things wrong. And I felt that in the short time, I couldn't write a nice data type abstraction to hide the intricacies of such a vector representation.
What about SBCL? As mentioned before, I normally use Franz Inc's excellent Allegro Common Lisp, but I wanted to use a "real" open source system for the contest. I'm slowly getting used to SLIME after more than 20 years of Franz's Emacs-Lisp interface. But when I had to debug my final BFFs solution, I felt almost blind because I wasn't able to look at local variables from within a backtrace, something that works quite nicely with Allegro. So I had to resort to the equivalent of printf()s (warn), which made me feel a bit dirty. Probably I should learn how others debug under SBCL, I'm sure there's a better way! [Edited to add: (declaim (optimize (debug 3))) seems to go a long way!]
In the weeks before the contest, I had toyed with the idea to use Go this year, but I didn't have the time to learn the language well enough to make this viable. And overall, Lisp has treated me quite well this year. Also I've been using it for about 30 years now. So I don't feel like quitting mid-contest.
There are still two opportunities for me to try to advance to round 2. Timezone-wise they are much more convenient for me. On the other hand, I need some luck to find a good solution for the medium-tough problem as quickly as in 1A, and a bit more to find a good solution for the tough problem at all. But I'm an eternal optimist...
