guitsaru

I’m currently learning Haskell by reading the book Real World Haskell. Usually, when I learn a new language, I like to play around with some programming puzzles online at places like a problem from the Google Code Jam archives.

I started this with a brute force solution, actually simulating a chain of snappers. It worked well for the small input set, but predictably failed on the large input set. I started analyzing the problem and found an equation that solves it based on the number of snappers and the number of snaps which now solves the problem in O(1) time. The equation I came up with is different than the given analysis (which makes use of xor), but I’m still happy with it.

All of the magic is in the isOn function. The rest is input and output management.