towers of hanoi. recursion, i'm sure this will be on someone'sproblem set

Discussion in 'C Programming' started by G G, Sep 9, 2013.

  1. G G

    G G Guest

    uh?

    i can solve it by hand, the towers of hanoi.
    but, i'm missing the recursion algorithm altogether.
    wait, don't give me the answer, maybe a hint...
    the base cases is what? and how did you think through it
    to get the base case. (you don't have to give me the base case,
    but maybe what,how, maybe what was right, what should
    i be looking for or thinking about to find the base case. it can't
    be the "number of disk" to be moved are on target pole?
    it would also be the case that the other poles are empty.

    and, in the logic of the program don't i have to check on
    the size of the disk if one is on the peg before i can move
    a disk to a pole?

    let me also add. the function is suppose to have four parameters
    a) The number of disks to be moved
    b) The peg on which these disks are initially threaded
    c) The peg to which this stack of disks is to be moved
    d) The peg to be used as a temporary holding area

    not given, i created solveTower prototype:

    solveTower( int numberOfDisk, int initialPegWithDisk, int finalPegWithDisk,
    int temporaryHoldingPeg);

    and, so, this is to be called on until the base case occurs?

    should i post the exercise's text? as you can see i'm confused a bit. :)
    a great bit.

    g.
     
    G G, Sep 9, 2013
    #1
    1. Advertisements

  2. G G

    Eric Sosman Guest

    For me, the crucial step in inventing a recursion is not
    identifying the base case, but finding how to decompose the
    large problem into smaller problems. In this case, you look
    at the original stack of disks 1,2,...,N on peg A, and you
    think "If only I could move the upper disks 1,2,...,(N-1) from
    A to B, then I could move disk N from A to C, then I could move
    1,2,...,(N-1) from B to C." And there's your decomposition:
    You began with the problem of moving N disks, and now you've
    got two smaller problems (moving N-1 disks, twice) plus one
    move of the lone disk N that you know how to do directly.

    This should give you enough to get well started.
     
    Eric Sosman, Sep 9, 2013
    #2
    1. Advertisements

  3. G G

    G G Guest

    ok, i've got it. i think.

    thanks. decomposition flip the switch.
    right, as you say n-1 twice and a move... smaller and smaller problem to solve
    right, right.
    (n-1, A, B, C)
    move( n, A,C)
    (n-1, B, C, A)

    something like that... ok. let me think on it and code it up, but yeah, good,
    good. great hint!

    thanks a lot,

    g.
     
    G G, Sep 9, 2013
    #3
  4. G G

    Bill Davy Guest


    You can make it more interesting with a random initial allocation of disks,
    in which case you find the first disk on C which is out of place (the bad
    disk), move everything above the bad disk off it (to A or B - the choice
    matters), move the bad disk (to B or A) and then move the correct disk to C.
    But that may not be optimal either.
     
    Bill Davy, Sep 10, 2013
    #4
  5. G G

    G G Guest

    This should give you enough to get well started.
    Bill, first things first. :)

    Guys and Ladies let me apologize about how long my writing will be.
    I just think there is something really cool about this and I don't want
    to miss it.

    Ben gave me great insight into thinking about the problem, but
    I'm having trouble tracing my thoughts by hand. pencil and paper.
    I think I'm on the right track, but apparently I don't fully understand.
    So, if you all don't mind, please a little more discussion???

    Given:
    Disks
    Three Pegs (or poles) (for this problem)
    restrictions: smaller disk must always be on top of a larger disk
    only one disk can be moved at a time to a peg/pole.

    function parameters:
    The number of disks to be moved
    The peg on which those disks are initially threaded
    The peg to which this stack of disks is to be moved
    The peg to be used as a temporary holding area.

    Ben discussion of decomposing the problem to a smaller
    and smaller problem. simpler and simpler

    Find: a recursive algorithm that solves the Tower of Hanoi.

    Solution:

    Let the poles have the names A, B, and C. ( I found that I had to make
    the names a little more generic as I try to trace the function by hand)

    The disks will start on A and all will have to be moved to C, with the constraints
    mentioned above.

    In the simplest of cases, there is only one disk. So that disk can be moved
    to the final destination. A direct move. from A to C. so let me call A the
    source of the disk and C the destination of the disk.
    move from source to destination.

    The next simplest of cases, there are two disk. So, one the smallest disk
    which is on top of a larger disk must be move to a temporary locations,
    amongst the three pegs.

    So move a disk from A to B. From source to the temporary peg named B.

    Now a direct move can take place. move a disk from A to C. I say direct only
    because I am envisioning the pegs and disk as if I can reach out and grab and
    move them. Of course, this is the larger of the two disk.
    move a disk from A to C
    move a disk from source to destination.
    ( here I realize the destination is changing, the destination will not always
    be the same peg for each move.)

    Finally move the disk on B to C. The peg B temporary held the smallest disk.
    move a disk from source to destination. ( here again I note that source is not
    A peg, source should be the peg from which I am grabbing the disk.
    so, yes, move a disk from source to destination. that thought took a while
    to grasp even with Ben's very very good hint. (different sources and different
    destination. i mean i new that each disk may have to go to a different peg, but
    using A,B,C, the concrete, instead of the generic source, destination, temporary
    kept tying me up, mentally.

    Ok, armed with the generic thought of, move a disk from a source to a destination
    the next case, starting with three disk. This is where I seem to loose it.
    With three disk I understand I'm going to need to temporary move a disk to
    another peg. Also, I realize that must happen more than once. Meaning that there
    are not pegs to place the smaller disk so that a direct move of the largest
    disk can go to the final destination. ( OK, too many word, ok )

    The concrete: A, B, C, three disk on A with smallest on top, largest at the bottom.

    move a disk from A to C ( i know do this from trial and error otherwise i would
    end doing more moves...)
    move a disk from A to B

    at this point, the largest disk is by itself on peg A, but it cannot be moved to
    peg C because the smallest disk is there.
    so, the smallest disk, which is on C, has to be moved to a temporary location
    which meets the constraints, smaller on top of larger. Therefore the disk on C
    can be moved to B.

    Now the disk on A can be moved to C. This places the largest disk on C.

    There are two disk on B so, there are actually two places where the smallest disk
    may go and hold to the rules. The smallest could be moved to C or the smallest
    could be moved to A. Moving the smallest to B, is not helping. so, I temporarily
    place the smallest disk on A, or move a disk from B to A temporarily.

    move a disk from B to C

    move a disk from A to C

    done.

    P-code:

    solveTowerOfHanoi ( int n, int source, int destination, int temporaryPeg)
    {
    if ( n == 1)
    print the move "one disk from source to destination" // source: A,B,C
    // destination: A,B,C
    else
    begin
    solveTowerOfHanoi( n -1, source, temporaryPeg, destination)
    /*
    this is what i think is confusing me, the names, here i realize
    i am passing into the function the destination, temporaryPeg
    */
    move from source to destination (here destination is temporaryPeg)

    /*
    the following call's placement of parameters seem to take some
    insight, right? i'm missing it.

    */
    solveTowerOfHanoi( n - 1, ............ what.................)

    end /* else */

    I had this problem before and I thought I had mastered it. once the base case is occurs,
    tracing the function back up, so to speak (write).
    n=3
    solveTowerOfHanoi ( 3 - 1, A, C, B )

    solveTowerOfHanoi ( 2 - 1, A, B, C )

    [--- solveTowerOfHanoi ( 1 -1, A, C, B )

    here n = 1
    print the move one disk from source to destination
    so move one disk from A to C
    [-----------

    aren't i back at the: solveTowerOfHanoi ( 2 - 1, A, B, C )
    so that means ???

    move from source to destination
    move from A to B

    solveTowerOfHanoi ( 2 - 1, ...... what........ )

    here's where i have confused myself. do i think about the second to last move or
    the next move? at this point the source must change? the source needs to
    be C and destination needs to be B... so

    solveTowerOfHanoi ( 2- 1, C, B, A) which would lead to
    solveTowerOfHanoi ( n-1, destination, temporaryPeg, source)

    so:

    P-code:

    solveTowerOfHanoi ( int n, int source, int destination, int temporaryPeg)
    {
    if ( n == 1)
    print the move "one disk from source to destination" // source: A,B,C
    // destination: A,B,C
    else
    begin

    solveTowerOfHanoi( n -1, source, temporaryPeg, destination )

    move from source to destination (here destination is temporaryPeg)

    solveTowerOfHanoi( n - 1, destination, temporaryPeg, source )

    end /* else */

    } /* solveTowerOfHanoi */

    right? or close? i mean where did i lose it?

    thanks, i know it's wordy .... sorry....

    g.
     
    G G, Sep 12, 2013
    #5
  6. G G

    Eric Sosman Guest

    Let me in turn apologize for the brevity of my reply.
    Here's where you need to change viewpoints. Instead of "one disk
    atop a larger disk," try to see "a pile of one or more disks atop a
    larger disk."
     
    Eric Sosman, Sep 12, 2013
    #6
  7. G G

    G G Guest

    solveTowerOfHanoi ( int n, int source, int destination, int temporaryPeg)
    {
    if ( n == 1)
    print the move "one disk from source to destination" // source: A,B,C
    // destination: A,B,C
    else
    begin

    solveTowerOfHanoi( n -1, source, temporaryPeg, destination )

    move from source to destination

    solveTowerOfHanoi( n - 1, temporaryPeg, destination, source )

    end /* else */

    } /* solveTowerOfHanoi */

    ok.

    but to get that algorithm, i coded up the one i presented earlier.
    i could see where the problem was from the executing program.
    well, i got there, but i should have been able to do it with out the computer.
    i need to revisit my logic in the last solveTowerOfHanoi(), as to why i missed it the
    first time through. what is going where and why that's the case.

    i guess my thinking was backwards... i thought of a pile of disc that i could not move, or i did
    not know how to move, but i did know how to move one disc, so, i kept working up
    the disc from n.

    to me the n represents starting at the bottom of the disc and n-1 represents working
    up the disc column until i got to the top one.

    that maybe why the first algo was off...

    thanks,

    g.
     
    G G, Sep 12, 2013
    #7
  8. G G

    G G Guest

    On Thursday, September 12, 2013 3:19:35 PM UTC-4, G G wrote:

    Bill, i'm going to try the problem you proposed.

    the solution may not be pretty. :)


    g.
     
    G G, Sep 12, 2013
    #8
  9. G G

    BartC Guest

    Did your solution work? I've had a go and it looks similar to yours. But the
    way I did it:

    I use recursion a lot but I found this puzzle difficult! So I had a go with
    numbers on bits of card, moving them between 3 piles (I used to use playing
    cards, but haven't got any). This way I discovered the general strategy.

    The next step was coding something, but I avoid C; use an easier language
    (eg. Python) to play with algorithms, only coding in C, if that is the
    requirement, when it's all working! (That means you can also ask in any
    programming forum, as algorithm is usually independent of language).

    For this, I needed to find a representation for the pegs and discs, and I
    also found it essential to be able to display the current state of the pegs.
    For simplicity, shown horizontally, so the initial state might be shown as:

    Peg 1: (10 9 8 7 6 5 4 3 2 1 )
    Peg 2: ()
    Peg 3: ()

    And the final state (if it worked!) might be:

    Peg 1: ()
    Peg 2: (10 9 8 7 6 5 4 3 2 1 )
    Peg 3: ()

    The central function I had, the one similar to yours, looks like this
    (consider this pseudo-code):

    proc movediscs(n,a,b)=
    if n=1 then
    movedisc(a,b)
    else
    c:=thirdpeg(a,b)
    movediscs(n-1,a,c)
    movedisc(a,b)
    movediscs(n-1,c,b)
    endif
    end

    One difference is that this function works out the temporary peg for itself
    (you need a function that, given two different values from 1 to 3, returns
    the third value).

    The function movedisc() moves a single disc (from the top of peg a to the
    top of b), this is where the actual work is done, but this is irrelevant to
    the algorithm.
     
    BartC, Sep 13, 2013
    #9
  10. Things get simpler if you allow for the possibility of moving no discs.
    That's the way I like to do it, but it seems to be rare in all the
    presentations I've seen.

    <snip>
     
    Ben Bacarisse, Sep 13, 2013
    #10
  11. G G

    BartC Guest

    Do you mean, not bothering to explicitly represent the state of the pegs and
    discs?

    I have some benchmark programs that do that, just go through the motions (as
    the recursive efficiency was more important), for example:

    void hanoi(int num_discs,int start,int end) { /* not my code... */
    if (num_discs==1) return;
    hanoi ((num_discs - 1), start, 6-start-end);
    hanoi (1, start, end);
    hanoi ((num_discs - 1), (6-start-end), end);
    }

    But I was interested in deriving this code, and also in actually moving
    discs around so that at each step I could see what it was up to.
     
    BartC, Sep 13, 2013
    #11
  12. G G

    G G Guest

    Yes, the final algorithm did work. The earlier one presented had an error in
    the placement of the choices of source, destination, and temporary pegs to
    be past into the last recursive call in the function. Below is the correct one.
    Well, the one I used to produce the program.

    ---------------------------------------------------------------------
    solveTowerOfHanoi ( int n, int source, int destination, int temporaryPeg)
    {
    if ( n == 1)
    print the move "one disk from source to destination" // source: A,B,C
    // destination: A,B,C
    else
    begin

    solveTowerOfHanoi( n -1, source, temporaryPeg, destination )

    move from source to destination

    solveTowerOfHanoi( n - 1, temporaryPeg, destination, source )

    end /* else */

    } /* solveTowerOfHanoi */
    -------------------------------------------------------------------
    i found my error only when i had coded it up and ran the program. of course from thinking
    about it and drawing the trace and knowing how the disk should move from the constraints,
    i found the error quickly. ( here, speaking about the first algorithm where i had written so much :) )
    i'm learning C by self studying. i found this group and it has been great. i feel
    as if i am no longer just learning from the book's authors, I actually have teachers.
    that said the implementation in C was not bad at all. i don't mind sharing at all. everyone,
    here is sharing their knowledge with me, so ... no problem.

    (my thought is to do every exercise in the book. it takes some time, but really
    there are some things only discussed in the exercises that seem really important
    to having a well rounded comp. science start. anyway...)

    --------------------------------------------------------------------

    /*
    Exercise from C How To Program by Deitel and Deitel.
    This program is a solution to exercise 5.35 page 190,
    that ask for the creation of a program to solve the
    Towers of Hanoi. There are constraints as to how the
    disk may be placed on the pegs.

    The program must use recursion, and the function call must
    have the following parameters.

    The number of disks to be moved
    The peg on which these disks are intially threaded
    The peg to which this stack of disk is to be moved
    The peg to be used as a temporary holding area

    The print out is consistant with what is ask for by the problem:
    for example:
    1->3 (This means move one disk from peg 1 to peg 3.)
    1->2
    3->2
    1->3
    ...

    This program was written by gdotone, with a tremendous
    hint given by Ben of the comp.lang.c (google groups)
    */

    #include <stdio.h>

    /* prototype */
    void solveTowerOfHanoi ( int n, int source, int destination, int temporaryPeg );


    int main(int argc, char * argv[])
    {
    int n; /* number of disk */
    int initialPeg; /* starting peg with disc */
    int finalPeg; /* where disc should end up */
    int tempHoldingPeg; /* temporary Peg */

    printf( "This program solves the Tower of Hanoi recursively\n" );

    printf( "Enter the number of disc: " );
    scanf( "%d", &n );

    printf( "Enter the initial peg where disc can be found: " );
    scanf( "%d", &initialPeg );

    printf( "Enter final peg where disc should end up: " );
    scanf("%d", &finalPeg );

    printf( "Enter temporary holding peg: " );
    scanf( "%d", &tempHoldingPeg );

    printf("\n");
    printf( "The following means a disk on .#. peg moves to .#. peg.\n\n" );

    solveTowerOfHanoi(n, initialPeg, finalPeg, tempHoldingPeg );

    return 0;

    } /* end main( void ) */


    /******************** solveTowerOfHanoi *********************/

    void solveTowerOfHanoi ( int n, int source, int destination, int temporaryPeg)
    {
    if (n == 1)
    printf("%d -> %d\n", source, destination);
    else
    {
    solveTowerOfHanoi( n - 1, source, temporaryPeg, destination );
    printf( "%d -> %d\n", source, destination );
    solveTowerOfHanoi( n - 1, temporaryPeg, destination, source );
    } /* end else */

    } /* end solveTowerOfHanoi ( int n, int source ... ) */

    ----------------------------------------------------------------
    For this problem, it makes a simple case of putting all the disk on one initial peg.
    Actually, the program allows you to decide which peg will be your temporary peg.
    Well for example, using 3, 1, 3, 2 gives the same pattern of movement ask by the
    exercise in the book. those numbers are the responses used to the programs
    prompts.
    That's cool. The C program presented here could do the same with a few lines of code.
    Actually with a little extra work only the initial peg with all the disk on them really
    needs to be inputed. The program could be written to assign the other two pegs for what-
    ever purpose. ( a few more line of code, but of course some of the original lines
    would not be necessary. may be even a shorter program over all )

    g.
     
    G G, Sep 13, 2013
    #12
  13. G G

    Willem Guest

    Ben Bacarisse wrote:
    )<snip>
    )> The central function I had, the one similar to yours, looks like this
    )> (consider this pseudo-code):
    )>
    )> proc movediscs(n,a,b)=
    )> if n=1 then
    )> movedisc(a,b)
    )> else
    )> c:=thirdpeg(a,b)
    )> movediscs(n-1,a,c)
    )> movedisc(a,b)
    )> movediscs(n-1,c,b)
    )> endif
    )> end
    )
    ) Things get simpler if you allow for the possibility of moving no discs.

    Case in point:

    proc movediscs(n,a,b)=
    if n>0 then
    c:=thirdpeg(a,b)
    movediscs(n-1,a,c)
    movedisc(a,b)
    movediscs(n-1,c,b)
    endif
    end

    )> One difference is that this function works out the temporary peg for itself
    )> (you need a function that, given two different values from 1 to 3, returns
    )> the third value).
    )
    ) That's the way I like to do it, but it seems to be rare in all the
    ) presentations I've seen.

    Seems wasteful, when you can just pass along the third peg:

    proc movediscs(n,a,b,c)=
    if n>0 then
    movediscs(n-1,a,c,b)
    movedisc(a,b)
    movediscs(n-1,c,b,a)
    endif
    end

    SaSW, Willem
    --
    Disclaimer: I am in no way responsible for any of the statements
    made in the above text. For all I know I might be
    drugged or something..
    No I'm not paranoid. You all think I'm paranoid, don't you !
    #EOT
     
    Willem, Sep 13, 2013
    #13
  14. G G

    BartC Guest

    Yes, that's neater, although it doesn't change the number of actual discs
    that need to be moved. But it seems to double the number of calls needed,
    and makes it a bit slower.
    That's also neater, in not having to provide the extra bit of logic (at a
    cost of having to provide info that it ought to be able to deduce). However
    it also makes it a bit faster!

    I suppose the temporary peg can be worked out just at the beginning, so the
    logic is needed, but the user doesn't need to enter it and it will still be
    faster.
     
    BartC, Sep 13, 2013
    #14
  15. Seems wasteful to pass a third argument to a recursive function!! If
    'src' and 'dst' hold pegs numbered 1, 2 or 3, then src ^ dst is the spare
    peg:

    void move(int n_disks, int from_peg, int to_peg)
    {
    if (n_disks > 0) {
    move(n_disks - 1, from_peg, from_peg ^ to_peg);
    printf("Move disk from peg %d to peg %d\n", from_peg, to_peg);
    move(n_disks - 1, from_peg ^ to_peg, to_peg);
    }
    }

    (You'd probably want to comment that!) Still, wasteful is all
    relative...
     
    Ben Bacarisse, Sep 13, 2013
    #15
  16. Is it faster if you number the pegs 1, 2 and 3 and use xor? Actually I
    am surprised you can detect any difference in speed given that the
    program is likely to be IO bound.

    <snip>
     
    Ben Bacarisse, Sep 13, 2013
    #16
  17. No, but Willem has answered for me. In general, you want functions to
    work with vacuous cases (empty strings, zero-length arrays, no pegs...).

    <snip>
     
    Ben Bacarisse, Sep 13, 2013
    #17
  18. G G

    BartC Guest

    Using xor was marginally slower, although that might be to do with how my
    language works.

    But trying it in C in this form:

    void hanoi(int n,int a,int b) {
    if (n==1) return;
    hanoi (n-1, a, a^b);
    hanoi (1, a,b);
    hanoi (n-1, a^b, b);
    }

    even this was marginally (1%) slower than providing the extra argument.
    Although this version doesn't do any actual work of moving discs around, so
    the difference will be negligible. Avoiding an extra argument I think is
    more elegant however.
    Not really. While it was amusing to display the results at each step,
    normally it will only show the results at the beginning and the end.
     
    BartC, Sep 14, 2013
    #18
  19. G G

    Willem Guest

    Ben Bacarisse wrote:
    )> Seems wasteful, when you can just pass along the third peg:
    )>
    )> proc movediscs(n,a,b,c)=
    )> if n>0 then
    )> movediscs(n-1,a,c,b)
    )> movedisc(a,b)
    )> movediscs(n-1,c,b,a)
    )> endif
    )> end
    )
    ) Seems wasteful to pass a third argument to a recursive function!! If
    ) 'src' and 'dst' hold pegs numbered 1, 2 or 3, then src ^ dst is the spare
    ) peg:
    )
    ) void move(int n_disks, int from_peg, int to_peg)
    ) {
    ) if (n_disks > 0) {
    ) move(n_disks - 1, from_peg, from_peg ^ to_peg);
    ) printf("Move disk from peg %d to peg %d\n", from_peg, to_peg);
    ) move(n_disks - 1, from_peg ^ to_peg, to_peg);
    ) }
    ) }
    )
    ) (You'd probably want to comment that!) Still, wasteful is all
    ) relative...

    Indeed! The waste I was thinking of was the time I would need to
    think about a solution to finding the third peg, given the other two.


    SaSW, Willem
    --
    Disclaimer: I am in no way responsible for any of the statements
    made in the above text. For all I know I might be
    drugged or something..
    No I'm not paranoid. You all think I'm paranoid, don't you !
    #EOT
     
    Willem, Sep 14, 2013
    #19
  20. Ah, I hadn't thought of that. However, for me (and, I suspect, for you
    too) it's not a fair fight. Since I was already well-aware of the four
    argument version, any thought at all would be a wast of time (and that's
    probably the only time I'll ever say that).
     
    Ben Bacarisse, Sep 14, 2013
    #20
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.