Posts Tagged ‘five’

Programming Praxis – Median Of Five

December 4, 2012

In today’s Programming Praxis exercise, our goal is to determine to median of five numbers using only six comparisons. Let’s get started, shall we?

A quick import:

import Data.List

I didn’t like the element swapping and nested ifs of the provided algorithm, so I tried to come up with something a litte more in the spirit of functional programming. I was initially worried that the case statement would evaluate all three comparisons when the the first one was false, but some testing revealed that Haskell is lazy enough to skip the second comparison in that case.

median5 :: Ord a => [a] -> a
median5 ~[a',b',c,d',e'] = case (b<c, b<d, d<c) of
        (True, True , _    ) -> min c d
        (True, False, _    ) -> min b e
        (False, _   , True ) -> min c e
        (False, _   , False) -> min b d
    where ((_,b), (d,e)) = order (order a' b') (order d' e')
          order x y = if y < x then (y,x) else (x,y)

All that’s left to do is to verify that all permutations of the numbers 1 to 5 result in 3 as the median.

main :: IO ()
main = print . all ((== 3) . median5) $ permutations [1..5]

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) . K.group 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