diff options
| -rw-r--r-- | lib/day10.ml | 59 |
1 files changed, 53 insertions, 6 deletions
diff --git a/lib/day10.ml b/lib/day10.ml index 5f433e2..b22d1fa 100644 --- a/lib/day10.ml +++ b/lib/day10.ml @@ -1,24 +1,71 @@ open! Imports +open! Core +open! Bigarray +open! Owl.Dense.Ndarray module M = struct (* Type to parse the input into *) - type t = unit + type t = (int, int_elt) Generic.t * (int * int) array (* Parse the input to type t, invoked for both parts *) - let parse _inputs = () + let parse inputs = + let grid = + String.split_lines inputs + |> Array.of_list + |> Array.map ~f:(fun x -> String.to_array x |> Array.map ~f:char_to_int) + |> Generic.of_arrays int + in + grid, + Generic.filter (fun x -> x = 0) grid + |> Array.map ~f:(fun x -> Generic.ind grid x) + |> Array.map ~f:(fun x -> x.(0), x.(1)) + + let search start memory grid = + let queue = Queue.singleton start in + let seen = ref CoordSet.empty in + let found = ref 0 in + while not @@ Queue.is_empty queue do + let (x, y) = Queue.dequeue_exn queue in + if not @@ CoordSet.mem (x, y) !seen then begin + if memory then seen := CoordSet.add (x, y) !seen; + if Generic.get grid [|x; y|] = 9 then found := !found + 1 + else + Queue.enqueue_all queue + ([(x+1, y); (x-1, y); (x, y+1); (x, y-1)] + |> List.filter ~f:(fun (a, b) -> 0 <= a && a < Generic.nth_dim grid 0 && 0 <= b && b < Generic.nth_dim grid 1) + |> List.filter ~f:(fun (a, b) -> Generic.get grid [|a; b|] = Generic.get grid [|x; y|] + 1)); + end + done; + !found (* Run part 1 with parsed inputs *) - let part1 _ = () + let part1 (grid, heads) = + Array.fold heads ~init:0 ~f:(fun acc x -> acc + search x true grid) + |> print_endline_int (* Run part 2 with parsed inputs *) - let part2 _ = () + let part2 (grid, heads) = + Array.fold heads ~init:0 ~f:(fun acc x -> acc + search x false grid) + |> print_endline_int end include M include Day.Make (M) (* Example input *) -let example = "" +let example = +"89010123 +78121874 +87430965 +96549874 +45678903 +32019012 +01329801 +10456732 +" (* Expect test for example input *) -let%expect_test _ = run example ; [%expect {| |}] +let%expect_test _ = run example ; [%expect {| + 36 + 81 + |}] |