2019/day20.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dfile=day20.input] day20.m4
   3 # Optionally use -Dverbose=[12] to see some progress
   4 # Optionally use -Donly=[12] to skip a part
   5 # Optionally use -Dalgo=dfs|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(20), `ok', `',
   9 `errprint(`Missing common initialization
  10 ')m4exit(1)')
  11
  12 define(`input', include(defn(`file')))
  13 define(`input', translit(dquote(defn(`input')), `#', `='))
  14 ifdef(`algo', `', `define(`algo', `astar')')
  15
  16 define(`x_', 0)
  17 define(`y_', 0)
  18 define(`portals', 0)
  19 define(`moveu', ``u', $1, decr($2)')
  20 define(`mover', ``r', incr($1), $2')
  21 define(`moved', ``d', $1, incr($2)')
  22 define(`movel', ``l', decr($1), $2')
  23 define(`parse', `_$0(substr(defn(`input'), $1, 1))')
  24 define(`_parse', `ifelse(`$1', nl, `define(`y_', incr(y_))define(`x_', 0)',
  25   `ifelse(`$1', =, `', `$1', ` ', `', `point(`$1')')define(`x_', incr(x_))')')
  26 define(`point', `define(`g'x_`_'y_, `$1')ifelse(`$1', ., `', y_, 0, `',
  27   x_, 0, `', `_$0(`$1', defn(`g'decr(x_)`_'y_), `h')_$0($1,
  28   defn(`g'x_`_'decr(y_)), `v')')')
  29 define(`_point', `ifelse(`$2', `', `', `$2', ., `', `pushdef(`portal',
  30   ``$2$1','x_`,'y_`,$3')define(`portals', incr(portals))')')
  31 forloop_arg(0, decr(decr(len(defn(`input')))), `parse')
  32 define(`x_', decr(x_))
  33 define(`classify', `ifdef(`portal', `_$0(portal`'popdef(`portal'))$0()')')
  34 define(`_classify', `$0$4(`$1', ifelse(eval($3 == 1 || $3 == y_ ||
  35   $2 == 1 || $2 == x_), 1, ``o',`i'', ``i',`o''), $2, $3)')
  36 define(`_classifyh', `make(`$1', `$2', `$3', ifelse(defn(`g'incr($4)`_$5'),
  37   `.', `$4, $5, `r'', `decr($4), $5, `l''))')
  38 define(`_classifyv', `make(`$1', `$2', `$3', ifelse(defn(`g$4_'incr($5)),
  39   `.', `$4, $5, `d'', `$4, decr($5), `u''))')
  40 define(`make', `define(`$1$2', dquote(`$1', `$3', move$6($4, $5)))define(
  41   `g$4_$5', `$1$3')ifelse(`$1', `ZZ', `', `$2', `o', `define(`ports',
  42   ``$1','defn(`ports'))')')
  43 classify()
  44 define(`portals', eval(portals / 2))
  45 define(`width', eval(len(translit(substr(defn(`input'), eval(y_ / 2 * (x_ + 1)),
  46   incr(x_)), ` ABCDEFGHIJKLMNOPQRSTUVWXYZ'nl)) / 2))
  47 output(1, `parse complete, 'eval(portals - 1)` portal pairs beyond endpoints')
  48
  49 define(`resetprog', `define(`scans', 0)define(`hit', 0)define(`miss',
  50   0)define(`iter', 0)')
  51 define(`progress', `define(`$1', incr($1))ifelse('verbose`, 0, `',
  52   `_$0(eval(scans + hit + miss + iter))')')
  53 define(`_progress', `ifelse(eval($1 % 10000), 0, `output(2, `progress:$1')')')
  54 resetprog()
  55
  56 ifelse(algo, dfs, `
  57 output(1, `Using DFS algorithm')
  58
  59 define(`scan', `resetprog()pushdef(`best', 999999)_$0(shift(shift(AAo)), `$1',
  60   0)best(popdef(`best'))')
  61 define(`_scan', `ifdef(`g$2_$3', `progress(`scans')visit($@, defn(`g$2_$3'))')')
  62 define(`visit', `ifelse(eval($5 > best), 1, `', `$6', `ZZi', `_$0(`$4', $5)',
  63   `$6', `AAi', `', ifdef(`dist$2_$3_$4', `eval(dist$2_$3_$4 < $5)'), 1, `',
  64   `$6', `.', `define(`dist$2_$3_$4', $5)ifelse(`$1', `d', `', `_scan(moveu($2,
  65   $3), `$4', incr($5))')ifelse(`$1', `l', `', `_scan(mover($2, $3), `$4',
  66   incr($5))')ifelse(`$1', `u', `', `_scan(moved($2, $3), `$4', incr(
  67   $5))')ifelse(`$1', `r', `', `_scan(movel($2, $3), `$4', incr($5))')',
  68   `_scan(ifelse(`$4', `_', `move1', `move2')($6, `$4'), $5)')')
  69 define(`_visit', `ifelse(ifelse(`$1', `_', 0, `$1'), 0, `define(`best',
  70   decr($2))')')
  71 define(`move1', ``$3', $4, $5, `$6'')
  72 define(`move2', `ifelse(`$6$2', `0o', ``', 0, 0, 0', `$6$2', portals`i',
  73   ``', 0, 0, $6', ``$3', $4, $5, ifelse(`$2', `i', `incr', `decr')($6)')')
  74
  75 define(`showpath')
  76
  77 ', algo, astar, `
  78 output(1, `Using A* algorithm')
  79
  80 include(`priority.m4')
  81
  82 # Assumption: no cycles except through portals, thus DFS preprocessing works
  83 define(`scans', 0)
  84 define(`findpath', `_$0(shift(shift($1i)), `$1i', 0)_$0(shift(shift($1o)),
  85   `$1o', 0)')
  86 define(`_findpath', `ifelse(`$1', `', `', `ifdef(`g$2_$3',
  87   `progress(`scans')visit($@, defn(`g$2_$3'))')')')
  88 define(`visit', `ifelse(`$6', `AAi', `', `$6', `.', `ifelse(`$1', `d', `',
  89   `_findpath(moveu($2, $3), `$4', incr($5))')ifelse(`$1', `l', `',
  90   `_findpath(mover($2, $3), `$4', incr($5))')ifelse(`$1', `u', `',
  91   `_findpath(moved($2, $3), `$4', incr($5))')ifelse(`$1', `r', `',
  92   `_findpath(movel($2, $3), `$4', incr($5))')', `_visit(`$4', `$6', $5)')')
  93 define(`_visit', `define(`p$1$2', $3)define(`n$1', ``$2','defn(`n$1'))')
  94 foreach(`findpath', ports)
  95 output(2, `scans:'scans)
  96
  97 define(`heur', `ifelse(`$1', `_', 0, `eval($1 * ''width``)')')
  98
  99 define(`addwork', `define(`g$4$5', ``$3', `$1', `$2'')_$0(eval($3 + heur(`$5')),
 100   `$4', `$5')')
 101 define(`_addwork', `define(`f$2$3', $1)progress(`hit')insert($@)')
 102 define(`scan', `resetprog()addwork(`', `', 0, `AAo', `$1')loop(pop)clearall()')
 103 define(`loop', `ifelse($1, `', ``no path'', `ifelse(eval($1 + 0 > f$2$3), 1,
 104   `progress(`miss')loop(pop)', `$2', `ZZi', `decr($1)',
 105   `progress(`iter')_foreach(`_$0(', `, $@)', `', n$2)loop(pop)')')')
 106 define(`_loop', `ifelse(`$1', `', `', `decide(`$3', `$4', eval(first(g$3$4) +
 107   p$3$1), `$4', `$1', $1)')')
 108 define(`decide', `ifelse(ifelse(`$4', `_', 1, `$4', portals, 0, `$4$5', `0ZZi',
 109   1, `$5', `ZZi', 0, `$4$7', `0o', 0, 1), 0, `', `_$0(`$1', `$2', $3, `$5',
 110   ifelse(`$4', `_', ``_'', `$5', `ZZi', 0, `$7', `o', `decr($4)',
 111   `incr($4)'))')')
 112 define(`_decide', `ifelse(eval($3 < ifdef(`g$4$5', `first(g$4$5)', 999999)),
 113   1, `addwork($@)')')
 114
 115 define(`follow', `ifdef(`g$1$2', `_$0(`$1', g$1$2)')')
 116 define(`_follow', `ifelse(`$3', `', ``$1'', `follow(`$3', `$4')`,$1'')')
 117 ifelse(verbose, 0, `define(`showpath')', `define(`showpath', ` (follow(`ZZi',
 118   `$1'))')')
 119
 120 ', `output(0, `unknown algorithm')m4exit(1)')
 121
 122 ifelse(ifdef(`only', only, 1), 1, `
 123 define(`part1', scan(`_'))
 124 output(2, `scans:'scans` iter':iter` hits:'hit` miss:'miss)
 125 ')
 126
 127 ifelse(ifdef(`only', only, 2), 2, `
 128 define(`part2', scan(0))
 129 output(2, `scans:'scans` iter':iter` hits:'hit` miss:'miss)
 130 ')
 131
 132 divert`'part1`'showpath(`_')
 133 part2`'showpath(0)