🏡 index : ~doyle/aoc.git

d837d1cc265e5cea16b43376ee5ced6b98b168fb [patch]

ca0752f734d9eeaa42df8b46146227c8952e594e

d1188699e5c26918c398a11cc51d1bf8821dbb09

d837d1cc265e5cea16b43376ee5ced6b98b168fb.tar.gz

Add 2024 day 12

Diff

 README     |  4 ++--
 flake.lock | 24 ++++++++++++++----------
 2024/12.ml | 87 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 101 insertions(+), 14 deletions(-)

diff --git a/README b/README
index 0a04c45..68097cf 100644
--- a/README
+++ a/README
@@ -25,8 +25,8 @@
|        9 | OCaml    | |        9 | Haskell  |
|       10 | OCaml    | |       10 | Haskell  |
|       11 | OCaml    | |       11 | Haskell  |
+---------------------+ |       12 | Rust     |
                        |       13 | Haskell  |
|       12 | OCaml    | |       12 | Rust     |
+---------------------+ |       13 | Haskell  |
                        |       14 | Haskell  |
                        |       15 | Haskell  |
                        |       16 | Haskell  |
diff --git a/flake.lock b/flake.lock
index 2d33bfa..beab0ef 100644
--- a/flake.lock
+++ a/flake.lock
@@ -72,11 +72,11 @@
    },

    "nixpkgs": {
      "locked": {
        "lastModified": 1733392399,
        "narHash": "sha256-kEsTJTUQfQFIJOcLYFt/RvNxIK653ZkTBIs4DG+cBns=",
        "lastModified": 1734649271,
        "narHash": "sha256-4EVBRhOjMDuGtMaofAIqzJbg4Ql7Ai0PSeuVZTHjyKQ=",
        "owner": "NixOS",
        "repo": "nixpkgs",
        "rev": "d0797a04b81caeae77bcff10a9dde78bc17f5661",
        "rev": "d70bd19e0a38ad4790d3913bf08fcbfc9eeca507",
        "type": "github"
      },

      "original": {
@@ -123,11 +123,11 @@
    },

    "nixpkgs_4": {
      "locked": {
        "lastModified": 1733229606,
        "narHash": "sha256-FLYY5M0rpa5C2QAE3CKLYAM6TwbKicdRK6qNrSHlNrE=",
        "lastModified": 1733097829,
        "narHash": "sha256-9hbb1rqGelllb4kVUCZ307G2k3/UhmA8PPGBoyuWaSw=",
        "owner": "nixos",
        "repo": "nixpkgs",
        "rev": "566e53c2ad750c84f6d31f9ccb9d00f823165550",
        "rev": "2c15aa59df0017ca140d9ba302412298ab4bf22a",
        "type": "github"
      },

      "original": {
@@ -145,11 +145,11 @@
        "nixpkgs": "nixpkgs_2"
      },

      "locked": {
        "lastModified": 1733424534,
        "narHash": "sha256-yNH0n8C0JyGVnoXeFdSHJTXzEBPyxx1jPu7ez1vbNVg=",
        "lastModified": 1734619130,
        "narHash": "sha256-aibxngbQH4iGvq71ajf393u3BdhMhkrW1RdOj5NiaWA=",
        "owner": "ocaml",
        "repo": "ocaml-lsp",
        "rev": "93d9d6554fc127d475c4c27d878552c88d92d43d",
        "rev": "1628871bc216c708803376b83d2f4de05cafe4c0",
        "type": "github"
      },

      "original": {
@@ -215,11 +215,11 @@
        "nixpkgs": "nixpkgs_4"
      },

      "locked": {
        "lastModified": 1733440889,
        "narHash": "sha256-qKL3vjO+IXFQ0nTinFDqNq/sbbnnS5bMI1y0xX215fU=",
        "lastModified": 1734982074,
        "narHash": "sha256-N7M37KP7cHWoXicuE536GrVvU8nMDT/gpI1kja2hkdg=",
        "owner": "numtide",
        "repo": "treefmt-nix",
        "rev": "50862ba6a8a0255b87377b9d2d4565e96f29b410",
        "rev": "e41e948cf097cbf96ba4dff47a30ea6891af9f33",
        "type": "github"
      },

      "original": {
diff --git a/2024/12.ml b/2024/12.ml
new file mode 100755
index 0000000..33baf80 100755
--- /dev/null
+++ a/2024/12.ml
@@ -1,0 +1,87 @@
#!/usr/bin/env nix-shell

(*
#!nix-shell --pure -i ocaml -p ocaml
*)

let input =
  let rec aux () =
    try
      let parsed_line = read_line () |> String.to_seq |> List.of_seq in
      parsed_line :: aux ()
    with End_of_file -> []
  in
  aux () |> List.filter (fun v -> List.length v > 0)

let input' = input |> List.map Array.of_list |> Array.of_list

let is_valid (x, y) =
  x >= 0 && y >= 0 && y < Array.length input' && x < Array.length input'.(0)

let points =
  let rec walk_matching c x y visited =
    if (not (List.mem (x, y) visited)) && is_valid (x, y) && input'.(y).(x) == c
    then
      (x, y) :: visited
      |> walk_matching c (x - 1) y
      |> walk_matching c (x + 1) y
      |> walk_matching c x (y + 1)
      |> walk_matching c x (y - 1)
    else visited
  in
  let rec aux x y visited = function
    | [] ->
        []
    | [] :: rows ->
        aux 0 (y + 1) visited rows
    | (c :: cols) :: rows ->
        if List.mem (x, y) visited then aux (x + 1) y visited (cols :: rows)
        else
          let matching = walk_matching c x y [] in
          matching :: aux (x + 1) y (matching @ visited) (cols :: rows)
  in
  aux 0 0 [] input

let has_neighbour points (x, y) (dx, dy) =
  let neighbour = (x + dx, y + dy) in
  List.exists (( = ) neighbour) points

let fetch_neighbours points (x, y) =
  [(0, 1); (1, 0); (0, -1); (-1, 0)]
  |> List.filter (has_neighbour points (x, y))

let count_shared_edges points =
  List.fold_left
    (fun acc (x, y) -> acc + (fetch_neighbours points (x, y) |> List.length))
    0 points

let count_corners points =
  let is_corner (x, y) ((dy1, dx1), (dy2, dx2)) =
    let left_match = has_neighbour points (x, y) (dx1, dy1) in
    let right_match = has_neighbour points (x, y) (dx2, dy2) in
    let mid_match = has_neighbour points (x, y) (dx1 + dx2, dy1 + dy2) in
    ((not left_match) && not right_match)
    || (left_match && right_match && not mid_match)
  in
  let count_corners (x, y) =
    [((0, -1), (1, 0)); ((1, 0), (0, 1)); ((0, 1), (-1, 0)); ((-1, 0), (0, -1))]
    |> List.filter (is_corner (x, y))
    |> List.length
  in
  List.fold_left (fun acc (x, y) -> acc + count_corners (x, y)) 0 points

let part1 =
  let calc points =
    let area = List.length points in
    let perimeter = (4 * area) - count_shared_edges points in
    area * perimeter
  in
  points |> List.map calc |> List.fold_left ( + ) 0

let _ = part1 |> print_int |> print_newline

let part2 =
  let calc points = List.length points * count_corners points in
  points |> List.map calc |> List.fold_left ( + ) 0

let _ = part2 |> print_int |> print_newline