Solved

Experts Challenge I: Towers of Hanoi

Posted on 2004-04-26
16
1,160 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
 
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
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
C# Error - Add Failed 12 77
c# if statement weird reaction 3 42
what technologies offer Authentication over Web Services? 4 103
Authentication of Web Services 3 46
Article by: Najam
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…
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…
Get a first impression of how PRTG looks and learn how it works.   This video is a short introduction to PRTG, as an initial overview or as a quick start for new PRTG users.
This video demonstrates how to create an example email signature rule for a department in a company using CodeTwo Exchange Rules. The signature will be inserted beneath users' latest emails in conversations and will be displayed in users' Sent Items…

939 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

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now