Day 5

3 files changed, 53 insertions, 0 deletions

diff --git a/bin/main.ml b/bin/main.ml
index ce98887..b5d7303 100644
--- a/bin/main.ml
+++ b/bin/main.ml
@@ -34,6 +34,8 @@ let day_part_fn day part =
   | 3, 2 -> Day03.part2
   | 4, 1 -> Day04.part1
   | 4, 2 -> Day04.part2
+  | 5, 1 -> Day05.part1
+  | 5, 2 -> Day05.part2
   | _ ->
       failwith
         (Format.sprintf "Day %d, part %d, has not yet been implemented\n" day
diff --git a/data b/data
-Subproject 4314f8b670ed85271c4c1e16087139622bebc97
+Subproject 464e5178039496d1ed565669da7d13c14416a7d
diff --git a/lib/day05.ml b/lib/day05.ml
new file mode 100644
index 0000000..fb5fb76
--- /dev/null
+++ b/lib/day05.ml
@@ -0,0 +1,51 @@
+(*
+ * SPDX-FileCopyrightText: Copyright 2025 Alexandre Jesus <https://adbjesus.com>
+ *
+ * SPDX-License-Identifier: GPL-3.0-or-later
+ *)
+
+let parse_data ch =
+  In_channel.input_all ch
+  |> String.trim
+  |> String.split_on_char '\n'
+  |> List.map String.trim
+  |> List.filter (fun s -> String.length s > 0)
+  |> List.fold_left
+       (fun (r, v) s ->
+         match String.split_on_char '-' s with
+         | [ n ] -> (r, int_of_string n :: v)
+         | [ a; b ] ->
+             let a = int_of_string a in
+             let b = int_of_string b in
+             let rng = if a < b then (a, b) else (b, a) in
+             (rng :: r, v)
+         | _ -> failwith (Printf.sprintf "Invalid line: %s" s))
+       ([], [])
+
+let part1 ch =
+  let r, v = parse_data ch in
+  let is_fresh v (a, b) = v >= a && v <= b in
+  let is_fresh v = List.exists (is_fresh v) r in
+  (* O(|v| * |r|) which is good enough *)
+  (* Could be O((|v|+|r|) log (|v| + |r|)) with a line-sweep similar to part 2 *)
+  List.map is_fresh v
+  |> List.map Bool.to_int
+  |> List.fold_left ( + ) 0
+  |> Printf.printf "%d\n"
+
+let part2 ch =
+  parse_data ch
+  |> fst
+  |> List.fold_left (fun acc (a, b) -> (b + 1, 0) :: (a, 1) :: acc) []
+  |> List.sort compare
+  |> List.fold_left
+       (* (c, a, s) gives (count, active, start) *)
+       (* (v, t) gives (value, type) *)
+       (fun (c, a, s) (v, t) ->
+         match (t, a) with
+         | 0, 1 -> (c + v - s, 0, v)
+         | 0, _ -> (c, a - 1, s)
+         | _, 0 -> (c, 1, v)
+         | _ -> (c, a + 1, s))
+       (0, 0, 0)
+  |> fun (c, _, _) -> Printf.printf "%d\n" c