# Implementation of Tower of Hanoi iterative procedure

I have been working last night on implementing Tower of Hanoi without using recursion. I have found an algorithm on Wikipedia about the same topic here. I have implemented it and it's working fine (for odd numbers for now). But I am not happy with the code because it's kinda bulky, hence I want to modify it in a way so that actual lines of code will reduce with the same functionality and the algorithm in mind.

#include<stdio.h>
#include<math.h>
#include<stdlib.h>

display(int *A, int *B, int *C, int atop , int btop ,int ctop)
{
int i;
if(A[0]==0)
printf("\nEmpty A");
else
{
printf("\nA Stack :\n");
for (i=atop; i>=1; i--)
{
printf("  %d\n",A[i]);
}
}

if(B[0]==0)
printf("\nEmpty B\n");
else
{
printf("\nB Stack: \n");
for (i=btop; i>=1; i--)
{
printf("  %d\n",B[i]);
}
}

if(C[0]==0)
printf("\nEmpty C\n");
else
{
printf("\nC Stack: \n");
for (i=ctop; i>=1; i--)
{
printf("  %d\n",C[i]);
}
}

}

int main()
{
int step=0;
int n,i,*A,*B,*C,atop,btop,ctop,count=0;
int max=1;

printf("\nInput # disks");
scanf("%d",&n);

for(i=0; i<n; i++)
{
max*=2;
}
max=max-1;
printf("\n Max is :%d",max);
A= (int *)malloc(sizeof(int)*(n+1));
B= (int *)malloc(sizeof(int)*(n+1));
C= (int *)malloc(sizeof(int)*(n+1));
A[0]=B[0]=C[0]=0;
atop=btop=ctop=0;
for(i=n; i>0; i--)
{
atop++;
A[0]++;
A[atop]=i;
B[atop]=0;
C[atop]=0;
}

display(A,B,C,atop,btop,ctop);

do
{
count+=1;
step=(step%3)+1;

switch(step)
{

case 1://move between pegs A and C

printf("\n%d count:",count);
if(count%2 ==1)//move of disk 1
{
if(A[atop]==1)
{

ctop++;
C[ctop]=A[atop];
A[atop]=0;
atop--;
C[0]++;
A[0]--;
printf("\nDisk %d: A->C",C[ctop]);
}  //i is on A
else if(C[ctop]==1)//1 is on b
{

atop++;
A[atop]=C[ctop];
C[ctop]=0;
ctop--;
A[0]++;
C[0]--;
printf("\nDisk %d: C->A",A[atop]);

}
}//Movement of disk #1

else if(count %2 ==0)
{
if(ctop !=0 && A[atop]>C[ctop])
{
//C[0]--;
atop++;
A[atop]=C[ctop];
C[ctop]=0;
ctop--;
C[0]--;
A[0]++;
printf("\nDisk %d: C->A",A[atop]);
}
else if (ctop ==0)
{
ctop++;
C[ctop]=A[atop];
A[atop]=0;
atop--;
C[0]++;
A[0]--;
printf("\n disk %d:A->C",C[ctop]);
}
else if(atop !=0 && C[ctop]>A[atop])
{

ctop++;
C[ctop]=A[atop];
A[atop]=0;
atop--;
C[0]++;
A[0]--;
printf("\nDisk %d: A->C",C[ctop]);

}
else if(atop==0)
{
atop++;
A[atop]=C[ctop];
C[ctop]=0;
ctop--;
C[0]--;
A[0]++;
printf("\nDisk %d: C->A",A[atop]);
}

}//Movement of Disk non1

break;

case 2://move between pegs A and B

printf("\n%d count:",count);
if(count%2 ==1)//move of disk 1
{
if(A[atop]==1)
{

btop++;
B[btop]=A[atop];
A[atop]=0;
atop--;
B[0]++;
A[0]--;
printf("\nDisk %d: A->B",B[btop]);
}  //i is on A
else if(B[btop]==1)//1 is on b
{

atop++;
A[atop]=B[btop];
B[btop]=0;
btop--;
A[0]++;
B[0]--;
printf("\nDisk %d: B->A",A[atop]);

}
}//Movement of disk #1

else if(count %2 ==0)
{
if(btop !=0 && A[atop]>B[btop])
{
//B[0]--;
atop++;
A[atop]=B[btop];
B[btop]=0;
btop--;
B[0]--;
A[0]++;
printf("\nDisk %d: B->A",A[atop]);
}
else if (btop ==0)
{
btop++;
B[btop]=A[atop];
A[atop]=0;
atop--;
B[0]++;
A[0]--;
printf("\n disk %d:A->B",B[btop]);
}
else if(atop !=0 && B[btop]>A[atop])
{

btop++;
B[btop]=A[atop];
A[atop]=0;
atop--;
B[0]++;
A[0]--;
printf("\nDisk %d: A->B",B[btop]);

}
else if(atop==0)
{
atop++;
A[atop]=B[btop];
B[btop]=0;
btop--;
B[0]--;
A[0]++;
printf("\nDisk %d: B->A",A[atop]);
}

}//Movement of Disk non1

break;

case 3://move between pegs C and B

printf("\n%d count:",count);
if(count%2 ==1)//move of disk 1
{
if(C[ctop]==1)
{

btop++;
B[btop]=C[ctop];
C[ctop]=0;
ctop--;
B[0]++;
C[0]--;
printf("\nDisk %d: C->B",B[btop]);
}  //i is on C
else if(B[btop]==1)//1 is on b
{

ctop++;
C[ctop]=B[btop];
B[btop]=0;
btop--;
C[0]++;
B[0]--;
printf("\nDisk %d: B->C",C[ctop]);

}
}//Movement of disk #1

else if(count %2 ==0)
{
if(btop !=0 && C[ctop]>B[btop])
{
//B[0]--;
ctop++;
C[ctop]=B[btop];
B[btop]=0;
btop--;
B[0]--;
C[0]++;
printf("\nDisk %d: B->C",C[ctop]);
}
else if (btop ==0)
{
btop++;
B[btop]=C[ctop];
C[ctop]=0;
ctop--;
B[0]++;
C[0]--;
printf("\n disk %d:C->B",B[btop]);
}
else if(ctop !=0 && B[btop]>C[ctop])
{

btop++;
B[btop]=C[ctop];
C[ctop]=0;
ctop--;
B[0]++;
C[0]--;
printf("\nDisk %d: C->B",B[btop]);

}
else if(ctop==0)
{
ctop++;
C[ctop]=B[btop];
B[btop]=0;
btop--;
B[0]--;
C[0]++;
printf("\nDisk %d: B->C",C[ctop]);
}

}//Movement of Disk non1

break;

default:
printf("Some Error!");
}//switch end
//        display(A,B,C,atop,btop,ctop);
}
while((count <=max) && (C[0]!=n) );

printf("\n");
//display(A,B,C,atop,btop,ctop);
display(A,B,C,atop,btop,ctop);

return 0;
}


