2020/day25.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dfile=day25.input] day25.m4
   3
   4 include(`common.m4')ifelse(common(25), `ok', `',
   5 `errprint(`Missing common initialization
   6 ')m4exit(1)')
   7
   8 # Using optimizations from reddit:
   9 # https://www.reddit.com/r/adventofcode/comments/kkq6r3/2020_optimized_solutions_in_c_291_ms_total/gh730cw
  10 # https://github.com/Voltara/advent2020-fast/blob/main/src/day25.cpp
  11 # Combines baby-step/giant-step, Pohlig-Hellman, and Chinese Remainder
  12 # 7^k = input (mod 20201227) =>
  13 # (7^m)^a*7^b = input (mod 20201227)
  14 # 20201226 = 2 * 3 * 29 * 116099
  15 define(`M', 20201227)define(`M1', decr(M))
  16 define(`bits', `_$0(eval($1, 2))')
  17 define(`_bits', ifdef(`__gnu__', ``shift(patsubst($1, ., `, \&'))'',
  18   ``ifelse(len($1), 1, `$1', `substr($1, 0, 1),$0(substr($1, 1))')''))
  19 define(`modmul', `define(`d', 0)define(`b', $2)pushdef(`m', $3)foreach(`_$0',
  20   bits($1))popdef(`m')d`'')
  21 define(`_modmul', `define(`d', eval((d * 2 + $1 * b) % m))')
  22 define(`modpowM', `define(`r', 1)define(`a', $1)foreach(`_$0', bits($2))r`'')
  23 define(`_modpowM', `define(`r', ifelse($1, 1, `modmul(modmul(r, r, M), a, M)',
  24   `modmul(r, r, M)'))')
  25
  26 # Compute the lookup table for baby-step/giant-step
  27 define(`br', 1)
  28 define(`setup', `define(`D'br, $1)define(`br', modmul(br, 19372176, M))')
  29 forloop_arg(0, 340, `setup')
  30 define(`dlog116099', `_$0(0, modpowM($1, 174))')
  31 define(`_dlog116099', `ifdef(`D$2', `eval($1 * 341 + D$2)', `$0(incr($1),
  32   modmul($2, 16585664, M))')')
  33 # Precomputed lookups
  34 define(`idx', 0)
  35 define(`setup', `define(`dlog29_$1', idx)define(`idx', incr(idx))')
  36 foreach(`setup', 1, 176, 100, 0, 140, 48, 125, 117,
  37   76, 190, 244, 161, 206, 177, 24, 128,
  38   158, 59, 20, 232, 250, 195, 106, 105,
  39   220, 21, 102, 28, 26)
  40 define(`dlog29', `defn(`$0_'eval(modpowM($1, 696594) % 255))')
  41 define(`dlog3', `eval(modpowM($1, 6733742) >> 5 & 3)')
  42 define(`dlog2', `eval(modpowM($1, 10100613) != 1)')
  43 # CRT over factors of M1, with partial products precomputed
  44 define(`dlog', `eval((modmul(18227544, dlog116099($1), M1) +
  45   modmul(18808038, dlog29($1), M1) +
  46   modmul(13467484, dlog3($1), M1) +
  47   modmul(10100613, dlog2($1), M1)) % M1)')
  48
  49 define(`prep', `define(`C', $1)define(`D', $2)')
  50 prep(translit(include(defn(`file')), nl, `,'))
  51 define(`part1', modpowM(C, dlog(D)))
  52
  53 divert`'part1
  54 no part2