2019/day16.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dfile=day16.input] day16.m4
   3 # Optionally use -Dlimit=N to perform fewer than 100 phases
   4 # Optionally use -Donly=[12] to skip a part, or -Donly=3 for bonus
   5 # Optionally use -Dverbose=[12] to see some progress
   6
   7 include(`common.m4')ifelse(common(16), `ok', `',
   8 `errprint(`Missing common initialization
   9 ')m4exit(1)')
  10
  11 define(`input', translit(include(defn(`file')), `
  12 '))
  13 ifdef(`limit', `ifelse(eval(limit & 1), 1, `errprint(`Limit must be even
  14 ')m4exit(1)')', `define(`limit', 100)')
  15
  16 define(`l', len(input))
  17 define(`l1', decr(l))
  18 define(`parse', `_$0($1, substr(input, $1, 1))')
  19 define(`_parse', `define(`d0_$1', $2)define(`d2_$1', $2)')
  20 forloop_arg(0, l1, `parse')
  21 define(`d0_'l, 0)
  22 define(`d1_'l, 0)
  23 define(`o', eval(-10000000 + 1forloop(0, 6, `defn(`d0_'', `)')))
  24 define(`prep', `define(`d2_'eval(l + $1), d2_$1)define(`p'$1, 0)')
  25 forloop_arg(0, 7, `prep')
  26 define(`prep', `define(`t'i`$1', eval((i + $1) % 10))')
  27 forloop_var(`i', 0, 9, `forloop_arg(0, 9, `prep')')
  28 define(`last', `substr($1, decr(len($1)), 1)')
  29
  30 ifelse(ifdef(`only', only, 1), 1, `
  31
  32 define(`m', `_m(eval(($1 + 1) / ($2 + 1) % 4), $1)')
  33 define(`_m', `m$1($2, 2)')
  34 define(`m0')
  35 define(`m1', `` +d$$2_$1'')
  36 define(`m2')
  37 define(`m3', `` -d$$2_$1'')
  38 define(`slow', `define(`set$1', `last(eval('forloop(0, l1,
  39   `m(', `, $1)')`))')')
  40 define(`_medium', ``eval((d$$1_'incr($3)` + d$$2_$3 + 20 - d$$2_'eval($3 * 2 +
  41   1)` - d$$2_'eval($3 * 2 + 2)`) % 10)'')
  42 define(`medium', `define(`set$1', _$0(1, 2, $1))')
  43 define(`_fast', ``defn(`t'd$$1_'incr($3)``'d$$2_$3)'')
  44 define(`fast', `define(`set$1', _$0(1, 2, $1))')
  45 forloop_arg(0, l / 3 - 1, `slow')
  46 forloop_arg(l / 3, l / 2 - 1, `medium')
  47 forloop_arg(l / 2, l1, `fast')
  48
  49 define(`set', `define(`d$1_$3', set$3($1, $2))')
  50 define(`phase', `output(2, eval($1 * 2))forloop_rev(l1, 0, `set(1, 0,',
  51   `)')forloop_rev(l1, 0, `set(0, 1,', `)')')
  52
  53 forloop_arg(1, limit / 2, `phase')
  54 define(`part1', forloop(0, 7, `defn(`d0_'', `)'))
  55 ')
  56
  57 ifelse(eval(o > l * 10000 - 8 || o < l * 5000), 1,
  58 `define(`part2', ``part2 is not practical for this input'')',
  59 ifdef(`only', only, 2), 2, `
  60
  61 dnl https://github.com/akalin/advent-of-code-2019-python3/blob/master/day16.py
  62 output(1, `starting part2...')
  63
  64 dnl precomputed binomial mod 5
  65 define(`b', `define(`binom'n`$1', ifelse(eval($1 > n), 1, 0, n, 0, 1, $1, 0, 1,
  66   `eval((defn(`binom'decr(n)$1) + defn(`binom'decr(n)decr($1))) % 5)'))')
  67 forloop_var(`n', 0, 4, `forloop_arg(0, 4, `b')')
  68 define(`binomMod5', `ifelse($2, 0, 1, eval($1 < 5 && $2 < 5), 1,
  69   `binom$1$2', `_$0(defn(`binom'eval($1 % 5)eval($2 % 5)),
  70   `$0(eval($1 / 5), eval($2 / 5))')')')
  71 define(`_binomMod5', `ifelse($1, 0, 0, `eval($1 * $2 % 5)')')
  72 define(`binomMod10', `eval((!(~$1 & $2) * 5 +
  73   binomMod5($1, $2) * 6) % 10)')
  74
  75 define(`c', `_$0(0, 7, eval(($1 + o) % l), binomMod10(eval($1 + limit - 1),
  76   decr(limit)))')
  77 define(`_c', `ifelse($4, 0, `', `define(`p$1', eval((p$1 + d2_$3 * $4)
  78   % 10))ifelse($1, $2, `', `$0(incr($1), $2, incr($3), $4)')')')
  79 forloop_arg(0, eval(l * 10000 - o - 9), `c')
  80 define(`c', `_$0(0, eval(7 - i), eval((l * 10000 + i - 8) % l),
  81   binomMod10(eval(l * 10000 - o + i - 8 + limit - 1), decr(limit)))')
  82 forloop_var(`i', 0, 7, `c')
  83 define(`part2', forloop(0, 7, `defn(`p'', `)'))
  84
  85 ')
  86 ifelse(ifdef(`only', only), 3, `
  87
  88 # Bonus: https://www.reddit.com/r/adventofcode/comments/ebb8w6/2019_day_16_part_three_a_fanfiction_by_askalski/
  89 output(1, `starting part3...')
  90 include(`math64.m4')
  91
  92 define(`limit', 287029238942)
  93 define(`limit1', add64(limit, -1))
  94 define(`o', eval(-10000000 + 1forloop(0, 6, `defn(`d0_'', `)')))
  95
  96 dnl precomputed binomial mod 5
  97 define(`b', `define(`binom'n`$1', ifelse(eval($1 > n), 1, 0, n, 0, 1, $1, 0, 1,
  98   `eval((defn(`binom'decr(n)$1) + defn(`binom'decr(n)decr($1))) % 5)'))')
  99 forloop_var(`n', 0, 4, `forloop_arg(0, 4, `b')')
 100 define(`small', `ifelse(len($1$2), 2, `eval($1 < $3 && $2 < $3)')')
 101 define(`mod2', `eval(last($1) & 1)')
 102 define(`mod5', `eval(last($1) % 5)')
 103 define(`div2', `ifelse(eval(len($1) < 10), 1, `eval($1 / 2)',
 104   `div10(mul64($1, 5))')')
 105 define(`div5', `ifelse(eval(len($1) < 10), 1, `eval($1 / 5)',
 106   `div10(add64($1, $1))')')
 107 define(`div10', `substr($1, 0, decr(len($1)))')
 108 define(`binomMod', `ifelse($2, 0, 1, small($1, $2, $3), 1,
 109   `binom$1$2', `_$0(defn(`binom'mod$3($1)mod$3($2)),
 110   `$0$3(div$3($1), div$3($2))', $3)')')
 111 define(`_binomMod', `ifelse($1, 0, 0, `mod$3(mul64($1, $2))')')
 112 define(`binomMod2', `ifelse(eval(len($1) < 10 && len($2) < 10), 1,
 113   `eval(!(~$1 & $2))', `binomMod($1, $2, 2)')')
 114 define(`binomMod5', `binomMod($1, $2, 5)')
 115 define(`binomMod10', `eval((binomMod2($1, $2) * 5 +
 116   binomMod5($1, $2) * 6) % 10)')
 117
 118 define(`c', `ifelse(eval($1 % 10000), 0, `output(2, $1)')_$0(0, 7,
 119   eval(($1 + o) % l), binomMod10(add64($1, limit1), limit1))')
 120 define(`_c', `ifelse($4, 0, `', `define(`p$1', eval((p$1 + d2_$3 * $4)
 121   % 10))ifelse($1, $2, `', `$0(incr($1), $2, incr($3), $4)')')')
 122 forloop_arg(0, eval(l * 10000 - o - 9), `c')
 123 define(`c', `_$0(0, eval(7 - i), eval((l * 10000 + i - 8) % l),
 124   binomMod10(add64(eval(l * 10000 - o + i - 8), limit1), limit1))')
 125 forloop_var(`i', 0, 7, `c')
 126 define(`part3', forloop(0, 7, `defn(`p'', `)'))
 127
 128 ')divert`'part1
 129 part2
 130 ifdef(`part3', `part3', `dnl')