#lang racket

; Towers of Hanoi Solver
; author: Robert Keller

(require htdp/testing)
(require (lib "trace.rkt"))

; solve generates a list of moves that
; solve the N-disc towers problem
; with From To and Other being symbols for
; three spindles

(define (solve N From To Other)
  (if (= N 0)
      '()
      (append
       (solve (- N 1) From Other To)
       (list (list 'move From To))
       (solve (- N 1) Other To From))))

(check-expect (solve 1 'A 'B 'C) '((move A B)))
(check-expect (solve 2 'A 'B 'C) '((move A C) (move A B) (move C B)))
(check-expect (solve 3 'A 'B 'C) '((move A B) (move A C) (move B C) (move A B) (move C A) (move C B) (move A B)))

; simulate simulates a list of moves, such as generated by solve
; create a list of states from the start state to the end

(define (simulate Moves A B C)
  (cons (list (list A B C))
   (if (null? Moves)
      null
      (let* (
            (firstMove (first Moves))
            (restMoves (rest Moves))
            (FromTo    (rest firstMove))
            )
        (cond
          [(equal? FromTo '(A B)) (simulate restMoves (rest A)           (cons (first A) B) C)                 ]
          [(equal? FromTo '(A C)) (simulate restMoves (rest A)           B                  (cons (first A) C))]
          [(equal? FromTo '(B C)) (simulate restMoves A                  (rest B)           (cons (first B) C))]
          [(equal? FromTo '(B A)) (simulate restMoves (cons (first B) A) (rest B)           C)                 ]
          [(equal? FromTo '(C A)) (simulate restMoves (cons (first C) A) B                  (rest C))          ]
          [(equal? FromTo '(C B)) (simulate restMoves A                  (cons (first C) B) (rest C))          ]
          [else "something is wrong"])))))
                                
        
(check-expect (simulate (solve 3 'A 'B 'C) '(1 2 3) '() '())
  '((((1 2 3) () ()))
  (((2 3) (1) ()))
  (((3) (1) (2)))
  (((3) () (1 2)))
  ((() (3) (1 2)))
  (((1) (3) (2)))
  (((1) (2 3) ()))
  ((() (1 2 3) ()))))
       
(check-expect (simulate (solve 4 'A 'B 'C) '(1 2 3 4) '() '())
'((((1 2 3 4) () ()))
  (((2 3 4) () (1)))
  (((3 4) (2) (1)))
  (((3 4) (1 2) ()))
  (((4) (1 2) (3)))
  (((1 4) (2) (3)))
  (((1 4) () (2 3)))
  (((4) () (1 2 3)))
  ((() (4) (1 2 3)))
  ((() (1 4) (2 3)))
  (((2) (1 4) (3)))
  (((1 2) (4) (3)))
  (((1 2) (3 4) ()))
  (((2) (3 4) (1)))
  ((() (2 3 4) (1)))
  ((() (1 2 3 4) ()))))

(check-expect (simulate (solve 5 'A 'B 'C) '(1 2 3 4 5) '() '())
'((((1 2 3 4 5) () ()))
  (((2 3 4 5) (1) ()))
  (((3 4 5) (1) (2)))
  (((3 4 5) () (1 2)))
  (((4 5) (3) (1 2)))
  (((1 4 5) (3) (2)))
  (((1 4 5) (2 3) ()))
  (((4 5) (1 2 3) ()))
  (((5) (1 2 3) (4)))
  (((5) (2 3) (1 4)))
  (((2 5) (3) (1 4)))
  (((1 2 5) (3) (4)))
  (((1 2 5) () (3 4)))
  (((2 5) (1) (3 4)))
  (((5) (1) (2 3 4)))
  (((5) () (1 2 3 4)))
  ((() (5) (1 2 3 4)))
  (((1) (5) (2 3 4)))
  (((1) (2 5) (3 4)))
  ((() (1 2 5) (3 4)))
  (((3) (1 2 5) (4)))
  (((3) (2 5) (1 4)))
  (((2 3) (5) (1 4)))
  (((1 2 3) (5) (4)))
  (((1 2 3) (4 5) ()))
  (((2 3) (1 4 5) ()))
  (((3) (1 4 5) (2)))
  (((3) (4 5) (1 2)))
  ((() (3 4 5) (1 2)))
  (((1) (3 4 5) (2)))
  (((1) (2 3 4 5) ()))
  ((() (1 2 3 4 5) ()))))

(generate-report)