Tower of Hanoi

Did anyone else see Survivor last week? In it there was a famous puzzle called the Tower of Hanoi. It was also seen in the movie Rise of the Planet of the Apes.


Image source: Brilliant Puzzles. The puzzle in the above image is priced at $15.

I was pulling my hair out, because I could have solved it in 30 seconds. Then I would have gone back to camp and bored everybody with the mathematics and solution for it for three hours.

Here is a demo of the puzzle.

Here is some code I wrote solve it:



For example for a 5-piece puzzle, moving the stack from peg 1 to peg 2, call TowerOfHanoi(&nm,5,1,2,3), where &nm is a pointer to a variable for the number of moves, set initially to 0.

The minimum required moves for n pieces is 2^n-1. Here is the output of my program for 5 pieces:

1 Piece 1 to peg 2
2 Piece 2 to peg 3
3 Piece 1 to peg 3
4 Piece 3 to peg 2
5 Piece 1 to peg 1
6 Piece 2 to peg 2
7 Piece 1 to peg 2
8 Piece 4 to peg 3
9 Piece 1 to peg 3
10 Piece 2 to peg 1
11 Piece 1 to peg 1
12 Piece 3 to peg 3
13 Piece 1 to peg 2
14 Piece 2 to peg 3
15 Piece 1 to peg 3
16 Piece 5 to peg 2
17 Piece 1 to peg 1
18 Piece 2 to peg 2
19 Piece 1 to peg 2
20 Piece 3 to peg 1
21 Piece 1 to peg 3
22 Piece 2 to peg 1
23 Piece 1 to peg 1
24 Piece 4 to peg 2
25 Piece 1 to peg 2
26 Piece 2 to peg 3
27 Piece 1 to peg 3
28 Piece 3 to peg 2
29 Piece 1 to peg 1
30 Piece 2 to peg 2
31 Piece 1 to peg 2

Quote: Wizard

Did anyone else see Survivor last week? In it there was a famous puzzle called the Tower of Hanoi. It was also seen in the movie Rise of the Planet of the Apes.

I referred to the Towers of Hanoi as one of the classic examples to learn recursive algorithms. Another was to figure out all the ways to put 8 queens on a chessboard so that none of them could be taken by another one.

I haven't watched that show since the first season, and that was enough. I would have been pulling my hair out as well, not just for watching people flounder at the puzzle, but for having to watch the show in the first place.

Quote: Wizard

In it there was a famous puzzle called the Tower of Hanoi.

I've seen the puzzle bfore. I don't recall what the objective is. Somethig about inverting the tower, or rebuilding it on another spindle, moving only one piece at a time?

Quote: Nareed

I've seen the puzzle bfore. I don't recall what the objective is.

Move the stack to another spindle, one piece at a time, and a piece may never be above a smaller piece.

Maybe you should apply to Survivor Wiz! They cast a professional poker player before and I remember a discussion how game theory could applied to relationships in order to stay in the game.

The hanoi tower challenge can be watched here:

http://youtu.be/WOduw792DJc?t=12m3s
Continues
http://www.youtube.com/watch?v=jW8ROYqXuTA

In case anyone doesn't realize it, the number of moves required is a simple formula:

( 2 ^ discs ) - 1

Quote: Jufo81

Maybe you should apply to Survivor Wiz! They cast a professional poker player before and I remember a discussion how game theory could applied to relationships in order to stay in the game.

The hanoi tower challenge can be watched here:

http://youtu.be/WOduw792DJc?t=12m3s
Continues
http://www.youtube.com/watch?v=jW8ROYqXuTA

Ouch!

That was painful to watch.

I mean, how tricky is it? I had a wooden Tower with like 10 discs when I was a kid. It took no effort to figure it out....

Quote: Jufo81

Maybe you should apply to Survivor Wiz!

I have filled out the application twice but never got around to making a video. When it came down to it, I just didn't know what to do on it. They give you almost no guidance at all.

Quote: Wizard

I have filled out the application twice but never got around to making a video. When it came down to it, I just didn't know what to do on it. They give you almost no guidance at all.

I've never watched the show, but if it's anything like reality TV, you just need to eat a rat, get really drunk and act stupid. I suppose Survivor has sexy tan people too, so you might want to don some washboard abs and get under a lamp until you're Jersey-tan.

Oh yeah, and don't shave for a month.

Quote: Wizard

Here is some code I wrote solve it:

void TowerOfHanoi(int *MoveNum, int NumberPieces, int origin, int destination, int storage)
{
	if (NumberPieces==1) 
	{	
		(*MoveNum)++;
		cout << (*MoveNum) << "\tPiece 1 to peg " << destination << "\n";
	}
	else 
	{
		TowerOfHanoi(MoveNum,NumberPieces-1,origin,storage,destination);
		(*MoveNum)++;
		cout << (*MoveNum) << "\tPiece " << NumberPieces << " to peg " << destination << "\n"; 
		TowerOfHanoi(MoveNum,NumberPieces-1,storage,destination,origin);
	}
}

