Transcript of me solving - "The Tower of Hanoi".

I felt like solving a problem I had never solved before, I took up "The Tower of Hanoi". It is not that I had never heard or seen this problem before but I had never tried to solve it myself or even looked at solution. I was sitting at office with my friend Krishnaprasad Shivdasan, whom we normally refer as KP. He gave me a book written by Ronald L. Graham, Donald E. Knuth & Oren Patashnik, called Concrete Mathematics. The first chapter in the book is on "Recurrent Problems", with first reference to "The Tower of Hanoi".

Problem statement as in the book:


Let's look first at a neat little puzzle called the Tower of Hanoi, invented by the French mathematician Edouard Lucas in 1883. We are given a tower of eight disks, initially stacked in decreasing size on one of three pegs:

The objective is to transfer the entire tower to one of the other pegs, moving only one disk at a time and never moving a larger one onto a smaller.


Just reading this and the next paragraph and I stared with solving the problem, with a pen and a paper. The next paragraph that I read is also interesting.


Lucas furnished his toy with a romantic legend about a much larger Gold -wow. Tower of Brahma, which supposedly has 64 disks of pure gold resting on three diamond needles. At the beginning of time, he said, God placed these golden disks on the first needle and ordained that a group of priests should transfer them to the third, according to the rules above. The priests reportedly work day and night at their task. When they finish, the Tower will crumble and the world will end.


"The Tower of Brahma", Brahma is an Indian God. Now it interests me even more.

Trial runs now:

To make it easy myself to understand, I stared with small numbers of disks.

Let,
n be number of disks
m be number of moves -- this is what we’ll record.

(n=0)
Ha ha ha, without doing anything was able to say it would take no moves.
Thus, (m=0)

(n=1)
This just takes one move. Move the disk from first to last. To record my moves I would just name the pegs as A, the starting peg, B the swap peg, C the target peg.

1:AC

Thus, (m=1)

(n=2)
This is also went easy, move smallest disk to peg B, then move other disk to Peg C and then place the smallest disk over the other disk. To make it easy for us to record let us name smallest disk as 1 and other in the increasing sequence.

1:AB-C
2:A-C-

(“-“means no move for this disk)

Thus, (m=3)

(n=3)
This also goes fine.

1:AC-B-A-C
2:A-B---C-
3:A---C---

Thus, (m=7)

Now, I saw something interesting, there are two patterns in with these disks are moving, ABCA and ACBA. Let us see if this holds well with n=4.

(n=4)

1:AB-C-A-B-C-A-B-C
2:A-C---B---A---C-
3:A---B-------C---
4:A-------C-------

Yes, moving pattern still holds good.
(m=15)

Getting the above solution took me some good time. I failed to get it in the first run. It was going too astray, so I stared again. Anyway I managed to get the solution in 15 moves eventually. This also has the same pattern going on. Now there is something else is quite evident, biggest disk always moves A to C and it only gets to move once.

By now I have one thing clear in my mind, for first time move (n-1)th heap on B or to take it a step ahead move (n-2)th heap on C, and so on.

Now, let us try n=5.

(n=5)

1: AC-B-A-C-B-A-C-B-A-C-B-A-C-B-A-C
2: A-B---C---A---B---C---A---B---C-
3: A---C-------B-------A-------C---
4: A-------B---------------C-------
5: A---------------C---------------

(m=31)

This also follows our pattern ABCA and ACBA. By now I can see another interesting sequence for number of moves per disk.
For,
(n=5)
Number of moves 5th disk are 1
4: 2
3: 4
2: 8
1: 16

(n=4)
4: 1
3: 2
2: 4
1: 8

(n=3)
3: 1
2: 2
1: 4

(n=2)
2: 1
1: 2

(n=1)
1: 1

And this should and does sum up to 31, 15, 7, 3, and 1 respectively. Now this is interesting these numbers are from a series 2^0, 2^1, 2^2, 2^3 and 2^4. And most of us know Sum of “X^Y” for Y=0 to n-1 is “(X^n) – 1”.

