2018/day22.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dfile=day22.input] day22.m4
   3 # Optionally use -Dverbose=1 to see some progress
   4 # Optionally use -Dalgo=dijkstra|astar to choose search algorithm
   5 # Optionally use -Dpriority=1|2|3|4|5 to choose priority queue algorithms
   6
   7 include(`common.m4')ifelse(common(22), `ok', `',
   8 `errprint(`Missing common initialization
   9 ')m4exit(1)')
  10
  11 define(`parse', `define(`d', $2)define(`tx', $4)define(`ty', $5)')
  12 parse(translit((include(defn(`file'))), nl` ()', `,,'))
  13 define(`g', `ifdef(`g$1_$2', `', `_g($1, $2)')g$1_$2`'')
  14 define(`_g', `$0_($1, $2, ifelse($1$2, 00, 0, $1.$2, 'tx.ty`, 0, $2, 0,
  15   `eval($1*16807)', $1, 0, `eval($2*48271)', `n($1, $2, decr($1), decr($2))'))')
  16 define(`_g_', `define(`e$1_$2', eval(($3+'d`)%20183))define(`g$1_$2',
  17   eval(e$1_$2%3))')
  18 define(`n', `ifelse(g($3,$2)g($1,$4))eval(e$3_$2*e$1_$4)')
  19
  20 define(`tally', `forloop(0, 'tx`, `+g(', `, $1)')')
  21 define(`part1', eval(forloop_arg(0, ty, `tally')))
  22
  23 # Pending priorities fall in narrow range
  24 ifdef(`priority', `', `define(`priority', 2)')
  25 include(`priority.m4')
  26 ifdef(`algo', `', `define(`algo', `dijkstra')')
  27
  28 # rocky=neither=0, wet=torch=1, narrow=gear=2. addwork(x, y, equip, type, cost)
  29 define(`swap10', `2, 0')define(`swap20', `1, 0')
  30 define(`swap01', `2, 1')define(`swap21', `0, 1')
  31 define(`swap02', `1, 2')define(`swap12', `0, 2')
  32 define(`cnt', 0)
  33
  34 ifelse(algo, `dijkstra', `
  35 output(1, `Using Dijkstra search')
  36 define(`addwork', `ifelse(ifdef(`d$1_$2_$3', `eval($5 < d$1_$2_$3)', 1), 1,
  37   `define(`d$1_$2_$3', $5)insert($5, $1, $2, $3, $4)define(`cnt',
  38   incr(cnt))ifelse(eval(cnt%10000), 0, `output(1, ...cnt:`$*')')')')
  39 define(`loop', `ifelse(`$2.$3.$4', `$6', $1, `neighbors($2, $3, $4, $5,
  40   incr(d$2_$3_$4))loop(pop, `$6')')')
  41
  42 ', algo, `astar', `
  43 output(1, `Using A* search')
  44 define(`diff', `ifelse(eval($1 < $2), 1, $2 - $1, $1 - $2)')
  45 define(`heur', `diff('tx`, $1) + diff('ty`, $2) + ($3 != 1) * 7')
  46 define(`addwork', `ifelse(ifdef(`d$1_$2_$3', `eval($5 < d$1_$2_$3)', 1), 1,
  47   `define(`d$1_$2_$3', $5)_$0(eval($5 + heur($1, $2, $3)), $1, $2, $3, $4)')')
  48 define(`_addwork', `define(`f$2_$3_$4', $1)insert($@)define(`cnt',
  49   incr(cnt))ifelse(eval(cnt%10000), 0, `output(1, ...cnt:`$*')')')
  50 define(`loop', `ifelse(`$2.$3.$4', `$6', $1, eval($1 > f$2_$3_$4), 1, `loop(
  51   pop, `$6')', `neighbors($2, $3, $4, $5, incr(d$2_$3_$4))loop(pop, `$6')')')
  52
  53 ', `output(0, `unknown search algorithm')m4exit(1)')
  54
  55 define(`distance', `addwork(0, 0, 1, 0, 0)loop(pop, 'tx.ty.1`)clearall()')
  56 define(`check', `ifelse($1, -1, `', $1, 'eval(tx+30)`, `', $2, -1, `',
  57   `_$0($1, $2, $3, g($1, $2), $4)')')
  58 define(`_check', `ifelse($3, $4, `', `addwork($@)')')
  59 define(`neighbors', `addwork($1, $2, swap$3$4, eval($5+6))check(decr($1), $2,
  60   $3, $5)check($1, decr($2), $3, $5)check(incr($1), $2, $3, $5)check($1,
  61   incr($2), $3, $5)')
  62 define(`part2', distance())
  63
  64 divert`'part1
  65 part2