254 - Towers of Hanoi

[stubbscroll]

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]

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]

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 ?

[emotional blind]

m does not exeed 2^n-1

[Itachi-Forsaken]

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]

I used my own biginteger class. And I think there is no built-in data type to hold 2^100-1 perfectly.

[vkubushyn]

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]

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]

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]

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!