iterative towers of hanoi using only °elementary° data types

Discussion in 'C Programming' started by bagratte, Feb 20, 2012.

  1. bagratte

    bagratte Guest

    hello all,

    so the question is: is there any chance to solve a generic towers of hanoi iteratively not using any kind of arrays, stacks, bit-wise wizardry etc.?

    actually the problem is much wider than c language, but i just didn't know where to post. the question could be paraphrased as followed: are there any fixed number of variables by which one could represent the state of towers of hanoi?
    bagratte, Feb 20, 2012
    #1
    1. Advertising

  2. bagratte

    Noob Guest

    Re: iterative towers of hanoi using only elementary data types

    bagratte wrote:

    > actually the problem is much wider than c language, but i just didn't
    > know where to post. the question could be paraphrased as followed:
    > are there any fixed number of variables by which one could represent
    > the state of towers of hanoi?


    I think you want comp.programming
    Noob, Feb 20, 2012
    #2
    1. Advertising

  3. bagratte

    Eric Sosman Guest

    On 2/20/2012 9:08 AM, bagratte wrote:
    > [reformatted for legibility]
    >
    > so the question is: is there any chance to solve a generic towers of
    > hanoi iteratively not using any kind of arrays, stacks, bit-wise wizardry etc.?
    >
    > actually the problem is much wider than c language, but i just didn't know
    > where to post. the question could be paraphrased as followed: are there any
    > fixed number of variables by which one could represent the state of towers
    > of hanoi?


    Yes, of course. As a point of attack on the wider question,
    consider doing array-like things without using arrays. Instead of
    an array x[4], you could have free-standing variables x0,x1,x2,x3.
    You could then write

    /* Instead of x = y */
    switch (i) {
    case 0: x0 = y; break;
    case 1: x1 = y; break;
    case 2: x2 = y; break;
    case 3: x3 = y; break;
    }

    /* Instead of y = x */
    switch (i) {
    case 0: y = x0; break;
    case 1: y = x1; break;
    case 2: y = x3; break;
    case 4: y = x4; break;
    }

    The stupidity of this transformation isn't important; it just
    demonstrates in a sort of "existence proof" way that one could, at
    least in theory, perform array-like operations without arrays.

    Once you have array operations, you can go on to build all sorts
    of other data structures atop them: Stacks, lists, queues, trees,
    whatever you like. (Again, think of this as an existence proof,
    not as practical programming.)

    Here's another existence-proof-ish demonstration that a fixed
    number of variables suffices: The actual machine on which you run
    your program -- any program at all -- is finite and can manage only
    a fixed number of variables. (Yes, even if you "swap" variables to
    I/O devices: You still need to keep track of what's where, and your
    resources for record-keeping are finite.) The number of variables
    a program can manage is huge, but cannot exceed some very large but
    fixed limit. Ergo, QED, reductio ad nauseam, left as an exercise
    for the student, et cetera.

    --
    Eric Sosman
    d
    Eric Sosman, Feb 20, 2012
    #3
  4. bagratte

    BartC Guest

    "bagratte" <> wrote in message
    news:14882925.6018.1329746907715.JavaMail.geo-discussion-forums@vbbed8...
    > hello all,
    >
    > so the question is: is there any chance to solve a generic towers of hanoi
    > iteratively not using any kind of arrays, stacks, bit-wise wizardry etc.?
    >
    > actually the problem is much wider than c language, but i just didn't know
    > where to post. the question could be paraphrased as followed: are there
    > any fixed number of variables by which one could represent the state of
    > towers of hanoi?


    I found this on the first page of google hits for "solve tower of hanoi":

    /* Tower of Hanoi - the answer */
    /* How to move four rings from pin 1 to pin 3 using pin 2 as spare */
    #include <stdio.h>

    void move(int n,int A,int C,int B)
    /* number to move, source pole, destination pole and
    spare pole respectively */
    {
    if (n==1){printf("Move from %d to %d.\n",A,C);}
    else {move(n-1,A,B,C);move(1,A,C,B);move(n-1,B,C,A);}
    }

    int main(void)
    {
    move(4,1,3,2);
    }

    There are no arrays involved. The numbers of rings on each 'pole' are
    presumably stored in the different levels of stack.

    --
    Bartc
    BartC, Feb 20, 2012
    #4
  5. bagratte

    Noob Guest

    BartC wrote:

    > void move(int n, int A, int C, int B)
    > {
    > [...] { move(n-1,A,B,C); move(1,A,C,B); move(n-1,B,C,A); }
    > }


    Recursion is not allowed when an iterative solution is required.
    Noob, Feb 20, 2012
    #5
  6. bagratte

    BartC Guest

    "Noob" <root@127.0.0.1> wrote in message news:jhtqa2$uoi$...
    > BartC wrote:
    >
    >> void move(int n, int A, int C, int B)
    >> {
    >> [...] { move(n-1,A,B,C); move(1,A,C,B); move(n-1,B,C,A); }
    >> }

    >
    > Recursion is not allowed when an iterative solution is required.


    For some reason I didn't notice the word Iterative. Or Stacks. In that case
    I've no idea how it could be done, for N-rings in general where no upper
    limit is specified for N.

    Use strings? Or does that not count as an elementary datatype? And
    presumably a bitmap image is out too.

    And it sounds like we can't even use elementary types, by using bits in a
    number when N is 32 or 64. So what *can* we use?

    --
    Bartc
    BartC, Feb 20, 2012
    #6
  7. bagratte

    Paul N Guest

    On Feb 20, 2:08 pm, bagratte <> wrote:
    > hello all,
    >
    > so the question is: is there any chance to solve a generic towers of hanoi iteratively not using any kind of arrays, stacks, bit-wise wizardry etc.?
    >
    > actually the problem is much wider than c language, but i just didn't know where to post. the question could be paraphrased as followed: are there any fixed number of variables by which one could represent the state of towers of hanoi?


    Here's an iterative solution with a minimum number of variables:

    10 PRINT "Move the smallest disk forward one peg"
    20 PRINT "Make the only possible move that doesn't move the smallest
    disk"
    30 GOTO 10

    This will move all the disks to one of the other pegs, in the minimum
    number of moves, at which point you stop.
    Paul N, Feb 20, 2012
    #7
  8. bagratte

    BartC Guest

    "Paul N" <> wrote in message
    news:...
    > On Feb 20, 2:08 pm, bagratte <> wrote:
    >> hello all,
    >>
    >> so the question is: is there any chance to solve a generic towers of
    >> hanoi iteratively not using any kind of arrays, stacks, bit-wise wizardry
    >> etc.?
    >>
    >> actually the problem is much wider than c language, but i just didn't
    >> know where to post. the question could be paraphrased as followed: are
    >> there any fixed number of variables by which one could represent the
    >> state of towers of hanoi?

    >
    > Here's an iterative solution with a minimum number of variables:
    >
    > 10 PRINT "Move the smallest disk forward one peg"
    > 20 PRINT "Make the only possible move that doesn't move the smallest
    > disk"
    > 30 GOTO 10
    >
    > This will move all the disks to one of the other pegs, in the minimum
    > number of moves, at which point you stop.


    That uses stacks. (In the form of rings on pegs.)

    --
    Bartc
    BartC, Feb 20, 2012
    #8
  9. bagratte

    Liviu Guest

    "bagratte" <> wrote...
    >
    > so the question is: is there any chance to solve a generic towers
    > of hanoi iteratively not using any kind of arrays, stacks, bit-wise
    > wizardry etc.?


    Depends on what precisely you consider "bitwise wizardry" ;-)

    Don't find a handier reference now, but have a look at
    http://stackoverflow.com/questions/2209860/how-does-this-work-weird-towers-of-hanoi-solution

    On a hypothetic computer with native base-3 integer representation
    this could possibly qualify as the "natural" answer.

    Liviu
    Liviu, Feb 21, 2012
    #9
  10. bagratte

    bagratte Guest

    i do find that a bit-wise wizardry.

    now, the key point is in the word "generic" as with any particular configuration one could rudely figure out a number of variables that would represent the state of the pegs.

    to be more precise, what is in question is to write a function, say hanoi(n), that solves iteratively the towers of hanoi of 3 pegs with n disks. it doesn't even matter if the solution is the optimal one or otherwise. but since the optimal solutions are more investigated and present i pick the firstthat i come across, the one in http://en.wikipedia.org/wiki/Tower_of_Hanoi#Simpler_statement_of_iterative_solution, right? it says:

    make the legal move between pegs A and B
    make the legal move between pegs A and C
    make the legal move between pegs B and C
    repeat until complete

    all right, to move a disk from A to B i need to know what are the disks on top of the pile on each of the pegs. that gives me (at least) three variables that hold the radii of the topmost disk on respective pegs. say:

    A_top, B_top, C_top.

    now suppose, in some middle of the process, i am in a configuration where ihave:

    (from bottom to top)
    peg A: 8, 7, 6, 4, 3
    peg B: 5, 2
    peg C: 1

    just a random improvised configuration. now to make the move between, say, peg A and peg B, i recognize that the direction is from B to A. but then i have to be able to determine that the next disk on B is the one with radius5. similarly, in an eventual case when i want to move the 4 from A to somewhere, i have to know that the next one is a generic 6 and so forth...

    one could opt for representing brakes in the ordering of the disks on pegs.that would eventually give an n/2 variables per peg, which is, sadly, not fixed.

    i guess it's impossible unless there is an algorithm that always generates some well structured disk ordering pattern.

    so i am left to do it as christ commands and good folk obeys, i guess; using arrays.
    bagratte, Feb 21, 2012
    #10
  11. On Monday, February 20, 2012 10:08:27 PM UTC+8, bagratte wrote:
    > hello all,
    >
    > so the question is: is there any chance to solve a generic towers of hanoi iteratively not using any kind of arrays, stacks, bit-wise wizardry etc.?
    >
    > actually the problem is much wider than c language, but i just didn't know where to post. the question could be paraphrased as followed: are there any fixed number of variables by which one could represent the state of towers of hanoi?

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

    Solve the general difference equations first.

    Then by given the initial conditions, it is trivial to generate the
    solutions of all the movements of rings on the 3 to 5 rods.

    This is a math problem.
    88888 Dihedral, Feb 21, 2012
    #11
  12. bagratte

    Liviu Guest

    "bagratte" <> wrote...
    >
    > i do find that a bit-wise wizardry.


    Can't tell what "that" is since you snipped the entire context.

    In case this was in reply to my previous post, I wouldn't necessarily
    call it "bitwise wizardy", since that's only a trick of implementation.
    You could write your own functions similar to "(x & (x-1)) % 3"
    without relying on bit manipulations.

    > now, the key point is in the word "generic" as with any particular
    > configuration one could rudely figure out a number of variables that
    > would represent the state of the pegs.


    I guess here lies the misunderstanding. "Solving" the Hanoi problem
    does not necessarily require the program to remember the state of
    the pegs at each step.

    Suppose you found an algorithm to solve the problem, and you proved
    it correct using (sigh) pencil and paper.

    At that point, the program needs only implement the algorithm, not
    the proof. And, if the algorithm gives the next move based solely on
    the step number (index in the sequence of moves), then that's all that
    the program needs to implement - no need to remember the whole
    history of steps or state of the pegs. Unless, of course, you have
    additional requirements besides just "solving" which you haven't
    mentioned upfront, for example making an animation of the process.

    Liviu
    Liviu, Feb 22, 2012
    #12
  13. In article <14882925.6018.1329746907715.JavaMail.geo-discussion-forums@vbbed8>,
    bagratte <> wrote:
    >hello all,
    >
    >so the question is: is there any chance to solve a generic towers of hanoi iteratively
    >not using any kind of arrays, stacks, bit-wise wizardry etc.?


    Yes, but it's not easy and it's not interesting.

    The point of solving Towers of Hanoi isn't to solve the problem --
    it's been solved already -- but to teach the elegance of recursion.

    --
    -Ed Falk,
    http://thespamdiaries.blogspot.com/
    Edward A. Falk, Feb 22, 2012
    #13
  14. Re: iterative towers of hanoi using only °elementary° data types

    (Edward A. Falk) writes:
    > In article <14882925.6018.1329746907715.JavaMail.geo-discussion-forums@vbbed8>,
    > bagratte <> wrote:
    >>hello all,
    >>
    >>so the question is: is there any chance to solve a generic towers of
    >>hanoi iteratively not using any kind of arrays, stacks, bit-wise
    >>wizardry etc.?

    >
    > Yes, but it's not easy and it's not interesting.
    >
    > The point of solving Towers of Hanoi isn't to solve the problem --
    > it's been solved already -- but to teach the elegance of recursion.


    Yes, but solving an inherently recursive problem without using
    recursion can also be instructive (even if the only lesson is that
    recursion is better). And solving it without explicit recursion
    but using stacks (which is not what the OP asked) can help in
    understanding how recursion works.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Will write code for food.
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Feb 22, 2012
    #14
  15. bagratte

    Kaz Kylheku Guest

    Re: iterative towers of hanoi using only°elementary° data types

    On 2012-02-22, Edward A. Falk <> wrote:
    > In article <14882925.6018.1329746907715.JavaMail.geo-discussion-forums@vbbed8>,
    > bagratte <> wrote:
    >>hello all,
    >>
    >>so the question is: is there any chance to solve a generic towers of hanoi iteratively
    >>not using any kind of arrays, stacks, bit-wise wizardry etc.?

    >
    > Yes, but it's not easy and it's not interesting.
    >
    > The point of solving Towers of Hanoi isn't to solve the problem --
    > it's been solved already -- but to teach the elegance of recursion.


    And here I thought the point was to generate a delay of 585 billion years using
    only 64 disks and three rods.
    Kaz Kylheku, Feb 22, 2012
    #15
  16. bagratte

    BartC Guest

    "Liviu" <0m> wrote in message
    news:4f44626c$0$2324$c3e8da3$...
    > "bagratte" <> wrote...


    >> now, the key point is in the word "generic" as with any particular
    >> configuration one could rudely figure out a number of variables that
    >> would represent the state of the pegs.

    >
    > I guess here lies the misunderstanding. "Solving" the Hanoi problem
    > does not necessarily require the program to remember the state of
    > the pegs at each step.
    >
    > Suppose you found an algorithm to solve the problem, and you proved
    > it correct using (sigh) pencil and paper.


    You mean, being able to predict the pattern of moves, without having to
    'physically' move rings from one peg to another?

    I think the algorithm I posted does exactly that, as it doesn't seem to need
    to know the number of rings on each pole, but presumably needs the stack to
    remember where it is in the algorithm.

    --
    Bartc
    BartC, Feb 22, 2012
    #16
  17. bagratte

    Liviu Guest

    "BartC" <> wrote...
    > "Liviu" <0m> wrote...
    >> "bagratte" <> wrote...

    >
    >>> now, the key point is in the word "generic" as with any particular
    >>> configuration one could rudely figure out a number of variables that
    >>> would represent the state of the pegs.

    >>
    >> I guess here lies the misunderstanding. "Solving" the Hanoi problem
    >> does not necessarily require the program to remember the state of
    >> the pegs at each step.
    >>
    >> Suppose you found an algorithm to solve the problem, and you proved
    >> it correct using (sigh) pencil and paper.


    For reference, the link I posted was about the following snippet...

    for (int x=1; x < (1 << nDisks); x++)
    {
    int FromPole = (x&(x-1))%3;
    int ToPole = ((x|(x-1))+1)%3;
    moveDisk(FromPole, ToPole);
    }

    ....which does indeed solve the problem, as long as (1 << nDisks)
    fits into an int.

    > You mean, being able to predict the pattern of moves, without having
    > to 'physically' move rings from one peg to another?


    Yes, and without having to remember/check the state. What the above
    does is essentially "decode" the next move from just the step number.
    This can be proven to work correctly, so the program does not need
    to verify, for example, that the "moveDisk(FromPole, ToPole)" is a
    valid move within the rules, or that the last move completes the game.
    Those facts have been established by proving the algorithm, and the
    program needs just implement the known-good algorithm.

    My other point was that "solving" the problem is the "for" loop itself.
    "moveDisk" could be a user provided callback, which might use the
    information to, for example, draw an animation of the process. For
    that purpose, moveDisk itself may need to maintain its own internal
    history of moves and layout of the pegs/disks. However, those would
    be part of applying the solution, not of "solving" the problem per se.

    > I think the algorithm I posted does exactly that, as it doesn't seem
    > to need to know the number of rings on each pole, but presumably
    > needs the stack to remember where it is in the algorithm.


    Correct on both accounts. The algorithm is provably correct, and it
    does generate the optimum solution. However, it does also store
    more "state" in the stack, which grows to "n" deep. The "bits trick"
    only uses one bit per disk for the "x" counter (and no recursion).

    Liviu
    Liviu, Feb 22, 2012
    #17
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Constant

    Towers of Hanoi

    Constant, Sep 17, 2003, in forum: C++
    Replies:
    8
    Views:
    836
    Noah Roberts
    Sep 18, 2003
  2. elsheikhmh

    Towers of Hanoi

    elsheikhmh, Sep 18, 2003, in forum: C++
    Replies:
    1
    Views:
    492
    Kevin Goodsell
    Sep 18, 2003
  3. Replies:
    6
    Views:
    281
    Marcus Kwok
    Jan 9, 2006
  4. Udyant Wig
    Replies:
    4
    Views:
    345
    Udyant Wig
    Jun 26, 2009
  5. G G
    Replies:
    31
    Views:
    476
    Tim Rentsch
    Mar 9, 2014
Loading...

Share This Page