2022/day24.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dfile=day24.input] day24.m4
   3 # Optionally use -Dverbose=1 to see some progress
   4 # Optionally use -Dalgo=bfs|astar to choose search algorithm
   5 # Optionally use -Dpriority=0|1|2|3|4|5 to choose priority queue algorithm
   6
   7 include(`common.m4')ifelse(common(24, 1000003), `ok', `',
   8 `errprint(`Missing common initialization
   9 ')m4exit(1)')
  10
  11 include(`priority.m4')
  12 ifdef(`algo', `', `define(`algo', `astar')')
  13
  14 define(`input', translit(include(defn(`file')), nl`#', `;@'))
  15 define(`x', 0)define(`y', 0)
  16 define(`do', `ifelse(`$3', `;', `define(`y', incr($2))define(`maxx',
  17   decr($1))define(`x', 0)', `ifelse(`$3', `>', `define(`r$1_$2', `.')', `$3',
  18   `<', `define(`R$1_$2', `.')', `$3', `v', `define(`c$1_$2', `.')', `$3', `^',
  19   `define(`C$1_$2', `.')')define(`x', incr($1))')')
  20
  21 ifdef(`__gnu__', `
  22   patsubst(defn(`input'), `.', `do(x, y, `\&')')
  23 ',`
  24   define(`chew', `ifelse($1, 1, `do(x, y, `$2')', `$0(eval($1/2), substr(
  25     `$2', 0, eval($1/2)))$0(eval($1-$1/2), substr(`$2', eval($1/2)))')')
  26   chew(len(defn(`input')), defn(`input'))
  27 ')
  28 define(`maxy', decr(y))define(`x', decr(maxx))define(`y', decr(maxy))
  29
  30 #              123456      123456
  31 # time 0: rx_1 >>.... Rx_1 ...<.< look up 1,1 at x=1 x=1; 2,1 at x=2 x=2
  32 # time 1: rx_1 .>>... Rx_1 ..<.<. look up 1,1 at x=6 x=2; 2,1 at x=1 x=3
  33 # time 2: rx_1 ..>>.. Rx_1 .<.<.. look up 1,1 at x=5 x=3; 2,1 at x=6 x=4
  34 define(`r', `defn(`r'eval(('x`-$3%'x`-1+$1)%'x`+1)`_$2')')
  35 define(`R', `defn(`R'eval(($3+'x`-1+$1)%'x`+1)`_$2')')
  36 define(`c', `defn(`c$1_'eval(('y`-$3%'y`-1+$2)%'y`+1))')
  37 define(`C', `defn(`C$1_'eval(($3+'y`-1+$2)%'y`+1))')
  38 define(`b', `ifdef(`b$1_$2_$3', `', `define(`b$1_$2_$3',
  39   r($@)R($@)c($@)C($@))')b$1_$2_$3')
  40 define(`p', `ifelse(`$1.$2', `1.0',
  41   `addwork($@)', `$1.$2', 'x.maxy`, `addwork($@)', $1, 0, `', $1, 'maxx`, `',
  42   $2, -1, `', $2, 0, `', $2, 'maxy`, `', $2, 'incr(maxy)`, `', `ifelse(b($@),
  43   `', `addwork($@)')')')
  44 define(`visit', `p($1, $2, $3)p(incr($1), $2, $3)p(decr($1), $2, $3)p($1,
  45   incr($2), $3)p($1, decr($2), $3)')
  46
  47 ifelse(defn(`algo'), `bfs', `
  48 output(1, `Using bfs search')
  49 define(`addwork', `ifdef(`p$1_$2_$3', `', `pushdef(`work$3',
  50   `$*')define(`p$1_$2_$3')')')
  51 define(`_round', `ifelse(`$1,$2', defn(`goal'), `clear($3)clear(incr(
  52   $3))pushdef(`round', `$3popdef(`round')')', `popdef(`p$1_$2_$3')visit($1,
  53   $2, $4)')')
  54 define(`round', `ifdef(`work$1', `_$0(work$1, $2)popdef(`work$1')$0($@)',
  55   `ifelse(eval($1%50), 0, `output(1, `...time $1')')$0($2, incr($2))')')
  56 define(`_clear', `popdef(`p$1_$2_$3')')
  57 define(`clear', `ifdef(`work$1', `_$0(work$1)popdef(`work$1')$0($@)')')
  58
  59 ', defn(`algo'), `astar', `
  60 output(1, `Using A* search')
  61 define(`abs', `($1<$2)*($2-$1)+($1>$2)*($1-$2)')
  62 define(`dist', `eval(abs($1, $3)+abs($2, $4)+$5)')
  63 define(`addwork', `ifdef(`p$1_$2_$3', `', `define(`p$1_$2_$3')insert(dist(goal,
  64   $1, $2, $3), $@)')')
  65 define(`_round', `ifelse(defn(`goal'), `$2,$3', `$4clearall()popdef(
  66   `p$2_$3_$4')', `visit($2, $3, incr($4))round()')')
  67 define(`round', `_$0(pop())')
  68
  69 ', `fatal(`unknown search algo')')
  70
  71 define(`progress', 0)
  72 define(`rename', `define(`$2', defn(`$1'))popdef(`$1')')
  73 define(`show0', `output(1, `...$1')rename(`show$1', `show'eval($1+20000))')
  74 define(`show', `ifdef(`$0$1', `$0$1($1)')define(`progress', incr($1))')
  75 ifelse(eval(verbose >1), 1, `define(`round', `show(progress)'defn(`round'))')
  76
  77 define(`find', `define(`goal', `$1,$2')addwork($3, $4, $5)round($5, incr($5))')
  78 define(`part1', find(x, maxy, 1, 0, 0))
  79 define(`back', find(1, 0, x, maxy, part1))
  80 define(`part2', find(x, maxy, 1, 0, back))
  81
  82 divert`'part1
  83 part2