path: root/solutions.hs

-- #1 Find last element
myLast :: [a] -> a
myLast = last
mylast' = head . reverse

-- #2 Find second to last element
myButLast x = (reverse x) !! 1

-- #3 Find nth element
elementAt ls n = ls !! n-1

-- #4 Elements in a list
myLength [x] = 1
myLength (_:xs) = 1 + myLength xs
myLength' ls = helper ls 1 where
                helper [_] accum = accum
                helper (_:xs) accum = helper xs (accum+1)

-- #5 Reverse a list
myReverse [] = []
myReverse (x:xs) = myReverse xs ++ [x]

-- #6 Determine if list is a palindrome
isPalindrome ls = ls == reverse ls

-- #7 Flatten a nested list structure
-- New type, because haskell lists are homogenous
data NestedList a = Elem !a | List ![NestedList a]
nestedHead :: NestedList a -> a
nestedHead (Elem x) = x
nestedHead (List [x]) = nestedHead x

--nestedTail :: NestedList a -> NestedList a
--nestedTail (List x) = NestedList x

--flatten :: NestedList a -> [a]
--flatten xs = ne

-- Correct solution:
flatten :: NestedList a -> [a]
flatten (Elem x) = [x]
flatten (List x) = concatMap flatten x

-- #8 Eliminate consecutive duplicates
-- compress :: [a] -> [a]
-- compress a = helper a [] where
--                 helper [] part = reverse part
--                 helper [x] part = part
--                 helper (x:xs) part@(p:ps)
--                                 | x == p = helper xs part
--                                 | otherwise = helper xs (x:part)

-- Correct solution:
compress [] = []
compress (x:xs) = x : compress (dropWhile (== x) xs)

-- #9 Pack consecutive duplicates into sublists
pack :: (Eq a) => [a] -> [[a]]
pack [] = []
pack (x:xs) = let (first,rest) = span (== x) xs
                in (x:first) : pack rest

-- #10 Use previous to implement run-length encoding
encode :: (Eq a) => [a] -> [(Int, a)]
encode x = zip (map length group) (map head group)
                where group = pack x
-- Simpler solution:
encode' xs = [(length x, head x) | x <- pack xs]

-- #11 Modify the previous result such that an element with no duplicates get copied
-- directly into the resulting list. Requires special type:
data ListItem a = Single !a | Multiple !Int !a
    deriving (Show)
packToEnc :: Eq a => [a] -> ListItem a
packToEnc a@(fst:_)
                | len == 1 = Single fst
                | otherwise = Multiple len fst
                where len = length a

encodeModified :: Eq a => [a] -> [ListItem a]
-- encodeModified xs = [Multiple (length x) (head x) | x <- pack xs]
encodeModified xs = map packToEnc (pack xs)
-- This can also be done with a list comprehension:
encodeModified' xs = [y | x@(fst:_) <- pack xs, let len = length x,
                                let y = if len == 1 then Single fst else Multiple len fst]

-- #12 Decode modified RLE list
-- decodeSingle :: ListItem a -> [a]
-- decodeSingle (Single x) = [x]
-- decodeSingle (Multiple n x) = replicate n x
decodeModified :: Eq a => [ListItem a] -> [a]
decodeModified = concatMap decodeSingle
                where
                decodeSingle (Single x) = [x]
                decodeSingle (Multiple n x) = replicate n x

-- #13 Implement RLE directly (without packing first)
encodeDirect :: Eq a => [a] -> [ListItem a]
encodeDirect [] = []
encodeDirect (x:xs)
                | len == 1 = Single x : encodeDirect rest
                | otherwise = Multiple len x : encodeDirect rest
                where (dups,rest) = span (== x) xs
                      len = length dups + 1

-- #14 Duplicate elements of a list
dupli :: [a] -> [a]
dupli [] = []
dupli (x:xs) = x : (x : dupli xs)

-- #15 Replicate the elements of a list a certain number of times
repli :: [a] -> Int -> [a]
repli [] _ = []
repli (x:xs) n = replicate n x ++ repli xs n
-- Better solution:
repli' xs n = concatMap (replicate n) xs

-- #16 Drop every nth element from a list
dropEvery :: [a] -> Int -> [a]
--dropEvery xs n = [ x | x <- zip xs $ cycle [1,2,3]]
-- Correct solution
dropEvery xs n = [ i | (i,c) <- zip xs (cycle [1..n]), c /= n]

-- #17 Split a list into two parts given the length of the first
split xs n = splitAt n xs
split' :: [a] -> Int -> ([a],[a])
split' (x:xs) n | n > 0 = let (f,l) = split' xs (n-1) in (x : f,l)
split' xs _ = ([], xs)

-- #18 Extract a slice from a list
slice :: [a] -> Int -> Int -> [a]
slice xs s f = [ i | (i, j) <- zip xs [1..], s <= j, j <= f]
-- A small improvement, since zip cuts off based on the shorter list:
slice' xs s f = [i | (i,j) <- zip xs [1..f], j >= s]
-- A completely different take:
slice'' xs i j = take (j-i+1) $ drop (i-1) xs

-- #19 Rotate a list n places to the left
rotate :: [a] -> Int -> [a]
rotate xs n
            | n < 0 = drop l xs ++ take l xs
            | otherwise = drop n xs ++ take n xs
            where l = length xs + n
-- Simpler solution:
rotate' xs n = drop nn xs ++ take nn xs
                where nn = n `mod` length xs

-- #20 Remove the kth element from a list
removeAt :: Int -> [a] -> (a, [a])
removeAt n xs = (xs!!(n-1), take (n-1) xs ++ drop n xs)

-- #21 Insert an element at the given position
insertAt :: a -> [a] -> Int -> [a]
insertAt x xs n = take (n-1) xs ++  x : drop (n-1) xs

-- #22 Create a list containing all integers in a given range
range :: Enum a => a -> a -> [a]
range i j = [i..j]
range' i j = i : range (i+1) j

-- #23 - #30 are all based on randomness

-- #31 Determine whether a given number is prime
isPrime n
        | n == 2 = True
        | otherwise = helper n 2 where
            helper x y
                | rem x y == 0 = False
                | y*y > x = True
                | otherwise = helper x (y+1)

-- #32 Determine the GCD of two numbers
euclid gcd 0 = gcd
euclid x y = euclid y (x `rem` y)

-- #33 Determine whether two numbers are coprime (relative primes)
coprime x y = euclid x y == 1

-- #34 Calculate Euler's totient function
totient n
    | isPrime n = n-1
    | otherwise = length $ filter (n `coprime`) [1..n-1]

isFactor n fac = 0 == rem n fac

-- #35 Find the prime factors of a positive integer
primeFactors n = filter isPrime $ filter (\f -> rem n f == 0) [2.. ceiling $ sqrt $ fromIntegral n]
-- Improved method which creates full factorization:
primeFactors' n = helper n 2 where
        helper n f
            | f*f > n       = [n]
            | rem n f == 0  = f : helper (div n f) f
            | otherwise     = helper n (f+1)

-- #36 Find prime factors with multiplicity
prime_factors_mult n = map swap $ encode' $ primeFactors' n
    where swap (x,y) = (y,x)

-- #37 Improved totient
totient' n = foldr (\(p,m) a -> ((p-1) * (p ^(m-1))) * a) 1 (prime_factors_mult n)

-- #38 Compare totient and totient'
-- Time for totient 10090090: 1:16
-- Time for totient' 10090090: <1

-- #39 Find list of primes in a given range
primesR l u = filter (isPrime) [l..u]

-- #40 Find the Goldbach primes for a given number
-- goldbach n = foldr (\) n (primesR 2 n)