2019/day18.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dfile=day18.input] day18.m4
   3 # Optionally use -Dverbose=[12] to see some progress
   4 # Optionally use -Donly=[12] to skip a part
   5 # Optionally use -Dalgo=dynamic|astar to compare path-finding algorithms
   6 # Optionally use -Dpriority=1|2|3|4|5 to choose priority queue algorithms
   7
   8 include(`common.m4')ifelse(common(18), `ok', `',
   9 `errprint(`Missing common initialization
  10 ')m4exit(1)')
  11
  12 # Careful: this code assumes that there are no single-letter macro names.
  13 # Exploit fact that on initial read, every line is a comment, so even if
  14 # keys `d', `n', `l' are adjacent, we don't eat the rest of the line.
  15 define(`input', include(defn(`file')))
  16 define(`input', translit(dquote(defn(`input')), `#@', `=_'))
  17 ifdef(`algo', `', `define(`algo', `dynamic')')
  18
  19 define(`careful', `_careful(`$0')`$0'')
  20 define(`_careful', `output(0, `unquoted use of single letter $1')')
  21 define(`door', eval(1 << 26))
  22 define(`val', `ifelse(`$1', ., 0, `val$1')')
  23 define(`lookup', `defn(`lookup'eval($1))')
  24 define(`makeval', `_$0(substr($1, $2, 1), eval((1 << $2) | $3))')
  25 define(`_makeval', `define(`val$1', $2)define(`lookup$2', `$1')define(`$1',
  26   defn(`careful'))')
  27 forloop(0, 25, `makeval(`abcdefghijklmnopqrstuvwxyz', ', `, 0)')
  28 forloop(0, 25, `makeval(`ABCDEFGHIJKLMNOPQRSTUVWXYZ', ', `, door)')
  29 define(`val_', 0)
  30 define(`_', defn(`careful'))
  31 define(`allkeys', 0)
  32 define(`firstbit', `($1 & ~($1 - 1))')
  33 define(`foreach_key', `ifelse($1, 0, `', `$2(lookup(firstbit($1)),
  34   `$3', `$4', `$5', `$6', `$7')$0(eval($1 - firstbit($1)), `$2', `$3', `$4',
  35   `$5', `$6', `$7')')')
  36
  37 define(`x_', 0)
  38 define(`y_', 0)
  39 define(`parse', `_$0(substr(defn(`input'), $1, 1))')
  40 define(`_parse', `ifelse(`$1', nl, `define(`y_', incr(y_))define(`x_', 0)',
  41   `ifelse(`$1', =, `', `point(`$1')')define(`x_', incr(x_))')')
  42 define(`point', `define(`g'x_`_'y_, `$1')ifelse(`$1', ., `', `$1', =, `',
  43   `define(`pos$1', x_`,'y_)ifelse(eval(val$1 & door), door, `',
  44   `define(`allkeys', eval(allkeys | val$1))define(`near$1', val$1)')')')
  45 pushdef(`_careful')
  46 forloop_arg(0, decr(decr(len(defn(`input')))), `parse')
  47 popdef(`_careful')
  48 define(`x_', decr(x_))
  49 output(1, `parse complete')
  50
  51 # Assume coordinates of @ divide quadrant (true for puzzle, false for example)
  52 define(`getq', `eval(($1 > $3) + 2 * ($2 > $4))')
  53 define(`moveU', `$1, decr($2), `U'')
  54 define(`moveR', `incr($1), $2, `R'')
  55 define(`moveD', `$1, incr($2), `D'')
  56 define(`moveL', `decr($1), $2, `L'')
  57 define(`scans', 0)
  58 define(`scan', `output(2, `scanning from $1')forloop_var(`x', 0, x_,
  59   `forloop_var(`y', 0, y_, `ifdef(`g'x`_'y, `define(`dist'x`_'y,
  60   999999)')')')ifelse(`$1', `_', `', `define(`q$1', getq(pos$1,
  61   pos_))')pushdef(`seen', 0)_$0(pos$1, `', 0, `$1')popdef(`seen')')
  62 define(`_scan', `ifdef(`g$1_$2', `define(`scans', incr(scans))visit($@)')')
  63 define(`visit', `ifelse(eval(dist$1_$2 < $4), 1, `',
  64   `define(`dist$1_$2', $4)pushdef(`seen', seen)ifelse(_$0(defn(`g$1_$2'),
  65   val(defn(`g$1_$2')), $4, `$5'), `', `ifelse(`$3', `D', `', `_scan(moveU($1,
  66   $2), incr($4), `$5')')ifelse(`$3', `L', `', `_scan(moveR($1, $2), incr($4),
  67   `$5')')ifelse(`$3', `U', `', `_scan(moveD($1, $2), incr($4), `$5')')ifelse(
  68   `$3', `R', `', `_scan(moveL($1, $2), incr($4), `$5')')')popdef(`seen')')')
  69 define(`_visit', `ifelse($2, 0, `', `$1', `$4', `', eval($2 & door), door,
  70   `define(`seen', eval(seen | ($2 & ~door)))', `define(`path$4$1',
  71   $3)define(`seen$4$1', seen)define(`near$4', eval(near$4 | $2))-')')
  72
  73 foreach_key(allkeys, `scan')
  74 scan(`_')
  75 output(2, `scans:'scans)
  76
  77 define(`until', `$2`'ifelse($1, 0, `$0($@)')')
  78 define(`closure', `foreach_key(eval(near$1 & ~near_), `_$0', $@)')
  79 define(`_closure', `foreach_key(eval(near_ & ~val$2), `merge',
  80   $@)define(`near_', eval(near_ | val$1))define(`path_$1', 0)')
  81 define(`merge', `ifdef(`path$1$2', `', `define(`path$1$2', eval(path$1$3 +
  82   path$2$3))define(`path$2$1', path$1$2)define(`seen$1$2', eval(seen$1$3 |
  83   seen$2$3 | val$3))define(`seen$2$1', seen$1$2)define(`near$1', eval(near$1 |
  84   val$2))define(`near$2', eval(near$2 | val$1))define(`q$2', q$3)')')
  85 until(`eval(allkeys == near_)', `foreach_key(near_, `closure')')
  86
  87 ifelse(eval(verbose >= 3), 1, `
  88 define(`show', ``$1'')
  89 define(`decode', `foreach_key($1, `show')')
  90 define(`temp', `output(3, `key $1')foreach_key(eval(allkeys - val$1),
  91   `_$0', `$1')')
  92 define(`_temp', `output(3, ` to $1: 'path$2$1` via 'decode(seen$2$1))')
  93 foreach_key(allkeys, `temp')
  94 ')
  95
  96 define(`hit', 0)
  97 define(`miss', 0)
  98 define(`iter', 0)
  99 define(`progress', `define(`$1', incr($1))ifelse(eval((hit + miss + iter) %
 100   10000), 0, `output(2, `progress:'eval(hit + miss + iter))')')
 101 define(`reach0', `ifdef(`seen$3$1', `eval(seen$3$1 & ~$2)')')
 102 define(`reach1', `ifdef(`seen$4$1', `eval(seen$4$1 & ~$2)')')
 103 define(`reach2', `ifdef(`seen$5$1', `eval(seen$5$1 & ~$2)')')
 104 define(`reach3', `ifdef(`seen$6$1', `eval(seen$6$1 & ~$2)')')
 105 define(`path0', `ifelse(`$3', `_', `eval(path$3$1 - 2)', `path$3$1')')
 106 define(`path1', `ifelse(`$4', `_', `eval(path$4$1 - 2)', `path$4$1')')
 107 define(`path2', `ifelse(`$5', `_', `eval(path$5$1 - 2)', `path$5$1')')
 108 define(`path3', `ifelse(`$6', `_', `eval(path$6$1 - 2)', `path$6$1')')
 109 define(`path4', `path$3$1')
 110 define(`next0', ``$1', `$4', `$5', `$6'')
 111 define(`next1', ``$3', `$1', `$5', `$6'')
 112 define(`next2', ``$3', `$4', `$1', `$6'')
 113 define(`next3', ``$3', `$4', `$5', `$1'')
 114 define(`square', `ifelse(forloop_var(`x', decr($1), incr($1), `forloop_var(`y',
 115   decr($2), incr($2), `_$0')'), `...._....', 1, 0)')
 116 define(`_square', `defn(`g'x`_'y)')
 117 define(`changed', `ifelse(`$1', `$6', `', `0, `$6'`'')ifelse(`$2', `$7', `',
 118   `1, `$7'`'')ifelse(`$3', `$8', `', `2, `$8'`'')ifelse(`$4', `$9', `',
 119   `3, `$9'`'')')
 120
 121 ifelse(algo, astar, `
 122 output(1, `Using A* algorithm')
 123
 124 include(`priority.m4')
 125
 126 define(`heur', `pushdef(`b0', 0)pushdef(`b1', 0)pushdef(`b2', 0)pushdef(`b3',
 127   0)foreach_key($3, `_$0', `', `$4', `$5', `$6', `$7')eval(b0 + b1 + b2 +
 128   b3)popdef(`b0', `b1', `b2', `b3')')
 129 define(`_heur', `check(norm(q$1), path(q$1)($@))')
 130 define(`check', `ifelse(eval($2 > b$1), 1, `define(`b$1', $2)')')
 131
 132 define(`addwork', `define(`g$4$5$6$7$3', ``$2', `$1'')_$0(eval($2 + heur($@)),
 133   `$3', `$4', `$5', `$6', `$7')')
 134 define(`_addwork', `define(`f$3$4$5$6$2', $1)progress(`hit')insert($@)')
 135 define(`distance', `addwork(`', 0, $@)loop(pop)clearall()define(`c$2$3$4$5$1',
 136   defn(`final'))popdef(`final')')
 137 define(`loop', `ifelse(eval($1 > f$3$4$5$6$2), 1, `progress(`miss')loop(pop)',
 138   $2, 0, `$1pushdef(`final', `$3$4$5$6$2')', `progress(`iter')foreach_key($2, `_$0', $2, `$3', `$4', `$5',
 139   `$6')loop(pop)')')
 140 define(`_loop', `ifelse(reach(q$1)(`$1', eval(allkeys - $2), `$3', `$4',
 141   `$5', `$6'), 0, `decide(`$3$4$5$6$2', eval(first(g$3$4$5$6$2) +
 142   path(q$1)($@)), eval($2 - val$1), next(q$1)($@))')')
 143 define(`decide', `ifelse(eval($2 < ifdef(`g$4$5$6$7$3', `first(g$4$5$6$7$3)',
 144   999999)), 1, `addwork($@)')')
 145
 146 define(`follow', `ifdef(`c$2$3$4$5$1', `_$0(defn(`c$2$3$4$5$1'),
 147   len(`$2$3$4$5'))')')
 148 define(`_follow', `$0_(shift(g$1), `$1', $2)')
 149 define(`_follow_', `ifelse(`$1', `', `', `_follow(`$1', $3)lookup(substr(`$1',
 150   $3) - substr(`$2', $3))')')
 151
 152 ', algo, dynamic, `
 153 output(1, `Using dynamic programming algorithm')
 154
 155 define(`better', `ifelse(eval($1 < first(best)), 1, `define(`best',
 156   `$@')')')
 157 define(`distance', `ifelse($1, 0, 0, ifdef(`c$2$3$4$5$1', 1), 1,
 158   `progress(`hit')first(c$2$3$4$5$1)', `progress(`miss')pushdef(`best',
 159   999999)foreach_key($1, `_$0', $@)define(`c$2$3$4$5$1',
 160   defn(`best'))first(best)popdef(`best')')')
 161 define(`_distance', `ifelse(reach(q$1)(`$1', eval(allkeys - $2), `$3', `$4',
 162   `$5', `$6'), 0, `better(eval(path(q$1)($@) + distance(eval($2 - val$1),
 163   next(q$1)($@))), next(q$1)($@))')')
 164
 165 define(`follow', `ifdef(`c$2$3$4$5$1', `_$0(changed(`$2', `$3', `$4', `$5',
 166   c$2$3$4$5$1), $@)')')
 167 define(`_follow', ``$2'follow(eval($3 - val$2), next$1(shift($@)))')
 168
 169 ', `output(0, `unknown algorithm')m4exit(1)')
 170
 171 ifelse(ifdef(`only', only, 1), 1, `
 172 output(1, `starting part 1')
 173 define(`norm', `0')
 174 define(`reach', `reach0')
 175 define(`path', `path4')
 176 define(`next', `next0')
 177 define(`part1', distance(allkeys, `_'))
 178 output(2, `hits:'hit` misses:'miss` iters:'iter)
 179 ')
 180
 181 ifelse(square(pos_), 0, `define(`part2', ``grid not suitable for part2'')',
 182 ifdef(`only', only, 2), 2, `
 183 output(1, `starting part 2')
 184 define(`hit', 0)
 185 define(`miss', 0)
 186 define(`iter', 0)
 187 define(`norm', `$1')
 188 define(`reach', `reach$1')
 189 define(`path', `path$1')
 190 define(`next', `next$1')
 191 define(`part2', distance(allkeys, `_', `_', `_', `_'))
 192 output(2, `hits:'hit` misses:'miss` iters:'iter)
 193 ')
 194
 195 divert`'part1`'ifelse(verbose, 0, `', ` (follow(allkeys, `_'))')
 196 part2`'ifelse(verbose, 0, `', ` (follow(allkeys, `_', `_', `_', `_'))')