2018/day19.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dfile=day19.input] day19.m4
   3
   4 include(`common.m4')ifelse(common(19), `ok', `',
   5 `errprint(`Missing common initialization
   6 ')m4exit(1)')
   7
   8 define(`input', translit(include(defn(`file')), nl`#', `;'))
   9 define(`ip', `r'substr(defn(`input'), 3, 1))
  10 define(`list', substr(defn(`input'), 5))
  11 define(`cnt', 0)
  12 define(`visit', `_$0(cnt, translit(`$1', ` ', `,'))')
  13 define(`_visit', `define(`i$1', `$2')define(`a$1', `$3,$4,$5')define(
  14   `cnt', incr($1))')
  15 ifdef(`__gnu__', `
  16   patsubst(defn(`list'), `\([^;]*\);', `visit(`\1')')
  17 ', `
  18   define(`_chew', `visit(substr(`$1', 0, index(`$1', `;')))define(`tail',
  19     substr(`$1', incr(index(`$1', `;'))))ifelse(index(
  20     defn(`tail'), `;'), -1, `', `$0(defn(`tail'))')')
  21   define(`chew', `ifelse(eval(`$1 < 20'), 1, `_$0(`$2')', `$0(eval(`$1/2'),
  22     substr(`$2', 0, eval(`$1/2')))$0(eval(len(defn(`tail'))` + $1 - $1/2'),
  23     defn(`tail')substr(`$2', eval(`$1/2')))')')
  24   chew(len(defn(`list')), defn(`list'))
  25 ')
  26 forloop(0, 5, `define(`r'', `, 0)')
  27 define(`addr_', `define(`r$3', eval(r$1+r$2))')
  28 define(`addi_', `define(`r$3', eval(r$1+$2))')
  29 define(`mulr_', `define(`r$3', eval(r$1*r$2))')
  30 define(`muli_', `define(`r$3', eval(r$1*$2))')
  31 define(`banr_', `define(`r$3', eval(r$1&r$2))')
  32 define(`bani_', `define(`r$3', eval(r$1&$2))')
  33 define(`borr_', `define(`r$3', eval(r$1|r$2))')
  34 define(`bori_', `define(`r$3', eval(r$1|$2))')
  35 define(`setr_', `define(`r$3', r$1)')
  36 define(`seti_', `define(`r$3', $1)')
  37 define(`gtir_', `define(`r$3', eval($1>r$2))')
  38 define(`gtri_', `define(`r$3', eval(r$1>$2))')
  39 define(`gtrr_', `define(`r$3', eval(r$1>r$2))')
  40 define(`eqir_', `define(`r$3', eval($1==r$2))')
  41 define(`eqri_', `define(`r$3', eval(r$1==$2))')
  42
  43 # Peephole optimization: instead of computing sum of factors with O(value^2)
  44 # pairs, compute it with O(sqrt(value)) effort.
  45 define(`n2', 3)define(`n3', 5)define(`n5', 7)
  46 define(`nextp', `ifdef(`n$1', `', `define(`n$1', _$0(incr(incr($1))))')n$1')
  47 define(`_nextp', `ifelse(eval($1 % 3 && $1 % 5), 0, `$0(incr(incr($1)))',
  48   `ifelse(nargs(factor($1)), 2, $1, `$0(incr(incr($1)))')')')
  49 define(nargs, `$#')
  50 define(`factor', `ifelse($1, 1, `', `ifelse(eval($1 & 1), 0,
  51   `,2$0(eval($1 >> 1))', `_$0($1, 3)')')')
  52 define(`_factor', `ifelse($1, 1, `', `ifelse(eval($2 * $2 > $1), 1, `,$1',
  53   `ifelse(eval($1 % $2), 0, `,$2$0(eval($1 / $2), $2)',
  54   `$0($1, nextp($2))')')')')
  55
  56 define(`part', `ifelse($1, $2, `incr($1)', `((($1 * $2) - 1) / ($2 - 1))')')
  57 define(`total', `_$0(1, $2, shift($@))')
  58 define(`_total', `ifelse(`$#', 3, `eval($1 * part($2, $3))',
  59   $3, $4, `$0($1, $2 * $3, shift(shift(shift($@))))',
  60   `$0(eval($1 * part($2, $3)), $4, shift(shift(shift($@))))')')
  61
  62 define(`eqrr_', `define(`r$3', eval(r$1==r$2))ifelse($1, $3, `hack(decr(ip),
  63   r$2)')')
  64 define(`hack', `ifelse(defn(`i$1'), `mulr', `_$0(a$1, $2, incr($2))')')
  65 define(`_hack', `define(`r0', total($4factor($4)))define(`r$1', $5)define(
  66   `r$2', $5)')
  67 define(`run', `_$0(ip)')
  68 define(`_run', `ifdef(`i$1', `i$1()_(a$1)define(defn(`ip'), incr(ip))$0(ip)')')
  69 define(`part1', run()r0)
  70 forloop(1, 5, `define(`r'', `, 0)')define(`r0', 1)
  71 define(`part2', run()r0)
  72
  73 divert`'part1
  74 part2