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

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:
1. As far as I know, VC++ uses int64 instead of long long.
2. You need bignum for this problem, long long isn't enough.

Rajib
New poster
Posts: 28
Joined: Tue Nov 04, 2003 6:45 am
Location: Bangladesh
Hi there,
Some of your given input is not valid. The maximum possible value of moves can be 2^n-1. But you have > 2^n-1 in case of following data:
36 23478162346434234
67 2349302402348238482342348
88 747328293948729334241100234
Output is correct without these inputs.

beloni
Learning poster
Posts: 66
Joined: Thu Jan 05, 2006 1:41 pm
Location: Pelotas, RS, Brazil
hei, what you mean with reverse the peg order, d91-lek ??
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^36-1 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

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:
m does not exeed 2^n-1

Itachi-Forsaken
New poster
Posts: 10
Joined: Mon May 07, 2007 4:45 am
Hi
I was just wonder do you have to make your own class to hold the 2^100-1? Or is there already a data type that can do that..
I'm pretty sure my algorithm works but then I don't know how to hold such large numbers..

Thanks for the help

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:
I used my own biginteger class. And I think there is no built-in data type to hold 2^100-1 perfectly.
Ami ekhono shopno dekhi...
HomePage

vkubushyn
New poster
Posts: 6
Joined: Fri Oct 26, 2007 11:34 pm
Location: Las Vegas, NV
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

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
``````
I get

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

dawynn
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm
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

dawynn
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm
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.

dawynn
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm
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.

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;
}
``````
Warning: Once we have identified my RE problem, this code will be removed.

Thanks!