It would look more elegant if you got rid of the "if" statement (branches of logic <=> bad), and just added
if(!NumberPieces) return; in the beginning. :)
i

Quote: Tiltpoul

I've never watched the show, but if it's anything like reality TV, you just need to eat a rat, get really drunk and act stupid. I suppose Survivor has sexy tan people too, so you might want to don some washboard abs and get under a lamp until you're Jersey-tan.

Well, they also cast a pale white token nerd almost every season though.

Quote: Wizard

I have filled out the application twice but never got around to making a video. When it came down to it, I just didn't know what to do on it. They give you almost no guidance at all.

Hmm, I would do a card trick and say that I am the "ultimate trickster" to get their attention, or something lame like that...

Many of the players you see on the show aren't even real applicants but were recruited, reports say mostly from certain bars in Los Angeles and California. These recruited aspiring actors don't always even care about the game as long as they get exposure. That's why the quality of the show went really downhill at some point but I think they now take more true fan applicants again.

Casting for 2012 seasons is open now *wink wink*: http://www.cbssurvivorcasting.com/

Quote: weaselman

It would look more elegant if you got rid of the "if" statement (branches of logic <=> bad), and just added
if(!NumberPieces) return; in the beginning. :)
i

Good point. I put more of an emphasis on coding like I actually think than using as few lines as possible. I'm aware good programmers like to code as tight as possible, but I'm not a good programmer.

Quote: Wizard

Good point. I put more of an emphasis on coding like I actually think than using as few lines as possible. I'm aware good programmers like to code as tight as possible, but I'm not a good programmer.

Actually that is no longer true among professional software engineers. Using as few lines as possible was considered a valuable skill at the dawn of programming, but they discovered that programmers were using too many mathematical tricks, and/or default features of the language or of the binary representation of numbers. In an economic setting the real cost was in modifying the code. Nowadays they favor much longer code that spells out the steps in gruesome detail.

A well known and simple piece of code is:

for(i=0;i<n;i++)for(j=0;j<n;j++) A[i,j]=i/j*j/i;

which makes use of the intrinsic nature of integer division to give you the identity matrix.

Now you are supposed to use more prosaic code:

for(i=0;i<n;i++)for(j=0;j<n;j++) if(i==j) A[i,j]=1; else A[i,j]=0;

Wizard,
Isn't it true that you filmed a segment for a show produced by the creator of Survivor?

I'll echo pacomartin's sentiment. As computer time got cheaper and programmers stayed expensive, the emphasis shifted to writing code that was easy to test and modify, not necessarily used the computer most efficiently.

I always enjoy giving students "Tower of Hanoi" as their first attempt to do recursive code. It's a good example because explaining the solution verbally (well, first you will move the 7 disks to the empty pole, then the big one, then the 7 disks back....repeat this idea) is pretty much exactly how the code reads.

I'm REALLY glad I didn't see the episode -- I would have been screaming "YOU IDIOTS" at my TV the entire time!

Quote: pacomartin

Wizard, Isn't it true that you filmed a segment for a show produced by the creator of Survivor?

I've been on two reality shows:

1. The Casino. I was heavily featured in an episode that never aired. I blame myself that the producers never aired it. As I recall this one was by Mark Burnett, who also produces Survivor.
2. Vegas Challenge. A seldom-seen tournament that took place at the Flamingo. I have a video tape of it, perhaps I'll try to convert it to an AVI file and post it on YouTube.

(edit)

Quote: pacomartin

for(i=0;i<n;i++)for(j=0;j<n;j++) A[i,j]=i/j*j/i;

which makes use of the intrinsic nature of integer division to give you the identity matrix.

Now you are supposed to use more prosaic code:

for(i=0;i<n;i++)for(j=0;j<n;j++) if(i==j) A[i,j]=1; else A[i,j]=0;

Actually, both variants aren't very good :)
The "right way" to get an identity matrix if you are doing it professionally, would be something like

memset(a, 0, n*n*sizeof(int));
for(i=0; i < n; i++) a[ i][ i] = 1;


The goal is not (and never was) to write as few lines of code as possible. The goal is first efficiency, and second readability. When optimizing for these two criteria, more often than not you end up with fewer lines, but that is more of a byproduct.

(an even better version of the loop above is)
for(i=0; i < n*n; i+n+1) ((int*) a)[ i]=1;


When talking about efficiency, it is not "computer time" you are trying to save, it is the person's sitting in front of the computer, and waiting for your program to finish. That person's time is often way more expensive than the time of the guy who wrote the program (and even if it isn't, multiplied by the number of users, it still will be). Besides, what I always tell my students is that it is not supposed to take you any more time to write good code. It could take a little longer first time around, but once you are used to it, it becomes second nature.

And the second goal - readability is actually a huge time saver for (expensive) programmers - not having to parse through the crud of unnecessary checks, pointless branches, intermediate variables and useless comments helps a great deal when you need to understand quickly what the piece of code you are looking at is doing.

In fact, many of the "shortcut patterns", like the ones above, are recognized by a programmer with any experience momentarily, and do not need to be "read" at all ... you just say to yourself "aha, identity matrix", and keep going without making any pause at all.