254  Towers of Hanoi
Moderator: Board moderators

 Experienced poster
 Posts: 151
 Joined: Tue Nov 16, 2004 7:23 pm
 Location: Norway
 Contact:
hei, what you mean with reverse the peg order, d91lek ??
according to the problem, the order must be A, B, C...
and for the input:
36 23478162346434234
the output should be
0 0 36
because 2^361 is less than 23478162346434234, then all disks are to be moved to peg C !!
Where is my reasoning wrong ?
according to the problem, the order must be A, B, C...
and for the input:
36 23478162346434234
the output should be
0 0 36
because 2^361 is less than 23478162346434234, then all disks are to be moved to peg C !!
Where is my reasoning wrong ?
"A machine can do the work of fifty ordinary men, but no machine can do the work of one extraordinary man.", Shahriar Manzoor

 A great helper
 Posts: 383
 Joined: Mon Oct 18, 2004 8:25 am
 Location: Bangladesh
 Contact:

 New poster
 Posts: 10
 Joined: Mon May 07, 2007 4:45 am
I used my own biginteger class. And I think there is no builtin data type to hold 2^1001 perfectly.
Ami ekhono shopno dekhi...
HomePage
HomePage
Hey, I think I have a working solution to problem 254, however it times out. For any input I've tried it's run instantly, even 100 discs and an arbitrarily large number of moves that is less that (2^n)1. My algorithm involves moving as many discs at a time as possible, so even in the case of 100 discs the run time is never more than n^2.
For input
I get
instantly.
Can anyone give me some valid input that could possibly generate an infinite loop? I am at a loss as to why my program times out.
For input
Code: Select all
3 5
64 2
8 45
100 1267650600228229401496703205375
100 249573895792387598723342235454
100 1000000000000000000000000000000
100 1
23 231234
80 398573924759238475987234
99 3895732987529387459237955432
0 0
Code: Select all
1 1 1
62 1 1
4 2 2
0 0 100
37 33 30
29 15 56
99 1 0
7 6 10
27 31 22
43 26 30
Can anyone give me some valid input that could possibly generate an infinite loop? I am at a loss as to why my program times out.
Couple hints:
On the old Online Judge site, there is a link entitled "Methods to Solve" that gives some helpful advice on many problems. One thing it points out is that this is best solved with bit manipulation. Which makes sense.
Think on this: the smallest ring moves every other turn. If there are an even number of rings, it moves one peg to the right. If there are an odd number of rings, it moves one peg to the left. So, if the lowest order bit is a one, the smallest peg moved that turn. The next smallest ring moves every other even turn in the opposite direction of the smallest ring, etc. The code is left to you to figure out how to pull out up to 100 bits.
Again, it should be noted that the smallest ring does not always move to peg 3 first. The following input:
3 1
4 1
0 0
Produces the following output:
2 0 1
3 1 0
In the end, all rings must end up on peg 3  so the problem is attacked slightly different depending on whether you have an even number or odd number of rings.
I'm guessing that the folks that designed the input for this problem probably loaded it with a slew of data so that if you *don't* solve it with bitwise manipulation, you will see Time Limit Exceeded. Which means that the code to find the bits also needs to be efficient.
That all being said, here's some data that seems to work with my program. I believe its correct  but the online judge is currently down, so I can't validate my code. However, I've weeded out the invalid data previously posted and loaded with some extra real data values. Please feel free to correct if anything seems out of line here:
Input:
3 5
64 2
8 45
100 1267650600228229401496703205375
100 1
36 23478162346
36 46956324692
36 46956324693
36 68719476735
20 231234
80 398573924759238475987234
67 146930240234823848234
67 147030240234823848234
67 147530240234823848234
99 3895732987529387459237955432
88 74732829394872933424110023
0 0
Output:
1 1 1
62 1 1
4 2 2
0 0 100
99 1 0
15 11 10
14 11 11
14 10 12
0 0 36
4 6 10
27 31 22
19 15 33
25 10 32
15 21 31
43 30 26
36 29 23
On the old Online Judge site, there is a link entitled "Methods to Solve" that gives some helpful advice on many problems. One thing it points out is that this is best solved with bit manipulation. Which makes sense.
Think on this: the smallest ring moves every other turn. If there are an even number of rings, it moves one peg to the right. If there are an odd number of rings, it moves one peg to the left. So, if the lowest order bit is a one, the smallest peg moved that turn. The next smallest ring moves every other even turn in the opposite direction of the smallest ring, etc. The code is left to you to figure out how to pull out up to 100 bits.
Again, it should be noted that the smallest ring does not always move to peg 3 first. The following input:
3 1
4 1
0 0
Produces the following output:
2 0 1
3 1 0
In the end, all rings must end up on peg 3  so the problem is attacked slightly different depending on whether you have an even number or odd number of rings.
I'm guessing that the folks that designed the input for this problem probably loaded it with a slew of data so that if you *don't* solve it with bitwise manipulation, you will see Time Limit Exceeded. Which means that the code to find the bits also needs to be efficient.
That all being said, here's some data that seems to work with my program. I believe its correct  but the online judge is currently down, so I can't validate my code. However, I've weeded out the invalid data previously posted and loaded with some extra real data values. Please feel free to correct if anything seems out of line here:
Input:
3 5
64 2
8 45
100 1267650600228229401496703205375
100 1
36 23478162346
36 46956324692
36 46956324693
36 68719476735
20 231234
80 398573924759238475987234
67 146930240234823848234
67 147030240234823848234
67 147530240234823848234
99 3895732987529387459237955432
88 74732829394872933424110023
0 0
Output:
1 1 1
62 1 1
4 2 2
0 0 100
99 1 0
15 11 10
14 11 11
14 10 12
0 0 36
4 6 10
27 31 22
19 15 33
25 10 32
15 21 31
43 30 26
36 29 23
Waah! I was wrong. I just reread the problem. According to their "Algorithm", the smallest disk should alwasy move from A to B to C back to A. So, for an even number of disks, the disks will all end up on peg C. For an odd number of disks, the disks will all end up on peg B.
That violates the classic Hanoi puzzle, but this is the way they've defined the problem.
And I did finally get my code judged. I got a RE. Hmm. Bizarre. Testing on a Linux box with gcc/g++ 4.2 presents validly running code  but somehow they indicate a runtime error with 4.1. Whatever.
That violates the classic Hanoi puzzle, but this is the way they've defined the problem.
And I did finally get my code judged. I got a RE. Hmm. Bizarre. Testing on a Linux box with gcc/g++ 4.2 presents validly running code  but somehow they indicate a runtime error with 4.1. Whatever.
OK  posting my code is not my favorite option, but I'm at a loss for what is happening here. I run this on my Ubuntu Linux box with gcc / g++ 4.2 and everything works fine. I submit it to the judge, and he tells me Runtime Error. Admittedly  C++ is not my primary programming language, so if anyone can kindly point out what would cause RE here, I would be most grateful.
Warning: Once we have identified my RE problem, this code will be removed.
Thanks!
Code: Select all
#include <iostream>
#include <cstdlib>
using namespace std;
char cTurns [ 200 ] = { '\0' }, sTurns [ 200 ] = { '\0' };
void fBinaryConvert ( )
{
for ( int i = 0; sTurns [ 0 ] != '\0'; i ++ )
{
short startPoint = 0, endPoint = 0;
short oldRem = 0, newRem = 0;
if ( sTurns [ 0 ] == '1' )
{
oldRem = 1;
startPoint = 1;
};
while ( sTurns [ startPoint ] != '\0' )
{
newRem = ( sTurns [ startPoint ]  '0' ) % 2;
sTurns [ endPoint ] = ( ( sTurns [ startPoint ]  '0' )
+ ( oldRem * 10 ) ) / 2 + '0';
oldRem = newRem;
startPoint ++;
endPoint ++;
};
sTurns [ endPoint ] = '\0';
cTurns [ i ] = oldRem == 0 ? '0' : '1';
cTurns [ i + 1 ] = '\0';
};
}
int main ( )
{
short iRings;
short sTower1, sTower2, sTower3, sTempTower;
short k;
cin >> iRings >> sTurns;
while ( iRings > 0 )
{
fBinaryConvert ();
sTower1 = 0;
sTower2 = 0;
sTower3 = 0;
for ( k = 0; cTurns [ k ] != '\0'; k++ )
{
if ( cTurns [ k ] == '1' )
{
sTower3 ++;
sTempTower = sTower2;
sTower2 = sTower1;
sTower1 = sTempTower;
}
else
{
sTower1 ++;
sTempTower = sTower2;
sTower2 = sTower3;
sTower3 = sTempTower;
}
}
int iTest = iRings  k;
if ( iTest % 2 )
{
sTempTower = sTower2;
sTower2 = sTower3;
sTower3 = sTempTower;
}
sTower1 += iTest;
if ( iRings % 2 )
cout << sTower1 << " " << sTower3 << " " << sTower2 << endl;
else
cout << sTower1 << " " << sTower2 << " " << sTower3 << endl;
cin >> iRings >> sTurns;
}
return 0;
}
Thanks!