Thus number of moves need to move an “n” disk heap from A to C are “(2^n) -1”. That’s “2^0 - 1 = 0”, “2^1 - 1 = 1”, “2^2 - 1 = 3”, “2^3 - 1 = 7”, “2^4 - 1 = 15”and “2^5 - 1 = 31”.

Now I am In search of an algorithm that can be applied to any number of disks.
Let us try moving 4 disks, that is:

(A: 4321, B: -, C: -)
Move 4321 heap on C, from A.
Means,
Move 321 heap on B, from A
Move 4 to C, from A.
Move 321 heap on C, from B, over 4.
(A: -, B: -, C: 4321)

(A: 4321, B: -, C: -)
Move 321 heap on B, from A
Means,
Move 21 heap on C, from A.
Move 3 to B, from A.
Move 21 heap on B, from C. over 3.
(A: 4, B: 321, C: -)

(A: -, B: 321, C: 4)
Move 321 heap on C, from B, over 4.
Means,
Move 21 heap on A, from B.
Move 3 to C, from B, over 4.
Move 21 heap on C, from A, over 34.
(A: -, B: -, C: 4321)

(A: 4321, B: -, C: -)
Move 21 heap on C, from A.
Means,
Move 1 to B, from A.
Move 2 to C, from A.
Move 1 to C, over 2, from B.
(A: 43, B: -, C: 21)

(A: 4, B: 3, C: 21)
Move 21 heap on B, from C. over 3.
Means,
Move 1 to A, from C, over 4.
Move 2 to B, from C, over 3,
Move 1 to B, from A, over 23
(A: 4, B: 321, C: -)

(A: -, B: 321, C: 4)
Move 21 heap on A, from B.
Means,
Move 1 to C, from B, over 4.
Move 2 to A, from B.
Move 1 to A, from C, over 2.
(A: 21, B: 3, C: 4)

(A: 21, B: -, C: 43)
Move 21 heap on C, from A, over 34.
Means,
Move 1 to B, from A.
Move 2 to C, from A, over 34.
Move 1 to C, from B, over 234.
(A: -, B: -, C: 4321)

So, we can see something in this move pattern that is we have 3 classifications of the pegs. Namely, resting peg, swap peg, and target peg let us denote those as R(n), S(n), and T(n) respectively for nth disk.


Now we can say (more generalized form),

Move nth heap on T (n), from R (n)
Means,
Move (n-1)th heap on S(n), from R(n)
Move n to T(n), from R(n).
Move (n-1)th heap on T(n), from S(n), over n.

Move 0th heap on T (0), from R (0).
Means,
Move nothing


Now we’ll just leave this recursive solution as is, and look for some patterns, knowing recursive solutions are slow.

Let me try a non-recursive solution also and remember we had a Pattern ABCA, and ACBA there is another pattern of moves. Smallest disk moves every alternate move, that is starting from the first move and first move is always for the smallest.

Moves of disk,
1: 1-3-5-7-9-11 and so on and so forth.
2: -2---6---10---14 and so on and so forth.
3: ---4-------12-------18 and so on and so forth.
4: -------8---------------24 and so on and so forth.

--

Logically nth, disk should first move after (n-1)th heap is moved on S(n) and that’s “(2^(n-1)-1)+1”th move. See if “321” formation has to happen on B for 4 to get on C. We know by now it will take 7 moves before 4 moves. Thus it is “2^(n-1)”th move or for 4 its 8th move. So the first move of any disk isn’t a function of number of disks.


First move of nth disk happens at “2^(n-1)”th move of the disk system.


Let us see when nth disk will move the second time, let us take the moves of moving 4 disks.

(A:4321, B: -, C: -)
(A:432, B: 1, C: -)
(A:43, B: 1, C: 2)*
(A:43, B: -, C: 21)
(A:-4, B: 3, C: 21)
(A:41, B: 3, C: 2)
(A:41, B: 32, C: -)*
(A:4, B: 321, C: -)
(A:-, B: 321, C: 4)
(A:-, B: 32, C: 41)
(A:2, B: 3, C: 41)*
(A:21, B: 3, C: 4)
(A:21, B: -, C: 43)
(A:2, B: 1, C: 43)
(A: -, B: 1, C: 432)*
(A: -, B: -, C: 4321)

