Mercurial > lbo > hg > aoc22
changeset 51:fd579cbd3a93
Leakyroof: add a few comments
author | Lewin Bormann <lbo@spheniscida.de> |
---|---|
date | Wed, 13 Dec 2023 15:02:07 +0100 |
parents | fd8411815fff |
children | 0a0ff94175b5 |
files | 2023/leakyroof.ml |
diffstat | 1 files changed, 5 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- a/2023/leakyroof.ml Wed Dec 13 09:34:10 2023 +0100 +++ b/2023/leakyroof.ml Wed Dec 13 15:02:07 2023 +0100 @@ -22,12 +22,16 @@ type cover = { rows : bool array; cols : bool array } [@@deriving sexp] + (* Memory for covered rows/columns. Runtime and memory efficient: no copies + necessary, just some bits set temporarily. *) let cover_for_roof roof = { rows = Array.create ~len:roof.m false; cols = Array.create ~len:roof.n false; } + (* Execute function f while row m is covered in cover. + Restore previous state after f returns. Return f's result. *) let with_row_covered m cover f = let old = cover.rows.(m) in cover.rows.(m) <- true; @@ -65,6 +69,7 @@ Array.find_mapi roof.a ~f end +(* Recursive optimal solution guaranteed *) let rec solve roof cover = match Roof.first_open_leak roof cover with | None -> Roof.covers cover