@ b16190dee4ae781544f8119bec44f00f5224c810 | 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))