From d60cf6d68fa7d121dce1470c89f65aab3bc8f46b Mon Sep 17 00:00:00 2001 From: Eric Blake Date: Sat, 13 Jan 2024 16:17:47 -0600 Subject: [PATCH] day 23 optimize again Speed up to ~16.3s silent (~26s verbose) by inlining foreach out of the hot loop, and by reusing the node visit macro as its own witness of being already visited. The same number of paths are explored, but now the progress meter increments only when work is done instead of when previously visited nodes are hit again, so the counter drops to 6M from 14.7M previously. (It would also be possible to use pushdef(`t'n, `show(p)') to track the same work as before, but that slows verbose execution even more.) --- 2023/day23.m4 | 21 ++++++++++++--------- 1 file changed, 12 insertions(+), 9 deletions(-) diff --git a/2023/day23.m4 b/2023/day23.m4 index 63734d8..ae3322a 100644 --- a/2023/day23.m4 +++ b/2023/day23.m4 @@ -151,21 +151,24 @@ define(`visit', `ifdef(`n$1_$2', `pair($3, n$1_$2, $4)ifdef(`s$1_$2', `', output(1, `...compressing graph') define(`s1_0')_visit(1, 1, 0, 1) -# travel(n, dist, part) -define(`_travel', `travel($2, eval($3+e$1_$2), $4)') -define(`travel', `ifelse(`$1', 'n`, `ifelse(eval($2 > part$3), 1, `define( - `part$3', $2)')', `ifdef(`t$1', `', `pushdef(`t$1')_foreach(`_$0($1, ', - `, $2, $3)', E$3_$1)popdef(`t$1')')')') +# Create tN(dist) and TN(dist) for each node N +define(`_travel_', ``$2$3(eval($''1+e$1_$3``))'') +define(`_travel', `define(`$2$1', ifelse(eval(verbose > 0), 1, + ``show(p)'')`pushdef(`$2$1')'_foreach(`$0_($1, `$2', ', `)', + shift($@))`popdef(`$2$1')')') +define(`travel', `_$0($1, `t'E1_$1)_$0($1, `T'E2_$1)') +forloop_arg(0, decr(n), `travel') +define(`t'n, `ifelse(eval($1 > part1), 1, `define(`part1', $1)')') +define(`T'n, `ifelse(eval($1 > part2), 1, `define(`part2', $1)')') define(`p', 0) define(`rename', `define(`$2', defn(`$1'))popdef(`$1')') -define(`show0', `output(1, `...$1')rename(`show$1', `show'eval($1+100000))') +define(`show0', `output(1, `...$1')rename(`show$1', `show'eval($1+500000))') define(`show', `ifdef(`$0$1', `$0$1($1)')define(`p', incr($1))') ifelse(eval(verbose > 0), 1, `define(`_travel', `show(p)'defn(`_travel'))') -define(`part1', 0)define(`part2', 0) -travel(0, 0, 1) -travel(0, 0, 2) +define(`part1', 0)t0(0) +define(`part2', 0)T0(0) divert`'part1 part2 -- 2.11.4.GIT