Mercurial > lbo > hg > aoc22
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)