254 - Towers of Hanoi

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

bundy
New poster
Posts: 10
Joined: Tue Jul 23, 2002 2:39 pm
Location: Findlay, Oh
Contact:

254 - Towers of Hanoi

Post by bundy »

So I have what appears to me to be a working solution to problem 254, but the judge seems to think otherwise 8). I have timed out. Not sure what my issue is, maybe i was given input that I did not account for. I could use a push in the right diretion. At least when I type valid data, the program appears to be fast. As far as invalid data, I haven't been able to input anything that will junk it up.

[cpp]

#include <iostream>
#include <cmath>

using namespace std;


const int PROGRAM_END = 0;
const int MAX_DISKS = 100;
const int TOWER_COUNT = 3;

int movesToMake = 0;
int moves = 0;
bool quit = false;
void Recurise (int tower[], int numb, int begin, int finish, int hold);
void moveRing(int tower[], int to, int from);

int main()
{
int tower[TOWER_COUNT];
int diskCount = 0;

while(cin >> diskCount >> movesToMake)
{

if (diskCount == 0 && movesToMake == 0)
return 0;

if (movesToMake < 0 ||
diskCount < 0 ||
diskCount > MAX_DISKS ||
movesToMake > (pow(2,diskCount) -1))
{
continue;
}

moves = 0;
quit = false;
tower[0] = diskCount;
tower[1] = 0;
tower[2] = 0;

Recurise(tower,diskCount,0,1,2);

cout << tower[0] << " " << tower[1] << " " << tower[2] << endl;

}

return 0;
}

void Recurise (int tower[], int numb, int begin, int finish, int hold)
{

if (numb == 0)
return;
Recurise(tower, numb-1,begin, hold, finish);
moveRing(tower, begin, finish);
if (quit)
return;
Recurise(tower, numb-1,hold, finish, begin);
}

void moveRing(int tower[], int from, int to)
{



if (moves++ < movesToMake)
{

tower[to]++;
tower[from]--;
}
else
{
quit = true;
}

return;
}
[/cpp]

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

100 1267650600228229401496703205375
0 0

Your program can't handle this input data.

bundy
New poster
Posts: 10
Joined: Tue Jul 23, 2002 2:39 pm
Location: Findlay, Oh
Contact:

Post by bundy »

thanks for pointing that out. That was a silly mistake on my part.

Still doesn't deal with my timeout issue. I am using the correct algorithm for solving hanoi, but that number that you gave is pretty large. Must be why i time out. Is there a trick to this problem like a shortcut?

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

I suggest you not to move the ring one by one, you should try to move 2^k - 1 rings a time.

bundy
New poster
Posts: 10
Joined: Tue Jul 23, 2002 2:39 pm
Location: Findlay, Oh
Contact:

Post by bundy »

interesting idea. I will have to think about that. Thanks for the tip.

bundy
New poster
Posts: 10
Joined: Tue Jul 23, 2002 2:39 pm
Location: Findlay, Oh
Contact:

Post by bundy »

.. wrote:I suggest you not to move the ring one by one, you should try to move 2^k - 1 rings a time.
when you say "k" what are you refering to? How does it relate to n and m?

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

What I mean is, you should move as more rings as possible one time.
It is quite clear that you will got TLE if you move ring one by one in the 100 rings case.

bundy
New poster
Posts: 10
Joined: Tue Jul 23, 2002 2:39 pm
Location: Findlay, Oh
Contact:

Post by bundy »

let me ask this.. is there some kind of trick to doing that or it is an algorithm? I need to get back into this kind of thinking.. brain doesn't want to coporate yet. :D

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

Sure, my algorithm is like this:

Given m, n
If k is the largest k such that m >= 2^k-1, then we know that we are on the way to move k+1 rings from towr A to another tower(say B), and k rings already moved to another tower(tower C).
So we can directly move k rings to tower B, and then minus m by 2^k-1.
For the new m, consider again how many rings are moved from tower B to tower C........and so on.....
Hope you understand what I am saying, I am not good in presentation of idea :wink:

bundy
New poster
Posts: 10
Joined: Tue Jul 23, 2002 2:39 pm
Location: Findlay, Oh
Contact:

Post by bundy »

ok i understand the algo but not working through it correctly

given n = 3 and m = 5

k would be 2, so first move 2 rings to b.

now m = 2

k = 1

1 rings from b to c.