(“*” marks the move of disk 2)

        1
        2
4       3
+-------+-------+---


        1
        2
        3       4
+-------+-------+---

--

See the recursive algorithm we made, that says move “n-1”th heap on S(n), and then move nth disk to T(n).

                1
                2
                3
                4
+-------+-------+---

--

And later move “n-1”th heap to T(n).

3               1
4               2
+-------+-------+---

                1
4       3       2
+-------+-------+---
(First time “n-1”th disk moves is after “n-2”th heap was moved to T(n)=C )

        1
        2
4       3 
+-------+-------+---
(Moving “n-2”th heap over “n-1”th disk)

        1
        2
        3       4
+-------+-------+---
(nth disk moves to T(n) )

1
2       3       4
+-------+-------+---
(“n-2”th heap again moves to R (n) to free “n-1”th disk to move to T(n) )

1               3
2               4
+-------+-------+---
(second time “n-1”th disk moves)

--

Meanwhile, first time “n-1”th disk moved was “2^(n-2)” after that it took ( ( 2^(n-2) ) - 1) moves to get “n-2”th heap over it. Then one move for n to move to T(n). Then ( ( 2^(n-2) ) - 1) moves to set “n-1”th disk free to move on nth disk, that is making “n-2”th heap on R(n). Thus moves after first move are “ ( ( 2^(n-2) ) - 1) + 1 + ( ( 2^(n-2) ) - 1) = (2 ^(n-1) -1)”. This is for “n-1”th disk, so for nth disk it should be “2^n - 1”.

So, second move for 2 should be after “2^2 - 1=3”, for 3 should be “2^3 - 1=7”, and for 4 should be “2^4 - 1=15”. Now we can say nth disk moves after this many moves, that is 2^n moves after first move or second move is that 2^(n-1)+2^n moves.

First two moves
1:1,3
2:2,6
3:4,12
4:8,24
And so on


Second move for nth disk is at 2^(n-1)+2^n move of the disk system.


Now let us look for the mth move of an nth disk. Suppose we again have 4 disks:

(A:4321, B: -, C: -)
(A:432, B: 1, C: -)
(A:43, B: 1, C: 2)*
(A:43, B: -, C: 21)
(A:-4, B: 3, C: 21)
(A:41, B: 3, C: 2)
(A:41, B: 32, C: -)*
(A:4, B: 321, C: -)
(A:-, B: 321, C: 4)
(A:-, B: 32, C: 41)
(A:2, B: 3, C: 41)*
(A:21, B: 3, C: 4)
(A:21, B: -, C: 43)
(A:2, B: 1, C: 43)
(A: -, B: 1, C: 432)*
(A: -, B: -, C: 4321)


This algorithm is target driven, 4 needs to reach C (Target) for that it needs “123” heap on B (Swap) for this 3 needs “12” heap on C (Swap for 3, as its Target is B, from A). So after “(A:-, B: 321, C: 4)” move 3 needs 2 to go to A, and 2 makes 1 to go to C. So there is one thing clear, pack and unpack is going on. Let us see the movement of disk 1, on the first step 4 needs to go to C, thus instruction flows to 2 to move to C and then 2 wants 1 to move to B. Once 2 reaches C it asks, 1 to come over it. After this way for 3 is clear thus it moves, then 3 needs 2 over it. This would force 1 to move off 2 and then come back.

Leaving the first move every other move needs pack and unpack both.
Move (n-1)th heap on S(n)
Move n to T(n)
Move (n-1)th heap on T(n)
Move (n+1) to T(n+1)
Move (n-1)th heap on S(n)
Move n to T(n)
Move (n-1)th heap on T(n)
Move (n+2) to T(n+2)
Move (n-1)th heap on S(n)
Move n to T(n)
Move (n-1)th heap on T(n)
Move (n+1) to T(n+1)
Move (n-1)th heap on S(n)
Move n to T(n)
Move (n-1)th heap on T(n)

