• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 1174
  • Last Modified:

Experts Challenge I: Towers of Hanoi

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
eternal_21
Asked:
eternal_21
  • 4
  • 4
  • 4
  • +2
2 Solutions
 
AvonWyssCommented:
"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
 
rama_krishna580Commented:
0
 
AvonWyssCommented:
rama, did you read the question at all?
0
Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
NTACCommented:
lol, I'm crying over here....  lol
0
 
gregoryyoungCommented:
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
 
NTACCommented:
No I am quite sure this is a challenge.   I was laughing at Avon's response to rama's post.  
0
 
eternal_21Author Commented:
 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
 
gregoryyoungCommented:
any recursive algorithm has an in place cousin using stack instead of method recursion .... recursion just uses an implicit stack (the call stack).
0
 
AvonWyssCommented:
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
 
AvonWyssCommented:
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
 
gregoryyoungCommented:
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
 
eternal_21Author Commented:
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
 
eternal_21Author Commented:
500 points to AvonWyss for the solution that had we received any other submissions, may very well have not been duplicated.
0
 
eternal_21Author Commented:
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
 
gregoryyoungCommented:
wow in place recursion with a stack how impressing.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

Cloud Class® Course: Microsoft Office 2010

This course will introduce you to the interfaces and features of Microsoft Office 2010 Word, Excel, PowerPoint, Outlook, and Access. You will learn about the features that are shared between all products in the Office suite, as well as the new features that are product specific.

  • 4
  • 4
  • 4
  • +2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now