2021/day15.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dhashsize=H] [-Dfile=day15.input] day15.m4
   3 # Optionally use -Dverbose=1 to see some progress
   4 # Optionally use -Dpriority=0|1|2|3|4|5 to choose priority queue algorithms
   5
   6 include(`common.m4')ifelse(common(15, 1000003), `ok', `',
   7 `errprint(`Missing common initialization
   8 ')m4exit(1)')
   9
  10 # Pending priorities fall in narrow range
  11 ifdef(`priority', `', `define(`priority', 2)')
  12 include(`priority.m4')
  13
  14 define(`input', translit(include(defn(`file')), nl, `;'))
  15 define(`width', index(defn(`input'), `;'))
  16 define(`x', 0)define(`y', 0)
  17 define(`do', `ifelse(`$3', `;', `define(`y', incr($2))define(`x', 0)',
  18   `define(`g$1_$2', $3)define(`x', incr($1))')')
  19 ifdef(`__gnu__', `
  20   patsubst(defn(`input'), `.', `do(x, y, `\&')')
  21 ',`
  22   define(`chew', `ifelse($1, 1, `do(x, y, `$2')', `$0(eval($1/2), substr(
  23     `$2', 0, eval($1/2)))$0(eval($1-$1/2), substr(`$2', eval($1/2)))')')
  24   chew(len(defn(`input')), defn(`input'))
  25 ')
  26
  27 define(`_g', `eval(1 + (defn(`g'eval($1%'width`)`_'eval(
  28   $2%'width`)) - 1 + $1/'width` + $2/'width`) % 9)')
  29 define(`g', `ifdef(`g$1_$2', `g$1_$2()', `_g($1, $2)')')
  30 define(`edge1', decr(width))
  31 define(`edge2', eval(5*width-1))
  32 define(`count', 0)
  33 define(`addwork', `define(`d$1_$2_$3', $4)insert($4, $1, $2, $3)define(`count',
  34   incr(count))ifelse(eval(count%10000), 0, `output(1, ...count)')')
  35 define(`distance', `addwork($1, 0, 0, 0)loop(pop, edge$1)clearall()')
  36 define(`loop', `ifelse(`$3,$4', `$5,$5', $1, `neighbors($2, $3, $4,
  37   d$2_$3_$4, $5)loop(pop, $5)')')
  38 define(`check', `ifdef(`d$1_$2_$3', `', `addwork($1, $2, $3,
  39   eval($4 + g($2, $3)))')')
  40 define(`neighbors', `ifelse($2, 0, `', `check($1, decr($2), $3, $4)')ifelse($3,
  41   0, `', `check($1, $2, decr($3), $4)')ifelse($2, $5, `', `check($1,
  42   incr($2), $3, $4)')ifelse($3, $5, `', `check($1, $2, incr($3), $4)')')
  43 define(`part1', distance(1))
  44 define(`part2', distance(2))
  45
  46 divert`'part1
  47 part2