Solved

# Experts Challenge I: Towers of Hanoi

Posted on 2004-04-26
1,159 Views
C# Experts Challenge

After working on some questions with AvonWyss and others, I had the idea of creating an “Experts’ Challenge.”  I have come up with a challenge for this week and we will see what kind of interest there is out there.  Any Experts-Exchange members are welcome to participate, so don’t be intimidated by the title!

Experts Challenge I: Towers of Hanoi

“It is rumored that somewhere in Asia a group of spiritually advanced monks is hard at work transferring golden disks.  When they are finished moving a tower of 64 of these disks from the first peg to the third peg of a sacred three-peg stand, then the next Maha Pralaya will begin, in which the universe will dissolve and revert to its unmanifested state.  The 64 disks have different sizes, and the monks must obey two rules: (1) only one disk can be moved at a time, and (2) a bigger disk can never be placed on top of a smaller disk.”

This is the infamous “Towers of Hanoi” problem.  This problem can be found in many programming textbooks in a section labeled (you guessed it) “Recursive Algorithms.”

The challenge this week is to create a method that solves the Towers of Hanoi problem *non-recursively*.

Rules:

1.  The problem must be solved in one method, and this method cannot call itself (directly or indirectly – no tricks!).

2.  The pegs must be identified by the integers 0, 1, and 2 for the first, second and third pegs (i.e.: 0 based index).

3.  The method must have the same prototype as below: string (int n, int start, int finish), where n is the number of disks to move, start is a peg from the set {0, 1, 2} finish is a remaining peg where you would like the tower to end up.  So to move 8 disks from the first peg to the third peg, you would call “MoveTowers(8, 0, 2)”.

4.  The method must return a string in the format “(x,y)” for each move of a disk where x is the starting peg, and y is the destination peg of a disk.  For example, moving a disk from the first peg to the third peg would produce the string “(0, 2)”.  Moving a tower of 2 disks from the first peg to the third peg would produce the string “(0,1)(0,2)(1,2)”.

5.  You do not need to worry about argument checking.  Assume that n will always be greater than zero, and start and finish will be two distinct elements from the set {0, 1, 2}.

######
Here is an example in c# of a recursive method that solves the Towers of Hanoi problem:

string MoveTowers(int n, int start, int finish)
{
if(n==1)
return String.Format("({0},{1})", start, finish);
else
{
int spare = 3 - start - finish;
return MoveTowers(n - 1, start, spare) + MoveTowers(1, start, finish) + MoveTowers(n - 1, spare, finish);
}
}

The method call “MoveTowers(3, 0, 1)” returns the string, “(0,2)(0,1)(2,1)(0,2)(1,0)(1,2)(0,2)”.
######

Good Luck!
0
Question by:eternal_21
• 4
• 4
• 4
• +2

LVL 14

Accepted Solution

AvonWyss earned 500 total points
"The method call “MoveTowers(3, 0, 1)” returns the string, “(0,2)(0,1)(2,1)(0,2)(1,0)(1,2)(0,2)”."

This output would rather be for MoveTowers(3, 0, 2), wouldn't it?

But anyways, here's my solution:

private static string MoveTowers(int n, int start, int finish) {
int[] stack=new int[n+2];
int[] movePattern=new int[n+2];
int[] mapping=new int[4] {0, start, 3-start-finish, finish};
int dir=n&1;
StringBuilder result=new StringBuilder();
for(int i=0; i<=(n+1); i++) {
stack[i] = 1;
movePattern[i] = i+1;
}
for(int i=1; i<=n; i=movePattern[0]) {
result.Append('(');
result.Append(mapping[stack[i]]);
result.Append(',');
stack[i]=(stack[i]+(((i&1)>0) ? dir : 1-dir))%3+1;
result.Append(mapping[stack[i]]);
result.Append(')');
movePattern[0] = 1;
movePattern[i-1] = movePattern[i];
movePattern[i] = i+1;
}
return result.ToString();
}
0

LVL 23

Expert Comment

0

LVL 14

Expert Comment

rama, did you read the question at all?
0

LVL 4

Expert Comment

lol, I'm crying over here....  lol
0

LVL 37

Expert Comment

Is this really supposed to be a challenge ? This sounds to me like your Data Structures class homework to show in place recursion via the use of a stack.

If this is not your homework and you are going to continue I'd be happy to participate but this sounds a bit fishy especially as a "challenge" since this is a 200 or 300 level class homework assignment.
0

