99 OCaml: Intermediate Exercises

Table of Contents

Intermediate problems taken from here. Instead of just being a store for solutions, this aims to actually go deeper and float all the learning takeaways that I had when completing the problem set. The code-snippets here can be tangled in emacs I will expose this code as an org-file publicly once I’ve completed the 99 problems. It will be hosted on Codeberg, hopefully it helps others. and can be executed directly.

This is still a WIP, this info alert will be removed once both the intermediate and beginner exercises have been completed. There’s some dependency between the two sets of problems and it’s not that clean yet – that’s why both sets (beginner, intermediate) are being worked on at the same time.

TODO Lists #

1. Flatten a List #

Flatten a nested list structure.

1
2
3
4
5
6
type 'a node =
  | One of 'a
  | Many of 'a node list

(* input: *)
flatten [One "a"; Many [One "b"; Many [One "c" ;One "d"]; One "e"]];

2. Eliminate Duplicates #

Eliminate consecutive duplicates of list elements.

1
compress ["a"; "a"; "a"; "a"; "b"; "c"; "c"; "a"; "a"; "d"; "e"; "e"; "e"; "e"];;

3. Pack Consecutive Duplicates #

Pack consecutive duplicates of list elements into sublists.

1
2
3
4
5
6
pack ["a"; "a"; "a"; "a"; "b"; "c"; "c"; "a"; "a"; "d"; "d"; "e"; "e"; "e"; "e"];;
(*
- : string list list =
[["a"; "a"; "a"; "a"]; ["b"]; ["c"; "c"]; ["a"; "a"]; ["d"; "d"];
 ["e"; "e"; "e"; "e"]]
 *)

4. Decode a Run-Length Encoded List #

Given a run-length code list generated as specified in the previous problem, construct its uncompressed version.

1
2
3
4
5
6
7


decode [Many (4, "a"); One "b"; Many (2, "c"); Many (2, "a"); One "d"; Many (4, "e")];;
(*
- : string list =
["a"; "a"; "a"; "a"; "b"; "c"; "c"; "a"; "a"; "d"; "e"; "e"; "e"; "e"]
*)

5. Run-Length Encoding of a List (Direct Solution) #

Implement the so-called run-length encoding data compression method directly.
I.e. don’t explicitly create the sublists containing the duplicates, as in problem “Pack consecutive duplicates of list elements into sublists”, but only count them.
As in problem “Modified run-length encoding”, simplify the result list by replacing the singleton lists (1 X) by X.

6. Replicate the Elements of a List a Given Number of Times #

Replicate the elements of a list a given number of times.

1
2
3

 replicate ["a"; "b"; "c"] 3;;
(* - : string list = ["a"; "a"; "a"; "b"; "b"; "b"; "c"; "c"; "c"] *)

7. Drop Every N’th Element From a List #

Drop every N’th element from a list.

1
2
3

drop ["a"; "b"; "c"; "d"; "e"; "f"; "g"; "h"; "i"; "j"] 3;;
(* - : string list = ["a"; "b"; "d"; "e"; "g"; "h"; "j"] *)

8. Extract a Slice From a List #

Given two indices, i and k, the slice is the list containing the elements between the i‘th and k‘th element of the original list (both limits included).
Start counting the elements with 0 (this is the way the List module numbers elements).

1
2
3
4


slice ["a"; "b"; "c"; "d"; "e"; "f"; "g"; "h"; "i"; "j"] 2 6;;
(* - : string list = ["c"; "d"; "e"; "f"; "g"] *)

9. Rotate a List N Places to the Left #

Rotate a list N places to the left.

1
2
3

rotate ["a"; "b"; "c"; "d"; "e"; "f"; "g"; "h"] 3;;
(* - : string list = ["d"; "e"; "f"; "g"; "h"; "a"; "b"; "c"] *)

10. Extract a Given Number of Randomly Selected Elements From a List #

The selected items shall be returned in a list. We use the Random module and initialise it with Random.init 0 at the start of the function for reproducibility and validate the solution. To make the function truly random, however, one should remove the call to Random.init 0.

1
2
3

rand_select ["a"; "b"; "c"; "d"; "e"; "f"; "g"; "h"] 3;;
(* - : string list = ["e"; "c"; "g"] *)

11. Generate the Combinations of K Distinct Objects Chosen From the N Elements of a List #

