Difficulty understanding the Towers of Hanoi exercise from CIS194
I've just completed the first exercise (Credit Card Number Validation) and was quite happy with myself. But moving on to the next exercise I found myself having trouble trying to understand some parts of the question. I've solved Towers of Hanoi before with an imperative language, but I'm having trouble visualising the steps described in this paragraph: To move n discs (stacked in increasing size) from peg a to peg b using peg c as temporary storage, 1. move n-1 discs from a to c using b as temporary storage 2. move the top disc from a to b 3. move n-1 discs from c to b using a as temporary storage. I've never seen the solution described this way before. So if I start with 5 discs, then for the first step I'll be moving 4 (n-1) discs? But can't I only move 1 disc at a time? And step 2 says to move the top disc from a to b. Which disc is the top disc at this point? I'm still in a very imperative mindset (and having no formal training doesn't help), but I'm hoping that will improve as I go through this course!
The tower of hanoi function you are writing is doing the "move n discs from
peg A to peg C using peg B" stuff.
1. moving n-1 discs doesn't mean moving them in one step, but rather using
the proper sequence of moves that results in (n-1) discs to be moved
2. after you've moved n-1 discs, only one disc is left on the peg and it is
the largest disc from the set of n discs
3. do the same as in point 1
Try to translate the steps literally to code, it will work and
understanding will come after that :)
Best, PV
On Sun, Aug 30, 2015 at 8:27 AM, John Del Rosario
I've just completed the first exercise (Credit Card Number Validation) and was quite happy with myself.
But moving on to the next exercise I found myself having trouble trying to understand some parts of the question.
I've solved Towers of Hanoi before with an imperative language, but I'm having trouble visualising the steps described in this paragraph:
To move n discs (stacked in increasing size) from peg a to peg b using peg c as temporary storage, 1. move n-1 discs from a to c using b as temporary storage 2. move the top disc from a to b 3. move n-1 discs from c to b using a as temporary storage.
I've never seen the solution described this way before. So if I start with 5 discs, then for the first step I'll be moving 4 (n-1) discs? But can't I only move 1 disc at a time?
And step 2 says to move the top disc from a to b. Which disc is the top disc at this point?
I'm still in a very imperative mindset (and having no formal training doesn't help), but I'm hoping that will improve as I go through this course!
_______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
On Sun, Aug 30, 2015 at 1:27 PM, John Del Rosario
So if I start with 5 discs, then for the first step I'll be moving 4 (n-1) discs? But can't I only move 1 disc at a time?
Yes, the problem description elides a few explanations. The idea is that there are two kinds of moves: "atomic" moves where we move 1 disc at a time. And then there's a "big" move, comprising a sequence of atomic moves. One big move accomplishes one unified goal. An example of a big move is moving 4 discs from one peg to another. In the problem text, whether a "move" refers to an atomic move or a big move is something left for the reader to infer. A shortcut is to take every mention of "move" to mean a sequence of one or more atomic moves. But that clashes with the fact that Move is a type synonym representing only atomic moves. Result: confusion. More precise wording of the problem will help. I have nothing to do with CIS194, but allow me to thank you for the pedagogical bug report all the same. -- Kim-Ee
participants (3)
-
John Del Rosario -
Kim-Ee Yeoh -
Petr Vápenka