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[]