Update 1: a number of people over at Hacker News have pointed out major inefficenies in my solution, and various better ways of solving this. At this point, I think it’s fair to say the tldr; is that while my bad solution was prohibitevly slow in Ruby, Go could run it with ease. If you are like me and don’t always come up with the best solutions, you may want to consider other languages for these kinds of situations too.
Update 2: I had originally assumed I had a bug in my solution that was causing the Go program to have the incorrect output, but a Hacker News commenter pointed out that it was probably the integer type I was using. The version of go I was originally running, 1.0.3, defaults integers to 32 bit, whereas version 1.1 and above defaults to 64 bit. After updating my version of Go, this program generates the correct output, but now takes about 2 minutes and 47 seconds to run. Not as compelling an arument as before, but well within the limits required.
This past weekend, I participated in the qualification round of Google Code Jam 2013. It was year is my third time participating, and the third time that I have used Ruby as my primary language.
Since I have no prior experience in actually being competitive in programming competitions and I use Ruby at my day job (it’s one of the that drew me there), I’d never given my language choice much of a second thought. Sure, I knew Ruby wasn’t going to be zomg fast, but I always assumed that if I chose the right solution and wrote in an efficient manner (memoizing, storing values/lookups that would be used later, limiting search spaces, etc), my ability to write code quickly and concisely mattered more than sheer processing speed.
I was wrong.