Posts Tagged ‘split’

Programming Praxis – Miscellanea

April 26, 2011

In today’s Programming Praxis exercise, our goal is to write three fucntions: FizzBuzz, a function to determine if a base 36 number is prime and one to split a list down the middle while going through the list only once. Let’s get started, shall we?

Some imports:

import Data.Foldable (toList)
import Data.Numbers.Primes
import Data.Sequence (ViewL(..), (|>), fromList, viewl, empty)

First up we have the classic FizzBuzz interview question. There are plenty of ways to solve it, but I’m partial to this one.

fizzbuzz :: Integral a => a -> IO ()
fizzbuzz n = mapM_ (putStrLn . f) [1..n] where
    f n = case (mod n 3, mod n 5) of (0, 0) -> "FizzBuzz"
                                     (0, _) -> "Fizz"
                                     (_, 0) -> "Buzz"
                                     _      -> show n

To determine if a word is prime we convert it from base 36 to base 10 and then determine if it’s prime.

isPrimeWord :: String -> Bool
isPrimeWord = isPrime . sum . zipWith (*) (iterate (* 36) 1) . reverse .
    map (\c -> maybe 0 id . lookup c $ zip (['0'..'9'] ++ ['A'..'Z']) [0..])

For splitting the list, the tortoise and hare algorithm seems dubious to me given the requirement that the list is only scanned once, since both of them scan the list (albeit looking only at half of the elements each). I’ve gone with a different approach. We start with two empty lists, which are balanced. If the lists are balanced, the next element will be added to the right one, which unbalances the list. If they are not balanced, the left element of the right list is added to the end of the left list.

splitList :: [a] -> ([a], [a])
splitList = f True (empty, empty) where
    f _     (l,r) [] = (toList l, toList r)
    f True  (l,r) (x:xs) = f False (l, r |> x) xs
    f False (l,r) (x:xs) = f True ((\(h :< t) -> (l |> h, t |> x)) $ viewl r) xs

Some tests to see if everything is working correctly:

main :: IO ()
main = do fizzbuzz 20
          print . not $ isPrimeWord "PRAXIS"
          print $ isPrimeWord "LISP"
          print $ splitList [] == ([],[] :: [Int])
          print $ splitList [1..4] == ([1,2],[3,4])
          print $ splitList [1..5] == ([1,2],[3,4,5])