hanoi-tower.clj

(defn hanoi-tower
  [n]
  (let [steps (dec (int (Math/pow 2 n)))
        odd-n? (not= 0 (mod n 2))]
    (letfn [(legal-move? [from to]
              (or (empty? to)
                  (and (not (empty? from))
                       (< (peek from) (peek to)))))
            (move [[from to spare :as state] n]
              (let [new-state (if odd-n?
                                (condp = (mod n 3)
                                  1 (if (legal-move? from to)
                                      [(pop from) (conj to (peek from)) spare]
                                      [(conj from (peek to)) (pop to) spare])

                                  2 (if (legal-move? from spare)
                                      [(pop from) to (conj spare (peek from))]
                                      [(conj from (peek spare)) to (pop spare)])

                                  0 (if (legal-move? spare to)
                                      [from (conj to (peek spare)) (pop spare)]
                                      [from (pop to) (conj spare (peek to))]))
                                (condp = (mod n 3)
                                  1 (if (legal-move? from spare)
                                      [(pop from) to (conj spare (peek from))]
                                      [(conj from (peek spare)) to (pop spare)])

                                  2 (if (legal-move? from to)
                                      [(pop from) (conj to (peek from)) spare]
                                      [(conj from (peek to)) (pop to) spare])

                                  0 (if (legal-move? spare to)
                                      [from (conj to (peek spare)) (pop spare)]
                                      [from (pop to) (conj spare (peek to))])))]
                (comment (println (str n "/" steps) "-" state "->" new-state))
                (if (= n steps)
                  (cons new-state nil)
                  (lazy-seq (cons new-state (move new-state (inc n)))))))]
      (let [from (vec (reverse (range 1 (inc n))))
            init-state [from [] []]]
        (lazy-seq (cons init-state (move init-state 1)))))))

(defn hanoi-tower-print
  [s]
  (let [column-length (* 2 (+ 2 (count (first s))))
        pattern (format "%1$s %1$s %1$s" (str "%-" column-length "s"))]
    (doseq [state s]
      (Thread/sleep 10)
      (println (apply format pattern state)))))

(hanoi-tower-print (hanoi-tower 3))
[3 2 1] [] []
[3 2] [1] []
[3] [1] [2]
[3] [] [2 1]
[] [3] [2 1]
[1] [3] [2]
[1] [3 2] []
[] [3 2 1] []
=> nil

(hanoi-tower-print (hanoi-tower 4))
[4 3 2 1] [] []
[4 3 2] [] [1]
[4 3] [2] [1]
[4 3] [2 1] []
[4] [2 1] [3]
[4 1] [2] [3]
[4 1] [] [3 2]
[4] [] [3 2 1]
[] [4] [3 2 1]
[] [4 1] [3 2]
[2] [4 1] [3]
[2 1] [4] [3]
[2 1] [4 3] []
[2] [4 3] [1]
[] [4 3 2] [1]
[] [4 3 2 1] []
=> nil