Problem 40: Goldbach’s conjecture.
I hate Goldbach and his conjecture. That being said, since we have a sieve from problem 39, we can use it. I wonder how fast this is compared to a solution involving trial division, but I’m kinda stuck when trying to time stuff in GHCi (obviously not the right tool for the job, but I’m just starting out, so point me in the right direction :):
goldbach n = head [ (p1, p2) | p1 <- primesR 2 (n - 2), let p2 = n - p1, isPrime p2]
where
factors a = filter (isFactor a) [2..a-1]
isFactor a b = a `mod` b == 0
isPrime a = null $ factors a
Problem 41: Print all even numbers in a range and their Goldbach composition.
It surprised me to see that one of the solutions filters the even numbers from the
[n..m] range with filter even, but then uses dropWhile to filter out 2 - weird
inconsistency, I guess they are trying to showcase many functions:
goldbach_list n m = map goldbach $ filter (>2) $ filter even [n..m]
Problem 49: Gray codes.
The way to construct an n-bit Gray code recursively is very simple: Prefix the (n-1)-bit Gray code with 0, and concatenate it with the reverse (n-1)-bit Gray code prefixed with 1.
On an unrelated note, for the solutions given in the Haskell wiki, you will notice they’re flat out wrong. In this case, the last solution which claims to be more efficient produces an entirely erroneous sequence. This is a common theme in the 99problems pages in the wiki, unfortunately.
gray :: Int -> [String]
gray 0 = [""]
gray n = [ '0' : x | x <- previous ] ++ [ '1' : x | x <- reverse previous ]
where previous = gray (n - 1)
Problem 50: Huffman code.
Woohoo!
import Data.List
import Data.Ord (comparing)
-- Just defining a tree. Leaves and branches which are trees, yadda yadda, you know this.
data Htree a = Leaf a | Branch (Htree a) (Htree a)
deriving Show
-- Read right-to-left. We will create leaves for each pair given, then sort them based on
-- frequency. Subsequently, we'll create a Htree, then serialise it and sort the results.
-- That last (first to appear) sorting step is only necessary to show the result in the
-- order it appears in the question, and is not necessary per se:
huffman freq = sortBy (comparing fst) $ serialise $
htree $ sortBy (comparing fst) $ [ (w, Leaf x) | (x, w) <- freq]
where htree [(_,t)] = t
-- Remember we are building a tree from (weight, Htree) pairs.
-- The Htrees (initially all leaves) are sorted on weight, and
-- `insertBy (comparing fst)` makes sure it gets inserted at the right place.
htree ((w1,t1):(w2,t2):wts) = htree $ insertBy (comparing fst) (w1 + w2, Branch t1 t2) wts
-- The serialisation rules are known from Huffman:
serialise (Branch l r) = [(x, '0':code) | (x, code) <- serialise l] ++
[(x, '1':code) | (x, code) <- serialise r]
serialise (Leaf x) = [(x, "")]
I don’t have much commentary for this one, because I’m in kind of a rush to get packing and leave for a much-awaited (and needed) vacation. See you soon.
« Past Future »