From b9437d842566f234f7df5581e37db6cbe23da32a Mon Sep 17 00:00:00 2001 From: Jordan Doyle 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