Generate the combinations of K distinct objects chosen from the N elements of a list.
In how many ways can a committee of 3 be chosen from a group of 12 people? We all know that there are C(12,3) = 220 possibilities (C(N,K) denotes the well-known binomial coefficients). For pure mathematicians, this result may be great. But we want to really generate all the possibilities in a list.

1
2
3
4

extract 2 ["a"; "b"; "c"; "d"];;
(* - : string list list = *)
(* [["a"; "b"]; ["a"; "c"]; ["a"; "d"]; ["b"; "c"]; ["b"; "d"]; ["c"; "d"]] *)

12. Group the Elements of a Set Into Disjoint Subsets #

Group the elements of a set into disjoint subsets
In how many ways can a group of 9 people work in 3 disjoint subgroups of 2, 3 and 4 persons? Write a function that generates all the possibilities and returns them in a list.
Generalize the above function in a way that we can specify a list of group sizes and the function will return a list of groups.

1
2
3
4
5
6
7
8
9
group ["a"; "b"; "c"; "d"] [2; 1];;

(*
- : string list list list =
[[["a"; "b"]; ["c"]]; [["a"; "c"]; ["b"]]; [["b"; "c"]; ["a"]];
 [["a"; "b"]; ["d"]]; [["a"; "c"]; ["d"]]; [["b"; "c"]; ["d"]];
 [["a"; "d"]; ["b"]]; [["b"; "d"]; ["a"]]; [["a"; "d"]; ["c"]];
 [["b"; "d"]; ["c"]]; [["c"; "d"]; ["a"]]; [["c"; "d"]; ["b"]]]
*)

13. Sorting a List of Lists According to Length of Sublists #

Sorting a list of lists according to length of sublists.
We suppose that a list contains elements that are lists themselves. The objective is to sort the elements of this list according to their length. E.g. short lists first, longer lists later, or vice versa.
Again, we suppose that a list contains elements that are lists themselves. But this time the objective is to sort the elements of this list according to their length frequency; i.e., in the default, where sorting is done ascendingly, lists with rare lengths are placed first, others with a more frequent length come later.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
length_sort [["a"; "b"; "c"]; ["d"; "e"]; ["f"; "g"; "h"]; ["d"; "e"];
             ["i"; "j"; "k"; "l"]; ["m"; "n"]; ["o"]];;
(*
- : string list list =
[["o"]; ["d"; "e"]; ["d"; "e"]; ["m"; "n"]; ["a"; "b"; "c"]; ["f"; "g"; "h"];
 ["i"; "j"; "k"; "l"]]
*)

frequency_sort [["a"; "b"; "c"]; ["d"; "e"]; ["f"; "g"; "h"]; ["d"; "e"];
                ["i"; "j"; "k"; "l"]; ["m"; "n"]; ["o"]];;
(*
- : string list list =
[["i"; "j"; "k"; "l"]; ["o"]; ["a"; "b"; "c"]; ["f"; "g"; "h"]; ["d"; "e"];
 ["d"; "e"]; ["m"; "n"]]
*)

TODO Arithmetic #

14. Determine Whether a Given Integer Number Is Prime #

Determine whether a given integer number is prime.

1
2
3
4
5
6
not (is_prime 1);;
(* - : bool = true *)
is_prime 7;;
(* - : bool = true *)
not (is_prime 12);;
(* - : bool = true *)

15. Determine the Greatest Common Divisor of Two Positive Integer Numbers #

Determine the greatest common divisor of two positive integer numbers.
Use Euclid’s algorithm.

my v0 GCD solution (works, but inefficient)

1
2
3
4
5
let rec gcd lo hi =
  if lo = 0 then hi else if hi = 0 then lo else
    let lo, hi = (Int.min lo hi), (Int.max lo hi) in
    let diff = hi - lo in
    gcd lo diff;;

Code Snippet 1: v0 GCD solution by me (inefficient, small steps from substraction)

1
2
let rec gcd a b =
    if b = 0 then a else gcd b (a mod b);;

Code Snippet 2: model solution

1
2
3
4
5
6
7
let gcd a b =
  let rec aux a b =
    if b = 0 then a
    else aux b (a % b) (*--- modulo makes it logarithmic because big jumps*)
  in
  aux (abs a) (abs b);;
gcd 20536 7826;;

