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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
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
|
