Initial commitHEADmain

3 files changed, 224 insertions, 0 deletions

diff --git a/README.md b/README.md
new file mode 100644
index 0000000..c56271f
--- /dev/null
+++ b/README.md
@@ -0,0 +1,3 @@
+# 99hs
+
+My solutions to some of the [Ninety-Nine Haskell Problems](https://wiki.haskell.org/H-99:_Ninety-Nine_Haskell_Problems).
diff --git a/notes b/notes
new file mode 100644
index 0000000..c899a16
--- /dev/null
+++ b/notes
@@ -0,0 +1,11 @@
+Consider concatMap
+
+Use dropWhile to drop based on a specific condition
+
+takeWhile returns the longers possible prefix that satisfies a condition
+span does the same, but also returns the rest of the list (2 element tuple)
+
+Cycle repeats a given sequence infinitely:
+cycle [1,2,3] = [1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3]...
+
+Repeat is like cycling a single element
diff --git a/solutions.hs b/solutions.hs
new file mode 100644
index 0000000..039e974
--- /dev/null
+++ b/solutions.hs
@@ -0,0 +1,210 @@
+-- #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)