This shows after every unpack/pack we have movement of some higher number disk and we can quite evidently see between any two moves of nth disk we have “Move (n-1)th heap” twice plus one more move. This is just the same as second move. That is 2^n-1 or we can say every 2^n moves nth disk will move.


So,
mth move of nth disk, M(m,n) = 2^(n-1) + (m-1)2^n
or M(m,n) = 2^n( 1/2 + (m-1) )
or M(m,n) = 2^n(m-1/2)

Let us verify for few values of m and n,
M(1,1)=1
M(3,2)=4(2.5)=10
M(2,4)=16(1.5)=24

Now let us look at the direction of movement, remember ABCA and ACBA. Let us try to prove that. Before we go ahead let us look at the recursive algorithm we deduced.


Move nth heap on T (n), from R (n)
Means,
Move (n-1)th heap on S(n), from R(n)
Move n to T(n), from R(n).
Move (n-1)th heap on T(n), from S(n), over n.

Move 0th heap on T (0), from R (0).
Means,
Move nothing


Now if R (n) =A, T (n) =C, so S (n) =B
And know T (n-1) = S (n), as we start with all are at R (n), so R (n-1) =A, Thus S (n-1) =C. One nth disk moves to T (n) =C, “n-1”th disk will be at S (n) =B, now new target for n-1 is T (n) =C and S (n-1) = R (n) = A

Moves:
n:A(B)C
n-1:A(C)B(A)C

Notation: “n:A(B)C” means A is the resting peg, B is the swap peg and C is the target peg for the nth disk.

Moves:
n-1:A(C)B
n-2:A(B)C(A)B

Moves:
n-1:B(A)C
n-2:B(C)A(B)C

Move let us see how many ways any disk can move,

A(C)B, B(A)C,C(B)A,A(B)C,C(A)B,B(C)A

The above moves are part of the patterns we saw before.
ABCA has A(C)B, B(A)C,C(B)A
ACBA has A(B)C,C(A)B,B(C)A

If we say, ABCA as clockwise and ACBA as anticlockwise, visualize by keeping pegs in a triangle. We will have to prove disk moving in one formation only sticks to the same formation for whole run.

Let x can be A, B or C.

Moves
n: x(x-1)x+1
n-1: x(x+1)x-1,x-1(x)x+1

n: x(x+1)x-1
n-1: x(x-1)x+1,x+1(x)x-1

So we can see if nth disk wants to move from x to x+1, then it needs to move “n-1”th disk from x to x-1 to x+1, or to say x to x-1 to x-2. For nth disk’s move from x to x-1, it is x to x+1 to x-1, or to say x to x+1 to x+2.

We can see x(x+1)x-1 and x-1(x)x+1 move in the same direct (anticlockwise)and so do x(x-1)x+1 and x+1(x)x-1 (clockwise).

So we slow if nth disk moves clockwise, “n-1”th disk moves anticlockwise and visa versa. Now let us look at the bigger picture. Largest Disk always moves from A to C that is anticlockwise. This moves the heap over it from two times, that also in clockwise direction. This would make next heap four times in anticlockwise direction and so on so forth.

This even gives the proof for the series we saw before, 2^0, 2^2…, 2^n-1 as number of moves for disk in descending order.

So, we can say now
If largest disk is even, then all even disks move in anticlockwise direction and all odd disks move on clockwise direction. Now as smallest disk always moves first, the first movement will be clockwise, that is AB.

Else if largest disk is odd, then all odd disks move in anticlockwise direction and all even disks move on clockwise direction. Thus the first movement will be anticlockwise, that is AC.

Let us make a formula to get the disk direction, if N the largest disk and n is the target disk,0 < n <=N.


Direction, D(N,n) = (N-n) mod 2
0 will mean anticlockwise, that is ACBA
1 will mean clockwise, that is ABCA


From previous discussion we even know that mth move of nth disk happens at “2^n (m-1/2)”. Now we even know how nth disk move in an N disk set.

M(m,n) = 2^n(m-1/2)
or
m=M(m,n)/2^n+1/2

This M(m,n) is nothing but kth move of this disk system. Let us write it again with k.

m=k/2^n+1/2

