2020/day13.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dfile=day13.input] day13.m4
   3
   4 include(`common.m4')ifelse(common(13), `ok', `',
   5 `errprint(`Missing common initialization
   6 ')m4exit(1)')
   7
   8 include(`math64.m4')
   9 define(`list', quote(translit((include(file)), nl`()', `,')`x'))
  10 define(`time', first(list))
  11 define(`best', decr(time))
  12 define(`pos', 0)
  13 define(`check', `ifelse(`$1', `x', `', `_$0($1)')define(`pos', incr(pos))')
  14 define(`_check', `ifelse(eval(($1 - time % $1) < (best - time % best)), 1,
  15   `define(`best', $1)')pushdef(`need', `$1,'eval((10 * $1 - pos) % $1))')
  16 foreach(`check', shift(list))
  17 define(`part1', eval((best - time % best) * best))
  18
  19 define(`bits', `_$0(eval($1, 2))')
  20 define(`_bits', ifdef(`__gnu__', ``shift(patsubst($1, ., `, \&'))'',
  21   ``ifelse(len($1), 1, `$1', `substr($1, 0, 1),$0(substr($1, 1))')''))
  22 define(`bits64', `ifelse(eval(len($1) < 10), 1, `bits($1)', `_$0(mul64($1,
  23   5)), eval(substr($1, decr(len($1))) & 1)')')
  24 define(`_bits64', `bits64(substr($1, 0, decr(len($1))))')
  25 no64()pushdef(`bits64', `bits($1)')
  26 define(`modmul', `define(`d', 0)define(`a', ifelse(index($1, -), 0, `add64($1,
  27   $3)',  $1))define(`b', ifelse(index($2, -), 0, `add64($2, $3)',
  28   $2))pushdef(`m', $3)foreach(`_$0', bits64(a))popdef(`m')d`'')
  29 define(`_modmul', `define(`d', add64(d, d))ifelse(lt64(m, d), 1, `define(`d',
  30   add64(d, -m))')ifelse($1, 1, `define(`d', add64(d, b))')ifelse(lt64(m, d), 1,
  31   `define(`d', add64(d, -m))')')
  32 define(`pair', `define(`$1', $3)define(`$2', $4)')
  33 define(`ext', `pair(`r_', `r', $1, $2)pair(`m', `s', 1, 0)pair(`n', `T', 0,
  34   1)_$0()')
  35 define(`_ext', `ifelse(r, 0, `', `define(`q', eval(r_ / r))pair(`r_', `r', r,
  36   eval(r_ - q * r))pair(`m', `s', s, eval(m - q * s))pair(`n', `T', T,
  37   eval(n - q * T))$0()')')
  38 define(`p1', 1)define(`p2', 1)define(`r1', 0)define(`r2', 0)
  39 define(`do', `crt($1, eval(1 + (p2 < p1)))')
  40 define(`crt', `_$0($1, $2, `p$3', `r$3', eval($1 * p$3))')
  41 define(`_crt', `ifelse($3, 1, `pair(`$3', `$4', $1, $2)', `ext($3,
  42   $1)pair(`$3', `$4', $5, eval((modmul(modmul($4, n, $5), $1, $5) +
  43   modmul(modmul($2, m, $5), $3, $5)) % $5))')')
  44 stack_foreach(`need', `do')
  45 popdef(`add64')popdef(`mul64')popdef(`lt64')popdef(`bits64')
  46 ext(p1, p2)define(`p', mul64(p1, p2))
  47 define(`part2', add64(modmul(modmul(r1, n, p), p2, p), modmul(modmul(r2, m, p),
  48   p1, p)))
  49 ifelse(lt64(p, part2), 1, `define(`part2', add64(part2, -p))')
  50
  51 divert`'part1
  52 part2