Towers of Hanoi are ........ing me off

bananaHUNT · 12-13-2009, 06:47 AM

Hi, I made the recursive solution for the ToH problem, but I can't wrap my head around the iterative version.
I can't use vectors etc, just integer arrays or structs. Teacher gave me some clues though:

1. Always move the smallest disc first in a “clockwise” manner.
2. Then, move the smaller remaining disc onto the the other (which is the only legal move left).
3. Keep repeating this process.

I've been busy with the recursive one for almost 2 days, and now this again.. sigh.

bananaHUNT · 12-13-2009, 01:47 PM

50 views and none is answering..

nadroj · 12-13-2009, 05:26 PM

First: no one guaranteed any answer!

I think you had code up earlier, but it was long. This sometimes deters people from helping (as it did when I looked earlier). I would suggest you post code, though minimal code to show what youve done. Its probably a good idea to not put all of your code if its long (as it was earlier)--just post enough to explain what youve got or enough to reproduce an error/warning/other problem. If you dont post any code or pseudocode/english description of what youve attempted, then your even less likely to get help.

Any recursive function can be implemented as an iterative function, and vice versa. This has been proven. So dont give up as there is a solution!

The hints given are pretty good. Start with a completely new file and try and understand then implement the hints. Dont try and implement anything if you dont understand it--it will only bring more confusion.

bananaHUNT · 12-13-2009, 05:37 PM

----

nadroj · 12-13-2009, 05:44 PM

Quote:

Originally Posted by nadroj

I think you had code up earlier, but it was long. This sometimes deters people from helping (as it did when I looked earlier)

Quote:

Originally Posted by nadroj

The hints given are pretty good. Start with a completely new file and try and understand then implement the hints.

It seems youve ignored both of my suggestions. If your confused, its because your trying to convert your existing recursive solution to an iterative one, which is probably hard to do. You arent working on a recursive approach anymore, your re-doing the solution using an iterative approach. Start over. Ignore what youve done for the recursive one, look at the hints which I think are pretty good, and give it a shot. Post your attempt at the iterative approach and let us know when your stuck.

EDIT: Also, the code youve given and suggested we look at call functions that you havent included, so we dont know what it does. I wouldnt look at it even if you did post it. Though maybe others would, of course. Dont take anything personal if Im sounding harsh, because Im not trying to. Hopefully you understand, given that Ive already attempted to help and youve apparently completely ignored it. Should I spend more time "helping"?

bananaHUNT · 12-13-2009, 05:59 PM

I'm sorry for ignoring your advice, I just don't know where to begin, so starting from my recursive code seems logical.

Ok, I would guess you would have to transfer first the smallest disc, and then make the only move that is possible. And keep switching this. But you also have to switch the rotation of the transfer in the process. And stop the program when all discs are in order. Would it be good to use structs or integer arrays?

nadroj · 12-13-2009, 06:20 PM

If you are using, say, n discs and t towers, then have t arrays, each of length n. So say theres 5 discs and 3 towers, create 3 int arrays, each of length 5. Initialize one of the towers to have values that are decreasing, say 5 down to 1 or 4 down to 0 (which might make understanding things easier, since the arrays are 0 based and go from 0 to 4). If a disc is on a tower, its position in the tower is the same as its index, any other values are, say, -1 or whatever. If you need to keep track of how many discs are on each tower you could even use the 1st element (index [0]) to store how many discs are there. This way you dont have to work with the discs being 0-based, just worry about indices 1-5, and 0 is, again how many on that tower (if you need this).

And keep with the given hints:

Quote:

1. Always move the smallest disc first in a “clockwise” manner.
2. Then, move the smaller remaining disc onto the the other (which is the only legal move left).
3. Keep repeating this process.

So the very first iteration has no choice but to move tower1[5] (last disc which is the smallest because its on top) to, say, tower2[1] (if doing 1-based, as described above). Then, again your only option is to move tower1[4] to tower3[1].

Dont overcomplicate things with tons of functions, variables, structs (dont really need any structs, I dont think), and tons of arguments to any functions. Since this is an iterative approach, you shouldnt need many functions.

nadroj · 12-13-2009, 06:26 PM

I think the best thing to do is to ignore programming (or at least that specific to any language, say C++). Grab a piece of paper, or better yet, the TOH puzzle itself! And try and work on the mechanical details that you as a person would do to solve this. Try and formalize what your doing. Then take this and transfer it to C++. The programming part is the easiest part of any problem.

bananaHUNT · 12-13-2009, 06:32 PM

Code:

    int y ( 1 );
    int x = 2^discs;
    for ( int i = 1 ; i < x ; i++ )
    {
        if ( i & 1 )
        {
            if ( y == 3 )
            {
                gold_discs--;
                copper_discs++;
                copper_rod [ copper_discs ] = 1;
                y = 2;
            }
            else
            {
                if ( y == 1 )
                {
                    copper_discs--;
                    silver_discs++;
                    silver_rod [ silver_discs ] = 1;
                    y = 3;
                }
                else
                {
                    silver_discs--;
                    gold_discs++;
                    gold_rod [ gold_discs ] = 1;
                    y = 1;
                }
            }
        }
        else
        {
            make only legal move left;
        }
    }

I think I've got the algorithm in my head, is this about right?
On odd moves you set the lowest disc to A -> B -> C -> A -> .. and on the even moves you make the only legal move possible. But how could I check for that?

nadroj · 12-13-2009, 06:46 PM