This would give us a fractional number, and will have to discard the fraction part of it to get the location of nth disk at kth disk system move.

m=floor(k/2^n+1/2)

As all disks are on A to begin with, we can do something more.
Let peg A=0, B=1, C=2

Peg location of nth disk on kth move, P(n,k) = floor(k/2^n+1/2) mod 3. So if I make to define a function that return a list, [ACB] or [ABC] depending on the input, D(N,n) will be an input to that.

L(a) = [ACB] for a =0, And
L(a) = [ABC] for a =1

Now, P(n,k) is the index in the returned list for some value of N and n. Now if L(a)[i] means ith index of list L(a).


Then location of nth disk, in a set of N disks, on the kth system move,
W(n,N,k) = L( D(N,n) ) [P(n,k)]
or
W(n,N,k) = L( (N – n) mod 2 ) [floor( (k/2^n) + (1/2) ) mod 3]
where,
L(a) = [ACB] for a =0, And
L(a) = [ABC] for a =1


Let us try a few,
W(2,4,8)=L(4-2 mod 2)[floor(8/2^2+1/2) mod 3] = L(0)[2] = B
W(4,5,24)=L(5-4 mod 2)[floor(24/2^4+1/2) mod 3] = L(1)[2] = C

Let us now try “The Tower of Brahma”
W(64,64,2^63)=L(0 mod 2)[ floor( 2^63/2^64+1/2 ) mod 3 ] = L(0)[1] = C, the first and the last time the largest disk of Brahma’s tower moves or it is half way to end of the world.

Now we have a mathematical representation of the recursive algorithm we had deduced before.

Before I sign off, don't you see this disk system recording time like a clock? Assuming moving any disk takes the same amount of time.

Never stop writing non-production code

After we started with jobs (or to say once we are out of school), initial year are about experimentation. As learning is need of the hour. We write more non-production code than production code. This makes us understand and then implement what we are told to. This goes on for few years but after that we gather so much of experience that we really don’t need to write sample codes before we implement something. Still we do get new kind of implementations to do and we do what we did before, write some non-production codes. Introduction of testing tools for test first programming even allow us not to spend our time on sample codes but just write direct production codes. As those are always tested every-time you run the build. So the journey from an ad-hoc code to a mature code that even solves the problem at hand can happen while writing production code only. This conservers your energy and only channelizes in solving the problem at hand. This approach normally reaps great results and most of the time error free codes. I can’t remember an instance were my code failed in a scenario that I had thought of before. Even after reaping so much from test first programming I felt dissatisfied. There was something missing from this coder’s diet -- Unbound-creativity.

What author refers to as Unbound-creativity?
An unstoppable desire to, create on a limitless canvas.

Every time you put a new layer – you add new constraints. Those help do work faster and neater. Even using testing frameworks make you work in their constraints. From creativity standpoint standardization is a necessary evil. Standardization has all the benefits in the world for commercial organizations and large-distributed coding teams but in end of the day, it comes in the way of the creativity of an individual. Coding isn’t an exact science by any means; it’s an Art of instructing a computer. Per say physics also relies on an Art -- Art of reading and understanding nature. Nothing that human does can just be science; it will have an element of art to it.
In true sense we all programmers are artists, we create something that a beholder can admire. It can be your code or its output but most of the firms don’t think so they just think programmers as resources, in a simple mathematical model. They have helped commercialization of this art. To sustain and keep resource outputs predictable, they shortlist languages and create a pool of commodity programmers by increasing demand. As they have money and we need some every month, we have to ourselves strike a balance. Don’t ever stop learning; to help this you can do innovative things. Like learn a language every week/month, or select a language else than what you work with. Then try to create all you can think-off with the new language.

Whatever you do start-writing some code again for yourself, enjoy writing code without any specifications or guidelines. May be a few layers below you normally code at work!? Write some nonsense, fun-sake, enjoyable, masterpiece, state of the art non-production code, just for yourself regularly.

And remember what Donald Ervin Knuth wrote once;

“A programmer who subconsciously views himself as an artist will enjoy what he does and will do it better”

( http://nitin.tumblr.com/post/1761267 )