2022/day16.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dfile=day16.input] day16.m4
   3 # Optionally use -Dverbose=1 to see some progress
   4 # Optionally use -Dreduce=floyd|bfs to choose reduction algorithm
   5 # Optionally use -Dalgo=dfs|dijkstra|astar to choose search algorithm
   6 # Optionally use -Dpriority=0|1|2|3|4|5 to choose priority queue algorithm
   7
   8 include(`common.m4')ifelse(common(16, 1000003), `ok', `',
   9 `errprint(`Missing common initialization
  10 ')m4exit(1)')
  11
  12 include(`priority.m4')
  13 ifdef(`reduce', `', `define(`reduce', `bfs')')
  14 ifdef(`algo', `', `define(`algo', `astar')')
  15
  16 # First, parse in the data, and simplify the graph
  17 # Floyd-Warshall computes all pairwise minimum distances in O(n^3) effort,
  18 # but since n is only 60 for my input, that isn't horrible.  Alternatively,
  19 # a BFS search from each of the 16 interesting starting points (AA and up
  20 # to 15 valve roooms) is also O(n^2) search from O(n) points, but with less
  21 # overall work to perform.
  22 #
  23 # There are at most 15 valves worth opening. Part 2 needs to track the best
  24 # score for each possible set of reachable rooms bM; however, that score is
  25 # not sufficient for pruning (A->B may score worse than B->A, but if B is
  26 # closer to C, A->B->C may be better than B->A->C), so this also uses bXXM
  27 # which includes the current room.  Time taken (cutoffs at 26/30) does not
  28 # need to be stored in state, but is passed through recursion to prune paths
  29 # when time expires.
  30 # n - number of input lines
  31 # nN - number to name
  32 # nXX - name to number
  33 # rXX - valve rate for room XX
  34 # tXX_ - neighbors of XX
  35 # tXX_YY - travel time from XX to YY
  36 # v - number of interesting rooms
  37 # vXX - bitmask value for interesting room XX
  38 # vall - bitmask for all interesting rooms
  39 # bXXM - best time-30 score for room + bitmask
  40 # BXXM - best time-30 time for room + bitmask
  41 # bM - best time-26 score for bitmask
  42 # i - number of seen time-26 bitmasks
  43 # list - interesting rooms, sorted highest rate first
  44 define(`v', 0)define(`vall', 0)
  45 define(`list')
  46 define(`sort', `ifelse(`$2', `', ``,`$1''', `ifelse(eval(r$1>r$2), 1,
  47   ``,$@'', ``,`$2''$0(`$1', shift(shift($@)))')')')
  48 define(`gen', `define(`v$6', `(1<<$7)')define(`vall', eval(vall|
  49   v$6))define(`visit$6', `ifelse(eval('dquote(`$8$5&'v$6)`),0,`visit(`$6',
  50   eval(`$8$2+1+'t$8$1_$6),`$8$3',`$8$4',`$8$5')')')define(`list',
  51   sort(`$6'list))define(`v', incr($7))')
  52 define(`n', 0)define(`ceil', 0)define(`Valve', `_/')
  53 translit((include(defn(`file'))), `/=;'nl` 'alpha, `(,,)'define(`_',
  54   `define(`n'n, `$1')define(`n$1', n)define(`t$1_$1', 0)define(`r$1',
  55   $2)define(`ceil', eval(ceil+$2))define(`t$1_', dquote(`', shift(shift(
  56   $@))))ifelse(`$2', 0, `', `gen(1, 2, 3, 4, 5, `$1', v, `$')')define(`n',
  57   incr(n))'))
  58 define(`_visiteach', _foreach(`defn(`visit'', `)', list))dnl see _visit below
  59
  60 ifelse(defn(`reduce'), `floyd', `
  61 output(1, `Using Floyd-Warshall to reduce graph')
  62 define(`prep', `_foreach(`define(`t$1_'', `, 1)', t$1_)')
  63 forloop(0, decr(n), `prep(defn(`n'', `))')
  64 define(`t', `ifdef(`t$1_$2', `t$1_$2', 'n`)')
  65 define(`_bump', `ifelse(eval(`$2>$3+$4'), 1, `define(`$1', eval(`$3+$4'))')')
  66 define(`bump', `_$0(`t$1_$2', t(`$1', `$2'), t(`$1', `$3'), t(`$3', `$2'))')
  67 define(`prep2', `forloop(0, $1, `bump(`$2', defn(`n'', `), `$3')')')
  68 define(`prep1', `forloop(0, $1, `prep2($1, defn(`n'', `), `$2')')')
  69 forloop(0, decr(n), `prep1('decr(n)`, defn(`n'', `))')
  70
  71 ', defn(`reduce'), `bfs', `
  72 output(1, `Using BFS to reduce graph')
  73 define(`round', `ifdef(`t$1_$3', `', `define(`t$1_$3', $2)t$3_')')
  74 define(`_walk', `ifelse(`$3', `', `', `$0(`$1', incr($2)_foreach(`round(`$1',
  75   `$2', ', `)', shift($@)))')')
  76 define(`walk', `ifelse(r$1, 0, `', `_$0(`$1', 1t$1_)')')
  77 _walk(`AA', 1tAA_)
  78 forloop(0, decr(n), `walk(defn(`n'', `))')
  79
  80 ', `fatal(`unknown algorithm for reduce')')
  81
  82 define(`part1', 0)define(`i', 0)
  83 define(`progress', 0)
  84 define(`rename', `define(`$2', defn(`$1'))popdef(`$1')')
  85 define(`show0', `output(1, `...$1')rename(`show$1', `show'eval($1+100000))')
  86 define(`show', `ifdef(`$0$1', `$0$1($1)')define(`progress', incr($1))')
  87 define(`check1', `ifelse(eval($1>part1), 1, `define(`part1', $1)')')
  88 define(`check2', `ifelse(ifdef(`b$2', `eval(`$1-4*$3>'b$2)', `define(`i',
  89   incr(i))1'), 1, `define(`b$2', eval(`$1-4*$3'))')')
  90 # _visit(oldroom, oldtime, newscore, newrate, newmask)
  91 define(`_visit', `ifelse(eval(`$2<26'), 1, `check2($3, $5, $4)')ifelse(
  92   ifelse(eval(defn(`b$1$5')`+0<$3'), 1, `define(`b$1$5', $3)1')ifelse(
  93   eval(defn(`B$1$5')`+0<30-$2'), 1, `define(`B$1$5', `30-$2')1'), `', `', $5,
  94   'vall`, `check1($3)', `$0each($@)')')
  95 # visit(newroom, newtime, oldscore, oldrate, oldmask)
  96 define(`visit', `ifelse(eval($2>=30), 1, `check1($3)', `_$0(`$1', `$2',
  97   eval(`$3+(30-$2)*'r$1), eval($4+r$1), eval($5|v$1))')')
  98 ifelse(eval(verbose >1), 1, `define(`visit', `show(progress)'defn(`visit'))',
  99   `output(1, `Starting search')')
 100 define(`vAA', 0)visit(`AA', 0, 0, 0, 0)
 101
 102 output(1, ...i` possibilities to check')
 103 define(`part2', 0)
 104 define(`max', `ifelse($2, `', $1, `$0(ifelse(eval($2>$1), 1, $2, $1),
 105   shift(shift($@)))')')
 106 define(`_b', `ifelse(eval(`$1&(1<<$2)'), 0, `', `, b(eval(`$1&~(1<<$2)'))')')
 107 define(`b', `ifdef(`b$1', `', `define(`b$1', max(0forloop(0, ''decr(v)``,
 108   `_$0($1, ', `)')))')b$1')
 109 define(`_collect', `ifelse(eval(`$1+$2'>part2), 1, `define(`part2',
 110   eval(`$1+$2'))')')
 111 define(`collect', `_$0(b($1), b(eval('vall`^$1)))')
 112 forloop_arg(0, eval(vall/2), `collect')
 113
 114 # TODO: does an alternative to DFS help?
 115 # Search favors minimum priority, but we want maximum score; do this by
 116 # using 30*sum(valves) as the ceiling, where ceiling-score is priority
 117 dnl define(`goal', eval(0xfffff1e))
 118 ifelse(`
 119 define(`_use', `ifelse(ifdef(`v$3', `v$3($1)', 0), 1, `', ifdef(`d$1',
 120   `eval($2 < d$1)', 1), 1, `addwork($1, $2)show(progress)')')
 121 define(`progress', 0)
 122 define(`rename', `define(`$2', defn(`$1'))popdef(`$1')')
 123 define(`show1000', `output(1, `...$1')rename(`show$1', `show'eval($1+1000))')
 124 define(`show', `ifdef(`$0$1', `$0$1($1)')define(`progress', incr($1))')
 125 define(`neighbors',)
 126 dnl forloop(0, decr(count), ``check('', ``, $'`1, $'`2)'')dnl
 127 dnl `first(ifdef(`n0', `defn(`n0')undefine(`n0')undefine(`n1')', `_$0()'))')
 128 define(`_neighbors', `ifdef(`n1', `defn(`n1')popdef(`n1')$0()')')
 129 define(`distance', `output(1, `...part $2')addwork(`0000000$1$2', 0)_$0($2)')
 130 ')
 131
 132 divert`'part1
 133 part2