Skip to content
Tutorials Center
My learning

Topics

Lesson 40 of 40 ยท Projects and Practice

OCaml Practice Problems with Solutions and Hints

Sharpen your OCaml with eight exercises on lists, strings, maps, recursion, trees, graphs and backtracking. Each has a statement, a solution, tested results and a runnable Python version.

Reading code teaches you the syntax. Writing it teaches you OCaml. These eight problems cover the tools from this course: pattern matching, recursion, accumulators, Map, Hashtbl, Queue, variants and backtracking. Try each one before you open the solution, and think about types first: what goes in, what comes out.

OCaml is not available in the site's code runners, so the solutions are read-only. The results in comments were worked out by hand for small inputs and cross-checked with the Python versions you can run below. Python stand-ins follow the same algorithms so you can experiment with inputs.

1. Run-length encoding

Turn "aaabccdd" into [('a', 3); ('b', 1); ('c', 2); ('d', 2)].

OCAML
let rle s =
  let n = String.length s in
  let rec go i acc =
    if i >= n then List.rev acc
    else begin
      let j = ref i in
      while !j < n && s.[!j] = s.[i] do incr j done;
      go !j ((s.[i], !j - i) :: acc)
    end
  in
  go 0 []

(* rle "aaabccdd" = [('a', 3); ('b', 1); ('c', 2); ('d', 2)] *)

The recursion carries an accumulator in reverse; the inner loop measures one run. A fully functional version can use List.fold_right or recursion on the character list.

Extra: write decode : (char * int) list -> string with Buffer and String.make.

2. Balanced brackets

