From 2e7006389647b742e872c6a8c3fd6382209f1550 Mon Sep 17 00:00:00 2001 From: Eric Blake Date: Fri, 12 Jan 2024 16:57:39 -0600 Subject: [PATCH] day 23 optimize Add verbose mode to see progress, and approximately how many times travel() is called. Reduce runtime from >10m to 90s with a heuristic learned from the megathread: any perimeter node (one with fewer than 4 neighbors) is a pinch point; traveling backwards between perimeter nodes will only ever result in a dead end, so leave those directional. Prunes work from 102M down to 14.7M calls to travel(). --- 2023/day23.m4 | 49 +++++++++++++++++++++++++++++++------------------ 1 file changed, 31 insertions(+), 18 deletions(-) diff --git a/2023/day23.m4 b/2023/day23.m4 index 19f2367..63734d8 100644 --- a/2023/day23.m4 +++ b/2023/day23.m4 @@ -1,17 +1,14 @@ divert(-1)dnl -*- m4 -*- # Usage: m4 [-Dfile=day23.input] day23.m4 +# Optionally use -Dverbose=1 to see some progress -# TODO: Add verbose progress indicator. 8 minutes of staring is too long. -# Ideas for optimization: +# TODO: Ideas for optimization: # * Square root of work. Instead of doing ~3^34 branches from start to end, # do ~3^17 branches from start to mid, ~3^17 branches from end to mid, # then search for best valid pair among the results. Requires storing -# path as a bitmap (two ints). -# * Avoid dead work: http://clb.confined.space/aoc2023/#day23 -# mentions an easy way to label nodes by their shortest unweighted path -# to end (9 levels), and keep track of when a level is full (all paths to -# nodes in higher level must be avoided once last node in current level -# is visited) +# path as a bitmap. A single int bitmap is possible: although there are 36 +# nodes, our path must include start, end, and their two neighbors, which +# therefore don't need a bit in the map. # * Early abort. The max path occupies at most n-1 edges, and we know the # best score possible from all nodes. By comparing the potential possible # contribution of all unvisited nodes (subtract the current node's @@ -106,13 +103,14 @@ include(`common.m4')ifelse(common(23), `ok', `', define(`input', translit(include(defn(`file')), `#.>v'nl, `01234')) define(`x', 0)define(`y', 0)define(`n', 1) +define(`check', `ifdef(`$1', `define(`c'$1, incr(defn(`c'$1)))1')') define(`do0', `define(`x', incr($1))') define(`do1', `define(`g$1_$2')do0($@)') -define(`do2', `ifdef(`n'decr($1)`_$2', `', `ifdef(`n'incr($1)`_$2', `', - `define(`n'incr($1)`_$2', n)define(`n'n, incr($1)`,$2')define(`n', - incr(n))')')do1($@)') -define(`do3', `ifdef(`n$1_'decr($2), `', `define(`n$1_'incr($2), n)define(`n'n, - `$1,'incr($2))define(`n', incr(n))')do1($@)') +define(`do2', `ifelse(check(`n'decr($1)`_$2'), 1, `', check(`n'incr($1)`_$2'), + 1, `', `define(`n'incr($1)`_$2', n)define(`c'n, 1)define(`n'n, + incr($1)`,$2')define(`n', incr(n))')do1($@)') +define(`do3', `ifelse(check(`n$1_'decr($2)), 1, `', `define(`n$1_'incr($2), + n)define(`c'n, 1)define(`n'n, `$1,'incr($2))define(`n', incr(n))')do1($@)') define(`do4', `define(`maxx', $1)define(`x', 0)define(`y', incr($2))') ifdef(`__gnu__', ` @@ -125,17 +123,24 @@ ifdef(`__gnu__', ` # Assumption: all decision points are entered from top or left, and # exit to bottom or right. Reduce the graph to just the distances between -# nodes of interest, for a much smaller problem to solve. +# nodes of interest, for a much smaller problem to solve. In part 2, a +# naive brute force with no constraints on edges visits over 102 million +# edges, but given that we are a planar graph and cannot visit a node twice, +# any node with fewer than 4 neighbors is on a perimeter; edges between two +# perimeter nodes should always be directional to avoid cutting off a path +# to the end node. This change alone reduces work to 14.7 million edge visits. ifdef(`g1_0', `', `fatal(`failed assumption about start point')') ifdef(`g'decr(decr(maxx))`_'decr(y), `', `fatal(`failed assumption about end point')') -define(`n0', `1,0') -define(`n'n, decr(decr(maxx))`,'decr(y)) +define(`n0', `1,0')define(`c0', 1) +define(`n'n, decr(decr(maxx))`,'decr(y))define(`c'n, 1) define(`n'decr(decr(maxx))`_'decr(y), n) # pair(from_n, to_n, dist) +# Ep_n: list of neighbors for part p from node n +# en_m: weight of edge from node n to m define(`pair', `ifelse($1, $2, `', `define(`E1_$1', defn(`E1_$1')`,$2')define( - `E2_$1', defn(`E2_$1')`,$2')define(`E2_$2', defn(`E2_$2')`,$1')define( - `e$1_$2', $3)define(`e$2_$1', $3)')') + `E2_$1', defn(`E2_$1')`,$2')ifelse(eval(c$1==4 || c$2==4), 1, `define(`E2_$2', + defn(`E2_$2')`,$1')')define(`e$1_$2', $3)define(`e$2_$1', $3)')') # visit(x, y, from_n, dist) define(`_visit', `ifdef(`g$1_$2', `popdef(`g$1_$2')visit(incr($1), $2, $3, incr($4))visit($1, incr($2), $3, incr($4))visit(decr($1), $2, $3, @@ -143,6 +148,7 @@ define(`_visit', `ifdef(`g$1_$2', `popdef(`g$1_$2')visit(incr($1), $2, $3, define(`visit', `ifdef(`n$1_$2', `pair($3, n$1_$2, $4)ifdef(`s$1_$2', `', `define(`s$1_$2')_$0(incr($1), $2, n$1_$2, 1)_$0($1, incr($2), n$1_$2, 1)')', `_$0($@)')') +output(1, `...compressing graph') define(`s1_0')_visit(1, 1, 0, 1) # travel(n, dist, part) @@ -150,6 +156,13 @@ 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')')')') + +define(`p', 0) +define(`rename', `define(`$2', defn(`$1'))popdef(`$1')') +define(`show0', `output(1, `...$1')rename(`show$1', `show'eval($1+100000))') +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) -- 2.11.4.GIT