Wednesday, May 28, 2008

Google Treasure Hunt 2008: Puzzle 1 (robot) solution

Google Treasure Hunt is a sequence of (four?) nice puzzles, three of which have been published so far. Since everybody blogs how they solved them, here are my solutions (so far).


;;; "Robot" puzzle
;;;
;;; Author: Simon Leinen
;;; Date created: 18-May-2008
;;;
;;; There's an NxM (N cases wide and M cases high) grid with the robot
;;; in the upper left corner and a treasure in the lower right. The
;;; robot can only go RIGHT or DOWN. How many possible distinct paths
;;; are there for the robot to reach the treasure?
;;;
;;; Solution:
;;;
;;; If the grid is 1xM or Nx1, there is only one possibility. This is
;;; our stop condition: Npaths(1,M) = 1, Npaths(N,1) = 1.
;;;
;;; Otherwise, M>1 and N>1. So the robot can go right and take one of
;;; Npaths(N-1,M) paths to the destination, or go down and take one of
;;; Npaths(N,M-1) paths.
;;;
;;; It is trivial to write a recursive function according to this
;;; definition, but the function will be very inefficient, because it
;;; generates an exponential explosion of recursive calls - most
;;; invocations will generate two new invocations -> chain reaction.
;;;
;;; This is the same as a certain definition of the Fibonacci series
;;; (which I personally don't find that natural), and a standard way
;;; to solve this is through "memoization", i.e. remembering the
;;; results for all calls that have terminated. There are many
;;; standard libraries for this, but I don't know where to find one
;;; and how to use it, so I'll roll my own.
;;;
;;; Thankfully, Lisp has "bignums", so we don't have to worry too much
;;; about how large the result may get.
;;;
;;; I could have improved efficiency somewhat by ordering width and
;;; height, but the code is Good Enough as is.

(in-package :cl-user)

(defvar +memo-npaths+
(make-hash-table :test #'equal))

(defmacro with-memoization ((&rest arglist) memo-form form)
(let ((result-var (gensym "result"))
(memo-var (gensym "memo")))
`(let* ((,memo-var ,memo-form)
(,result-var (gethash (list ,@arglist) ,memo-var)))
(or ,result-var
(setf (gethash (list ,@arglist) ,memo-var)
,form)))))

(defun npaths (width height)
(with-memoization (width height)
+memo-npaths+
(npaths-internal width height)))

(defun npaths-internal (width height)
(if (or (zerop width) (zerop height))
1
(+ (npaths (1- width) height)
(npaths width (1- height)))))

1 comment:

Anonymous said...

or the more simple method. The robot needs to travel height-1 number of downs and width-1 number of rights.

thus the number of rearrangements of height-1 objects and different width-1 objects is just:

(h-1+w-1)!/((h-1)!(w-1)!)