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.