254 - Towers of Hanoi

[bundy]

So I have what appears to me to be a working solution to problem 254, but the judge seems to think otherwise . 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]

[..]

100 1267650600228229401496703205375
0 0

Your program can't handle this input data.

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

[..]

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

[bundy]

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

[bundy]

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?

[..]

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]

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.

[..]

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

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

[..]

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]

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]

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]

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]

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