omahafoki.blogg.se - Hanoi towers function

HANOI TOWERS FUNCTION CODE

If we capture these rules, then the last thing we need to do is to work out which disk to move on every iteration.

If a disc has an even parity, it always moves like so A -> C -> B -> A etc.

If a disc has an odd parity, it always moves in the following pattern A -> B -> C -> A etc.

Lets assume our three pegs are A, B, and C with A being the source peg ( where all discs start) and B being the destination peg ( where all discs end up), I call C the pivot peg.

Every disc with the same parity always moves through the same pattern when it comes to their turn to be shifted.

But if we start with 4 discs, disc 1 will be even, disc 2 will be odd and so forth. For example, if we start with 3 discs, the smallest disc ( disc 1) will be odd, the next one ( disc 2) will be even, and the last one ( disc 3) will be odd.

We start with X number of discs, and assign a parity to each one depending on whether we have an odd or an even number of discs.

Here is the pattern that I noticed which produced a working solution. I came up with several possible intuitive solutions and got bogged down with every one of them before I got one that worked. If it took you less than an hour, you’re a much smarter developer than I am.

HANOI TOWERS FUNCTION CODE

Once you have it, try and code it to work out all the bugs, go ahead, I’ll wait :). Before reading any further, do try and come up with the most intuitive solution that you can for this problem ( and don’t cheat by looking it up :)). While it might seem like it should be obvious ( after all we can easily move the disks around to solve it) it is actually very elusive. To solve the Towers of Hanoi programmatically, we need to find a pattern that will easily lend itself to being expressed in code. But, what if you need to translate your solution into code? For those of you who are aware that this problem has a simple recursive solution, pretend to forget it for a second :).īeing the good problem solvers that we are, we will approach this methodically. It is a pretty simple puzzle and you can quickly work out the correct sequence to move the discs and solve the problem. You have 3 pegs ( A, B, C) and a number of discs ( usually 8) we want to move all the discs from the source peg ( peg A) to a destination peg ( peg B), while always making sure that a bigger disc never ends up on top of a smaller one. The Towers of Hanoi problem is very well understood.

Let me demonstrate by looking at Towers of Hanoi as a programming exercise. Incidentally, this also makes a very good case for the value of math skills in a programming context. It’s when a problem is not intuitively recursive, but has a recursive solution, that is where the difference between being able to use it and really understanding it comes out. There are other problems, that we can come up with, which have intuitively recursive solutions and we don’t have too much trouble with those. For example, we know that a recursive function is the best way to traverse a tree in order – it’s in every textbook and so that is how we do it. Even when we understand how it works, we tend to only use it by rote, on problems that we expect to have recursive solutions.

Many programmers don’t really understand recursion – it’s a fact, I’ve seen it time and time again.