1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
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
|
