Escape From Zurg - A Scheme Solution

I came across this paper, which offers up a fun programming problem. Mainly:

Buzz, Woody, Rex, and Hamm have to escape from Zurg.

They merely have to cross one last bridge before they are free. However, the bridge is fragile and can hold at most two of them at the same time. Moreover, to cross the bridge a flashlight is needed to avoid traps and broken parts.

The problem is that our friends have only one flashlight with one battery that lasts for only 60 minutes (this is not a typo: sixty). The toys need different times to cross the bridge (in either direction):

TOY    TIME
Buzz   5 minutes
Woody 10 minutes
Rex   20 minutes
Hamm  25 minutes

Since there can be only two toys on the bridge at the same time, they cannot cross the bridge all at once. Since they need the flashlight to cross the bridge, whenever two have crossed the bridge, somebody has to go back and bring the flashlight to those toys onthe other side that still have to cross the bridge.

The problem now is: In which order can the four toys cross the bridge in time (thatis, in 60 minutes) to be saved from Zurg?

Here's a solution to the problem in Scheme. Note, it makes use of the very cool amb operator.

;; Inspired by:
;;  http://web.engr.oregonstate.edu/~erwig/papers/Zurg_JFP04.pdf
;;  http://web.engr.oregonstate.edu/~erwig/zurg/
;;
;; amb stuff
;;  http://mitpress.mit.edu/sicp/full-text/sicp/book/node88.html
;;  http://docs.mandragor.org/files/Programming_languages/Scheme/Teach_Yourself_Scheme_in_Fixnum_Days_en/tysch016.htm
;;
(require (planet "amb.scm" ("wmfarr" "amb.plt" 1 0))) 

(define (require x)
  (if (not x)
      (amb)))

(define (pick-one elts)
  (require (> (length elts) 0))
  (amb (car elts) (pick-one (cdr elts))))

;; Setup the rules for the game
(define all-toys '(buzz woody rex hamm))

; How much time does it cost for each toy?
(define (cost who)
  (cond ((assq who '((buzz . 5)
                     (woody . 10)
                     (rex . 20)
                     (hamm . 25))) => cdr)
        (else (error (format "Can't calculate the cost of ~a, unknown type" who)))))


;; The actual solution to the problem.
(define (cross toys clock)
  ;; Cross the toys from left to right.
  (define (cross-left-to-right left-side right-side remaining moves)
    (cond ((null? left-side) (cons remaining (reverse moves)))
          (else
           (let* ((t1 (pick-one left-side))
                  (t2 (pick-one left-side))
                  (time-used  (max (cost t1) (cost t2))))
             (require (not (eq? t1 t2)))
             (require (>= (- remaining time-used) 0))
             (cross-right-to-left (remove t2 (remove t1 left-side))
                                  (append (list t1 t2) right-side)
                                  (- remaining time-used)
                                  (cons (list t1 t2) moves))))))
  ;; Cross the toys the other way around
  (define (cross-right-to-left left-side right-side remaining moves)
    (cond ((null? left-side) (cons remaining (reverse moves)))
          (else
           (let* ((t (pick-one right-side))
                  (time-used (cost t)))
             (require (>=  (- remaining time-used) 0))
             (cross-left-to-right (cons t left-side)
                                  (remove t right-side)
                                  (- remaining time-used)
                                  (cons (list t) moves))))))
  
  ;; Actually kick off the process by sending them from 
  ;; the left side to the right
  (with-amb
   (cross-left-to-right toys '() clock '())))

;; Go!
(cross all-toys 60)

Personally, I find this solution cleaner than both the Haskell and Prolog solution - but that's probably more what I'm comfortable with.

Hmm, I wonder, what's a good way to measure the different solutions?