From b9437d842566f234f7df5581e37db6cbe23da32a Mon Sep 17 00:00:00 2001
From: Jordan Doyle <jordan@doyle.la>
Date: Fri, 27 Dec 2024 01:34:29 +0700
Subject: [PATCH] Add 2024 day 18

---
 README     |  4 ++--
 2024/18.ml | 72 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 74 insertions(+), 2 deletions(-)

diff --git a/README b/README
index 84212d8..c266f46 100644
--- a/README
+++ a/README
@@ -31,8 +31,8 @@
 |       15 | OCaml    | |       15 | Haskell  |
 |       16 | OCaml    | |       16 | Haskell  |
 |       17 | OCaml    | |       17 | Rust     |
-+---------------------+ |       18 | Haskell  |
-                        |       19 | Haskell  |
+|       18 | OCaml    | |       18 | Haskell  |
++---------------------+ |       19 | Haskell  |
                         |       20 | Haskell  |
                         |       21 | Rust     |
                         |       22 | Haskell  |
diff --git a/2024/18.ml b/2024/18.ml
new file mode 100755
index 0000000..5190521 100755
--- /dev/null
+++ a/2024/18.ml
@@ -1,0 +1,72 @@
+#!/usr/bin/env nix-shell
+
+(*
+#!nix-shell --pure -i ocaml -p ocaml
+*)
+
+let blocks =
+  let rec aux () =
+    try
+      match read_line () |> String.split_on_char ',' with
+      | [x; y] ->
+          (int_of_string x, int_of_string y) :: aux ()
+      | _ ->
+          failwith "bad input"
+    with End_of_file -> []
+  in
+  aux ()
+
+let rec take n xs =
+  match (n, xs) with 0, _ | _, [] -> [] | _, x :: xs -> x :: take (n - 1) xs
+
+module PosMap = Map.Make (struct
+  type t = int * int
+
+  let compare = compare
+end)
+
+let traverse blocks =
+  let grid_size = (70, 70) in
+  let start_pos = (0, 0) in
+  let target_pos = grid_size in
+  let is_valid_position (x, y) =
+    x >= 0 && y >= 0
+    && x <= fst grid_size
+    && y <= snd grid_size
+    && not (List.mem (x, y) blocks)
+  in
+  let rec bfs queue distances =
+    match queue with
+    | [] ->
+        None
+    | (pos, dist) :: rest ->
+        if pos = target_pos then Some dist
+        else
+          let neighbours =
+            [(0, -1); (0, 1); (1, 0); (-1, 0)]
+            |> List.map (fun (dx, dy) -> (fst pos + dx, snd pos + dy))
+            |> List.filter is_valid_position
+            |> List.filter (fun p -> not (PosMap.mem p distances))
+          in
+          let new_distances =
+            List.fold_left
+              (fun acc p -> PosMap.add p (dist + 1) acc)
+              distances neighbours
+          in
+          let new_queue = rest @ List.map (fun p -> (p, dist + 1)) neighbours in
+          bfs new_queue new_distances
+  in
+  bfs [(start_pos, 0)] (PosMap.singleton start_pos 0)
+
+let part1 =
+  traverse (take 1024 blocks) |> Option.get |> print_int |> print_newline
+
+let part2 =
+  let first_allowed_from_back =
+    Array.init (List.length blocks) Fun.id
+    |> Array.to_list
+    |> List.find (fun n ->
+           traverse (take (List.length blocks - n) blocks) |> Option.is_some )
+  in
+  let x, y = List.nth blocks (List.length blocks - first_allowed_from_back) in
+  Printf.printf "%d,%d\n" x y
--
rgit 0.1.5