During one programming class, I remember the professor describing a linear congruential generator for pseudorandom numbers. I thought to myself, "That can't be the best way, I came up with that on my own at home." Then, being young, I said that out loud. I think the professor said something to the effect of "Yes, you're very smart, now shut up."

I also remember helping to solve a variation of the Tower of Hanoi, and getting my name in a published paper.

You should already know what the Tower of Hanoi puzzle is. If not, you know how to use Google: I'm not going to describe it to you here.

You probably didn't need a diagram for how to swap something. |

I hadn't thought about this for years, and then I go and watch two 3blue1brown videos about the Tower (part 1 and part 2) and the whole thing comes trickling back.

We were given a challenge: if we could produce a correct algorithm to solve this variation, then the professor would put our names on the paper he was going to publish. It wasn't easy, but after some days we managed to find the solution. The rest, as they say, is in the International Journal of Computer Mathematics.

Classic Tower of Hanoi solution |

Here's a notation that will help: We'll list the positions of the disks from biggest to smallest, in a single string. So we start out at "AAAA..." and we want to end up at "CCCC...". The classic solution is to first go from AAAA... to ABBB... (by recursion), then to CBBB..., then to CCCC....

There's another variation, mentioned in the 3blue1brown videos, where you can only move disks to the right, except that you can also move a disk from the last peg to the first. This might be called the Cyclic Tower of Hanoi, and it has a solution that's different from, but similar to, the classic Tower. The difference is that here you can't just move the big disk from A to C. It has to go to B first. So you move everything else to C, move the big disk to B, move everything else to A, move the big disk to C, then move everything else to C. This involves "move everything else" three times, so overall it takes more moves. Using our notation, this means we go from AAAA... to ACCC... to BCCC... to BAAA... to CAAA... to CCCC....

Our variation involved swapping, and was a little more complicated. Suppose we're going to implement a function "solve", which moves a tower from A to C. To move the big disk to C you can't just get "everything else" out of the way. You need the second-biggest disk to be on C, for the swap to work. That is, we need to get from AAAA... to ACBB.... Let's ignore how to do that for a moment, and just say we have a function that does that, called "unfold". Basically the function "unfold" takes a stack "AAAA..." and moves to "CBBB...", where the biggest disk of that stack is on one peg, and the rest of that stack is on another. Suppose we also have the reverse function, "fold".

So the overall solution function, "solve", can work by first calling "unfold" to set up the big-disk swap (ACBB...), then doing that swap (CABB...), then calling "fold" to tidy everything up (CCCC...). This is a good start, but unlike with the classic and cyclic variations, our "unfold" function isn't just a smaller version of the overall solution. We still need to define it.

To implement "unfold", how do we get from AAAA... to CBBB...? As before we've got to move the big disk from A to C. So we start by going from AAAA... to ACBB..., then swap to CABB..., then somehow get from CABB... to CBBB.... The first part is easy, we call "unfold" on the sub-tower. This last part is new, though. Now we need some algorithm that can insert a disk underneath a stack. That is, it needs to get from something like ABBB... to BBBB.... This requires another function, let's call that "insert". We'll also need "extract", the inverse of this function (so we can implement "fold").

To implement "insert", how do we get from ABBB... to BBBB...? The big disk needs to get from A to B, so we need to set things up for that swap. This means we need to go from ABBB... to ABCC..., swap to BACC..., and then go from BACC... to BBBB.... Finally we have all the tools we need: The first step there is just moving a whole tower (BB... to CC...), which is the "solve" function we're ultimately building. The last step is "fold" (ACC... to BBB...).

How the five functions call each other. |

I made a site that demonstrates this and a few other variations of the Tower of Hanoi, at the link below.

## No comments:

## Post a Comment