Solved

Experts Challenge I: Towers of Hanoi

Posted on 2004-04-26
16
1,161 Views
Last Modified: 2011-10-03
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
Comment
Question by:eternal_21
  • 4
  • 4
  • 4
  • +2
16 Comments
 
LVL 14

Accepted Solution

by:
AvonWyss earned 500 total points
ID: 10926255
"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

by:rama_krishna580
ID: 10926275
0
 
LVL 14

Expert Comment

by:AvonWyss
ID: 10926483
rama, did you read the question at all?
0
PRTG Network Monitor: Intuitive Network Monitoring

Network Monitoring is essential to ensure that computer systems and network devices are running. Use PRTG to monitor LANs, servers, websites, applications and devices, bandwidth, virtual environments, remote systems, IoT, and many more. PRTG is easy to set up & use.

 
LVL 4

Expert Comment

by:NTAC
ID: 10927719
lol, I'm crying over here....  lol
0
 
LVL 37

Expert Comment

by:gregoryyoung
ID: 10929755
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

by:NTAC
ID: 10929821
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

by:eternal_21
ID: 10930835
 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

by:gregoryyoung
ID: 10931465
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

by:AvonWyss
AvonWyss earned 500 total points
ID: 10931863
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

by:AvonWyss
ID: 10931880
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

by:gregoryyoung
ID: 10932219
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

by:eternal_21
ID: 10935761
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

by:eternal_21
ID: 10935784
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

by:eternal_21
ID: 10935883
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

by:gregoryyoung
ID: 10939699
wow in place recursion with a stack how impressing.
0

Featured Post

NAS Cloud Backup Strategies

This article explains backup scenarios when using network storage. We review the so-called “3-2-1 strategy” and summarize the methods you can use to send NAS data to the cloud

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Error in script 11 58
designing in object programming 12 79
Video Player 2017 5 25
Install Problem 13 32
This article is for Object-Oriented Programming (OOP) beginners. An Interface contains declarations of events, indexers, methods and/or properties. Any class which implements the Interface should provide the concrete implementation for each Inter…
Entity Framework is a powerful tool to help you interact with the DataBase but still doesn't help much when we have a Stored Procedure that returns more than one resultset. The solution takes some of out-of-the-box thinking; read on!
This tutorial gives a high-level tour of the interface of Marketo (a marketing automation tool to help businesses track and engage prospective customers and drive them to purchase). You will see the main areas including Marketing Activities, Design …
With Secure Portal Encryption, the recipient is sent a link to their email address directing them to the email laundry delivery page. From there, the recipient will be required to enter a user name and password to enter the page. Once the recipient …

803 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question