# the 99 problems

``````(require 'ob-haskell)
(require 'ob-clojure)
``````
``````:set +m
``````

## List

### 1. Find the last element

``````last [1, 2, 3, 4]
``````
```4
```

### 2. Find the but last element

``````last . init \$ [1,2,3,4]
``````
```3
```

### 3. find kth element

``````[1,2,3,4,5] !! 2
``````
```3
```

### 4. length

``````length [1,2,3,4,5]
``````
```5
```

### 5. reverse list

``````reverse [1,2,3,4,5]
``````
 5 4 3 2 1

### 6. palindrome

``````let isPalindrome a = reverse a == a
isPalindrome [1,2,3,2,1]
``````
```True
```

### 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]])
``````
```Prelude> [1,2,3,4,5]
```

### 8. compress

``````import Data.List
``````
```abcade
```

### 9. pack

``````group ['a', 'a', 'a', 'a', 'b', 'c', 'c', 'a', 'a', 'd', 'e', 'e', 'e', 'e']
``````
```Prelude Data.List| ["aaaa","b","cc","aa","d","eeee"]
```

### 10. encode

``````map (\n -> (head n, length n)) \$ group "aaaabccaadeeee"
``````
 a 4 b 1 c 2 a 2 d 1 e 4

### 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

``````
```Prelude Data.List> Prelude Data.List> Prelude Data.List> Prelude Data.List| Prelude Data.List| Prelude Data.List| Prelude Data.List> [Multiple 4 'a',Single 'b',Multiple 2 'c',Multiple 2 'a',Single 'd',Multiple 4 'e']
```

### 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']
``````
```Prelude Data.List> "aaaabccaadeeee"
```

### 13. Run-length encoding of a list

``````encodeModified "aaaabccaadeeee"
``````
 Multiple 4 a Single b Multiple 2 c Multiple 2 a Single d Multiple 4 e

### 14. Duplicate the elements of a list.

``````let dupli = concatMap (replicate 2)

dupli [1,2,3,4]
``````
```Prelude Data.List| Prelude Data.List> [1,1,2,2,3,3,4,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
``````
```Prelude Data.List| Prelude Data.List> [1,1,1,2,2,2,3,3,3,4,4,4]
```

### 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
``````
```Prelude Data.List| Prelude Data.List> "abdeghk"
```

### 17. Split a list into two parts; the length of the first part is given

``````splitAt 3 "abcdefghik"
``````
 abc defghik

### 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
``````
```Prelude Data.List| Prelude Data.List> "cdefg"
```

### 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)
``````
```ghabcdef
```

### 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"
``````
 c abd

### 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
``````
```Prelude| Prelude| Prelude> "aXbcd"
```

### 22. Create a list containing all integers within a given range

``````range a b= [a..b]
range 4 9
``````
 4 5 6 7 8 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
``````
```Prelude System.Random| Prelude System.Random| Prelude System.Random| Prelude System.Random> dbc
```

### 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
``````
```Prelude System.Random> [41,13,4,36,3,33]
```

### 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"
``````
```Prelude System.Random Data.List| Prelude System.Random Data.List| Prelude System.Random Data.List|
<interactive>:172:1: error:
parse error (possibly incorrect indentation or mismatched brackets)
```
``````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"
``````
```Prelude| Prelude| Prelude| Prelude> ["abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde"]
```
``````filter (\x -> ((length x)==3)) \$ subsequences "abcdef"
``````
 abc abd acd bcd abe ace bce ade bde cde abf acf bcf adf bdf cdf aef bef cef def

### 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"]
``````
 o de de mn abc fgh ijkl

## 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
``````
```Prelude Data.List| Prelude Data.List| Prelude Data.List| Prelude Data.List| Prelude Data.List> True
```

### 32. Determine the greatest common divisor of two positive integer numbers

``````gcd 36 63
``````
```9
```
``````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
``````
```Prelude| Prelude| Prelude> True
```

### 34. Calculate Euler's totient function phi(m)

``````totient n = length \$ filter (coprime n) [1..n]
totient 10
``````
```4
```

### 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
``````
```Prelude Data.List| Prelude Data.List| Prelude Data.List> Prelude Data.List| Prelude Data.List| Prelude Data.List| Prelude Data.List| Prelude Data.List> [3,3,5,7]
```

### 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
``````
 3 2 5 1 7 1