Day 9

3 files changed, 105 insertions, 0 deletions

diff --git a/bin/main.ml b/bin/main.ml
index 229f681..3d957d5 100644
--- a/bin/main.ml
+++ b/bin/main.ml
@@ -42,6 +42,8 @@ let day_part_fn day part =
   | 7, 2 -> Day07.part2
   | 8, 1 -> Day08.part1
   | 8, 2 -> Day08.part2
+  | 9, 1 -> Day09.part1
+  | 9, 2 -> Day09.part2
   | _ ->
       failwith
         (Format.sprintf "Day %d, part %d, has not yet been implemented\n" day
diff --git a/data b/data
-Subproject 841a39c875a41588f10c57b58af2a088f338dff
+Subproject e479718840bd0124b170271196b2f60f7fdb3c5
diff --git a/lib/day09.ml b/lib/day09.ml
new file mode 100644
index 0000000..ad31a48
--- /dev/null
+++ b/lib/day09.ml
@@ -0,0 +1,103 @@
+(*
+ * SPDX-FileCopyrightText: Copyright 2025 Alexandre Jesus <https://adbjesus.com>
+ *
+ * SPDX-License-Identifier: GPL-3.0-or-later
+ *)
+
+let parse ch =
+  ch
+  |> In_channel.input_lines
+  |> List.filter (( <> ) "")
+  |> List.map (fun s -> Scanf.sscanf s "%d,%d" (fun x y -> (x, y)))
+
+let part1 ch =
+  let coords = parse ch in
+  let area (x1, y1) (x2, y2) = (abs (x1 - x2) + 1) * (abs (y1 - y2) + 1) in
+  let rec solve acc coords =
+    match coords with
+    | [] | _ :: [] -> acc
+    | h :: t ->
+        let acc = List.fold_left (fun acc c -> Int.max acc (area h c)) acc t in
+        solve acc t
+  in
+  solve 0 coords |> Printf.printf "%d\n"
+
+let part2 ch =
+  (* This approach assumes the following (which holds true for my input):
+     - Points to form the polygon are given clockwise order
+       (this can be dealt with by reversing the point list)
+     - Every point gives a corner
+       (these could be included, but were not needed in my input)
+     - There are no adjacent edges
+       (this would need a different approach, we could probably build the polygon with coordinate compression)
+
+     The idea is:
+     - Compute directions of vertices to know if it is a convex or concave corner
+     - For each vertex check all other vertices that make up an interior rectangle,
+       taking into account that depending on corner only some vertices give an
+       interior rectangle.
+     - For each interior rectangle check if there are any overlapping edges. If
+       there are no overlapping edges, this is a valid rectangle.
+   *)
+  let coords = parse ch in
+  let n = List.length coords in
+  let dir c1 c2 =
+    match (c1, c2) with
+    | (x1, y1), (x2, y2) when x1 = x2 && y1 < y2 -> `D
+    | (x1, y1), (x2, y2) when x1 = x2 && y2 < y1 -> `U
+    | (x1, y1), (x2, y2) when y1 = y2 && x1 < x2 -> `R
+    | (x1, y1), (x2, y2) when y1 = y2 && x2 < x1 -> `L
+    | _ -> failwith "Invalid input (repeated point, or no common coordinate)"
+  in
+  let ccoords = List.to_seq coords |> Seq.cycle in
+  let dirs =
+    Seq.map2 dir
+      (Seq.take (n + 1) (Seq.drop (n - 1) ccoords))
+      (Seq.take (n + 1) ccoords)
+    |> Array.of_seq
+  in
+  let coords = Array.of_list coords in
+  let ans = ref 0 in
+  let ans1 = ref coords.(0) in
+  let ans2 = ref coords.(0) in
+  let all_outside (x1, y1) (x2, y2) =
+    let xl, xu = if x1 < x2 then (x1, x2) else (x2, x1) in
+    let yl, yu = if y1 < y2 then (y1, y2) else (y2, y1) in
+    coords
+    |> Array.to_seq
+    |> Seq.mapi (fun i c -> (i, c))
+    |> Seq.for_all (fun (i, (x1, y1)) ->
+        let x2, y2 = coords.((i + 1) mod n) in
+        let x1, x2 = if x1 < x2 then (x1, x2) else (x2, x1) in
+        let y1, y2 = if y1 < y2 then (y1, y2) else (y2, y1) in
+        x2 <= xl || xu <= x1 || y2 <= yl || yu <= y1)
+  in
+  let try_rect c1 condfn =
+    Array.iter
+      (fun c2 ->
+        if condfn c1 c2 && all_outside c1 c2 then
+          let xd = abs (fst c1 - fst c2) in
+          let yd = abs (snd c1 - snd c2) in
+          let a = (xd + 1) * (yd + 1) in
+          if a > !ans then (
+            ans := a;
+            ans1 := c1;
+            ans2 := c2))
+      coords
+  in
+  for i = 0 to n - 1 do
+    let d1 = dirs.(i) in
+    let d2 = dirs.(i + 1) in
+    let c = coords.(i) in
+    match (d1, d2) with
+    | `U, `R -> try_rect c (fun (x1, y1) (x2, y2) -> x1 <= x2 && y1 <= y2)
+    | `R, `U -> try_rect c (fun (x1, y1) (x2, y2) -> x1 <= x2 || y1 <= y2)
+    | `R, `D -> try_rect c (fun (x1, y1) (x2, y2) -> x2 <= x1 && y1 <= y2)
+    | `D, `R -> try_rect c (fun (x1, y1) (x2, y2) -> x2 <= x1 || y1 <= y2)
+    | `D, `L -> try_rect c (fun (x1, y1) (x2, y2) -> x2 <= x1 && y2 <= y1)
+    | `L, `D -> try_rect c (fun (x1, y1) (x2, y2) -> x2 <= x1 || y2 <= y1)
+    | `L, `U -> try_rect c (fun (x1, y1) (x2, y2) -> x1 <= x2 && y2 <= y1)
+    | `U, `L -> try_rect c (fun (x1, y1) (x2, y2) -> x1 <= x2 || y2 <= y1)
+    | _ -> failwith "Non-corner vertex"
+  done;
+  Printf.printf "%d\n" !ans