Posts Tagged ‘same’

Programming Praxis – Same Five Digits

April 19, 2011

In today’s Programming Praxis exercise, our goal is to solve a numeric riddle. Let’s get started, shall we?

Some imports:

import Data.List
import qualified Data.List.Key as K

The relevant squares are the ones that consists only of the digits 1 through 5. The explanation as to why can be found in the provided solution.

squares :: [Integer]
squares = filter (all (`elem` "12345") . show) .
          takeWhile (< 100000) $ map (^2) [100..]

The rest of the riddle can be solved with picking the correct element out of a list comprehension. Note the conditions that a < b and b < c. This prevents the same triple occurring in different permutations. I originally hadn’t included these, which is why I couldn’t get it working initially.

sameFive :: Maybe (Integer, Integer, Integer)
sameFive = fmap (fst . head) . find (null . tail) . snd $ K.sort snd
           [ ((a,b,c), findIndex (== 1) dc)
           | a <- squares, b <- squares, a < b, c <- squares, b < c
           , let dc = map length . group . sort $ show =<< [a,b,c]
           , sort dc == [1..5], and $ zipWith (/=) dc [1..5]

All that’s left to do is to see if we get the correct answer.

main :: IO ()
main = print sameFive

Programming Praxis – Carl Hewitt’s Same-Fringe Problem

August 3, 2010

In today’s Programming Praxis exercise we have to implement Carl Hewitt’s same-fringe algorithm, which determines if two binary trees have the same leaves in the same order, regardless if their respective structures. The simple solution of flattening both trees and comparing them doesn’t work in most languages, since their strict evaluation requires that the entire flattened list be loaded into memory, which will fail on big trees. Haskell on the other hand is lazy by default, so we don’t need to do anything complicated to have things work correctly. Let’s get started, shall we?

Since we’ll be working with binary trees, we’ll need to define a data structure for them:

data Tree a = Node (Tree a) (Tree a) | Leaf a

Flattening a tree is trivial.

flatten :: Tree a -> [a]
flatten (Node l r) = flatten l ++ flatten r
flatten (Leaf x)   = [x]

As mentioned in the intro, all we need to do is check whether the two flattened lists are equal.

sameFringe :: Eq a => Tree a -> Tree a -> Bool
sameFringe a b = flatten a == flatten b

As always, a test to see if things are working correctly:

main :: IO ()
main = print $ sameFringe (Node (Leaf 1) (Node (Leaf 2) (Leaf 3)))
                          (Node (Node (Leaf 1) (Leaf 2)) (Leaf 3))

Looks like they are. But how do we prove this method doesn’t require a big memory overhead? Well, let’s just create some big trees and find out. A binary tree of depth 28 has 2^28 = over 268 million leaves. At the very least, that would result in a list of 1 GB, and that’s assuming 32 bits per integer and no overhead. Since Haskell’s default lists are linked lists, you should probably at least double that. However, the following program

main = print $ sameFringe (treeOfDepth 28 (Leaf 1))
                          (treeOfDepth 28 (Leaf 1))
       where treeOfDepth n t = iterate (\x -> Node x x) t !! (n - 1)

hums along at a constant memory use of less than 20 MB when interpreted and less than 3 MB when compiled, the compiled version finishing in just under 32 seconds. To quote Larry Kersten, “Hard work often pays off after time, but laziness always pays off now.” 🙂