Slashfear's Programming challenge!!!

Hi Guys,

This time I am fully loaded with a programming Challenge, all the programming language's are allowed ๐Ÿ˜‰.

Here is the Problem:

This is a classic problems. The Tower of Hanoi or Towers of Hanoi (also known as The Towers of Brahma) is a mathematical game or puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks neatly stacked in order of size on one rod, the smallest at the top, thus making a conical shape as shown below:

[โ€‹IMG]

The objective of the puzzle is to move the entire stack to another rod, obeying the following rules:

-> Only one disk may be moved at a time.
-> Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.
-> No disk may be placed on top of a smaller disk.


Let us assume that the priests are attempting to move the disks from peg 1 to peg 3. We wish to develop an algorithm that will print the precise sequence of peg-to-peg disk transfers.If we were to approach this problem with conventional methods, we would rapidly find ourselves hopelessly knotted up in
managing the disks.

Clue to solution: if we attack the problem with recursion in mind, it immediately becomes tractable. Moving n disks can be viewed in terms of moving only n - 1 disks (hence, the recursion), as follows:

a) Move n - 1 disks from peg 1 to peg 2, using peg 3 as a temporary holding area.
b) Move the last disk (the largest) from peg 1 to peg 3.
c) Move the n - 1 disks from peg 2 to peg 3, using peg 1 as a temporary holding area.

Sample output:
[B]Enter the starting number of disks: 4

1 --> 2
1 --> 3
2 --> 3
1 --> 2
3 --> 1
3 --> 2
1 --> 2
1 --> 3
2 --> 3
2 --> 1
3 --> 1
2 --> 3
1 --> 2
1 --> 3
2 --> 3
[/B]
Lets see who finish this puzzle first....... let me give my solution later!!! ;-)

Don't try to google it, Its not going to help you out in improving your programming skill (this puzzle is only for those who wanna be a serious programmer ๐Ÿ˜)


-Arvind(slashfear)

