-
Notifications
You must be signed in to change notification settings - Fork 5
Notes for Week 5 Recursion
- Chapter 5 agenda
- Online chapter
- Tail recursion - Haskell Wiki, SO, Wikibooks
The double factorial of a number n is the product of every other number from 1 (or 2) up to n.
For example, the double factorial of 8 is: 8 × 6 × 4 × 2 = 384, and the double factorial of 7 is: 7 × 5 × 3 × 1 = 105.
Define a doublefactorial function in Haskell. Make sure it is tail recursive (the LYAH chapter doesn't include any information about tail recusion, but you can read about it here).
Implement the function log2, which computes the integer log (base2) of its argument. That is, log2 computes the exponent of the largest power of 2 which is less than or equal to its argument.
For example, log2 16 = 4, log2 11 = 3, and log2 1 = 0.
Write a recursive function to solve the classic Towers of Hanoi problem. Call it hanoi n, where n is the number of rings you need to move from the first post to the third post in the puzzle.
The game consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape. The objective of the puzzle is to move the entire stack to another rod, obeying the following rules:
1. Only one disk may be moved at a time. 2. Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod. 3. No disk may be placed on top of a smaller disk.
Play the game to learn more.
Imagine a fourth post is added to the Towers of Hanoi puzzle. Can you think of a strategy which makes use of the fourth post? Define a Haskell function hanoi' to compute the number of moves required to solve the puzzle now.
- How do we determine when something is wrong? How to debug without println?
- Some ideas here: http://www.haskell.org/haskellwiki/Debugging
-
How do you reason about tail recursion? Only method can you do anything else?
-
Why did some versions of the first question return 0 for 10, 20, 100 etc, e.g.
doubFact 0 = error "Don't know how to double factorial 0" doubFact 1 = 1 doubFact 2 = 2 doubFact n | (nextN /= 0) = n * doubFact nextN where nextN = n - 2
doubFact n = doubFact' n 1
doubFact' 0 a = a
doubFact' 1 a = a
doubFact' n a = doubFact' (n - 2) (n * a)
Alternate answer:
doubleFactorial'' :: Integer -> Integer
doubleFactorial'' n
| n <= 1 = 0
doubleFactorial'' n = doDoubleFactorial n 1
where doDoubleFactorial :: Integer -> Integer -> Integer
doDoubleFactorial n t
| n <= 1 = t
| otherwise = doDoubleFactorial (n - 2) n * t
log2 1 = 0
log2 x = 1 + log2 (div x 2)
-- Tail recursion
log2' n = log2'' n 0
log2'' 1 a = a
log2'' n a = log2'' (div n 2) (a+1)
Cheeky (non-recursive) version:
log2Cheeky n = truncate (sqrt n)
or, as we'll find out in the next chapter...
log2Cheeky' = truncate . sqrt
Alternate answer:
log2'' :: Integer -> Integer
log2'' n
| n <= 1 = 0
log2'' n =
let doLog2 n t
| n <= 1 = t
doLog2 n t = doLog2 (n `div` 2) 1 + t
in doLog2 n 0
The following procedure demonstrates this approach:
- label the pegs A, B, C—these labels may move at different steps
- let n be the total number of discs
- number the discs from 1 (smallest, topmost) to n (largest, bottommost)
To move n discs from peg A to peg C (from Wikipedia):
- move n−1 discs from A to B. This leaves disc n alone on peg A
- move disc n from A to C
- move n−1 discs from B to C so they sit on disc n
Rewrite the patterns to match the rules (I just used trial and error using just rule 2 and n - 1 for the left and right hand side functions):
- a b c -> a c b (Rule 1 (switch a and b) -> b a c, Rule 2 (return a and b) -> a c b)
- a b -> a c (Rule 2)
- a b c -> b a c (Rule 3 (switch b and c) -> a c b, Rule 2 (return b and c) -> b a c)
Note: This is easier to do if the goal is to move it to the middle peg - because you don't have to transform it for Rule 2.
Andrew's Solution
Adapted the QuickSort example from the book as a template of how to write the recursive function. Started with:
hanoi 0 _ _ _ = []
hanoi n a b c = hanoi n a b c ++ [(a,b)] ++ hanoi n a b c
Answer:
hanoi 0 _ _ _ = []
hanoi n a b c = hanoi (n-1) a c b ++ [(a,c)] ++ hanoi (n-1) b a c
Call it using:
hanoi 1 1 2 3
[(1,3)]
hanoi 2 1 2 3
[(1,2),(1,3),(2,3)]
hanoi 3 1 2 3
[(1,3),(1,2),(3,2),(1,3),(2,1),(2,3),(1,3)]
Matt's function to apply the pairs produced by above 'hanoi' function to a set of 3 poles (a list of 3 lists) ordered as source, spare, destination:
applyMoves ((from,to):nextMoves) pegs | trace ("(from:" ++ show from ++ ", to:" ++ show to ++ ") pegs:" ++ show pegs) False = undefined
applyMoves [] pegs = pegs
applyMoves ((1,2):nextMoves) pegs = applyMoves nextMoves [tail (pegs!!0), head (pegs!!0):pegs!!1, pegs!!2]
applyMoves ((1,3):nextMoves) pegs = applyMoves nextMoves [tail (pegs!!0), pegs!!1, head (pegs!!0):pegs!!2]
applyMoves ((2,1):nextMoves) pegs = applyMoves nextMoves [head (pegs!!1):pegs!!0, tail (pegs!!1), pegs!!2]
applyMoves ((2,3):nextMoves) pegs = applyMoves nextMoves [pegs!!0, tail (pegs!!1), head (pegs!!1):pegs!!2]
applyMoves ((3,1):nextMoves) pegs = applyMoves nextMoves [head (pegs!!2):pegs!!0, pegs!!1, tail (pegs!!2)]
applyMoves ((3,2):nextMoves) pegs = applyMoves nextMoves [pegs!!0, head (pegs!!2):pegs!!1, tail (pegs!!2)]
applyMoves (dodgyMove:nextMoves) pegs = error "Invalid moves: "
The first guard demonstrates using 'trace' to debug you'll need the following at the top of your .hs file to enable it:
import Debug.Trace
Call applyMoves using
applyMoves (hanoi 3 1 2 3) [ [1..3], [], [] ]
applyMoves (hanoi 10 1 2 3) [ [1..10], [], [] ]
Matt's Solution
This approach uses a list of 3 lists to represent the towers. It takes the towers as input and recursively returns the result of the next move on the towers as output.
import Debug.Trace
hanoi' disk towers
| trace (show towers) False = undefined
| disk == 0 = moveTopDisk disk towers
| otherwise = step3 disk (step2 disk (step1 disk towers))
step1 disk (a:b:[c]) = let (a':c':[b']) = hanoi' (disk-1) [a,c,b] in [a', b', c']
step2 disk towers = moveTopDisk disk towers
step3 disk (a:b:[c]) = let (b':a':[c']) = hanoi' (disk-1) [b,a,c] in [a', b', c']
moveTopDisk disk (a:b:[c]) = [tail a,b,head a:c]
Call it using (it's 0 based):
hanoi' 4 [ [0..4], [], [] ] -- 5 disks
hanoi' 9 [ [0..9], [], [] ] -- 10 disks
Katie's solution (with pretty printing)
Call using putStr, ie: putStr(hanoi 3) where 3 is the number of disks. Moves these from peg 1 to peg 3.
hanoi :: Int -> String
hanoi n
| n < 1 = "No moves required to shift zero or negative number of disks\n"
| otherwise = hanoiMoves n 1 3
hanoiMoves :: Int -> Int -> Int -> String
hanoiMoves 1 fromPeg toPeg = hanoiPrint fromPeg toPeg
hanoiMoves n fromPeg toPeg = hanoiMoves (n-1) fromPeg otherPeg ++ hanoiMoves 1 fromPeg toPeg ++ hanoiMoves (n-1) otherPeg toPeg
where otherPeg = 6 - toPeg - fromPeg
hanoiPrint :: Int -> Int -> String
hanoiPrint fromPeg toPeg = "Move disk from peg " ++ show fromPeg ++ " to peg " ++ show toPeg ++ "\n"
Haskell Wiki Solution
hanoi :: a -> a -> a -> Int -> [(a, a)]
hanoi source using dest n
| n == 0 = []
| n == 1 = [(source, dest)]
| otherwise = hanoi source dest using (n-1)
++ hanoi source using dest 1
++ hanoi using source dest (n-1)
Challenge question:
No one completed this but we found out that there is no proven optimal solution. This is known as Reve's puzzle.
A Haskell solution using the Frame-Stewart algorithm, which is presumed to be optimal, can be found here: http://stackoverflow.com/questions/3607161/towers-of-hanoi-with-k-pegs
- Gnome3 and Unity in Ubuntu