Code Snippet 3: abs only one time on entry (negative handling), recursion is purely arithmetic

16. Calculate Euler’s Totient Function \(\phi(m)\) #

Euler’s so-called totient function \(\phi(m)\) is defined as the number of positive integers r (1 ≤ r < m) that are coprime to m. We let \(\phi(1)\) = 1.
Find out what the value of \(\phi(m)\) is if m is a prime number.
Euler’s totient function plays an important role in one of the most widely used public key cryptography methods (RSA). In this exercise you should use the most primitive method to calculate this function (there are smarter ways that we shall discuss later).

1
2
3
4
5
6
7
let rec gcd a b =
    if b = 0 then a else gcd b (a mod b);;
let coprime a b = ( gcd a b ) = 1;;
let phi m =
  let rec aux acc n =
    if n = 1 then acc + 1 else if coprime m n then aux (acc + 1) (n - 1) else aux acc (n - 1) in
  aux 0 (m - 1);;

Code Snippet 4: My solution

1
2
3
4
5
6
7
let phi n =
  let rec count_coprime acc d =
    if d < n then
      count_coprime (if coprime n d then acc + 1 else acc) (d + 1)
    else acc
  in
  if n = 1 then 1 else count_coprime 0 1;;

Code Snippet 5: Model solution

17. Determine the Prime Factors of a Given Positive Integer #

Construct a flat list containing the prime factors in ascending order.

1
2
3

factors 315;;
(* - : int list = [3; 3; 5; 7] *)

18. Determine the Prime Factors of a Given Positive Integer (2) #

Construct a list containing the prime factors and their multiplicity.
Hint: The problem is similar to problem Run-length encoding of a list (direct solution).

1
2
factors 315;;
(* - : (int * int) list = [(3, 2); (5, 1); (7, 1)] *)

19. Calculate Euler’s Totient Function \(\phi(m)\) (Improved) #

See problem “Calculate Euler’s totient function \(\phi(m)\)” for the definition of Euler’s totient function.
If the list of the prime factors of a number m is known in the form of the previous problem then the function phi(m) can be efficiently calculated as follows: Let [(p1, m1); (p2, m2); (p3, m3); ...] be the list of prime factors (and their multiplicities) of a given number m. Then \(\phi(m)\) can be calculated with the following formula:
\[ \phi(m) \newline = (p1 - 1) \times p1^{m1 - 1} \times (p2 - 1) \times p2^{m2 - 1} \times (p3 - 1) \times p3^{m3 - 1} \times … \]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
let factors n =
    let rec aux d n =
      if n = 1 then [] else
        if n mod d = 0 then
          match aux d (n / d) with
          | (h, n) :: t when h = d -> (h, n + 1) :: t
          | l -> (d, 1) :: l
        else aux (d + 1) n
    in
      aux 2 n;;
let pow base exp =
  let rec aux acc b e =
    if e = 0 then acc else aux (acc * b) b (e - 1) in
  aux 1 base exp;; (*--- naive power fn, tail recursive*)
let phi_improved n =
  let rec aux acc = function
    | [ ] -> acc
    | (p, m) :: t -> aux ( (p - 1) * (pow p (m - 1)) * acc ) t
  in
  aux 1 (factors n);;
phi_improved 10;;
phi_improved 13;;

Code Snippet 6: model ans

20. Goldbach’s Conjecture #

Goldbach’s conjecture says that every positive even number greater than 2 is the sum of two prime numbers. Example: 28 = 5 + 23. It is one of the most famous facts in number theory that has not been proved to be correct in the general case. It has been numerically confirmed up to very large numbers. Write a function to find the two prime numbers that sum up to a given even integer.

1
2
goldbach 28;;
(* - : int * int = (5, 23) *)

21. A List of Goldbach Compositions #

Given a range of integers by its lower and upper limit, print a list of all even numbers and their Goldbach composition.
In most cases, if an even number is written as the sum of two prime numbers, one of them is very small. Very rarely, the primes are both bigger than say 50. Try to find out how many such cases there are in the range 2..3000.

1
2
3
4
5
6
goldbach_list 9 20;;
(*
- : (int * (int * int)) list =
[(10, (3, 7)); (12, (5, 7)); (14, (3, 11)); (16, (3, 13)); (18, (5, 13));
 (20, (3, 17))]
 *)