2017/day15.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dmax=N] [-Dseeda=X -Dseedb=Y] [-Dfile=day15.input] day15.m4
   3 # Optionally use -Donly=[12] to skip a part
   4 # Optionally use -Dverbose=1 to see some progress
   5
   6 include(`common.m4')ifelse(common(15), `ok', `',
   7 `errprint(`Missing common initialization
   8 ')m4exit(1)')
   9
  10 ifdef(`max', `', `define(`max', 40000000)')
  11 define(`Generator', `(')define(`with', `)')
  12 define(`parse', `define(`seeda', $2)define(`seedb', $4)')
  13 ifdef(`seeda', `', `parse(translit(include(defn(`file')), ` 'nl, `,,'))')
  14
  15 # Montgomery multiplies: R=0x80000000, N=0x7fffffff, N' = 1,
  16 # R^2 mod N = 1
  17 # aR modN * bR modN = redc(a * b)
  18 # aR modN = redc(a * R^2 modN) = redc(a * 1)
  19 # redc(T) = (T + (T modR * N' * N))/R - (0 or 1 * N)
  20 # if m = T&((1<<31)-1)=T%R, redc(T) = (T + (m<<31)-m)/R%N
  21 # = (T/R*R + T%R + T%R*R - T%R)/R%N = (T/R+T%R)%N
  22 # Note that for n < N, redc(n) = n
  23 define(`E', defn(`eval'))
  24 define(`R', `R1(E(`($1>>16)*$2'),E(`($1&0xffff)*$2'))')
  25 define(`R1', `R2($@,E(`(($1&0x7fff)<<16)+($2&0x7fffffff)'))')
  26 define(`R2', `R3(E(`($1>>15)+($2<0)+($3<0)+($3&0x7fffffff)'))')
  27 define(`R3', `E(`($1&0x7fffffff)+($1<0)')')
  28
  29 define(`part1', 0)define(`part2', 0)
  30 define(`rename', `ifdef(`$2', `', `define(`$2', defn(`$1'))popdef(`$1')')')
  31 define(`stat', `output(1, `...$1')rename(`$0', `do'eval(`$1+100000'))_do($@)')
  32 define(`do', `ifdef(`$0$1',`$0$1',`_$0')(`$1',A(`$2'),B(`$3'))')
  33 define(`_do', `ifelse(E(`($2^$3)&0xffff'),0,`C`'')do(incr(`$1'),`$2',`$3')')
  34
  35 ifelse(defn(`only'), 2, `', `
  36 define(`A', `R(`$1',`16807')')
  37 define(`B', `R(`$1',`48271')')
  38 define(`C', `define(`part1', incr(part1))')
  39 define(`do'max, `pushdef(`_do')')
  40 define(`do0', defn(`stat'))
  41 do(0, seeda, seedb)
  42 popdef(`_do')
  43 ')
  44
  45 ifelse(defn(`only'), 1, `', `
  46 define(`A', `a(R(`$1',`16807'))')
  47 define(`a', `ifelse(eval(`$1&3'),0,`$1',`A(`$1')')')
  48 define(`B', `b(R(`$1',`48271'))')
  49 define(`b', `ifelse(eval(`$1&7'),0,`$1',`B(`$1')')')
  50 define(`C', `define(`part2', incr(part2))')
  51 popdef(`do'max)
  52 define(`do'eval(max/8), `pushdef(`_do')')
  53 define(`do0', defn(`stat'))
  54 do(0, seeda, seedb)
  55 ')
  56
  57 divert`'part1
  58 part2