Skip to content

Instantly share code, notes, and snippets.

@kohyama
Last active October 19, 2017 09:05
Show Gist options
  • Save kohyama/2848379 to your computer and use it in GitHub Desktop.
Save kohyama/2848379 to your computer and use it in GitHub Desktop.
Hanoi States
(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)])))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment