«

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 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

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[i] = 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[i] */
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

"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 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" <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

On Feb 20, 2:08*pm, bagratte <bagra...@live.com> 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" <> wrote in message
news:5b583cf1-3033-4652-b11d-...
> On Feb 20, 2:08 pm, bagratte <bagra...@live.com> 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

"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/2...hanoi-solution

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

Liviu

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_o...ative_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.