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

Online round 1 was done on three dates again this year. The first (1A) fell in the middle of the night so I skipped it.

Round 1B Problem A: Steed 2: Cruise Control

I attempted the second, 1B, but I was distracted by important household chores. That's also why I didn't make any sketches. The first problem was easy enough, and I found a solution while fixing a meal for a kid who'd just returned from boy scout camp. The basic idea is that the horses all queue up behind the slowest one, so the arrival time is the latest arrival time at the destination point for all horses. The solution (A.lisp) worked fine on the first attempt of the small dataset, and also on the large one.

Round 1B Problem B: Stable Neigh-bors

The large dataset, where the unicorn's mane can have mixed colors, looked significantly more complex than the small one, where there are only three colors. I attempted a straightforward greedy algorithm, but somehow got it wrong. Because I didn't feel in a good state of mind, I decided to give up at that point. Otherwise I would have attempted the small dataset of Problem C: Pony Express. The "large dataset" cases of both problem B and problem C looked just too difficult to me.

Round 1C Problem A: Ample Syrup

A quick analysis suggested to me that the radius of the pancakes isn't relevant, because only the bottom (largest) one "counts", so I need to pick the pancakes with the largest lateral surface. Of course that reasoning was wrong, because we also need to pick which will be the bottom pancake. This error cost me two bad attempts, but I managed to reuse most of the initial code by adding a loop around it that tries various base pancakes. The code is in A.lisp and, again, worked fine for both the small and the large dataset.

Round 1C Problem B: Parenting Partnering

The optimization problem looked a bit tricky (but doable) in the general case, but the "small dataset" case was very specialized and easy enough to attack. There are only 1 or 2 activities in total. Either each partner has one, or one partner has all 1 or 2. If each partner has one, then the optimal solution always involves two exchanges. If one partner has the only one activity, the solution is even more trivially two exchanges. If one partner has (all) two activities, then the optimal solution is two if those activities can be arranged on the same "half-circle" (12 hours or 720 minutes) of the day, otherwise four. I coded these cases in B.lisp and was successful on the small dataset. In hindsight I'm surprised that it took me so long, more than 45 minutes between my submissions for A and for B-small.

Round 1C Problem C: Core Training

Next, I decided to try the small dataset of problem C. While I thought B-large might be in reach for me, I was sure that C-small was easy and could be coded quickly. (I had and still have no idea how I could successfully approach C-large.)

In particular, I thought that the training budget should always be spent on the worst (lowest-p) cores first. So I wrote this trivial loop, ahem, recursion, that spends as much as possible on those worst cores until either the budget is used up, or the worst cores become improved enough to be as good as the next-better core, or the cores reach p=1. But all my attempts were rejected,  and embarrassingly I still don't know why. Probably my reasoning was again oversimplified. Or it was something about the Lisp representation of floating point numbers. Anyway, the non-functioning code is in C.lisp.

Conclusion

This was the end of my participation in Google Code Jam 2017, because with rank #1850 I didn't make the cut—only the top 1000 in each of the round 1 sub-rounds make it to round 2. Even if I had been successful with the small dataset of C, I wouldn't have made the top 1000. Had I successfully solved the large dataset of B with some time to spare, then it might have worked.

It was mostly fun to code these small problems in Lisp. My Lisp skills are getting a bit rusty though. And I'm still not as comfortable with the SBCL/SLIME combination as I am with Allegro Common Lisp and its Emacs interface, but as I had mentioned in previous posts, I wanted to use completely free/open source software. And the awesome Allegro debugger wouldn't have been of much help here anyway.

And I love the problems! Kudos to the Googlers who come up with them.

How did the other Lispers fare? Badly as far as I can see. There haven't been many Lisp submissions in 2017 anyway, compared with 2016.