Google Treasure Hunt 2008
2008-05-18 15:48 - General
Things have been quiet here recently. I mentioned that I recently purchased SICP, and I've read it all by now. It was interesting, but hard to apply in any meaningful way. Lisp doesn't really solve the problems I'm generally faced with. Or at least, I don't understand how to make it do so.
Well, now, I've just discovered the Google Treasure Hunt 2008. I've never heard of one in a prior year, but based on the first question (the only I've seen so far), it's the fun sort of puzzle I might really enjoy. To paraphrase, there's a robot on a board of a particular size. It can only move down or right. How many distinct paths can it take to get from one corner to the other?
Upon seeing this question, I immediately recognized a pattern similar to that of the Eight Queens puzzle, which I just saw as an exercise in the SICP book. So, I'm setting out now to attempt to apply some of my scheme skills. I wonder how much of it really sunk in ...
2008-05-19 00:12 - arantius
So, I threw together a scheme program that calculated the number. I should have realized long before I got to this point, but the exponentially-growing size of this problem, and the exponents involved, made my initial approach rather laughable. I refined it a few times over, but only managed to divide the time in half and again, or so. I've no idea how long it would have taken that simple approach to work, but I was able to see and derive the pattern, from doing that work.
Maybe I should have seen the pattern at first. It was rather simple, but I was excited to try to make use of some new knowledge. Anyways, after hitting some walls with the Scheme language, which I'm not very familiar with, I managed to throw a simpler script together in PHP (just because I know it well, and I know it has bcmath), and ... I got the right answer. Yippee!