2022/day11.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dfile=day11.input] day11.m4
   3 # Optionally use -Dverbose=1 to see some progress
   4
   5 include(`common.m4')ifelse(common(11), `ok', `',
   6 `errprint(`Missing common initialization
   7 ')m4exit(1)')
   8
   9 # Compress input into a more usable form.  From the example:
  10 # Monkey 0:
  11 #   Starting items: 79, 98
  12 #   Operation: new = old * 19
  13 #   Test: divisible by 23
  14 #     If true: throw to monkey 2
  15 #     If false: throw to monkey 3
  16 # becomes 0,79.98,$1*19,1%$%23,2,$3,
  17 define(`input', translit((include(defn(`file'))), `ldb,'nl` :='alpha`'ALPHA,
  18   `$1%.,'))
  19 define(`_parse', `pushdef(`l$1', $2)pushdef(`L$1', `$2,$2')')
  20 define(`parse', `ifelse(`$1', `', `', `define(`last', $1)define(`c$1',
  21   0)_foreach(`_$0($1,', `)', translit(`.$2', `.', `,'))define(`a$1',
  22   `eval(($3)$'`2)')define(`div$1', substr(`$4', 4))define(`t$1',
  23   `ifelse(eval($'eval(`($1&1)+1')substr(`$4', 3)`), 0, $5, 'substr($6,
  24   1)`)')$0(shift(shift(shift(shift(shift(shift(shift($@))))))))')')
  25 first(`parse'defn(`input'))
  26
  27 # Part 1 is nonlinear (the truncating division by 3), but also small enough
  28 # that 20 iterations fits in 32-bit math without special effort
  29 define(`throw', `define(`c$1', incr(c$1))pushdef(`l't$1($2, $2), $2)turn($1)')
  30 define(`turn', `ifdef(`l$1', `throw($1, a$1(l$1,
  31   `/3'popdef(`l$1')))')')
  32 define(`round1000', `output(1, ...$1)define(`round'eval($1+1000),
  33   defn(`$0'))popdef(`$0')')
  34 define(`round', `ifdef(`$0$1', `$0$1($1)')'forloop(0, last,
  35   ``turn('', ``)''))
  36 forloop_arg(1, 20, `round')
  37
  38 define(`prod', `eval(`$1*$2')')
  39 define(`max2', `ifelse($3, `', `$1, $2', `$0(ifelse(eval($3 > $1), 1,
  40   `$3, $1', eval($3 > $2), 1, `$1, $3', `$1, $2'), shift(shift(shift($@))))')')
  41 define(`part1', prod(max2(0, 0forloop(0, last, `,defn(`c'', `)'))))
  42
  43 # Part 2 won't fit in signed 32-bit math directly. But since all 8 monkeys
  44 # only care about distinct prime divisors, we can instead track numbers
  45 # relative to lcm(divisors). Even that won't fit in 32-bit math, but if we
  46 # split even and odd index divisors, the worst we can get is a modulus of
  47 # 11*13*17*19 (half of the first 8 primes), which fortunately squares within
  48 # 31 bits. The sample input uses 4 primes 13*17*19*23 instead of first 8.
  49 define(`f0', 1)define(`f1', 1)
  50 define(`_prep', `define(`f$2', eval(f$2*div$1))')
  51 define(`prep', `_$0($1, eval($1&1))define(`c$1', 0)')
  52 forloop_arg(0, last, `prep')
  53
  54 define(`throw', `define(`c$1', incr(c$1))pushdef(`L't$1($2, $3),
  55   `$2,$3')turn($1)')
  56 define(`_turn', `throw($1, a$1($2, %'f0`), a$1($3, %'f1`))')
  57 define(`turn', `ifdef(`L$1', `_$0($1, L$1`'popdef(`L$1'))')')
  58 forloop_arg(1, 10000, `round')
  59
  60 include(`math64.m4')
  61 define(`prod', `mul64(`$1', `$2')')
  62 define(`part2', prod(max2(0, 0forloop(0, last, `,defn(`c'', `)'))))
  63
  64 divert`'part1
  65 part2