There is way too much duplication in this code. This is dangerous and can lead to nasty bugs, when you need to make a change at somewhere, and you forget to make the similar change at all the other copy-pasted locations. Avoid copy-pasting code.

Rewrite display with the common logic extracted to another function:

void display_peg(char label, int *peg, int top)
{
int i;
if (peg[0] == 0) {
printf("\nEmpty %c", label);
} else {
printf("\n%c Stack :\n", label);
for (i = top; i >= 1; i--) {
printf("  %d\n", peg[i]);
}
}
}

void display(int *A, int *B, int *C, int atop , int btop ,int ctop)
{
display_peg('A', A, atop);
display_peg('B', B, btop);
display_peg('C', C, ctop);
}


You also forgot to declare the return type void of your original function, which raises warnings by the compiler.

Moving from one peg to another can be generalized and extracted to a function:

void move_from_peg1_to_peg2(
char peg1label, int * peg1, int * peg1top,
char peg2label, int * peg2, int * peg2top)
{
++*peg2top;
peg2[*peg2top]=peg1[*peg1top];
peg1[*peg1top]=0;
--*peg1top;
peg2[0]++;
peg1[0]--;
printf("\nDisk %d: %c->%c",peg2[*peg2top], peg1label, peg2label);
}


The same goes for deciding moving between pegs, based on the count:

void move_between_pegs(int count,
char peg1label, int * peg1, int * peg1top,
char peg2label, int * peg2, int * peg2top)
{
printf("\n%d count:",count);
if (count % 2 == 1) {
if (peg1[*peg1top] == 1) {
move_from_peg1_to_peg2(peg1label, peg1, peg1top, peg2label, peg2, peg2top);
} else if (peg2[*peg2top] == 1) {
move_from_peg1_to_peg2(peg2label, peg2, peg2top, peg1label, peg1, peg1top);
}
} else {
if (*peg1top == 0
|| (*peg2top != 0 && peg1[*peg1top] > peg2[*peg2top])) {
move_from_peg1_to_peg2(peg2label, peg2, peg2top, peg1label, peg1, peg1top);
} else if (*peg2top == 0
|| (*peg1top !=0 && peg2[*peg2top] > peg1[*peg1top])) {
move_from_peg1_to_peg2(peg1label, peg1, peg1top, peg2label, peg2, peg2top);
}
}
}


With these helper functions, your while loop that had almost 300 lines becomes so much simpler:

do
{
count+=1;
step=(step%3)+1;

switch(step)
{
case 1://move between pegs A and C
move_between_pegs(count, 'A', A, &atop, 'C', C, &ctop);
break;

case 2://move between pegs A and B
move_between_pegs(count, 'A', A, &atop, 'B', B, &btop);
break;

case 3://move between pegs C and B
move_between_pegs(count, 'C', C, &ctop, 'B', B, &btop);
break;

default:
printf("Some Error!");
}//switch end
}
while((count <=max) && (C[0]!=n) );


Notice that you don't need anymore the //switch end comment: you can see the entire switch content right in front of you. The same goes for the comments //move between pegs C and B: the function name and its parameters make it perfectly clear what is going on.

In fact, whenever you find yourself writing a comment for a block of code, consider extracting that block of code to a function, and let the function name and its parameters become self-explanatory, effectively replacing the comment itself.

Extracting duplicated code into methods is more than just good style. It can make previously invisible things visible. Notice above in move_between_pegs that I have fewer conditions than in your original code: I joined several independent if-else statements into one, with || condition. This simplification would have been difficult with the original code, because due to the lengthy blocks, it was hard to see their similarities. Only after I shortened them, it became crystal clear that some of the independent conditions will take the same action, and therefore they can be joined.

By eliminating duplication and making the code shorter, you can extend your vision, and understand the behavior of the code better, from a higher level, which often opens up the possibility for further optimizations.

• thank you so much @janos. it indeed looks much better :-) will try to evolve my coding keeping the pointers in mind . Aug 30, 2014 at 22:41