2016/day14.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dmax=N] [-Dstart=NNN] [-Dprefix=XXX] [-Dfile=day14.input] day14.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(14), `ok', `',
   7 `errprint(`Missing common initialization
   8 ')m4exit(1)')
   9
  10 ifdef(`start', `', `define(`start', 0)')
  11 ifdef(`max', `', `define(`max', 64)')
  12 ifdef(`prefix', `', `define(`prefix', translit(include(defn(`file')), nl))')
  13
  14 # Index is [0-9]*.  Assume that prefix is [a-z]*.  Also assume prefix +
  15 # index < 56 bytes, thus only 1 md5 pass needed.
  16 define(`N', defn(`define'))define(`E', defn(`eval'))
  17 define(`L', ``($1<<$2|($1>>1&0x7fffffff)>>31-$2)'')
  18 define(`F', `N(`$1',E(`$2+'L(E($1`+($4^$2&($3^$4))+$5+$7'),`$6')))')
  19 define(`G', `N(`$1',E(`$2+'L(E($1`+($3^$4&($2^$3))+$5+$7'),`$6')))')
  20 define(`H', `N(`$1',E(`$2+'L(E($1`+($2^$3^$4)+$5+$7'),`$6')))')
  21 define(`I', `N(`$1',E(`$2+'L(E($1`+($3^($2|~$4))+$5+$7'),`$6')))')
  22 define(`set', `define(`V$1', eval($1 + $2))')
  23 forloop(0, 9, `set(', `, 48)')
  24 define(`set', `define(`V'eval(9 + $1, 36), eval($1 + $2))')
  25 forloop(1, 26, `set(', `, 96)')
  26 define(`S0', `N(`X$2',$1)')
  27 define(`S1', `N(`X$2',E(X$2|$1`<<8'))')
  28 define(`S2', `N(`X$2',E(X$2|$1`<<16'))')
  29 define(`S3', `N(`X$2',E(X$2|$1`<<24'))')
  30 forloop(0, 15, `define(`X'eval(', `,16), 0)')
  31 define(`_P', `ifelse(`$1',,`S$3(128,$2)',`S$3(`V'substr(`$1',0,1),$2,$3)$0(
  32   substr(`$1',1),ifelse($3,3,`incr($2),0',`$2,incr($3)'))')')
  33 define(`P', forloop(0, 8, ``N(`X''', ``,0)'')dnl
  34 `N(`Xe',E(len($1)`*8'))_$0(`$1',0,0)')
  35 define(`set', `define(`Q$1', `,'defn(`V'E(`$1>>4', 16))`,'defn(`V'E(`$1&15',
  36   16)))')
  37 forloop_arg(0, 255, `set')
  38 define(`Q', `defn(`Q'E(`$1&0xff'))defn(`Q'E(`$1>>8&0xff'))defn(`Q'E('dnl
  39 ``$1>>16&0xff'))defn(`Q'E(`$1>>24&0xff'))')
  40 define(`md5', `P(`$1')_$0(`1732584193',`-271733879',`-1732584194',`271733878')')
  41 define(`_md5', `N(`A',`$1')N(`B',`$2')N(`C',`$3')N(`D',`$4')'dnl
  42 `F(`A',B,C,D,X0,7,`0xd76aa478')'dnl
  43 `F(`D',A,B,C,X1,12,`0xe8c7b756')'dnl
  44 `F(`C',D,A,B,X2,17,`0x242070db')'dnl
  45 `F(`B',C,D,A,X3,22,`0xc1bdceee')'dnl
  46 `F(`A',B,C,D,X4,7,`0xf57c0faf')'dnl
  47 `F(`D',A,B,C,X5,12,`0x4787c62a')'dnl
  48 `F(`C',D,A,B,X6,17,`0xa8304613')'dnl
  49 `F(`B',C,D,A,X7,22,`0xfd469501')'dnl
  50 `F(`A',B,C,D,X8,7,`0x698098d8')'dnl
  51 `F(`D',A,B,C,X9,12,`0x8b44f7af')'dnl
  52 `F(`C',D,A,B,Xa,17,`0xffff5bb1')'dnl
  53 `F(`B',C,D,A,Xb,22,`0x895cd7be')'dnl
  54 `F(`A',B,C,D,Xc,7,`0x6b901122')'dnl
  55 `F(`D',A,B,C,Xd,12,`0xfd987193')'dnl
  56 `F(`C',D,A,B,Xe,17,`0xa679438e')'dnl
  57 `F(`B',C,D,A,Xf,22,`0x49b40821')'dnl
  58 `G(`A',B,C,D,X1,5,`0xf61e2562')'dnl
  59 `G(`D',A,B,C,X6,9,`0xc040b340')'dnl
  60 `G(`C',D,A,B,Xb,14,`0x265e5a51')'dnl
  61 `G(`B',C,D,A,X0,20,`0xe9b6c7aa')'dnl
  62 `G(`A',B,C,D,X5,5,`0xd62f105d')'dnl
  63 `G(`D',A,B,C,Xa,9,`0x02441453')'dnl
  64 `G(`C',D,A,B,Xf,14,`0xd8a1e681')'dnl
  65 `G(`B',C,D,A,X4,20,`0xe7d3fbc8')'dnl
  66 `G(`A',B,C,D,X9,5,`0x21e1cde6')'dnl
  67 `G(`D',A,B,C,Xe,9,`0xc33707d6')'dnl
  68 `G(`C',D,A,B,X3,14,`0xf4d50d87')'dnl
  69 `G(`B',C,D,A,X8,20,`0x455a14ed')'dnl
  70 `G(`A',B,C,D,Xd,5,`0xa9e3e905')'dnl
  71 `G(`D',A,B,C,X2,9,`0xfcefa3f8')'dnl
  72 `G(`C',D,A,B,X7,14,`0x676f02d9')'dnl
  73 `G(`B',C,D,A,Xc,20,`0x8d2a4c8a')'dnl
  74 `H(`A',B,C,D,X5,4,`0xfffa3942')'dnl
  75 `H(`D',A,B,C,X8,11,`0x8771f681')'dnl
  76 `H(`C',D,A,B,Xb,16,`0x6d9d6122')'dnl
  77 `H(`B',C,D,A,Xe,23,`0xfde5380c')'dnl
  78 `H(`A',B,C,D,X1,4,`0xa4beea44')'dnl
  79 `H(`D',A,B,C,X4,11,`0x4bdecfa9')'dnl
  80 `H(`C',D,A,B,X7,16,`0xf6bb4b60')'dnl
  81 `H(`B',C,D,A,Xa,23,`0xbebfbc70')'dnl
  82 `H(`A',B,C,D,Xd,4,`0x289b7ec6')'dnl
  83 `H(`D',A,B,C,X0,11,`0xeaa127fa')'dnl
  84 `H(`C',D,A,B,X3,16,`0xd4ef3085')'dnl
  85 `H(`B',C,D,A,X6,23,`0x04881d05')'dnl
  86 `H(`A',B,C,D,X9,4,`0xd9d4d039')'dnl
  87 `H(`D',A,B,C,Xc,11,`0xe6db99e5')'dnl
  88 `H(`C',D,A,B,Xf,16,`0x1fa27cf8')'dnl
  89 `H(`B',C,D,A,X2,23,`0xc4ac5665')'dnl
  90 `I(`A',B,C,D,X0,6,`0xf4292244')'dnl
  91 `I(`D',A,B,C,X7,10,`0x432aff97')'dnl
  92 `I(`C',D,A,B,Xe,15,`0xab9423a7')'dnl
  93 `I(`B',C,D,A,X5,21,`0xfc93a039')'dnl
  94 `I(`A',B,C,D,Xc,6,`0x655b59c3')'dnl
  95 `I(`D',A,B,C,X3,10,`0x8f0ccc92')'dnl
  96 `I(`C',D,A,B,Xa,15,`0xffeff47d')'dnl
  97 `I(`B',C,D,A,X1,21,`0x85845dd1')'dnl
  98 `I(`A',B,C,D,X8,6,`0x6fa87e4f')'dnl
  99 `I(`D',A,B,C,Xf,10,`0xfe2ce6e0')'dnl
 100 `I(`C',D,A,B,X6,15,`0xa3014314')'dnl
 101 `I(`B',C,D,A,Xd,21,`0x4e0811a1')'dnl
 102 `I(`A',B,C,D,X4,6,`0xf7537e82')'dnl
 103 `I(`D',A,B,C,Xb,10,`0xbd3af235')'dnl
 104 `I(`C',D,A,B,X2,15,`0x2ad7d2bb')'dnl
 105 `I(`B',C,D,A,X9,21,`0xeb86d391')Q($1+A)Q($2+B)Q($3+C)Q($4+D)')
 106
 107 define(`sort', `ifelse(`$2', `', ``,$1'', `ifelse(eval($1 > $2), 1, ``,$@'',
 108   ``,$2'$0(`$1', shift(shift($@)))')')')
 109 define(`clean', `forloop($1, eval($1+2000), `popdef(`do'', `)')define(`found',
 110   0)forloop(48, 57, `define(`T'', `)')forloop(97, 102, `define(`T'', `)')')
 111 define(`list')clean(0)
 112 define(`O', `ifelse($6,,`output(1, `candidate at $1')',`$2$3$4$5',`$3$4$5$6',
 113   `OO($1,$2T$2)$0($1, shift(shift($@)))', `$0($1,shift(shift($@)))')')
 114 define(`OO', `ifelse(`$3', `', `N(`T$2')', `$1', `$3', `N(`T$2', `,$1')',
 115   `ifelse(E($1 - 1000 <= $3), 1, `output(1, `found $3 at $1')N(`found',
 116   incr(found))N(`list', sort($3list))ifelse(E(found >= max), 1,
 117   `N(`do'E($3 + 1000), `clean($3)')')')$0($1, $2, shift(shift(shift($@))))')')
 118 define(`M', `_M($1)')
 119 define(`_M', `ifelse($4,,,`$2$3',`$3$4',`N(`T$2',defn(`T$2')`,$1')O($@)','dnl
 120 ``$0($1,shift(shift($@)))')')
 121 define(`rename', `ifdef(`$2', `', `define(`$2', defn(`$1'))popdef(`$1')')')
 122 define(`grab', `ifelse(eval(`$# > 'max), 1, `$0(shift($@))',
 123   `$1define(`list')')')
 124
 125 ifelse(ifdef(`only', `only', 1), 1, `
 126 define(`do'start, `output(1, `...'decr($1))rename(`$0', `do'E(`$1+999'))do($@)')
 127 define(`do', `M($1md5('dquote(defn(`prefix'))dnl
 128 ``$1'))ifdef(`$0$1',`$0$1',`$0')(incr(`$1'))')
 129 do(start)
 130 define(`part1', grab(list))
 131 ')
 132
 133 define(`R', `ifelse(`$3',,,`S$2($3,$1,$2)$0(ifelse($2,3,`incr($1),0',''dnl
 134 ```$1,incr($2)'),shift(shift(shift($@))))')')
 135 define(`Md5', `_Md5(2016,md5(`$1')S0(128,8)N(`Xe',256))')
 136 define(`_Md5', `ifelse(`$1',0,`$2',`$0(decr($1),_md5(R(0,0$2)''dnl
 137 ```1732584193',`-271733879',`-1732584194',`271733878'))')')
 138 ifelse(ifdef(`only', `only', 2), 2, `
 139 define(`do'start, `output(1, `...'decr($1))rename(`$0', `do'E(`$1+9'))do($@)')
 140 define(`do', `_M($1Md5('dquote(defn(`prefix'))dnl
 141 ``$1'))ifdef(`$0$1',`$0$1',`$0')(incr(`$1'))')
 142 do(start)
 143 define(`part2', grab(list))
 144 ')
 145
 146 divert`'part1
 147 part2