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=1|2|3|4|5|6 to choose priority queue algorithm
   5
   6 include(`common.m4')ifelse(common(17, 1000003), `ok', `',
   7 `errprint(`Missing common initialization
   8 ')m4exit(1)')
   9
  10 ifelse(defn(`priority'), 6, `
  11 output(1, `Using syscmd for priority queue')
  12 define(`Goto', `syscmd(`$1')ifelse(sysval, 0, `', `fatal(`$2')')')
  13 define(`gOto', `define(`$1', dquote(mkstemp(`$1.XXXXXX')))ifelse($1, `',
  14   `fatal(`Unable to create temporary file')')m4wrap(`syscmd(`rm -f '$1)')')
  15 gOto(`goto')
  16 gOto(`GOTO')
  17 define(`insert', `Goto(`printf %s\\n "'translit(`\{{$@}}', `{}`'',
  18   ``'[]')`" >> 'goto, `Unable to insert $* into priority queue')')
  19 define(`pop', `Goto(`sort -t[ -k2,2n 'goto` > 'GOTO` &&
  20   head -n1 'GOTO` > 'goto, `Unable to pop from priority queue')translit(
  21   (_include(goto)), `[]''nl``()', ``'')Goto(`tail -n+2 'GOTO` > 'goto,
  22   `Unable to pop from priority queue')')
  23 define(`clearall', `Goto(: > goto && : > GOTO, `Unable to wipe files')')
  24 ', `
  25 include(`priority.m4')
  26 ')
  27 ifdef(`algo', `', `define(`algo', `astar')')
  28
  29 define(`input', translit(include(defn(`file')), nl, `0'))
  30 define(`x', 4)define(`y', 4)
  31 define(`do', `ifelse(`$3', 0, `define(`maxx', $1)define(`x', 4)define(`y',
  32   incr($2))', `define(`x', incr($1))define(`g$1_$2', $3)')')
  33
  34 ifdef(`__gnu__', `
  35   patsubst(defn(`input'), `.', `do(x, y, \&)')
  36 ',`
  37   define(`chew', `ifelse($1, 1, `do(x, y, $2)', `$0(eval($1/2), substr(
  38     `$2', 0, eval($1/2)))$0(eval($1-$1/2), substr(`$2', eval($1/2)))')')
  39   chew(len(defn(`input')), defn(`input'))
  40 ')
  41
  42 define(`p', `ifdef(`g$1_$2', `addwork($1, $2, `$3', $4+g$1_$2, `$5')')')
  43 define(`e', `p(incr($1), $2, `$0$5', $3, `$4$0')')define(`E', defn(`e'))
  44 define(`s', `p($1, incr($2), `$0$5', $3, `$4$0')')define(`S', defn(`s'))
  45 define(`w', `p(decr($1), $2, `$0$5', $3, `$4$0')')define(`W', defn(`w'))
  46 define(`n', `p($1, decr($2), `$0$5', $3, `$4$0')')define(`N', defn(`n'))
  47
  48 define(`ve1', `n($@, 1)e($@, 2)s($@, 1)')
  49 define(`ve2', `n($@, 1)e($@, 3)s($@, 1)')
  50 define(`ve3', `n($@, 1)s($@, 1)')
  51 define(`vs1', `e($@, 1)s($@, 2)w($@, 1)')
  52 define(`vs2', `e($@, 1)s($@, 3)w($@, 1)')
  53 define(`vs3', `e($@, 1)w($@, 1)')
  54 define(`vw1', `s($@, 1)w($@, 2)n($@, 1)')
  55 define(`vw2', `s($@, 1)w($@, 3)n($@, 1)')
  56 define(`vw3', `s($@, 1)n($@, 1)')
  57 define(`vn1', `w($@, 1)n($@, 2)e($@, 1)')
  58 define(`vn2', `w($@, 1)n($@, 3)e($@, 1)')
  59 define(`vn3', `w($@, 1)e($@, 1)')
  60
  61 define(`vE1', `ifdef(`g'eval($1+4)`_$2', `addwork(eval($1+4), $2, `E4',
  62   $3+defn(`g'eval($1+1)`_$2')+defn(`g'eval($1+2)`_$2')+defn(`g'eval($1+3
  63   )`_$2')+defn(`g'eval($1+4)`_$2'), `$4EEEE')')')
  64 define(`vE4', `vN1($@)E($@, 5)vS1($@)')
  65 define(`vE5', `vN1($@)E($@, 6)vS1($@)')
  66 define(`vE6', `vN1($@)E($@, 7)vS1($@)')
  67 define(`vE7', `vN1($@)E($@, 8)vS1($@)')
  68 define(`vE8', `vN1($@)E($@, 9)vS1($@)')
  69 define(`vE9', `vN1($@)E($@, 10)vS1($@)')
  70 define(`vE10', `vN1($@)vS1($@)')
  71 define(`vS1', `ifdef(`g$1_'eval($2+4), `addwork($1, eval($2+4), `S4',
  72   $3+defn(`g$1_'eval($2+1))+defn(`g$1_'eval($2+2))+defn(`g$1_'eval($2+3
  73   ))+defn(`g$1_'eval($2+4)), `$4SSSS')')')
  74 define(`vS4', `vE1($@)S($@, 5)vW1($@)')
  75 define(`vS5', `vE1($@)S($@, 6)vW1($@)')
  76 define(`vS6', `vE1($@)S($@, 7)vW1($@)')
  77 define(`vS7', `vE1($@)S($@, 8)vW1($@)')
  78 define(`vS8', `vE1($@)S($@, 9)vW1($@)')
  79 define(`vS9', `vE1($@)S($@, 10)vW1($@)')
  80 define(`vS10', `vE1($@)vW1($@)')
  81 define(`vW1', `ifdef(`g'eval($1-4)`_$2', `addwork(eval($1-4), $2, `W4',
  82   $3+defn(`g'eval($1-1)`_$2')+defn(`g'eval($1-2)`_$2')+defn(`g'eval($1-3
  83   )`_$2')+defn(`g'eval($1-4)`_$2'), `$4WWWW')')')
  84 define(`vW4', `vS1($@)W($@, 5)vN1($@)')
  85 define(`vW5', `vS1($@)W($@, 6)vN1($@)')
  86 define(`vW6', `vS1($@)W($@, 7)vN1($@)')
  87 define(`vW7', `vS1($@)W($@, 8)vN1($@)')
  88 define(`vW8', `vS1($@)W($@, 9)vN1($@)')
  89 define(`vW9', `vS1($@)W($@, 10)vN1($@)')
  90 define(`vW10', `vS1($@)vN1($@)')
  91 define(`vN1', `ifdef(`g$1_'eval($2-4), `addwork($1, eval($2-4), `N4',
  92   $3+defn(`g$1_'eval($2-1))+defn(`g$1_'eval($2-2))+defn(`g$1_'eval($2-3
  93   ))+defn(`g$1_'eval($2-4)), `$4NNNN')')')
  94 define(`vN4', `vW1($@)N($@, 5)vE1($@)')
  95 define(`vN5', `vW1($@)N($@, 6)vE1($@)')
  96 define(`vN6', `vW1($@)N($@, 7)vE1($@)')
  97 define(`vN7', `vW1($@)N($@, 8)vE1($@)')
  98 define(`vN8', `vW1($@)N($@, 9)vE1($@)')
  99 define(`vN9', `vW1($@)N($@, 10)vE1($@)')
 100 define(`vN10', `vW1($@)vE1($@)')
 101
 102 define(`dist', `eval('maxx`-$1+'y`-$2-2+$3)')
 103 define(`addwork', `ifdef(`p$1_$2$3', `', `define(`p$1_$2$3')insert(dist($1,
 104   $2, $4), $@)')')
 105 define(`_round', `ifelse(`$2.$3', 'decr(maxx).decr(y)`, `eval($5)clearall()',
 106   `v$4($2, $3, `$5', `$6')round()')')
 107 define(`round', `_$0(pop())')
 108
 109 define(`progress', 0)
 110 define(`rename', `define(`$2', defn(`$1'))popdef(`$1')')
 111 define(`show0', `output(1, `...$1')rename(`show$1', `show'eval($1+10000))')
 112 define(`show', `ifdef(`$0$1', `$0$1($1)')define(`progress', incr($1))')
 113 ifelse(eval(verbose >1), 1, `define(`round', `show(progress)'defn(`round'))')
 114
 115 e(4, 4, 0, `', 1)s(4, 4, 0, `', 1)
 116 define(`part1', round())
 117
 118 vE1(4, 4, 0)vS1(4, 4, 0)
 119 define(`part2', round())
 120
 121 divert`'part1
 122 part2