2021/day14.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dfile=day14.input] day14.m4
   3 # Optionally use -Dverbose=1 to see some progress
   4 # Optionally use -Dalgo=full|sparse to choose an algorithm
   5
   6 include(`common.m4')ifelse(common(14), `ok', `',
   7 `errprint(`Missing common initialization
   8 ')m4exit(1)')
   9
  10 ifdef(`algo', `', `define(`algo', `sparse')')
  11
  12 include(`math64.m4')
  13 define(`elts', `BCFHKNOPSV')
  14 define(`input', translit(include(defn(`file')), nl` -', `;'))
  15 define(`offset', index(defn(`input'), `;;'))
  16 define(`rules', substr(defn(`input'), eval(offset+2)))
  17 define(`bump', `ifdef(`n$1$2', `define(`n$1$2', add64(n$1$2, $3))', `define(
  18   `n$1$2', $3)pushdef(`n$1', `$2')')')
  19 define(`init', `ifelse(len(`$1'), 1, `bump(0, `$1_', 1)define(`r$1_',
  20   `bump($'`1, `$1_', 1)')define(`last', `$1')', `bump(0, substr(`$1', 0, 2),
  21   1)$0(substr(`$1', 1))')')
  22 init(substr(defn(`input'), 0, offset))
  23 define(`rule', `define(`r$1$2',
  24   `bump($'`1, `$1$3', $'`2)bump($'`1, `$3$2', $'`2)')')
  25 define(`visit', `translit(`rule(`1', `2', `3')', `12>3', `$1')')
  26 ifdef(`__gnu__', `
  27   patsubst(defn(`rules'), `\([^;]*\);', `visit(`\1')')
  28 ', `
  29   define(`_chew', `visit(substr(`$1', 0, index(`$1', `;')))define(
  30     `tail', substr(`$1', incr(index(`$1', `;'))))ifelse(index(defn(`tail'),
  31     `;'), -1, `', `$0(defn(`tail'))')')
  32   define(`chew', `ifelse(eval($1 < 10), 1, `_$0(`$2')', `$0(eval($1/2),
  33     substr(`$2', 0, eval($1/2)))$0(eval(len(defn(`tail')) + $1 - $1/2),
  34     defn(`tail')substr(`$2', eval($1/2)))')')
  35   chew(len(defn(`rules')), defn(`rules'))
  36 ')
  37
  38 ifelse(algo, `full', `
  39 output(1, `Using full matrix multiply, O(log n)')
  40 define(`_prep', `define(`m1_$1_$2', 0)')
  41 define(`prep', `forloop(0, 99, `_$0($1,', `)')')
  42 forloop_arg(0, 99, `prep')
  43 define(`map', `eval(index(defn(`elts'), substr(`$1', 0, 1)) * len(defn(`elts'))
  44   + index(defn(`elts'), substr(`$1', 1)))')
  45 define(`bump', `define(`m1_$1_'map(`$2'), 1)')
  46 define(`_prep_', `ifdef(`r$1', `r$1($2)')')
  47 define(`_prep', `$0_(substr(defn(`elts'), $1, 1)`'substr(defn(`elts'), $2, 1),
  48   eval($1*len(defn(`elts'))+$2))')
  49 define(`prep', `forloop(0, decr(len(defn(`elts'))), `_$0($1,', `)')')
  50 forloop_arg(0, decr(len(defn(`elts'))), `prep')
  51
  52 define(`_dot', `, mul64(m$1_$3_$5, m$2_$5_$4)')
  53 define(`dot', `define(`m$3_$4_$5', add(0forloop(0, 99, `_$0($1, $2, $4, $5, ',
  54   `)')))')
  55 define(`_mult', `forloop(0, 99, `dot($1, $2, $3, $4, ', `)')')
  56 define(`mult', `output(1, $3)forloop(0, 99, `_$0($1, $2, $3, ', `)')')
  57 mult(1, 1, 2)
  58 mult(2, 2, 4)
  59 mult(1, 4, 5)
  60 mult(5, 5, 10)
  61 define(`bump', `define(`c$1', add64(c$1, $2))')
  62 define(`_comp', `ifelse(`$1', 0, `', `ifelse(min, 0, `define(`min', $1)',
  63   lt64($1, min), 1, `define(`min', $1)')ifelse(lt64(max, $1), 1,
  64   `define(`max', $1)')')')
  65 define(`comp', `_$0(defn(`c'substr(defn(`elts'), $1, 1)))')
  66 define(`prod', `bump(substr(defn(`elts'), eval($4/len(defn(`elts'))), 1),
  67   mul64($3, m$1_$2_$4))')
  68 define(`_tally', `ifelse(`$2', defn(`last')`_', `bump(defn(`last'), 1)',
  69   `forloop(0, 99, `prod($1, 'map(`$2')`, 'n0$2`, ', `)')')')
  70 define(`tally', `define(`min', 0)define(`max', 0)forloop(0, decr(len(defn(
  71   `elts'))), `define(`c'substr(defn(`elts'), ', `, 1), 0)')_stack_foreach(`n0',
  72   `_$0($1, ', `)', `t')forloop_arg(0, decr(len(defn(`elts'))),
  73   `comp')add64(max, -min)')
  74 define(`part1', tally(10))
  75 mult(10, 10, 20)
  76 mult(20, 20, 40)
  77 define(`part2', tally(40))
  78
  79 ', algo, `sparse', `
  80 output(1, `Using sparse matrix lookup, O(n)')
  81 define(`use', `r$1($3, n$2$1)popdef(`n$2$1')')
  82 define(`_round', `ifdef(`n$1', `use(defn(`n$1'), $1, $2)popdef(`n$1')$0($@)')')
  83 define(`round', `_$0(decr($1), $1)')
  84 define(`_comp', `ifelse(`$1', `', `', `ifdef(`min', `ifelse(lt64($1, min), 1,
  85   `define(`min', $1)')ifelse(lt64(max, $1), 1, `define(`max', $1)')',
  86   `define(`min', $1)define(`max', $1)')')')
  87 define(`comp', `_$0(defn(`c'substr(defn(`elts'), $1, 1)))')
  88 define(`collect', `define(`c$1', ifdef(`c$1', `add64(c$1, $2)', $2))')
  89 define(`_tally', `ifdef(`n$2$1', `collect(substr(`$1', 0, 1), n$2$1)')')
  90 define(`tally', `popdef(`min')popdef(`max')forloop(0, decr(len(defn(`elts'))),
  91   `popdef(`c'substr(defn(`elts'), ', `, 1))')_stack_foreach(`n$1', `_$0(',
  92   `, $1)', `t')forloop_arg(0, decr(len(defn(`elts'))), `comp')')
  93 forloop_arg(1, 10, `round')
  94 tally(10)define(`part1', eval(max-min))
  95 forloop_arg(11, 40, `round')
  96 tally(40)define(`part2', add64(max, -min))
  97
  98 ', `errprintn(`unrecognized algorithm 'algo)m4exit(1)')
  99
 100 divert`'part1
 101 part2