m = 1

that yeilds 1 ring on each pole which is correct, but seem to have a move left... what did i do wrong?

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

I forget to state that, after moving k rings,
you also have to move the k+1-th ring to the other tower. This is the one you left

If you think about the basic step you will know...

Move 3 rings from tower A to C =

Move 2 rings from A to B +
Move the 3rd ring from A to C +
Move 2 rings from B to C

Mikael Sterner
New poster
Posts: 1
Joined: Mon Aug 19, 2002 4:36 pm

254: n=0, m=0 ?

Post by Mikael Sterner »

Is the following a valid set of inputs and outputs for problem 254? (Towers of hanoi; input: 'number of discs', 'move index'; output: discs in stack 'A', 'B', 'C' after the moves.)

Input:
0 0
0 0

Output:
0 0 0

This is said: "The input file will consist of a series of lines. Each line will contain two integers n, m: n, lying within the range [0,100], will denote the number of disks and m, belonging to [0,2^n-1], will be the number of the last move. The file will end at a line formed by two zeros."

The phrase "The file will end at a line formed by two zeros." seems to be common to many problems, so I'd like to know how to interpret it exactly:

a) The last line of the input will consist of two zeros?
b) The first appearance of a line of two zeros denotes the end of the input?

Option b) would be easier to implement, but afaics option a) is just as valid an interpretation for problems where the end line is a valid line itself. (0 \in [0,100], 0 \in [0,2^0 - 1] = [0,0])

Mikael Sterner

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

Option b is the right one. "The file will end at ..." means the two zeros indicates the end of file, you should terminate your program. But only terminate your program if n and m are 0.

21743NX
New poster
Posts: 9
Joined: Tue Aug 27, 2002 8:39 am

254 Tower of Hanoi W.A

Post by 21743NX »

Hi, come kind soul please help me.


I keep getting W.A. for this question
Is there a faster solution rather than the solution that i am using now???

#include <iostream.h>
#include <math.h>

int main (void)
{
int N;
int moves, temp, temp2, k;
int one_c;
int one_now, one_nxt;
int AA, BB, CC;

while (cin >> N >> moves)
{
if (N == 0 && moves == 0)
{
break;
}

one_c = 1;
AA = N;
BB = 0;
CC = 0;

while (1)
{
k = 0;
for (k = 0; k <= moves; k++)
{
temp = (int)pow(2,k);
temp2 = (int)pow(2,k+1);

if (temp <= moves && temp2 > moves)
{
break;
}
}

one_now = one_c;

if (k == 0)
{
one_nxt = one_now + 1;
if (one_nxt > 3)
{
one_nxt -= 3;
}


switch (one_now)
{
case 1: AA--;
break;
case 2: BB--;
break;
case 3: CC--;
break;
default: cout << "something wrong" << endl;
break;
}

switch (one_nxt)
{
case 1: AA++;
break;
case 2: BB++;
break;
case 3: CC++;
break;
default: cout << "something wrong" << endl;
break;
}

break;
}


if (k%2 == 0)
{
one_nxt = one_c + 2;
if (one_nxt > 3)
{
one_nxt = one_nxt - 3;
}
}
else if (k%2 == 1)
{
one_nxt = one_c + 1;
if (one_nxt > 3)
{
one_nxt = one_nxt - 3;
}
}

switch (one_now)
{
case 1: AA = AA - k - 1;
break;
case 2: BB = BB - k - 1;
break;
case 3: CC = CC - k - 1;
break;
default: cout << "something wrong" << endl;
break;
}

switch (one_nxt)
{
case 1: AA = AA + k;
break;
case 2: BB = BB + k;
break;
case 3: CC = CC + k;
break;
default: cout << "something wrong" << endl;
}


temp = one_nxt + one_c;
switch ((temp))
{
case 3: CC = CC +1;
break;
case 4: BB = BB +1;
break;
case 5: AA = AA +1;
break;
default: cout << "something wrong" << endl;
break;
}

moves -= (long)pow(2,k);

if (moves <= 0)
{
break;
}

one_c = one_nxt;

}

cout << AA << " " << BB << " " << CC << endl;

}

return 0;

}

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan

..

Post by Even »

hello...

I use long double to slove it...

but it get WA...should I do it with BIG_NUM ??

or can you give me more test cases ??

thanks in advance..:)

Post Reply

Return to “Volume 2 (200-299)”