CrazyEngineers
  • 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
Howdy guest!
Dear guest, you must be logged-in to participate on CrazyEngineers. We would love to have you as a member of our community. Consider creating an account or login.
Replies
  • Corpse-Thrust

    MemberMay 22, 2009

    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. 😀
    Are you sure? This action cannot be undone.
    Cancel
  • pradeep_agrawal

    MemberMay 23, 2009

    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
    Are you sure? This action cannot be undone.
    Cancel
  • Corpse-Thrust

    MemberMay 23, 2009

    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?
    Are you sure? This action cannot be undone.
    Cancel
  • pradeep_agrawal

    MemberMay 23, 2009

    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
    Are you sure? This action cannot be undone.
    Cancel
  • Corpse-Thrust

    MemberMay 23, 2009

    @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<<a<<"->"<<b<<endl;
    cout<<a<<"->"<<c<<endl;
    cout<<b<<"->"<<c<<endl;
    }
    else if(n>2)
    {
    MoveDiscs(n-1, a, b, c);
    cout<<a<<"->"<<c<<endl;
    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 😁
    Are you sure? This action cannot be undone.
    Cancel
  • shalini_goel14

    MemberMay 23, 2009

    [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 ]
    Are you sure? This action cannot be undone.
    Cancel
  • pradeep_agrawal

    MemberMay 23, 2009

    @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
    Are you sure? This action cannot be undone.
    Cancel
  • slashfear

    MemberMay 26, 2009

    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 <iostream>
    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)
    Are you sure? This action cannot be undone.
    Cancel
  • pradeep_agrawal

    MemberMay 26, 2009

    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
    Are you sure? This action cannot be undone.
    Cancel
  • Saandeep Sreerambatla

    MemberMay 27, 2009

    Woha excellent solution 😀
    Are you sure? This action cannot be undone.
    Cancel
  • Corpse-Thrust

    MemberMay 27, 2009

    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<iostream.h>

    MoveDiscs(int n, char a, char c, char b)
    {
    if(n==2)
    {
    cout<<a<<"->"<<b<<endl;
    cout<<a<<"->"<<c<<endl;
    cout<<b<<"->"<<c<<endl;
    }
    else if(n>2)
    {
    MoveDiscs(n-1, a, b, c);
    cout<<a<<"->"<<c<<endl;
    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? 😛
    Are you sure? This action cannot be undone.
    Cancel
  • pradeep_agrawal

    MemberMay 27, 2009

    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
    Are you sure? This action cannot be undone.
    Cancel
  • Corpse-Thrust

    MemberMay 27, 2009

    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 😔
    Are you sure? This action cannot be undone.
    Cancel
  • sheeko

    MemberMay 28, 2009

    #include<iostream>
    
    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<<") "<<a<<" => "<<c<<endl<<endl;
    
        else
        {
            hanoi(n-1,a,c,b);
    
            cout<<++x<<") "<<a<<" => "<<c<<endl<<endl;
    
            hanoi(n-1,b,a,c);
        }
    }
    
    int main()
    {
        int n;
    
        char a='1',b='2',c='3';
    
        cout<<"enter the number of desks:";
    
        cin>>n;
    
        hanoi(n,a,b,c);
    
        return 0;
    }
    Are you sure? This action cannot be undone.
    Cancel
  • sarveshgupta

    MemberMay 28, 2009

    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 ..
    Are you sure? This action cannot be undone.
    Cancel
Home Channels Search Login Register