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 ...


I got it!
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!

Google Treasure Hunt in Lisp
2008-06-03 10:41 - simon

I agree that those are very nice puzzles. I have solutions for some of them in (Common) Lisp. For the first puzzle, "robot", you can use the natural recursive formulation if you use "memoization" to avoid the exponential complexity. See

Post a comment:

  If you do not have an account to log in to yet, register your own account. You will not enter any personal info and need not supply an email address.

You may use Markdown syntax in the comment, but no HTML. Hints:

If you are attempting to contact me, ask me a question, etc, please send me a message through the contact form rather than posting a comment here. Thank you. (If you post a comment anyway when it should be a message to me, I'll probably just delete your comment. I don't like clutter.)