# Towers of Hanoi

``````

In [1]:

n = 4

``````
``````

Out[1]:

4

``````
``````

In [2]:

A = collect(n:-1:1)
B = []
C = []

``````
``````

Out[2]:

0-element Array{Any,1}

``````
``````

In [3]:

function hanoi_rec(n, source, target, aux)
if n == 0
return
end
hanoi_rec(n-1, source, aux, target)
push!(target, pop!(source))
println(A, ", ", B, ", ", C)
hanoi_rec(n - 1, aux, target, source)
end

``````
``````

Out[3]:

hanoi_rec (generic function with 1 method)

``````
``````

In [4]:

hanoi_rec(n, A, B, C)

``````
``````

[4, 3, 2], Any[], Any[1]
[4, 3], Any[2], Any[1]
[4, 3], Any[2, 1], Any[]
[4], Any[2, 1], Any[3]
[4, 1], Any[2], Any[3]
[4, 1], Any[], Any[3, 2]
[4], Any[], Any[3, 2, 1]
Int64[], Any[4], Any[3, 2, 1]
Int64[], Any[4, 1], Any[3, 2]
[2], Any[4, 1], Any[3]
[2, 1], Any[4], Any[3]
[2, 1], Any[4, 3], Any[]
[2], Any[4, 3], Any[1]
Int64[], Any[4, 3, 2], Any[1]
Int64[], Any[4, 3, 2, 1], Any[]

``````
``````

In [5]:

A = collect(n:-1:1)
B = []
C = []

``````
``````

Out[5]:

0-element Array{Any,1}

``````
``````

In [6]:

function hanoi_it_1(source, target, aux)
n = length(source)
state = 4
nr = 2^n - 1
if length(source) % 2 == 0
state = 3
end
for i in 1:nr
if state == 4
from = source
to = target
elseif state == 3
from = source
to = aux
elseif state == 5
from = target
to = aux
end
if isempty(to) || (!isempty(from) && from[end] < to[end])
push!(to, pop!(from))
else
push!(from, pop!(to))
end
println(A, ", ", B, ", ", C)
if n % 2 == 0
state += 1
if state == 6
state = 3
end
else
state -= 1
if state == 2
state = 5
end
end
end
end

``````
``````

Out[6]:

hanoi_it_1 (generic function with 1 method)

``````
``````

In [7]:

hanoi_it_1(A, B, C)

``````
``````

3, 15
[4, 3, 2], Any[], Any[1]
[4, 3], Any[2], Any[1]
[4, 3], Any[2, 1], Any[]
[4], Any[2, 1], Any[3]
[4, 1], Any[2], Any[3]
[4, 1], Any[], Any[3, 2]
[4], Any[], Any[3, 2, 1]
Int64[], Any[4], Any[3, 2, 1]
Int64[], Any[4, 1], Any[3, 2]
[2], Any[4, 1], Any[3]
[2, 1], Any[4], Any[3]
[2, 1], Any[4, 3], Any[]
[2], Any[4, 3], Any[1]
Int64[], Any[4, 3, 2], Any[1]
Int64[], Any[4, 3, 2, 1], Any[]

``````
``````

In [8]:

A = collect(n:-1:1)
B = []
C = []

``````
``````

Out[8]:

0-element Array{Any,1}

``````
``````

In [9]:

function hanoi_it_2(source, target, aux)
prev = source
if length(source) % 2 == 0
push!(aux, pop!(source))
actual = aux
next = target
else
push!(target, pop!(source))
actual = target
next = aux
end
println(A, ", ", B, ", ", C)
while !(isempty(source) && isempty(aux))
if isempty(next) || (!isempty(prev) && prev[end] < next[end])
push!(next, pop!(prev))
else
push!(prev, pop!(next))
end
println(A, ", ", B, ", ", C)
push!(next, pop!(actual))
println(A, ", ", B, ", ", C)
prev, actual, next = actual, next, prev
end
end

``````
``````

Out[9]:

hanoi_it_2 (generic function with 1 method)

``````
``````

In [10]:

hanoi_it_2(A, B, C)

``````
``````

[4, 3, 2], Any[], Any[1]
[4, 3], Any[2], Any[1]
[4, 3], Any[2, 1], Any[]
[4], Any[2, 1], Any[3]
[4, 1], Any[2], Any[3]
[4, 1], Any[], Any[3, 2]
[4], Any[], Any[3, 2, 1]
Int64[], Any[4], Any[3, 2, 1]
Int64[], Any[4, 1], Any[3, 2]
[2], Any[4, 1], Any[3]
[2, 1], Any[4], Any[3]
[2, 1], Any[4, 3], Any[]
[2], Any[4, 3], Any[1]
Int64[], Any[4, 3, 2], Any[1]
Int64[], Any[4, 3, 2, 1], Any[]

``````