Week 5: Tower of Hanoi

So you're given 3 stools and 3 blocks that rest on the first stool, from largest to smallest. You are given the task to move all 3 blocks from the first to last stool one block at a time and can only be placed on an empty stool or one with a larger block on it. After playing this game for a couple of rounds, you notice a pattern. You notice there are precisely efficient ways to solve this in the least amount of steps. After some guess and check, one would notice that it takes (2^n)-1 steps. This can be done for any amount of blocks, where n represents that number.

That is the classic Tower of Hanoi problem given to us this week. Only, it's been tweaked ever so slightly. They added a stool. You might think that only makes it simpler. Well, it times in terms of completing the game, but not for figuring out the most efficient way to do it.

The classic 3 stool Tower of Hanoi problem is world famous for being solvable with recursive functions, and as we discussed last week, recursion is the property of referencing itself. In the 4 stool Tower of Hanoi problem, it also used recursion, but something a little extra. There really is no defined perfect solution for the most efficient way to find the number of steps. No matter what you Google or Bing (jk, don't bing it), everyone has a different opinion. The only agreed part of solving the 4 stool Tower of Hanoi is that there's 3 steps. You move N-K blocks to an intermediate stool, then K stools to the destination, then those N-K stools you previously moved to the destination, While N is the number of blocks, and K is a dynamic amount that changes. No one really agrees on how to determine K. If you want what I think, after computation, I determined K = ciel((2n)^(1/2))-1. While this is not necessarily the best solution, it does result in the most efficient amount of steps. With 4 blocks = 9 moves, 5 blocks = 13 moves, 6 blocks = 17 moves, etc.

Well that covers the Tower of Hanoi problem we discussed this week. We also discussed scopes and namespaces. We covered topics like global, local and non-local variables and saving names in a namespace as well as proper naming of variables and functions. That should do for this week, stay tuned for next week when we talk about trees, so I'll just make like one and leaf (haha, get it?).