Hmm.. interesting. I dont have time to really think about it, Ive only been giving you some high-level hints. I must do my work now and hopefully someone can give you their time. Good luck (this isnt a reply to scare you off). You seem to be getting somewhere without my help anyway.

**CornedBee** · 12-14-2009, 12:53 PM

Quote:

int x = 2^discs;

No time to dive into the logic of your program, but please note that ^ in C-style languages is bitwise xor, not exponentiation. To get "2 to the power of" you can use bit shifts.

slingerland3g · 12-14-2009, 01:13 PM

This has been addressed quite a few times on these forums. I am sure something below should strike your fancy!

C Board - Search Results

12-13-2009, 06:47 AM	#1
bananaHUNT Registered User Join Date: Dec 2009 Posts: 6	Towers of Hanoi are ........ing me off Hi, I made the recursive solution for the ToH problem, but I can't wrap my head around the iterative version. I can't use vectors etc, just integer arrays or structs. Teacher gave me some clues though: 1. Always move the smallest disc first in a “clockwise” manner. 2. Then, move the smaller remaining disc onto the the other (which is the only legal move left). 3. Keep repeating this process. I've been busy with the recursive one for almost 2 days, and now this again.. sigh. Last edited by bananaHUNT; 12-13-2009 at 01:47 PM.
bananaHUNT is offline

12-13-2009, 01:47 PM	#2
bananaHUNT Registered User Join Date: Dec 2009 Posts: 6	50 views and none is answering.. Last edited by bananaHUNT; 12-13-2009 at 02:08 PM.
bananaHUNT is offline

12-13-2009, 05:26 PM	#3
nadroj Registered User Join Date: Oct 2006 Location: Canada Posts: 1,243	First: no one guaranteed any answer! I think you had code up earlier, but it was long. This sometimes deters people from helping (as it did when I looked earlier). I would suggest you post code, though minimal code to show what youve done. Its probably a good idea to not put all of your code if its long (as it was earlier)--just post enough to explain what youve got or enough to reproduce an error/warning/other problem. If you dont post any code or pseudocode/english description of what youve attempted, then your even less likely to get help. Any recursive function can be implemented as an iterative function, and vice versa. This has been proven. So dont give up as there is a solution! The hints given are pretty good. Start with a completely new file and try and understand then implement the hints. Dont try and implement anything if you dont understand it--it will only bring more confusion.
nadroj is offline

12-13-2009, 05:37 PM	#4
bananaHUNT Registered User Join Date: Dec 2009 Posts: 6	---- Last edited by bananaHUNT; 12-13-2009 at 06:44 PM.
bananaHUNT is offline

12-13-2009, 05:59 PM	#6
bananaHUNT Registered User Join Date: Dec 2009 Posts: 6	I'm sorry for ignoring your advice, I just don't know where to begin, so starting from my recursive code seems logical. Ok, I would guess you would have to transfer first the smallest disc, and then make the only move that is possible. And keep switching this. But you also have to switch the rotation of the transfer in the process. And stop the program when all discs are in order. Would it be good to use structs or integer arrays?
bananaHUNT is offline

12-13-2009, 06:26 PM	#8
nadroj Registered User Join Date: Oct 2006 Location: Canada Posts: 1,243	I think the best thing to do is to ignore programming (or at least that specific to any language, say C++). Grab a piece of paper, or better yet, the TOH puzzle itself! And try and work on the mechanical details that you as a person would do to solve this. Try and formalize what your doing. Then take this and transfer it to C++. The programming part is the easiest part of any problem.
nadroj is offline

12-13-2009, 06:32 PM	#9
bananaHUNT Registered User Join Date: Dec 2009 Posts: 6	Code: int y ( 1 ); int x = 2^discs; for ( int i = 1 ; i < x ; i++ ) { if ( i & 1 ) { if ( y == 3 ) { gold_discs--; copper_discs++; copper_rod [ copper_discs ] = 1; y = 2; } else { if ( y == 1 ) { copper_discs--; silver_discs++; silver_rod [ silver_discs ] = 1; y = 3; } else { silver_discs--; gold_discs++; gold_rod [ gold_discs ] = 1; y = 1; } } } else { make only legal move left; } } I think I've got the algorithm in my head, is this about right? On odd moves you set the lowest disc to A -> B -> C -> A -> .. and on the even moves you make the only legal move possible. But how could I check for that? Last edited by bananaHUNT; 12-13-2009 at 06:37 PM.
bananaHUNT is offline

12-13-2009, 06:46 PM	#10
nadroj Registered User Join Date: Oct 2006 Location: Canada Posts: 1,243	Hmm.. interesting. I dont have time to really think about it, Ive only been giving you some high-level hints. I must do my work now and hopefully someone can give you their time. Good luck (this isnt a reply to scare you off). You seem to be getting somewhere without my help anyway.
nadroj is offline

12-14-2009, 01:13 PM	#12
slingerland3g Registered User Join Date: Jan 2008 Location: Seattle Posts: 586	This has been addressed quite a few times on these forums. I am sure something below should strike your fancy! C Board - Search Results
slingerland3g is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Iterative Towers of Hanoi	Mister C	C++ Programming	10	04-11-2009 01:11 AM
towers of hanoi - what is wrong with this code?	kanesoban	C Programming	4	09-17-2007 01:20 PM
Towers of Hanoi (need help)	Loudan	C++ Programming	3	01-30-2006 10:17 PM
Towers of Hanoi, special output.	spoon_	C Programming	3	03-15-2003 06:08 PM
Towers of Hanoi	janehung	C Programming	12	01-07-2002 06:40 AM