2023/day23.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dfile=day23.input] day23.m4
   3 # Optionally use -Dverbose=1 to see some progress
   4
   5 # TODO: Ideas for optimization:
   6 # * Square root of work. Instead of doing ~3^34 branches from start to end,
   7 # do ~3^17 branches from start to mid, ~3^17 branches from end to mid,
   8 # then search for best valid pair among the results.  Requires storing
   9 # path as a bitmap.  A single int bitmap is possible: although there are 36
  10 # nodes, our path must include start, end, and their two neighbors, which
  11 # therefore don't need a bit in the map.
  12 # * DP solution, which considers the state of 6 nodes at a time (as no level
  13 # of the graph is wider).  There are at most 76 possible states for 6 nodes:
  14 # https://www.reddit.com/r/adventofcode/comments/18ysozp/comment/kgdcc0p
  15 # |.....
  16 # .|....
  17 # ..|...
  18 # ...|..
  19 # ....|.
  20 # .....|
  21 # |()...
  22 # |(.)..
  23 # |(..).
  24 # |(...)
  25 # |.()..
  26 # |.(.).
  27 # |.(..)
  28 # |..().
  29 # |..(.)
  30 # |...()
  31 # .|()..
  32 # .|(.).
  33 # .|(..)
  34 # .|.().
  35 # .|.(.)
  36 # .|..()
  37 # ()|...
  38 # ..|().
  39 # ..|(.)
  40 # ..|.()
  41 # ().|..
  42 # (.)|..
  43 # .()|..
  44 # ...|()
  45 # ()..|.
  46 # (.).|.
  47 # (..)|.
  48 # .().|.
  49 # .(.)|.
  50 # ..()|.
  51 # ()...|
  52 # (.)..|
  53 # (..).|
  54 # (...)|
  55 # .()..|
  56 # .(.).|
  57 # .(..)|
  58 # ..().|
  59 # ..(.)|
  60 # ...()|
  61 # |()().
  62 # |()(.)
  63 # |().()
  64 # |(.)()
  65 # |.()()
  66 # |(()).
  67 # |(().)
  68 # |((.))
  69 # |(.())
  70 # |.(())
  71 # .|()()
  72 # .|(())
  73 # ()|().
  74 # ()|(.)
  75 # ()|.()
  76 # ().|()
  77 # (.)|()
  78 # .()|()
  79 # ()()|.
  80 # (())|.
  81 # ()().|
  82 # ()(.)|
  83 # ().()|
  84 # (.)()|
  85 # .()()|
  86 # (()).|
  87 # (().)|
  88 # ((.))|
  89 # (.())|
  90 # .(())|
  91 # More importantly, any two rows of nodes can be collapsed into one, with
  92 # a finite number of transitions to the next row that don't form a
  93 # disconnected loop.
  94
  95 include(`common.m4')ifelse(common(23), `ok', `',
  96 `errprint(`Missing common initialization
  97 ')m4exit(1)')
  98
  99 define(`input', translit(include(defn(`file')), `#.>v'nl, `01234'))
 100 define(`x', 0)define(`y', 0)define(`n', 1)
 101 define(`check', `ifdef(`$1', `define(`c'$1, incr(defn(`c'$1)))1')')
 102 define(`do0', `define(`x', incr($1))')
 103 define(`do1', `define(`g$1_$2')do0($@)')
 104 define(`do2', `ifelse(check(`n'decr($1)`_$2'), 1, `', check(`n'incr($1)`_$2'),
 105   1, `', `define(`n'incr($1)`_$2', n)define(`c'n, 1)define(`n'n,
 106   incr($1)`,$2')define(`n', incr(n))')do1($@)')
 107 define(`do3', `ifelse(check(`n$1_'decr($2)), 1, `', `define(`n$1_'incr($2),
 108   n)define(`c'n, 1)define(`n'n, `$1,'incr($2))define(`n', incr(n))')do1($@)')
 109 define(`do4', `define(`maxx', $1)define(`x', 0)define(`y', incr($2))')
 110
 111 ifdef(`__gnu__', `
 112   patsubst(defn(`input'), `.', `do\&(x, y)')
 113 ',`
 114   define(`chew', `ifelse($1, 1, `do$2(x, y)', `$0(eval($1/2), substr(
 115     `$2', 0, eval($1/2)))$0(eval($1-$1/2), substr(`$2', eval($1/2)))')')
 116   chew(len(defn(`input')), defn(`input'))
 117 ')
 118
 119 # Assumption: all decision points are entered from top or left, and
 120 # exit to bottom or right. Reduce the graph to just the distances between
 121 # nodes of interest, for a much smaller problem to solve.  In part 2, a
 122 # naive brute force with no constraints on edges visits over 102 million
 123 # edges, but given that we are a planar graph and cannot visit a node twice,
 124 # any node with fewer than 4 neighbors is on a perimeter; edges between two
 125 # perimeter nodes should always be directional to avoid cutting off a path
 126 # to the end node. This change alone reduces work to 14.7 million edge visits.
 127 ifdef(`g1_0', `', `fatal(`failed assumption about start point')')
 128 ifdef(`g'decr(decr(maxx))`_'decr(y), `',
 129   `fatal(`failed assumption about end point')')
 130 define(`n0', `1,0')define(`c0', 1)
 131 define(`n'n, decr(decr(maxx))`,'decr(y))define(`c'n, 1)
 132 define(`n'decr(decr(maxx))`_'decr(y), n)
 133 # pair(from_n, to_n, dist)
 134 # Ep_n: list of neighbors for part p from node n
 135 # en_m: weight of edge from node n to m
 136 define(`pair', `ifelse($1, $2, `', `define(`E1_$1', defn(`E1_$1')`,$2')define(
 137   `E2_$1', defn(`E2_$1')`,$2')ifelse(eval(c$1==4 || c$2==4), 1, `define(`E2_$2',
 138   defn(`E2_$2')`,$1')')define(`e$1_$2',  $3)define(`e$2_$1', $3)')')
 139 # visit(x, y, from_n, dist)
 140 define(`_visit', `ifdef(`g$1_$2', `popdef(`g$1_$2')visit(incr($1), $2, $3,
 141   incr($4))visit($1, incr($2), $3, incr($4))visit(decr($1), $2, $3,
 142   incr($4))visit($1, decr($2), $3, incr($4))')')
 143 define(`visit', `ifdef(`n$1_$2', `pair($3, n$1_$2, $4)ifdef(`s$1_$2', `',
 144   `define(`s$1_$2')_$0(incr($1), $2, n$1_$2, 1)_$0($1, incr($2), n$1_$2,
 145   1)')', `_$0($@)')')
 146 output(1, `...compressing graph')
 147 define(`s1_0')_visit(1, 1, 0, 1)
 148
 149 # Hueristic: best possible path remaining
 150 define(`b', 0)define(`B', 0)
 151 define(`_best', `ifelse($3, `', $2, `$0($1, ifelse(eval(e$1_$3>$2), 1, e$1_$3,
 152   $2), shift(shift(shift($@))))')')
 153 define(`best', `define(`b$1', _$0($1, 0E1_$1))define(`b', eval(b+b$1))define(
 154   `B$1', _$0($1, 0E2_$1))define(`B', eval(B+B$1))')
 155 forloop_arg(0, decr(n), `best')
 156
 157 # Create tN(dist, best) and TN(dist, best) for each node N
 158 define(`_travel_', ``$2$4(eval($''1+e$1_$4``), eval($''2-$3$1``))'')
 159 define(`_travel', `define(`$2$1', ifelse(eval(verbose > 0), 1,
 160   ``show(p)'')`ifelse(eval($'`1+$'`2>=part$3), 1, 'dquote(
 161   `pushdef(`$2$1')'_foreach(`$0_($1, `$2', `$4', ', `)',
 162   shift(shift(shift($@))))`popdef(`$2$1')')`)')')
 163 define(`travel', `_$0($1, `t', 1, `b'E1_$1)_$0($1, `T', 2, `B'E2_$1)')
 164 forloop_arg(0, decr(n), `travel')
 165 define(`t'n, `ifelse(eval($1 > part1), 1, `define(`part1', $1)')')
 166 define(`T'n, `ifelse(eval($1 > part2), 1, `define(`part2', $1)')')
 167
 168 define(`p', 0)
 169 define(`rename', `define(`$2', defn(`$1'))popdef(`$1')')
 170 define(`show0', `output(1, `...$1')rename(`show$1', `show'eval($1+200000))')
 171 define(`show', `ifdef(`$0$1', `$0$1($1)')define(`p', incr($1))')
 172 ifelse(eval(verbose > 0), 1, `define(`_travel', `show(p)'defn(`_travel'))')
 173
 174 define(`part1', 0)t0(0, b)
 175 define(`part2', 0)T0(0, B)
 176
 177 divert`'part1
 178 part2