government / examples / hanoi.gov.lisp

@ d87504922ed319f2e3fd703dca40b7219eeeada1 | history


; hanoi.gov.lisp: the moves that solve the Towers of Hanoi.
;
; To move n disks from one peg to another, move the top n-1 out of the way
; onto the spare peg, move the largest disk, then move the n-1 back on top
; of it. The answer is data: a list of (from to) moves, built from quoted
; symbols.

(define append
  (lambda (a b)
    (if (== a '())
        b
        (cons (car a) (append (cdr a) b)))))

(define move
  (lambda (from to)
    (cons from (cons to '()))))

(define hanoi
  (lambda (n from to spare)
    (if (== n 0)
        '()
        (append (hanoi (- n 1) from spare to)
                (cons (move from to)
                      (hanoi (- n 1) spare to from))))))

(hanoi 3 'left 'right 'middle)

(define length
  (lambda (l)
    (if (== l '())
        0
        (+ 1 (length (cdr l))))))

; n disks always take 2^n - 1 moves.
(length (hanoi 10 'left 'right 'middle))