the 99 problems
(require 'ob-haskell) (require 'ob-clojure)
:set +m
List
1. Find the last element
last [1, 2, 3, 4]
2. Find the but last element
last . init $ [1,2,3,4]
3. find kth element
[1,2,3,4,5] !! 2
4. length
length [1,2,3,4,5]
5. reverse list
reverse [1,2,3,4,5]
6. palindrome
let isPalindrome a = reverse a == a isPalindrome [1,2,3,2,1]
7. flatten list
:set +m data NestedList a = Elem a | List [NestedList a] let flatten (List []) = [] flatten (Elem a) = [a] flatten (List (x:xs)) = flatten x ++ flatten (List xs) flatten (List [Elem 1, List [Elem 2, List [Elem 3, Elem 4], Elem 5]])
8. compress
import Data.List map head $ group "aaaabccaadeeee"
9. pack
group ['a', 'a', 'a', 'a', 'b', 'c', 'c', 'a', 'a', 'd', 'e', 'e', 'e', 'e']
10. encode
map (\n -> (head n, length n)) $ group "aaaabccaadeeee"
11. Modified run-length encoding.
:set +m import Data.List data Modified a b = Single b | Multiple a b deriving Show let encode = map (\n -> (head n, length n)) . group let encodeModified = map modify . encode where modify (b, 1) = Single b modify (c, d) = Multiple d c encodeModified "aaaabccaadeeee"
12. Decode a run-length encoded list.
let decodeModified [] = [] decodeModified (x:xs) = decode x ++ decodeModified xs where decode (Multiple a b) = replicate a b decode (Single a) = [a] decodeModified [Multiple 4 'a',Single 'b',Multiple 2 'c', Multiple 2 'a',Single 'd',Multiple 4 'e']
13. Run-length encoding of a list
encodeModified "aaaabccaadeeee"
14. Duplicate the elements of a list.
let dupli = concatMap (replicate 2) dupli [1,2,3,4]
15. Replicate the elements of a list a given number of times.
let dupli a b = concatMap (replicate b) a dupli [1,2,3,4] 3
16. Drop every N'th element from a list.
let dropEvery a n = map fst $ filter (\(d, i) -> i `mod` n /= 0) $ zip a [1..] dropEvery "abcdefghik" 3
17. Split a list into two parts; the length of the first part is given
splitAt 3 "abcdefghik"
18. Extract a slice from a list.
let slice c a b = take (b-a+1) $ drop (a-1) c slice ['a','b','c','d','e','f','g','h','i','k'] 3 7
19. Rotate a list N places to the left.
let rotate a n = drop (c n) a ++ take (c n) a where c d = ((length a) + d) `mod` (length a) rotate ['a','b','c','d','e','f','g','h'] 3 rotate ['a','b','c','d','e','f','g','h'] (-2)
20. Remove the K'th element from a list.
let removeAt n a = (a !! (n-1), take (n-1) a ++ drop (n) a) removeAt 3 "abcd"
21. Insert an element at a given position into a list.
let insertAt x a n = fst b ++ [x] ++ snd b where b = splitAt (n-1) a insertAt 'X' "abcd" 2
22. Create a list containing all integers within a given range
range a b= [a..b] range 4 9
23. Extract a given number of randomly selected elements from a list
import System.Random let rnd_select xs n = do gen <- getStdGen return $ take n [ xs !! x | x <- randomRs (0, (length xs) - 1) gen] rnd_select "abcdefgh" 3
24. Draw N different random numbers from the set 1..M
let diffSelect xs n = do gen <- getStdGen return $ (take n . nub) [ xs !! x | x <- randomRs (0, (length xs) - 1) gen] diffSelect 6 43
25. Generate a random permutation of the elements of a list.
import Data.List let permu xs = do gen <- getStdGen return $ take 10 [ xs !! x | x <- randomRs (0, (length xs) - 1) gen] permu "asdfasdf"
import Data.List permutations "asd"
26. Generate the combinations of K distinct objects chosen from the N elements of a list
let combinations _ [] = [] combinations 0 _ = [[]] combinations n (x:xs) = map (x:) (combinations (n-1) xs) ++ combinations n xs combinations 3 "abcdef"
filter (\x -> ((length x)==3)) $ subsequences "abcdef"
TODO 27. Group the elements of a set into disjoint subsets.
combinations n = filter (\x -> ((length x)==n)) $ subsequences group ns xs = map ($ xs) $ map combinations ns group [2,3,4] ["aldo","beat","carla","david","evi","flip","gary","hugo","ida"]
28. Sorting a list of lists according to length of sublists
sortOn length ["abc","de","fgh","de","ijkl","mn","o"]
Arithmetic
31. is prime
isPrime p = filterPrime [2..p] where filterPrime [] = False filterPrime (x:xs) | x == p = True | otherwise = filterPrime [y | y <- xs, y `mod` x /= 0] isPrime 7
32. Determine the greatest common divisor of two positive integer numbers
gcd 36 63
let mygcd 0 a = a mygcd a 0 = a mygcd a b = mygcd b (a `mod` b) mygcd 36 63
33. Determine whether two positive integer numbers are coprime. Two numbers are coprime if their greatest common divisor equals 1
:set +m let coprime :: Int -> Int -> Bool coprime a b = (==1) $ gcd a b coprime 35 36
34. Calculate Euler's totient function phi(m)
totient n = length $ filter (coprime n) [1..n] totient 10
35. Determine the prime factors of a given positive integer. Construct a flat list containing the prime factors in ascending order
let primes = filterPrime [2..] where filterPrime (p:xs) = p:[x | x <- xs, x `mod` p /=0] let primeFactors :: Int -> [Int] -> [Int] primeFactors n (p:xs) | (n < p) = [] | (n `mod` p) == 0 = p:(primeFactors (n `div` p) (p:xs)) | otherwise = primeFactors n xs primeFactors 315 primes
36. Determine the prime factors of a given positive integer (2)
import Data.List primeFactorMult n = map (\x -> (head x, length x)) $ group $ primeFactors n primes primeFactorMult 315