Return true if every (, [ and { is closed in the right order.

OCAML
let balanced s =
  let opener = function ')' -> '(' | ']' -> '[' | '}' -> '{' | c -> c in
  let rec go stack i =
    if i = String.length s then stack = []
    else
      match s.[i] with
      | ('(' | '[' | '{') as c -> go (c :: stack) (i + 1)
      | (')' | ']' | '}') as c -> (
          match stack with
          | top :: rest when top = opener c -> go rest (i + 1)
          | _ -> false)
      | _ -> go stack (i + 1)
  in
  go [] 0

(* balanced "{[()]}" = true; balanced "([)]" = false; balanced "((" = false *)

A list used as a stack: push with ::, pop by matching. Both operations are O(1).

3. Word frequencies

Count how often each word appears, ignoring case, sorted by word.

OCAML
module SMap = Map.Make (String)

let word_counts text =
  text
  |> String.lowercase_ascii
  |> String.split_on_char ' '
  |> List.filter (fun w -> w <> "")
  |> List.fold_left
       (fun m w -> SMap.update w (function None -> Some 1 | Some n -> Some (n + 1)) m)
       SMap.empty
  |> SMap.bindings

(* word_counts "The cat the dog" = [("cat", 1); ("dog", 1); ("the", 2)] *)

The pipeline reads top to bottom. SMap.bindings returns sorted pairs because the map is ordered by key. Extra: return the top three words by count (List.sort on the second component).

4. Memoized Fibonacci

The naive fib takes exponential time. Cache results in a Hashtbl:

OCAML
let fib_memo n =
  let cache = Hashtbl.create 64 in
  let rec fib k =
    if k < 2 then k
    else
      match Hashtbl.find_opt cache k with
      | Some v -> v
      | None ->
          let v = fib (k - 1) + fib (k - 2) in
          Hashtbl.add cache k v;
          v
  in
  fib n

(* fib_memo 50 = 12586269025 *)

On a 64-bit system OCaml's int is 63 bits, so this is exact up to fib 90. Beyond that use Zarith. Extra: make an iterative version with two refs and compare.

5. Shortest path in a graph

Given a graph as an association list, find the minimum number of edges from a to b with breadth-first search.

OCAML
let shortest_path graph start goal =
  let q = Queue.create () in
  let seen = Hashtbl.create 16 in
  Queue.add (start, 0) q;
  Hashtbl.add seen start ();
  let rec loop () =
    match Queue.take_opt q with
    | None -> None
    | Some (node, d) when node = goal -> Some d
    | Some (node, d) ->
        let next = Option.value (List.assoc_opt node graph) ~default:[] in
        List.iter
          (fun m ->
            if not (Hashtbl.mem seen m) then begin
              Hashtbl.add seen m ();
              Queue.add (m, d + 1) q
            end)
          next;
        loop ()
  in
  loop ()

let g = [ (1, [ 2; 3 ]); (2, [ 4 ]); (3, [ 4 ]); (4, [ 5 ]); (5, []) ]
(* shortest_path g 1 5 = Some 3;  shortest_path g 5 1 = None *)

The queue gives breadth-first order, so the first time we reach the goal is the shortest way. The seen table stops cycles.

6. N-queens

Count the ways to place n queens on an n x n board so that none attack each other.

OCAML
let queens n =
  let rec place row cols diag1 diag2 =
    if row = n then 1
    else begin
      let count = ref 0 in
      for c = 0 to n - 1 do
        if not (List.mem c cols || List.mem (row - c) diag1 || List.mem (row + c) diag2)
        then count := !count + place (row + 1) (c :: cols) ((row - c) :: diag1) ((row + c) :: diag2)
      done;
      !count
    end
  in
  place 0 [] [] []

(* queens 4 = 2; queens 6 = 4; queens 8 = 92 *)

This is backtracking: try a column, recurse, and undo by simply not keeping the extended lists (they are immutable!). Persistent lists make backtracking trivial.

7. Folding a tree

Using the tree from variant types, write fold, then use it for the size, the height and the in-order list.

OCAML
type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree

let rec fold f acc = function
  | Leaf -> acc
  | Node (l, v, r) -> fold f (f (fold f acc l) v) r

let to_list t = List.rev (fold (fun acc v -> v :: acc) [] t)
let size t = fold (fun n _ -> n + 1) 0 t

let rec height = function
  | Leaf -> 0
  | Node (l, _, r) -> 1 + max (height l) (height r)

let t = Node (Node (Leaf, 1, Leaf), 2, Node (Leaf, 3, Node (Leaf, 4, Leaf)))
(* to_list t = [1; 2; 3; 4]; size t = 4; height t = 3 *)

fold visits left subtree, node, right subtree, which is in order. Every list-like operation can be built on it.

Return the index of x in a sorted array, or None.

OCAML
let binary_search a x =
  let rec go lo hi =
    if lo > hi then None
    else
      let mid = lo + ((hi - lo) / 2) in
      if a.(mid) = x then Some mid
      else if a.(mid) < x then go (mid + 1) hi
      else go lo (mid - 1)
  in
  go 0 (Array.length a - 1)

(* binary_search [|1; 3; 5; 7; 9|] 7 = Some 3;  binary_search [|1; 3; 5|] 4 = None *)

lo + (hi - lo) / 2 avoids integer overflow on huge arrays. The recursion is in tail position, so it runs in constant stack space.

Run some of them in Python

Python Stand-in: problems 1 to 4

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Python Stand-in: problems 5, 6 and 8

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

More challenges

  1. Merge two sorted lists without using List.sort, then write merge sort.
  2. Implement List.flatten, List.filter_map and List.partition yourself.
  3. Write an Option-returning safe_nth : 'a list -> int -> 'a option.
  4. Evaluate reverse Polish notation such as "3 4 + 2 *" with a stack.
  5. Parse and pretty-print a small subset of arithmetic using the expression project.
  6. Extend the state machine with refunds and write tests for it with Alcotest.
  7. Solve one problem per day for a week, using Map, Hashtbl, Queue, Buffer and Seq at least once each (containers).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why is a list a good stack in OCaml?

    Cons adds to the front in constant time, and matching on top :: rest removes it in constant time.
  2. 2. Which structure gives breadth-first order in the shortest-path solution?

    A FIFO queue explores all nodes at distance d before any at distance d + 1.
  3. 3. Why is backtracking easy with immutable lists in n-queens?

    Persistent data needs no explicit undo step.
  4. 4. Why write lo + (hi - lo) / 2 instead of (lo + hi) / 2?

    The sum lo + hi can exceed the largest integer. The difference form cannot.

Summary

  • Choose the structure that fits the access pattern: list as stack, queue for BFS, map for counting, hashtable for memoization.
  • Accumulators with List.rev, folds and tail recursion are the everyday functional tools.
  • Immutable data makes backtracking and recursion over trees simple.
  • Keep practising: small problems, solved without peeking, with types written first.

Next: Back to the OCaml course index