This year’s qualification problems were all straightforward puzzles. None of them needed sophisticated implementation techniques, or advanced algorithms, or complex data structures. They just needed patient analysis and careful coding. That’s nice from one perspective, but unfortunately it’s hard to make a good comparison of programming languages when every problem can be solved with just loops and arrays. Still, I succeeded in my goal of producing every output with a different (sometimes terrible) language.
Here’s my code and commentary on the problems. Warning: spoilers ahead. If you haven’t looked at the problems yet, go do that first.
A: Counting Sheep
There’s only one trick to this problem: detecting infinite loops. Otherwise it’s just a matter of implementing the counting process as specified.
There’s a special place in hell for people who write real programs in Bash and then expect their colleagues to maintain them. The Bourne Again Shell has grown features like a tumour – this code is %100 Bash builtins. It keeps track of digits simply by iterating over the string representations of numbers and storing the digits in an associative array.
Wikipedia says most of it:
dc is a cross-platform reverse-polish desk calculator which supports arbitrary-precision arithmetic. It is one of the oldest Unix utilities, predating even the invention of the C programming language. Like other utilities of that vintage, it has a powerful set of features but an extremely terse syntax.
The code says the rest:
Next time you hear someone brag about how much their favourite programming language can do with one line of code, ask if they’ve tried dc. They might like it.
This code extracts digits by repeatedly taking the remainder after dividing by 10, and keeps track of them in an array of flags.
B: Revenge of the Pancakes
The small case can be brute forced, and the official analysis suggests using BFS. Because there’s no need to flip a stack of pancakes more than once (because flipping is commutative and two flips cancel out) you can also solve it by just asking “Do I flip this stack?” for each possible stack of pancakes, and brute forcing all possible combinations to find the best one that works. For a total stack size of , a good way to implement that is to loop from to and use the numbers as a binary encoding of whether to flip each stack.
I didn’t do that. My solution is equivalent to the one in the analysis for the large case, but maybe a little easier to explain. The key insight is that if the bottom pancake needs flipping, there’s only one way to do it: flip the whole stack. So we can simply look at the bottom pancake and decide whether or not to flip the entire stack, and then we never consider flipping the whole stack again. Then we look at the pancake that’s second from the bottom. The only remaining possible way to flip this pancake (if we need to) is to flip all the pancakes from this one up. If we keep working up the pancake stack this way, we can figure out exactly when to flip and when to not flip.
You can implement this by simulating the whole flipping process with an array of “pancakes”, which results in an solution that’s fast enough ( is 100 at maximum). You can avoid doing a full simulation by only keeping track of how many times you’ve flipped, or (because two flips is the same as no flips as far as the higher pancakes are concerned) just whether you’ve flipped an even or odd number of times. This results in an solution, and it’s what I used because it’s easy to implement.
Lua’s designed as a powerful but fast and lightweight embeddable scripting language, and generally it’s not bad at being that. It has the usual variables and basic data types (including “tables” – associative arrays), as well as modules, first-class functions, closures and iterators. The standard library is deliberately minimal so that you can add only what you need (unlike Python).
It does have a few quirks like all variables being global by default.
When I first learned Awk, I thought it was pretty cool, tried it for a few things, then practically never used
it again. It’s like a next step up from basic *nix text-processing commands such as
tr – it adds all kinds of nice things like functions and variables. The trouble is, if you need
those things you might as well use a full-blown scripting language. About the only thing I use the
awk command for in practice is as a better
cut, which is kind of like buying one of
those all-in-one, automatic food processor machines and using it as a nifty blender.
This Awk code is an almost literal translation of the Lua code.
C: Coin Jam
For this problem it was really helpful to get away from a computer screen and do some pen-and-paper analysis. First I wrote down what “evaluating a string in base ” meant in algebraic terms.
where the variables represent the digits of the string. We need to multiply two numbers to get a coin (i.e., a number where the variables have a certain pattern of 1 and 0 values). Simply trying a factor (I chose ) and resolving the constraints gives a set of solutions. This had the side effect that was a suitable “proof” divisor for every coin I generated, so my code output that same list every time.
The problem statement helpfully points out that you can do preprocessing because you know the inputs beforehand. Preprocessing isn’t actually needed if you can calculate the coins directly, but I did do some postprocessing. I.e., I wrote a quick script that parsed the output and verified that it met all the requirements. That way I was pretty confident when I submitted.
Ruby is a new language for me, but because this blog is built with Jekyll, I’m using more of it nowadays. My impression so far is that it’s a lot like Python but with a heavier emphasis on map/reduce/filter-style programming (which I like). One the negative side, it has a lot of unnecessary complexity. The Zen of Python says there should be one obvious way to do things. It doesn’t work out that way, but at least Guido has tried. Ruby’s motto could be “Let’s add another way to do it!” Compare map and collect for example.
Because this problem is more about the analysis than the coding, Ruby feels kind of overpowered for the job compared to the other languages I used, but I wanted to use it at least once in this competition.
Kind of like Ruby, Haskell is overpowered for this job, but I wanted to use it anyway. I’m a pretty casual user of Haskell. Haskell programming requires a completely different approach from any other language I use (even Lisp), so I try it out every now and then to broaden my horizons.
Haskell’s lists are good enough for getting the “Correct” reponse from the judge, but Haskell doesn’t really become Haskell until you use its abstractions (yes, like the infamous monads).
The final problem in a Code Jam qualification round usually takes some special insight or creative approach, but this one just required patient analysis. If you treat the original tile pattern as a system input, and the result as a system output, it’s just about figuring out which output tiles depend on which input tiles, and then choosing a set of output tiles that covers the whole input.
The problem statement uses 1-based indexing, but I used 0-based indexing internally for simpler implementation.
After I’d thought through how the system worked, the overall solution was simple. If the original pattern has, say, 5 tiles, then I need to select output tiles to cover (0-based) input positions 0, 1, 2, 3, and 4. If the transformation has complexity 3, it turns out each output depends on up to 3 inputs, so I pick an output that depends on inputs 0, 1 and 2, and then an output that depends on inputs 3 and 4, and then I’m done.
Forth feels a bit like a glorified assembly language for a stack machine. It can be implemented extremely efficiently, so it’s historically been very popular for embedded systems.
Pascal used to be extremely popular, so there must be heaps of legacy Pascal around. The first time I got paid to write code, I was working on a legacy Pascal system. Maybe it’s just me, but it’s not a language that seems to get talked about much. I guess there’s nothing cool or exciting about it, but at the same time it’s no COBOL. The syntax feels a bit like BASIC, but it has pointers so it’s closer to C in terms of power.
The problem statement allows several possible solutions, but I deliberately made my two implementations
generate exactly the same output for the same input, so I could do smoke testing using generated data and
diff. I expected the Forth code to break if anything, but actually it was the Pascal code I messed
up. I’d misremembered that the
LongInt type was 64b on 64b machines, but actually it’s only 32b with
Free Pascal, so I got integer overflows.
I’ll be much more conservative in the next rounds. I’m likely to use more than one language, but I’ll stick to ones I’m comfortable using under time pressure, and I won’t care if I reuse languages. Also, unfortunately, I didn’t plan my schedule too well. There’s only one Round 1 slot before I leave for DConf, and if I don’t mess that up, I’ll still be on the road for Round 2. But, even if things don’t work out so well this year, at least I’ve met my personal challenge for the qualification round, and there’s always next year. On another note, if you’re going to DConf, too, say hi!
If you missed out on entering the 2016 Code Jam qualification, I really recommend giving it a try next year. The puzzles are creative, and it’s a good way to sharpen your programming skills. The online judge is available throughout the year for practice.