#!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