2021/day6.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dfile=day6.input] day6.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(6), `ok', `',
   7 `errprint(`Missing common initialization
   8 ')m4exit(1)')
   9
  10 ifdef(`algo', `', `define(`algo', `sparse')')
  11
  12 include(`math64.m4')
  13 forloop(0, 8, `define(`l'', `, 0)')
  14 define(`bump', `define(`l$1', incr(l$1))')
  15 foreach(`bump', translit((include(defn(`file'))), nl`()'))
  16
  17 ifelse(algo, `full', `
  18 output(1, `Using full matrix multiply, O(log n)')
  19 define(`_prep', `define(`m1_$1_$2', 0)')
  20 define(`prep', `forloop(0, 8, `_$0($1,', `)')')
  21 forloop_arg(0, 8, `prep')
  22 define(`prep', `define(`m1_$1', 1)')
  23 foreach(`prep', `0_6', `0_8', `1_0', `2_1', `3_2', `4_3', `5_4', `6_5',
  24   `7_6', `8_7')
  25
  26 define(`_dot', `, mul64(m$1_$3_$5, m$2_$5_$4)')
  27 define(`dot', `define(`m$3_$4_$5', add(0forloop(0, 8, `_$0($1, $2, $4, $5, ',
  28   `)')))')
  29 define(`_mult', `forloop(0, 8, `dot($1, $2, $3, $4, ', `)')')
  30 define(`mult', `output(1, $3)forloop(0, 8, `_$0($1, $2, $3, ', `)')')
  31 mult(1, 1, 2)
  32 mult(2, 2, 4)
  33 mult(1, 4, 5)
  34 mult(5, 5, 10)
  35 mult(10, 10, 20)
  36 mult(20, 20, 40)
  37 mult(40, 40, 80)
  38 define(`_prod', `, m$1_$2_$3')
  39 define(`prod', `, mul64(l$2, add(0forloop(0, 8, `_$0($1, $2, ', `)')))')
  40 define(`part1', add(0forloop(0, 8, `prod(80, ', `)')))
  41 define(`scale', `mult(eval(1<<$1), eval(1<<$1), eval(2<<$1))')
  42 forloop_arg(2, 7, `scale')
  43 define(`part2', add(0forloop(0, 8, `prod(256, ', `)')))
  44
  45 ', algo, `sparse', `
  46 output(1, `Using sparse matrix lookup, O(n)')
  47 define(`prep', `define(`c0_$1', l$1)')
  48 forloop_arg(0, 8, `prep')
  49 define(`iter', `_$0(decr($1), $1)')
  50 define(`_iter', `forloop(1, 8, `bump(', `, $1, $2)')define(`c$2_8',
  51   c$1_0)define(`c$2_6', add64(c$2_6, c$1_0))popdef(`c$1_0')')
  52 define(`bump', `define(`c$3_'decr($1), c$2_$1)popdef(`c$2_$1')')
  53 define(`_tally', `,c$1_$2')
  54 define(`tally', `add(0forloop(0, 8, `_$0($1, ', `)'))')
  55 forloop_arg(1, 80, `iter')
  56 define(`part1', tally(80))
  57 forloop_arg(81, 256, `iter')
  58 define(`part2', tally(256))
  59
  60 ', `errprintn(`unrecognized algorithm 'algo)m4exit(1)')
  61
  62 divert`'part1
  63 part2