LVL 4

Expert Comment

No I am quite sure this is a challenge.   I was laughing at Avon's response to rama's post.
0

LVL 10

Author Comment

Good call, gregoryyoung.  The quote was taken from a "Data Structures in Java" textbook, although no mention was made of a non-recursive solution.

You see this problem in textbooks all the time, but always in its recursive form.  I chose this partially because there would be a fair amount of people familiar with it.  It was not supposed to be extremely difficult for a couple of reasons: I wanted to see if there was any interest in the C# community for something like this, and I honestly did not have time to come up with a better challenge.

Part of the interest to me, is seeing how different developers come up with different solutions to the same problem.  I did think it would be longer than 2 hours before anyone posted a solution but I had though about putting a minimum wait time on the question (I will do that on the next one).  Had there been more submissions we could have created a function to verify the output.  If we continue, the challenges should be developed with some definition.  I think that a challenge should focus on some specific programming principle or areas of c#/.NET development, a solution should require a small amount of code, and a challenge should be able to be solved in more than one way, encouraging some discussion.

If you experts are interested in this, please give some feedback.  Finally, is anyone else still working on this question?

Oh, one more note: It should be clear that it's not what I was looking for, but for those of you that it isn't, no links *please.*
0

LVL 37

Expert Comment

any recursive algorithm has an in place cousin using stack instead of method recursion .... recursion just uses an implicit stack (the call stack).
0

LVL 14

Assisted Solution

AvonWyss earned 500 total points
gregoryyoung, what you write about stacks is true. However, if you examine my post, you'll see that the method I used does not really work like the translation of recursion to stack based would be.
0

LVL 14

Expert Comment

eternal, I like things like this (OK, could be somewhat harder *g*), just for recreation. And sometimes it allows one to learn something new. Therefore, I'm game for more of these...
0

LVL 37

Expert Comment

I will post a expert challenge.

I will offer 500 points and a grade of A for following challenge ...

Fastest program to solve Connect 4 500 (no data allowed)
Program to play reversi

needs to be more than 1 best wins

for fun ill throw out the classic "Write a program that prints its own soure code"  which is always a brainbuster if you havnt done it before and it also becomes a nifty postscript virus :P
0

LVL 10

Author Comment

AvonWyss, I want to thank you again for your participation.  As I said before, I did enjoy working on these problems with you.  It was rewarding to see you take it seriously...  Take a look at this, http:Q_20969289.html.  I am going to give Netminder's response some thought, and get back to him, but I didn't want to do that without asking for input from you.
0

LVL 10

Author Comment

500 points to AvonWyss for the solution that had we received any other submissions, may very well have not been duplicated.
0

LVL 10

Author Comment

And just to demonstrate how different the solutions can be, here was mine:

###

static string MoveTowers(int n, int start, int finish)
{
System.Text.StringBuilder moveString;
moveString = new System.Text.StringBuilder();

System.Collections.Stack stack;
stack = new System.Collections.Stack();

stack.Push(new int[] {n, start, finish});
while(stack.Count!=0)
{
int[] parameters;
parameters = (int[]) stack.Pop();

if(parameters[0]==1)
{
moveString.Append(String.Format("({0},{1})", parameters[1], parameters[2]));
}
else
{
int spare = 3 - parameters[1] - parameters[2];
stack.Push(new int[] {parameters[0] - 1, spare, parameters[2]});
stack.Push(new int[] {1, parameters[1], parameters[2]});
stack.Push(new int[] {parameters[0] - 1, parameters[1], spare});
}
}

return moveString.ToString();
}

###
0

LVL 37

Expert Comment

wow in place recursion with a stack how impressing.
0

## Featured Post

Having new technologies does not mean they will completely replace old components.  Recently I had to create WCF that will be called by VB6 component.  Here I will describe what steps one should follow while doing so, please feel free to post any qu…
Real-time is more about the business, not the technology. In day-to-day life, to make real-time decisions like buying or investing, business needs the latest information(e.g. Gold Rate/Stock Rate). Unlike traditional days, you need not wait for a fe…
Sending a Secure fax is easy with eFax Corporate (http://www.enterprise.efax.com). First, Just open a new email message.  In the To field, type your recipient's fax number @efaxsend.com. You can even send a secure international fax — just include t…
Access reports are powerful and flexible. Learn how to create a query and then a grouped report using the wizard. Modify the report design after the wizard is done to make it look better. There will be another video to explain how to put the final p…