changeset 59:dbabaef9b4ad

Day 10: minor clean-up
author Lewin Bormann <lbo@spheniscida.de>
date Thu, 21 Dec 2023 22:03:28 +0100
parents 76994fea8568
children bfee0c4830d2
files 2023/day10.ml
diffstat 1 files changed, 14 insertions(+), 5 deletions(-) [+]
line wrap: on
line diff
--- a/2023/day10.ml	Thu Dec 21 21:54:47 2023 +0100
+++ b/2023/day10.ml	Thu Dec 21 22:03:28 2023 +0100
@@ -249,11 +249,12 @@
   let mark_left_neighbors field t pathset from top =
     let pipe = get_pipe field top in
     let cands = candidate_positions from top pipe in
-    let cands = List.filter ~f:(exists field) cands in
-    let maybe_mark pos =
-      if not (Hash_set.mem pathset pos) then mark_inside field t pos else ()
+    let not_in_path pos = not (Hash_set.mem pathset pos) in
+    let neighs =
+      List.filter ~f:(fun c -> exists field c && not_in_path c) cands
     in
-    List.iter ~f:maybe_mark cands
+    let mark pos = mark_inside field t pos in
+    List.iter ~f:mark neighs
 
   (* mark ground tiles left-adjacent to path. *)
   let mark_initial field t path pathset =
@@ -283,11 +284,15 @@
     in
     let ok_neighs = List.filter ~f:ok neighs in
     List.iter ~f:(mark_inside field t) ok_neighs;
-    (* recurse into neighbors *)
+    (* recurse into neighbors (DFS) *)
     List.iter ~f:(mark_adjacent_ground field t pathset) ok_neighs
 
+  (* entry point: set up inside bitmap, mark initial left-of-path neighbors, and expand
+     from neighbors to all reachable tiles within the path. *)
   let count_enclosed_tiles field path =
     let t = create field in
+    (* in addition to the path list we supply a hash set of all nodes, which drastically
+       accelerates the marking process. *)
     let pathset = Hash_set.of_list (module Position) path in
     mark_initial field t path pathset;
     let mark ix marked =
@@ -303,6 +308,10 @@
   let field = Parse.parse_field input in
   let path = Part1.find_path field in
   let revpath = List.rev path in
+  (* dirty trick: we don't know which direction the traversal took.
+     But the direction determines what's "inside" and what's "outside".
+     Therefore: just calculate both inside and outside tiles, one of them
+     will be right *)
   let in_path1 = Part2.count_enclosed_tiles field revpath in
   let in_path2 =
     Part2.count_enclosed_tiles field (List.hd_exn revpath :: path)