Hanoi States

hanoi-states.clj

(require '[clojure.test :refer :all])

(defn hanoi-states [n]
  (letfn [
    (hanoi [s t d n]
      (if (zero? n) '()
          (concat (hanoi s d t (dec n))
                  (list
                    (condp = [s d]
                      [0 2] (fn [[[h & a] b c]] [(if a a '()) b (cons h c)])
                      [0 1] (fn [[[h & a] b c]] [(if a a '()) (cons h b) c])
                      [1 0] (fn [[a [h & b] c]] [(cons h a) (if b b '()) c])
                      [1 2] (fn [[a [h & b] c]] [a (if b b '()) (cons h c)])
                      [2 1] (fn [[a b [h & c]]] [a (cons h b) (if c c '())])
                      [2 0] (fn [[a b [h & c]]] [(cons h a) b (if c c '())])))
                  (hanoi t s d (dec n)))))]
    (map first
      (take-while (fn [[x f :as xf]] xf)
        (iterate (fn [[x [f & fs]]] (if f [(f x) fs]))
          [[(range 1 (inc n)) '() '()]
           (hanoi 0 1 2 n)])))))

(deftest hanoi-states-test
  (are [result expected] (= result expected)
    (hanoi-states 3) '([(1 2 3)    ()      ()]
                       [  (2 3)    ()     (1)]
                       [    (3)   (2)     (1)]
                       [    (3) (1 2)      ()]
                       [     () (1 2)     (3)]
                       [    (1)   (2)     (3)]
                       [    (1)    ()   (2 3)]
                       [     ()    () (1 2 3)])
    (hanoi-states 4) '([(1 2 3 4)      ()        ()]
                       [  (2 3 4)     (1)        ()]
                       [    (3 4)     (1)       (2)]
                       [    (3 4)      ()     (1 2)]
                       [      (4)     (3)     (1 2)]
                       [    (1 4)     (3)       (2)]
                       [    (1 4)   (2 3)        ()]
                       [      (4) (1 2 3)        ()]
                       [       () (1 2 3)       (4)]
                       [       ()   (2 3)     (1 4)]
                       [      (2)     (3)     (1 4)]
                       [    (1 2)     (3)       (4)]
                       [    (1 2)      ()     (3 4)]
                       [      (2)     (1)     (3 4)]
                       [       ()     (1)   (2 3 4)]
                       [       ()      () (1 2 3 4)])))