;
; Towers of Hanoi
;
; Copyright © 2016 Keith Packard <keithp@keithp.com>
;
; This program is free software; you can redistribute it and/or modify
; it under the terms of the GNU General Public License as published by
; the Free Software Foundation, either version 2 of the License, or
; (at your option) any later version.
;
; This program is distributed in the hope that it will be useful, but
; WITHOUT ANY WARRANTY; without even the implied warranty of
; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
; General Public License for more details.
;

					; ANSI control sequences

(define (move-to col row)
  (for-each display (list "\033[" row ";" col "H"))
  )

(define (clear)
  (display "\033[2J")
  )

(define (display-string x y str)
  (move-to x y)
  (display str)
  )

(define (make-piece num max)
					; A piece for position 'num'
					; is num + 1 + num stars
					; centered in a field of max *
					; 2 + 1 characters with spaces
					; on either side. This way,
					; every piece is the same
					; number of characters

  (define (chars n c)
    (if (zero? n) ""
      (+ c (chars (- n 1) c))
      )
    )
  (+ (chars (- max num 1) " ")
     (chars (+ (* num 2) 1) "*")
     (chars (- max num 1) " ")
     )
  )

(define (make-pieces max)
					; Make a list of numbers from 0 to max-1
  (define (nums cur max)
    (if (= cur max) ()
      (cons cur (nums (+ cur 1) max))
      )
    )
					; Create a list of pieces

  (map (lambda (x) (make-piece x max)) (nums 0 max))
  )

					; Here's all of the towers of pieces
					; This is generated when the program is run

(define towers ())

					; position of the bottom of
					; the stacks set at runtime
(define bottom-y 0)
(define left-x 0)

(define move-delay 25)

					; Display one tower, clearing any
					; space above it

(define (display-tower x y clear tower)
  (cond ((= 0 clear)
	 (cond ((not (null? tower))
		(display-string x y (car tower))
		(display-tower x (+ y 1) 0 (cdr tower))
		)
	       )
	 )
	(else 
	 (display-string x y "                    ")
	 (display-tower x (+ y 1) (- clear 1) tower)
	 )
	)
  )

					; Position of the top of the tower on the screen
					; Shorter towers start further down the screen

(define (tower-pos tower)
  (- bottom-y (length tower))
  )

					; Display all of the towers, spaced 20 columns apart

(define (display-towers x towers)
  (cond ((not (null? towers))
	 (display-tower x 0 (tower-pos (car towers)) (car towers))
	 (display-towers (+ x 20) (cdr towers)))
	)
  )

					; Display all of the towers, then move the cursor
					; out of the way and flush the output

(define (display-hanoi)
  (display-towers left-x towers)
  (move-to 1 23)
  (flush-output)
  (delay move-delay)
  )

					; Reset towers to the starting state, with
					; all of the pieces in the first tower and the
					; other two empty

(define (reset-towers len)
  (set! towers (list (make-pieces len) () ()))
  (set! bottom-y (+ len 3))
  )

					; Move a piece from the top of one tower
					; to the top of another

(define (move-piece from to)

					; references to the cons holding the two towers

  (define from-tower (list-tail towers from))
  (define to-tower (list-tail towers to))

					; stick the car of from-tower onto to-tower

  (set-car! to-tower (cons (caar from-tower) (car to-tower)))

					; remove the car of from-tower

  (set-car! from-tower (cdar from-tower))
  )

					; The implementation of the game

(define (_hanoi n from to use)
  (cond ((= 1 n)
	 (move-piece from to)
	 (display-hanoi)
	 )
	(else
	 (_hanoi (- n 1) from use to)
	 (_hanoi 1 from to use)
	 (_hanoi (- n 1) use to from)
	 )
	)
  )

					; A pretty interface which
					; resets the state of the game,
					; clears the screen and runs
					; the program

(define (hanoi len)
  (reset-towers len)
  (clear)
  (display-hanoi)
  (_hanoi len 0 1 2)
  #t
  )