2023/day17.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dfile=day17.input] day17.m4
   3 # Optionally use -Dverbose=1 to see some progress
   4 # Optionally use -Dpriority=0|1|2|3|4|5|6 to choose priority queue algorithm
   5 # Optionally use -Dalgo=dijkstra|astar to choose search algorithm
   6
   7 include(`common.m4')ifelse(common(17, 1000003), `ok', `',
   8 `errprint(`Missing common initialization
   9 ')m4exit(1)')
  10
  11 # Some hilarity for Allez Cuisine!  Why implement a priority stack in
  12 # m4, when you can go an order of magnitude slower by doing it in
  13 # shell.  Uses the obligatory "goto" for gluing across languages.
  14 ifelse(defn(`priority'), 6, `
  15 output(1, `Using syscmd for priority queue')
  16 define(`Goto', `syscmd(`$1')ifelse(sysval, 0, `', `fatal(`$2')')')
  17 define(`gOto', `define(`$1', dquote(mkstemp(`$1.XXXXXX')))ifelse($1, `',
  18   `fatal(`Unable to create temporary file')')m4wrap(`syscmd(`rm -f '$1)')')
  19 gOto(`goto')
  20 gOto(`GOTO')
  21 define(`insert', `Goto(`printf %s\\n "'translit(`\{{$@}}', `{}`'',
  22   ``'[]')`" >> 'goto, `Unable to insert $* into priority queue')')
  23 define(`pop', `Goto(`sort -t[ -k2,2n 'goto` > 'GOTO` &&
  24   head -n1 'GOTO` > 'goto, `Unable to pop from priority queue')translit(
  25   (_include(goto)), `[]''nl``()', ``'')Goto(`tail -n+2 'GOTO` > 'goto,
  26   `Unable to pop from priority queue')')
  27 define(`clearall', `Goto(: > goto && : > GOTO, `Unable to wipe files')')
  28 ', `
  29 # Priorities are fairly close in range; lower overhead of O(n) sorting of
  30 # priority pushdef stack beats complexity of O(log n) min-heap
  31 ifdef(`priority', `', `define(`priority', 2)')
  32 include(`priority.m4')
  33 ')
  34 ifdef(`algo', `', `define(`algo', `astar')')
  35
  36 define(`input', translit(include(defn(`file')), nl, `0'))
  37 define(`x', 1)define(`y', 1)
  38 define(`do', `ifelse(`$3', 0, `define(`maxx', $1)define(`x', 1)define(`y',
  39   incr($2))', `define(`x', incr($1))define(`g$1_$2', $3)')')
  40
  41 ifdef(`__gnu__', `
  42   patsubst(defn(`input'), `.', `do(x, y, \&)')
  43 ',`
  44   define(`chew', `ifelse($1, 1, `do(x, y, $2)', `$0(eval($1/2), substr(
  45     `$2', 0, eval($1/2)))$0(eval($1-$1/2), substr(`$2', eval($1/2)))')')
  46   chew(len(defn(`input')), defn(`input'))
  47 ')
  48
  49 # Comparison of heuristics:
  50 # None (aka Dijkstra search): 763k addwork, 170k insert, 158k visit
  51 # Manhattan without current node: 762k addwork, 164k insert, 158k visit
  52 # Manhattan + g$1_$2: 762k addwork, 159k insert, 158k visit
  53 # unconstrained min-path: 608k addwork, 140k insert, 122k visit
  54 # In other words, the extra startup time of running a separate Dijkstra
  55 # to populate our heuristic (23K insert) ultimately makes our A* search
  56 # perform more effectively, for less overall time.
  57 ifelse(defn(`algo'), `dijkstra', `
  58 output(1, `using only Dijkstra search')
  59 define(`dist', `$3')
  60
  61 ', defn(`algo'), `astar', `
  62 output(1, `using A* search, finding min-path heuristic')
  63 # Dijkstra search for unconstrained min path to destination.  This
  64 # makes for a more useful heuristic for the A* in dealing with the
  65 # constraints below.
  66 define(`_visit', `ifdef(`g$2_$3', `ifelse(ifdef(`h$2_$3', `eval($1<h$2_$3)', 1),
  67   1, `define(`h$2_$3', $1)insert($@)')')')
  68 define(`visit', `_$0($1, decr($2), $3)_$0($1, $2, decr($3))_$0($1, incr($2),
  69   $3)_$0($1, $2, incr($3))')
  70 define(`minpath', `ifelse($1, `', `', `visit(eval($1+g$2_$3), $2, $3)$0(pop)')')
  71 define(`h'decr(maxx)`_'decr(y), 0)
  72 minpath(-defn(`g'decr(maxx)`_'decr(y)), decr(maxx), decr(y))
  73 define(`dist', `eval($3+h$1_$2)')
  74
  75 ', `fatal(`unknown value for algo')')
  76
  77 # Rather than explicitly tracking how many steps in a row we have
  78 # moved straight, it's easier to enqueue only the points where we turn
  79 # (up to 6 neighbors in part 1, up to 14 in part 2).  State is then
  80 # x,y coordinate and h/v entry direction.  It's easiest to add a
  81 # point's weight when leaving it; but this would miss the weight of
  82 # the goal and overcount the weight of the first point.  Hack around
  83 # that by counting the goal weight at the beginning of the search.
  84 pushdef(`g1_1', defn(`g'decr(maxx)`_'decr(y)))
  85 define(`prep', `define(`d$1', decr($1))')
  86 forloop_arg(1, 10, `prep')
  87 define(`d0', 0)
  88 # visitD(part, x, y, dist, op, lo, hi)
  89 define(`visith', `ifdef(`g$2_$3', `ifelse($6, 0, `addwork(`$1', $2, $3, `v',
  90   $4)')ifelse($7, 0, `', `$0(`$1', $5($2), $3, eval($4+g$2_$3), `$5', d$6,
  91   d$7)')')')
  92 define(`visitv', `ifdef(`g$2_$3', `ifelse($6, 0, `addwork(`$1', $2, $3, `h',
  93   $4)')ifelse($7, 0, `', `$0(`$1', $2, $5($3), eval($4+g$2_$3), `$5', d$6,
  94   d$7)')')')
  95
  96 define(`addwork', `ifelse(ifdef(`$1$2_$3$4', `eval($5<$1$2_$3$4)', 1), 1,
  97   `define(`$1$2_$3$4', `$5')insert(dist($2, $3, $5), $2, $3, `$4', $5,
  98   `$1$2_$3$4')')')
  99 define(`_round', `ifelse(`$2.$3', 'decr(maxx).decr(y)`, `$5clearall()',
 100   `ifelse($5, $6, `visit($2, $3, `$4', $5, `incr')visit($2, $3, `$4',
 101   $5, `decr')')$0(pop)')')
 102 define(`round', `addwork(`$1', 1, 1, `h', 0)addwork(`$1', 1, 1, `v',
 103   0)_$0(pop)')
 104
 105 define(`progress', 0)
 106 define(`rename', `define(`$2', defn(`$1'))popdef(`$1')')
 107 define(`show0', `output(1, `...$1')rename(`show$1', `show'eval($1+10000))')
 108 define(`show', `ifdef(`$0$1', `$0$1($1)')define(`progress', incr($1))')
 109 ifelse(eval(verbose >1), 1, `define(`_round', `show(progress)'defn(`_round'))')
 110
 111 output(1, `starting part 1 traversal')
 112 define(`visit', `$0$3(`p', $1, $2, $4, `$5', 1, 3)')
 113 define(`part1', round(`p'))
 114
 115 output(1, `starting part 2 traversal')
 116 define(`visit', `$0$3(`P', $1, $2, $4, `$5', 4, 10)')
 117 define(`part2', round(`P'))
 118
 119 divert`'part1
 120 part2