First Google Code Jam!
The format of this competition, allowing us to run programs on our own machines, brought up a very interesting issue for me: what programming language should I be using? (I had had similar considerations for IPSC 2013, but GCJ’s problems are closer to the traditional ACM-ICPC style.)
The obvious choice is C++, the language I use for roughly every other competition, but its safety (or lack thereof) is not very appealing. I need speed, but not that much speed. Unfortunately I still haven’t gotten around to learning any other friendlier mid-level languages (on the list: D, Go, or Rust), so I have no close substitutes for C++ right now.
Python is certainly available for a reliable arbitrary-length integer type, if nothing else.
As for non-candidates, Java has BigInteger and memory safety, but all in all I decided the benefits are too minor and it’s too ugly without operator overloading. Scala is probably way too slow. So I don’t expect to be writing either language.
The only difficult choice I have to make is, of course, Haskell — which can be quite fast, even while it’s ridiculously type-safe and expressive and referentially transparent and easy to reason about, once you’ve:
- figured out how to do the problem
- scrapped step 1 and actually figured out how to do the problem functionally
- gotten the thing to compile
Even if I can handle step 1, step 2 is by no means a simple task, as my struggle to implement a mere Sieve of Eratosthenes efficiently shows. That is fun, but not at all intuitive; I am doubtful I can do this under contest conditions. It is extremely difficult to transfer my skills in learning how to implement, say, a segment tree or treap into this language.
But! Google links to the programming language breakdown for 2010 Qualification Round as an example, and much to my surprise, Haskell ranks somewhere between sixth and tenth place in popularity (depending on what you sort by), so there are functional superprogrammers who can presumably do something like this.
As it happens, I ended up implementing all four solutions to the qualification rounds in Haskell, because of the relaxed time limit and lack of any involved algorithms and data structures. I think it was worth it.
let sols = (g1 !! pred r1) `intersect` (g2 !! pred r2) in
printf "Case #%d: %s\n" tci $ case sols of
[] -> "Volunteer cheated!"
[a] -> show a
_ -> "Bad magician!"war :: [Double] -> [Double] -> Int
war nblocks kblocks = maximum . scanl (+) 0 . map snd . sort $
map (,-1) nblocks ++ map (,1) kblocksPattern matching! Scans, maps, tuple sections! <3
On the other hand, for problem C I encountered a subtle edge case where my program would print an extra row, which was partly hidden by Haskell’s replicate happily receiving a negative integer and not complaining. Too bad Haskell doesn’t have a natural number type.
In any case, I’m not expecting to continue this for later rounds, at least not for the ones with complex algorithms. I looked at STRefs and IORefs and the Vector library to learn how Haskell interfaces with mutable stuff — it's possible, but I'm quite sure I can't do it quickly enough for a contest. Besides, these skills are nontransferable to most programming competitions and instead just make me annoyed at all the cool Haskell features I don't get to use when I'm competing in them. Oh well.
The other thing I was doing during the contest, in partial anticipation of later rounds, was tidying up my Haskell installation and workflow. More on that later.
But remember that replicate bug? While thinking about installing libraries, I remembered something else that has nothing to do with Google Code Jam: I wanted to install Idris, a highly Haskellish and totally radical functional programming language with dependent types. I’m not even going to try to explain in this post, but theoretically, dependent types could have encoded the integers involved in that bug into the type system and caught it at compile time.
The installation failed, which is why I’m here and why this post is actually labeled Cabal installations rather than being about my attempt to use Haskell for competitive programming. The rest of this post is about my debugging efforts — a responsible offering of a solution for anybody who has to deal with this in the future and comes across this page by the well-worn method of “Googling the error message”.
After twenty eternities, cabal install idris errored out with a ridiculous message and an inexplicable sixty-something-character identifier that started with “_hashable”. The failing dependency was lens-4.1.2. The interesting lines I copied down are these:
lookupSymbol failed in relocateSection (relocate external)
unable to load package `void-0.6.1'I should have copied down the whole thing…
…but nothing came of it after putting it in Google. It seems as if the actual packages involved may be somewhat random.
So, for maybe the second time in my life, I decide to hop onto the #haskell IRC channel, and for the first time, I decide to say something. The somethings are preserved for all eternity on the logs. After help from some channel gurus and more Googling, I finally solved the problem by this method:
Nuke Haskell entirely and reinstall it from the package.
What a civilized solution, right?
On OS X, there’s a script at /Library/Frameworks/GHC.framework/Versions/Current/Tools/Uninstaller. It took me a while to figure out how to run it; eventually I cded into the directory and then sudo bash it. Then I deleted other stuff — /Library/Haskell, ~/.ghc, ~/.cabal. I cleaned up my $PATH, found the Haskell .pkg, checked its SHA1 against the online version, and installed it. That was quick.
$ cabal install idrisAnd after twenty to thirty more minutes of non-stop compiling, I had Idris installed!
But there were other installation failures — one error manifests itself with, as of time of writing, at least the two packages conduit and binary, probably more. But only on OS X. This is due to C++ preprocessor incompatibilities.
The problem is that OS X (specifically Xcode, I think, but don’t cite me on it) symlinks gcc to a version of clang, which doesn’t support all the same preprocessing directives slash bells and whistles as a true gcc (though it is arguably better in other ways (but this is another programming holy war I don’t have time to go into; I don’t have a strong opinion)). The result is mysterious error messages like this:
Data/Conduit/Internal.hs:338:4:
error: invalid preprocessing directive
#-}
^I think I read somewhere that there’s a wrapper script around clang to support it in the GHC pipeline, but in the meantime, to get a real gcc on OS X using Homebrew: tap homebrew/versions, then brew install gcc48. This takes a long time! The compiler has to bootstrap itself. Luckily, I had done this before and it was not necessary to nuke this along with the Haskell installation.
To tell GHC about this, find GHC settings (that’s the actual filename; I found mine under /Library/Frameworks/GHC.framework/Versions/7.6.3-x86_64/usr/lib/ghc-7.6.3) and edit the string paired with “C compiler command” to /usr/local/bin/gcc-4.8 or wherever Homebrew linked gcc48. Or you could just change the system-wide gcc symlink to point there, but I thought this fit my goals better. I’m mentioning this specifically because I remember seeing it online, but Googling for it led me several times to a link to a particular GitHub page that has since vanished, so the internet may be missing it.
After all this was done, I got to install a long list of useful Haskell packages. Here they are for my own future reference and for anybody who’s interested.
Selected from Stephen Diehl’s What I Wish I Knew When Learning Haskell and A Vim + Haskell Workflow:
hooglepointfreehlint(syntastic integration!)quickcheckcriterionghc-mod(syntastic integration!)hdevtools(syntastic integration!)
It may be necessary to manually symlink executables somewhere into your $PATH. If so, they can probably be found in ~/Library/Haskell/ghc-7.6.3/lib/ /bin. I had to do this with my old install, but after the nuke and reinstall I didn’t. I don’t know why.
I’m going to gush again: syntastic is just magical <3 — it magically interfaces with everything, and with hlint it taught me about more than one function lurking in the library I never knew about. Otherwise, the linked posts describe everything here perfectly, except for the fact that getting the Vim commands to work requires separate plugins specifically for interfacing with the tools that aren't mentioned. They're easy to find, though.
Other personal selections:
data-memocombinators(a significant number of my solutions for stuff like Project Euler and Brilliant.org depend on this)idris(see much earlier in this post)vector(the StackOverflow consensus is that this is nicer than Data.Array, apparently, and it’s a must-have if I ever need a speedy destructive algorithm)parsec(a recent project of mine depends on this; besides it’s just cool)transformers(? this may come with the platform by default, or at least a dependency of something above)
Alas, there’s a version dependency of Idris that clashes with Criterion. Note to self next time: get a cabal sandbox working. But that’s enough adventuring for the weekend before midterms, so I’m stopping here.