Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people, just like you, are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
Solved

Experts Challenge I: Towers of Hanoi

Posted on 2004-04-26
16
1,163 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
Announcing the Most Valuable Experts of 2016

MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

 
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

Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

This article describes a simple method to resize a control at runtime.  It includes ready-to-use source code and a complete sample demonstration application.  We'll also talk about C# Extension Methods. Introduction In one of my applications…
This article introduced a TextBox that supports transparent background.   Introduction TextBox is the most widely used control component in GUI design. Most GUI controls do not support transparent background and more or less do not have the…
The Email Laundry PDF encryption service allows companies to send confidential encrypted  emails to anybody. The PDF document can also contain attachments that are embedded in the encrypted PDF. The password is randomly generated by The Email Laundr…
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…

837 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