Replies

  • Corpse-Thrust
    Corpse-Thrust
    I guess I remember the general algorithm for solving this problem. But since I'm not exactly at my home, I can't post the solution program right now.

    I'll try to post the answer tonight, if possible. ๐Ÿ˜€
  • pradeep_agrawal
    pradeep_agrawal
    Yesterday i was out of home so could not give this a try. Here is my piece of code for the given problem.

    #include "stdio.h"
    
    #define TRUE 1
    #define FALSE 0
    
    
    /* 
     * Defining a structure and data type for representing each tower
     * tower is pointer to elements of tower
     * size represent number of elements in tower
     */
    typedef struct {
      int *tower;
      int size;
    } tower_t;
    
    
    /* Display the move */
    void display_move(tower_t* tt1, tower_t* tt2, tower_t* t1, tower_t* t2, tower_t* t3) {
      int from = 0;
      int to = 0;
    
      if(tt1->tower == t1->tower) {
        from = 1;
      } else if(tt1->tower == t2->tower) {
        from = 2;
      } else {
        from = 3;
      }
    
      if(tt2->tower == t1->tower) {
        to = 1;
      } else if(tt2->tower == t2->tower) {
        to = 2;
      } else {
        to = 3;
      }
    
      printf("Move from %d to %d\n", from, to);
      
    }
    
    
    /* Display current state of all towers */
    void display_towers(tower_t t1, tower_t t2, tower_t t3, int tower_size) {
      int i = 0;
      printf("Towers:\n");
      for(i = (tower_size - 1); i >= 0; i--) {
        printf("%d %d %d\n", t1.tower[i], t2.tower[i], t3.tower[i]);
      }
      printf("\n");
    }
    
    
    /* Moves elemet fro tt1 to tt2 using tt3 as buffer */
    void move(tower_t* tt1, tower_t* tt2, tower_t* tt3, tower_t* t1, tower_t* t2, tower_t* t3, int tower_size) {
      int move_to_tt2 = FALSE;
      int move_count = 0;
      int i = 0;
    
      //determining number of elements that can be moved from tt1
      for(i = (tt1->size - 1); i >= 0; i--) {
        if(((tt2->size == 0) || (tt2->tower[tt2->size - 1] > tt1->tower[i]))
            && ((tt3->size == 0) || (tt3->tower[tt3->size - 1] > tt1->tower[i]))) {
          move_count++;
        } else {
          break;
        }
      }
    
      //if number of elements is odd, move first element to tt2
      //else move first element to tt3
      if(move_count % 2) {
        move_to_tt2 = TRUE;
      } else {
        move_to_tt2 = FALSE;
      }
    
      //loop for moving each element till count of moveable element is not 0 in tt1
      while(move_count != 0) {
        if(move_to_tt2) {
          //display the current move
          display_move(tt1, tt2, t1, t2, t3);
    
          //move element from tt1 to tt2
          tt2->tower[tt2->size++] = tt1->tower[--tt1->size];
          tt1->tower[tt1->size] = 0;
    
          //toggle flag to move next element to tt3
          move_to_tt2 = FALSE;
    
          //display current state of all towers after move
          display_towers(*t1, *t2, *t3, tower_size);
    
          //move pegs from tower tt3 to tt2
          move(tt3, tt2, tt1, t1, t2, t3, tower_size);
        } else {
          //display the current move
          display_move(tt1, tt3, t1, t2, t3);
    
          //move element from tt1 to tt3
          tt3->tower[tt3->size++] = tt1->tower[--tt1->size];
          tt1->tower[tt1->size] = 0;
    
          //toggle flag to move next element to tt2
          move_to_tt2 = TRUE;
    
          //display current state of all towers after move
          display_towers(*t1, *t2, *t3, tower_size);
    
          //move pegs from tower tt2 to tt3
          move(tt2, tt3, tt1, t1, t2, t3, tower_size);
        }
    
        //one more element moved, decrementing count
        move_count--;
      }
    }
    
    
    int main() {
      tower_t t1 = {0};
      tower_t t2 = {0};
      tower_t t3 = {0};
      int tower_size = 0;
      int i = 0;
    
      //taking tower size as input
      scanf("%d", &tower_size);
    
      //validating tower size
      if(tower_size <= 0) {
        printf("Invalid tower size\n");
        return 0;
      }
    
      //allocating memory for each tower
      t1.tower = (int*)malloc(sizeof(int) * tower_size);
      t2.tower = (int*)malloc(sizeof(int) * tower_size);
      t3.tower = (int*)malloc(sizeof(int) * tower_size);
    
      //initializing elements of t1 with the peg it contains
      //initializing elements of t2 and t3 with 0 as they are initially empty
      for(i = 0; i < tower_size; i++) {
        t1.tower[i] = tower_size - i;
        t2.tower[i] = t3.tower[i] = 0;
      }
    
      //initializing size of t1 with current tower size as it contain all pegs
      //initializing size t2 and t3 with 0 as they are initially empty
      t1.size = tower_size;
      t2.size = t3.size = 0;
    
      //display the initial state of all towers
      display_towers(t1, t2, t3, tower_size);
    
      //moving complete tower 1 to tower 2 using tower 3 as buffer
      move(&t1, &t2, &t3, &t1, &t2, &t3, tower_size);
    
      //free the memory previously allocated for each tower
      free(t1.tower);
      free(t2.tower);
      free(t3.tower);
    
      return 0;
    }
    
    Compile the file with above code and run as:
    a.exe < input.txt > output.txt [on windows]
    a.out < input.txt > output.txt [on linux]

    Here,
    a.exe or a.out are the executables generated after compilation

    input.txt is the file containing input, e.g., for tower of size (or height) 4, input.txt will be:
    4

    output.txt is the output file containing result, for given example output.txt will contain

    Towers:
    1 0 0
    2 0 0
    3 0 0
    4 0 0
    
    Move from 1 to 3
    Towers:
    0 0 0
    2 0 0
    3 0 0
    4 0 1
    
    Move from 1 to 2
    Towers:
    0 0 0
    0 0 0
    3 0 0
    4 2 1
    
    Move from 3 to 2
    Towers:
    0 0 0
    0 0 0
    3 1 0
    4 2 0
    
    Move from 1 to 3
    Towers:
    0 0 0
    0 0 0
    0 1 0
    4 2 3
    
    Move from 2 to 1
    Towers:
    0 0 0
    0 0 0
    1 0 0
    4 2 3
    
    Move from 2 to 3
    Towers:
    0 0 0
    0 0 0
    1 0 2
    4 0 3
    
    Move from 1 to 3
    Towers:
    0 0 0
    0 0 1
    0 0 2
    4 0 3
    
    Move from 1 to 2
    Towers:
    0 0 0
    0 0 1
    0 0 2
    0 4 3
    
    Move from 3 to 2
    Towers:
    0 0 0
    0 0 0
    0 1 2
    0 4 3
    
    Move from 3 to 1
    Towers:
    0 0 0
    0 0 0
    0 1 0
    2 4 3
    
    Move from 2 to 1
    Towers:
    0 0 0
    0 0 0
    1 0 0
    2 4 3
    
    Move from 3 to 2
    Towers:
    0 0 0
    0 0 0
    1 3 0
    2 4 0
    
    Move from 1 to 3
    Towers:
    0 0 0
    0 0 0
    0 3 0
    2 4 1
    
    Move from 1 to 2
    Towers:
    0 0 0
    0 2 0
    0 3 0
    0 4 1
    
    Move from 3 to 2
    Towers:
    0 1 0
    0 2 0
    0 3 0
    0 4 0
    
    Let me know if any item need clarification.

    P.S.:
    1. If you want to see only move statement and don't want to see towers state after each move, remove "display_towers" function call from code.
    2. If you want to see only towers state after every move and don't want to move statement, remove "display_move" function call from code.

    -Pradeep
  • Corpse-Thrust
    Corpse-Thrust
    WOW...

    I did try it yesterday, but the stupid me used procedural programming to solve this, and had so much trouble trying to implement it using functions yesterday night. I had gone almost crazy. But, using classes/structures to represent a tower? Genius man, why didn't I think of this? Makes you realize how superior the object oriented programming approach is...

    You are officially my hero Pradeep <3

    EDIT : btw is this solvable using simple procedural programming instead of the approach Pradeep used?
  • pradeep_agrawal
    pradeep_agrawal
    Thanks for your appreciation Corpse-Thrust.

    Corpse-Thrust
    btw is this solvable using simple procedural programming instead of the approach Pradeep used?
    I have used the procedural programming approach in my program. If you are talking about usage of
    typedef struct {
      int *tower;
      int size;
    } tower_t;
    
    The problem can be solved without using that, it will be just declaration and passing of few extra variables to functions. I used it so that it is easy to code, understand, and maintain.

    -Pradeep
  • Corpse-Thrust
    Corpse-Thrust
    @Pradeep Oh okay, I get it now... Sorry for the misunderstanding lol.

    ~~~

    Well, I finally worked my butt off, and came up with an answer of my own.

    I made a function called MoveDiscs(int n, char a, char c, char b) which will print out the procedure to move n number of discs from tower a to tower c, using tower b as a support. Here's the code :

    MoveDiscs(int n, char a, char c, char b)
    {
    if(n==2)
    {
    cout<"< cout<"< cout<"< }
    else if(n>2)
    {
    MoveDiscs(n-1, a, b, c);
    cout<"< MoveDiscs(n-1, b, c, a);
    }
    }
    The code for main() would be something like :
    void main()
    {
    int x;
    cout<<"enter the number of discs in tower A : ";
    cin>>x;
    MoveDiscs(x, "A", "C", "B");
    }
    Output should be similar to slashfear's sample output, only with A, B and C instead of the numbers he used. I have yet to test this all out on my PC, coz there's no light, and I'm using my mobile phone to post this ๐Ÿ˜
  • shalini_goel14
    shalini_goel14
    [off-topic post]

    @Pradeep Sir

    I love your quick replies to all programs here though I never dared to look inside your code but I have a question going in my mind from last few days. You joined CE in 2006 around two years back as compared to me. You never thought of sharing your superb art of programming with CEans? Can we know the reason behind this? You are always seem here asking questions like taking interviews or either giving solutions to programs asked.That's really good luck for us.

    PS: Apologies if my any question offends you . ๐Ÿ˜”

    [/off-topic post ]
  • pradeep_agrawal
    pradeep_agrawal
    @Corpse-Thrust, the code is just perfect. A simple and straight forward solution to the problem. Great going Corpse-Thrust.

    Few minor modification needed in code:
    1. Validation of input.
    2. Handling for x = 1
    3. "MoveDiscs(x, "A", "C", "B");" should be "MoveDiscs(x, 'A', 'C', 'B');".
    As you are replying from mobile and did not got a chance to compile and run the code, so this is fine.๐Ÿ˜‰

    I had to do some extra handling in my code to display the towers with each move. But i feel that also could have been handled in a better way with lesser code using the approach you followed.

    -Pradeep
  • slashfear
    slashfear
    Hi Guys,

    @pradeep, Good solution dude......... (Can't we make a solution in a simple and smaller way? buddy!!! ๐Ÿ˜’)
    @Corpse-Thrust, good try but give us the complete code....

    Isn't there any other programming guys to give the solution for this puzzle.....?๐Ÿ˜•

    Oh boy...... only C and C++ Rocks, i guess......๐Ÿ˜


    Here is my solution in C++ guys,

     
    [B]
    #include 
    using namespace std;
    
    void towers( int, int, int, int );
    
    int main()
    {
       int nDisks;
       cout << "Enter the starting number of disks: ";
       cin >> nDisks;
       towers( nDisks, 1, 3, 2 );
       return 0;
    }
    
    void towers( int disks, int start, int end, int temp )
    {
       if ( disks == 1 ) {
          cout << start << " --> " << end << '\n';
          return;
       }
       // move disks - 1 disks from start to temp
       towers( disks - 1, start, temp, end );
       // move last disk from start to end
       cout << start << " --> " << end << '\n';
       // move disks - 1 disks from temp to end
       towers( disks - 1, temp, end, start );
    }[/B]
    
    
    PS: Pradeep isn't this the small and better way to solve this puzzle!!! :smile:


    Any comments please post it across guys!!!;-)


    -Arvind(slashfear)
  • pradeep_agrawal
    pradeep_agrawal
    That's a small and sweet solution to the problem. Good work Slashfear.

    slashfear
    @pradeep, Good solution dude......... (Can't we make a solution in a simple and smaller way? buddy!!! ๐Ÿ˜’)
    I agree that the solution is lot simpler like you did. As i already said in a reply to Corpse-Thrust mail that I had to do some extra handling in my code to display the towers with each move. But i admit, that also could have been handled in a better way with lesser code using the approach you folks followed.

    slashfear
    @Corpse-Thrust, good try but give us the complete code....
    I tried the code from Corpse-Thrust. The code works but need few minor changes. The logic he has used is similar to yours.

    -Pradeep
  • Saandeep Sreerambatla
    Saandeep Sreerambatla
    Woha excellent solution ๐Ÿ˜€
  • Corpse-Thrust
    Corpse-Thrust
    slashfear
    @Corpse-Thrust, good try but give us the complete code....
    lol the only thing I missed was that #include line and a few details which Mr. Pradeep mentioned ๐Ÿ˜›

    Anyways,

    #include

    MoveDiscs(int n, char a, char c, char b)
    {
    if(n==2)
    {
    cout<"< cout<"< cout<"< }
    else if(n>2)
    {
    MoveDiscs(n-1, a, b, c);
    cout<"< MoveDiscs(n-1, b, c, a);
    }
    }

    void main()
    {
    int x;
    cout<<"enter the number of discs in tower A : ";
    cin>>x;
    if(x>1)
    MoveDiscs(x, 'A', 'C', 'B');
    else
    cout<<"invalid input";
    }
    @Pradeep -> quick n00b question, but what's validation of input? ๐Ÿ˜›
  • pradeep_agrawal
    pradeep_agrawal
    Corpse-Thrust
    @Pradeep -> quick n00b question, but what's validation of input?
    If your program does work/does not work for particular set of values (e.g., in this case number of disc in tower <= 0 is invalid input), its not compulsory but a good practice to do input validation before processing the data.

    Corpse-Thrust
    cin>>x;
    if(x>0 && x<1)
    MoveDiscs(x, 'A', 'C', 'B');
    else
    cout<<"invalid input";
    If feel the condition should be "if(x<=1)" because the condition you have specified will never execute the "MoveDiscs(x, 'A', 'C', 'B');" code and will always give "invalid input" as output.

    -Pradeep
  • Corpse-Thrust
    Corpse-Thrust
    pradeep_agrawal
    If feel the condition should be "if(x<=1)" because the condition you have specified will never execute the "MoveDiscs(x, 'A', 'C', 'B');" code and will always give "invalid input" as output.

    -Pradeep
    Oh man, I should've known I did a mistake there. I wanted the code to run for x greater than 1, to handle the case for x=1 and any -ve input.

    I've edited the code now. Sorry for the mistake, I was in a hurry, so I just went ahead and typed out whatever was in my mind and didn't bother to put some thought to it. Sorry ๐Ÿ˜”
  • sheeko
    sheeko
    #include
    
    using std::cin;
    
    using std::cout;
    
    using std::endl;
    
    void hanoi(int n,char a,char b,char c)
    {
        static int x=0;
    
        if(n==1)
            cout<<++x<<") "< "< "<>n;
    
        hanoi(n,a,b,c);
    
        return 0;
    }
  • sarveshgupta
    sarveshgupta
    hey that's some distinct ways this problem can be attempted.

    I remember it as it was in my previous semester..
    great work guys..

    Wonder! Recursion just makes the code so small ..

You are reading an archived discussion.

Related Posts

This is my favorite topic and I can't stop discussing it infinite times. I'm still to find better answers. I always believed bicycles could be modified to make them smoother...
We are conducting a series of FREE workshops which are targeted at: 1. Helping you understand what a company looks for in a particular employee 2. Discovering your qualities (mental...
hello..hai ...namste.I am Madhav studying B.E in BIT Mesra,ranchi (2nd year completed) E.C.E branch.I like to make the most of this forum... let us see ๐Ÿ˜›
hi everybody i'm praveen studying in final year E&E i want some details on seminar topics & paper presentation pleas3 help me
Hi all CEans!!!!! I recently noted that the colour scheme for member titles is not appropriate. The reason behind this from my point of view is that the colour of...