2022/day20.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dfile=day20.input] day20.m4
   3 # Optionally use -Dverbose=1 to see some progress
   4 # Optionally use -Dscan=linear|sqrt|log to choose scan algorithm
   5
   6 include(`common.m4')ifelse(common(20), `ok', `',
   7 `errprint(`Missing common initialization
   8 ')m4exit(1)')
   9
  10 ifdef(`scan', `', `define(`scan', `log')')
  11
  12 # Each input is stored in iN, with cnt tracking number of inputs, and z the
  13 # index of the line relevant to the solutions.
  14 define(`cnt', 0)
  15 define(`do', `define(`i$1', $2)define(`cnt', incr($1))ifelse($2, 0,
  16   `define(`z', $1)')')
  17
  18 define(`input', translit(include(defn(`file')), nl, `;'))
  19 ifdef(`__gnu__', `
  20   patsubst(defn(`input'), `\([^;]*\);', `do(cnt, `\1')')
  21 ', `
  22   define(`_chew', `do(cnt, substr(`$1', 0, index(`$1', `;')))define(
  23     `tail', substr(`$1', incr(index(`$1', `;'))))ifelse(index(defn(`tail'),
  24     `;'), -1, `', `$0(defn(`tail'))')')
  25   define(`chew', `ifelse(eval($1 < 12), 1, `_$0(`$2')', `$0(eval($1/2),
  26     substr(`$2', 0, eval($1/2)))$0(eval(len(defn(`tail')) + $1 - $1/2),
  27     defn(`tail')substr(`$2', eval($1/2)))')')
  28   chew(len(defn(`input')), defn(`input'))
  29 ')
  30
  31 ifelse(defn(`scan'), `linear', `
  32 output(1, `Using O(n) scan on doubly-linked list')
  33 # Nodes are stored in a doubly-linked circular list: a given index with value
  34 # iN has next at nN and previous pN, and action aN says which direction and
  35 # how many spots forward or backward (fN/bN) to scan for the insertion point.
  36 # Scanning is linear, with an average of cnt/4 spots visited.  Once start
  37 # and end spots are found, stitching redefines 6 links associated with 5
  38 # nodes: s(a,b,i,d,e) turns a<=>i<=>b, c<=>d into a<=>b, c<=>i<=>d
  39 # For 5000 elements, effort exceeds 67 million scans, but less than 50k eval
  40 define(`D', defn(`define'))
  41 define(`_prep', ``s(p$1,n$1,$1,$2$3($1))'')
  42 define(`prep', `D(`a$1', ifelse($2, 0, `', `_$0($1, ifelse(eval(
  43   $2>''cnt``/2), 1, ``b',eval(- $2+''cnt``-1)', eval($2<-''cnt``/2), 1,
  44   ``f',eval($2+''cnt``-1)', eval($2>0), 1, ``f',$2', ``b',eval(- $2)'))'))')
  45 ifelse(eval(verbose >1), 1, `define(`_prep', defn(`_prep')`define(`effort',
  46   eval(effort+$3))')')
  47 define(`_reset', `D(`n$1', incr($1))D(`p'incr($1), $1)prep($1,
  48   eval(i$1$2%('cnt`-1)))ifelse(`$2', `', `D(`f'incr($1),
  49   `f$1(n$'1`)')D(`b'incr($1), `b$1(p$'1`)')')')
  50 define(`reset', `forloop(0, decr(cnt), `_$0(', `, `$1')')define(`n'decr(cnt),
  51   0)define(`p0', decr(cnt))define(`f0', `$'1`,n$'1)define(`b0', `p$'1`,$'1)')
  52
  53 define(`a', `a$1')
  54 define(`s', `D(`p$2',`$1')D(`n$1',`$2')D(`n$3',`$5')D(`p$5',`$3')D(`n$4',
  55   `$3')D(`p$3',`$4')')
  56 define(`coord3', `+i$1')
  57 define(`coord2', `+i$1`'coord3(f'eval(1000%cnt)`($1))')
  58 define(`coord1', `+i$1`'coord2(f'eval(1000%cnt)`($1))')
  59 define(`coord', `coord1(f'eval(1000%cnt)`(z))')
  60 define(`account', `output(2, `effort: 'eval($1*defn(`effort')+0))')
  61
  62 ', defn(`scan'), `sqrt', `
  63 output(1, `Using O(sqrt n) scan on bins of singly-linked lists')
  64 # Nodes are stored in bins starting at 70 elements each, for 72 bins. Each bin
  65 # is singly-linked with bN at the head and lN the current bin size; for
  66 # convenience, bbN is the next bin in a circular list of bins.  Each index has
  67 # nN as the next element in its bin or blank if it the tail of the bin, and BN
  68 # is the bin currently containing that index.  Bin size is not automatically
  69 # rebalanced, but with only 10 mixes of input that is fairly evenly
  70 # distributed, the bins do not degrade too badly.  On average, moving a node
  71 # requires scanning through half of one bin to find the start spot, jumping
  72 # through half the bins to find the destination bin, then scanning through half
  73 # that bin to find the destination spot.  Worst-case input could degrade to all
  74 # indices migrating to a common bin, with linear scanning from then on.
  75 # f: find by value, c: move by count, s: stitch
  76 # For 5000 elements, effort exceeds 7.3 million recursive calls to f and c,
  77 # along with 3.9 million calls to eval.  Tracing bin assignments shows that
  78 # bin 1 is the destination only 9 times, while bin 63 is the destination
  79 # 1900 times; this skew explains why effort is more than the predicted 5.7
  80 # million calls if the code also implemented bin rebalancing.
  81 # Implementing backward bin scanning may cut effort roughly in half.
  82 ifdef(`bin', `', `define(`bin', ifelse(cnt, 7, 3, 70))')
  83 define(`_prep', ``s($'`1,$1,n$1,f(`b'$'`1,0,$1)+$2)'')
  84 define(`prep', `define(`a$1', ifelse($4, 0, `', `_$0($1, $4)'))ifelse($2,
  85   'decr(bin)`, `define(`n$1')define(`l$3', 'bin`)define(`bb$3',
  86   incr($3))define(`b'incr($3), incr($1))', `define(`n$1', incr($1))')define(
  87   `B$1', $3)')
  88 define(`_reset', `prep($1, eval($1%'bin`), eval($1/'bin`),
  89   eval((i$1$2%$3+$3)%$3))')
  90 define(`reset', `forloop(0, decr(cnt), `_$0(', `, `$1', ''decr(
  91   cnt)``)')define(`bb'eval(cnt/bin), 0)define(`l'eval(cnt/bin),
  92   eval(cnt%bin))define(`b0', 0)define(`n'decr(cnt))')
  93
  94 define(`a', `a$1(B$1)')
  95 define(`_c', `ifelse($2, 0, `$1,`$3'', `$0($1, decr($2), `n'$3)')')
  96 define(`c', `ifelse(eval(l$1<$3), 1, `$0(bb$1, `', eval($3-l$1))', `_$0($1,
  97   eval($3), `b$1')')')
  98 define(`f', `ifelse($1, $3, ``$1',$2', `$0(`n'$1, incr($2), $3)')')
  99 define(`augment', `define(`$1', defn(`$1')`define(`effort', incr(effort))')')
 100 ifelse(eval(verbose >1), 1, `augment(`f')augment(`c')augment(`_c')')
 101 define(`_s', `define(`B$3', $1)define(`n$3', $2)define(`$2', $3)define(`l$1',
 102   incr(l$1))')
 103 define(`s', `define(`l$1', decr(l$1))define(`$4', $3)_$0(c($1, `', $5), $2)')
 104 define(`get', `ifelse($2, `', `defn(`b'bb$1)', `$2')')
 105 define(`coord3', `+i$1')
 106 define(`coord2', `+i$1`'coord3(get(c(B$1, f(`b'B$1, 0, $1)+eval(1000%cnt))))')
 107 define(`coord1', `+i$1`'coord2(get(c(B$1, f(`b'B$1, 0, $1)+eval(1000%cnt))))')
 108 define(`coord', `coord1(get(c(defn(`B'z), f(`b'defn(`B'z), 0,
 109   z)+eval(1000%cnt))))')
 110 define(`account', `output(2, `effort: 'effort)')
 111
 112 ', defn(`scan'), `log', `
 113 output(1, `Using O(log n) scan on WAVL tree')
 114 # See http://sidsen.azurewebsites.net//papers/rb-trees-talg.pdf
 115 # Store the indices in a modified WAVL search tree of ordered nodes (keys are
 116 # implicit: insertion by position rather than key value). Every node knows the
 117 # size of its subtrees, and by storing a parent link, a given node can
 118 # determine its index in O(log n) effort.  For 5000 nodes, there are just over
 119 # 12 levels, or roughly 24 defines per deletion/insertion sequence just to keep
 120 # the sizes up-to-date (over 1.3 million calls), plus more overhead in
 121 # maintaining tree pointers.  Still, this is less overall effort, and we
 122 # are guaranteed the tree remains self-balanced due to the WAVL algorithm.
 123 # Each index N is tied to a given node consisting of nNL, nNR, nNp, nNP, nNs
 124 # for left, right, parent, rank parity, and size; there are always cnt nodes,
 125 # but shuffling temporarily removes a node from one spot in tree r and inserts
 126 # it elsewhere. The nil pointer is an empty string, not an undefined macro.
 127 define(`D', defn(`define'))define(`I', defn(`ifelse'))
 128 define(`Def', defn(`define'))
 129 ifelse(eval(verbose >1), 1, `define(`Def', `D(`effort',incr(effort))D($'`@)')')
 130 define(`nP', 1)define(`np')define(`ns', 0)define(`nL')define(`nR')
 131 define(`parity', `n$1P`'')
 132 define(`t0', 1)define(`t1', 0)
 133 define(`toggle', `D(`n$1P', defn(`t'n$1P))')
 134 define(`size', `n$1s`'')
 135 define(`cmp', `eval(`(($1)>($2))-(($2)>($1))')')
 136 define(`splicep', `D(`n$1p', $3)I($3, `', `D(`r', $1)',
 137   `I($2, n$3L, `D(`n$3L', $1)', `D(`n$3R', $1)')')')
 138 define(`splicec', `D(`n$1$3', $2)I($2, `', `', `D(`n$2p', $1)')')
 139 #    z=$3         y
 140 # x=$2    D =>  x   z
 141 # A  y=$1      A B C D
 142 #    B  C
 143 define(`_dblrotr', `splicep($1, $3, n$3p)splicec($2, n$1L, `R')D(
 144   `n$1L', $2)D(`n$2p', $1)splicec($3, n$1R, `L')D(`n$1R', $3)D(
 145   `n$3p', $1)Def(`n$3s', eval(size(n$3L)+size(n$3R)+1))Def(`n$2s',
 146   eval(size(n$2L)+size(n$2R)+1))Def(`n$1s', eval(n$2s+n$3s+1))')
 147 define(`dblrotr', `_$0($1, $2, n$2p)')
 148 #    z=$3         x
 149 #  x=$1   C =>  A   z
 150 # A  y=$2          y C
 151 define(`_rotr', `splicep($1, $3, n$3p)D(`n$1R', $3)D(`n$3p',
 152   $1)D(`n$3L', $2)Def(`n$3s', eval(n$3s-n$1s+n$2s))Def(`n$1s',
 153   eval(n$1s-n$2s+n$3s))I($2, `', `', `D(`n$2p', $3)')')
 154 define(`rotr', `_$0($1, n$1R, n$1p)')
 155 define(`_dblrotl', `splicep($1, $3, n$3p)splicec($3, n$1L, `R')D(
 156   `n$1L', $3)D(`n$3p', $1)splicec($2, n$1R, `L')D(`n$1R', $2)D(
 157   `n$2p', $1)Def(`n$3s', eval(size(n$3L)+size(n$3R)+1))Def(`n$2s',
 158   eval(size(n$2L)+size(n$2R)+1))Def(`n$1s', eval(n$2s+n$3s+1))')
 159 define(`dblrotl', `_$0($1, $2, n$2p)')
 160 define(`_rotl', `splicep($1, $3, n$3p)D(`n$1L', $3)D(`n$3p',
 161   $1)D(`n$3R', $2)Def(`n$3s', eval(n$3s-n$1s+n$2s))Def(`n$1s',
 162   eval(n$1s-n$2s+n$3s))I($2, `', `', `D(`n$2p', $3)')')
 163 define(`rotl', `_$0($1, n$1L, n$1p)')
 164 define(`sibling', `I($2, `', `', n$2L, $1, `n$2R', `n$2L')')
 165 define(`balance', `I($4, `', `rot$5($1)toggle($2)', parity($4), $3,
 166   `rot$5($1)toggle($2)', `dblrot$5($4, n$4p)toggle($4)toggle($1)toggle($2)')')
 167 define(`_insbal_', `I($3$4, $4t$5, `_insbal($2, n$2p)', $3$4, $4$5,
 168   `balance($1, $2, $3, I($1, n$2L, `n$1R, `r'', `n$1L, `l''))')')
 169 define(`_insbal', `toggle($1)I($2, `', `', `$0_($1, $2, n$1P, n$2P,
 170   parity(sibling($1, $2)))')')
 171 define(`insbal', `_$0($1, n$1p)')
 172 define(`_insert_', `Def(`n$3s', incr(n$3s))I(eval($1<=n$4s), 1,
 173   `I($4, `', `D(`n$3L', $2)D(`n$2p', $3)n$3R', `$0($1, $2, $4,
 174   n$4L)')', `I(n$3R, `', `D(`n$3R', $2)D(`n$2p', $3)$4',
 175   `$0(eval($1-n$4s-1), $2, n$3R, defn(`n'n$3R`L'))')')')
 176 define(`_insert', `D(`n$2L')D(`n$2R')D(`n$2p')D(`n$2P',
 177   0)Def(`n$2s', 1)I($3, `', `D(`r', $2)', `I($0_($1, $2, $3,
 178   n$3L), `', `insbal(n$2p)')')')
 179 # insert(pos, node)
 180 define(`insert', `_$0($1, $2, r)')
 181 define(`_at_', `I($3, 0, $2, $3, -1, `_at($1, n$2L)',
 182   `_at($1-size(n$2L)-1, n$2R)')')
 183 define(`_at', `$0_($1, $2, cmp($1, size(n$2L)))')
 184 # at(index) => node
 185 define(`at', `_$0($1, r)')
 186 define(`_pos', `I($1, `', `', `I($1, n$2R, `+size(n$2L)+1')$0($2, n$2p)')')
 187 # pos(node) => index
 188 define(`pos', `eval(size(n$1L)_$0($1, n$1p))')
 189 define(`_succ', `I(n$1L, `', $1, `$0(n$1L)')')
 190 define(`_succ_', `I($2, `', `', $1, n$2R, `$0($2, n$2p)', $2)')
 191 define(`succ', `I(n$1R, `', `_$0_($1, n$1p)', `_$0(n$1R)')')
 192 define(`swap', `splicep($2, $1, n$1p)splicec($2, n$1R, `R')D(
 193   `n$1R')splicec($2, n$1L, `L')D(`n$1L')D(`n$2P', n$1P)D(
 194   `n$1p')Def(`n$2s', n$1s)')
 195 define(`fix3', `I($1, n$2L, `I(n$3P, parity(n$3R), `dblrotl(n$3L,
 196   $3)toggle($3)', `rotl($3)toggle($3)I(n$2L., .n$2R, `', `toggle($2)')')',
 197   `I(n$3P, parity(n$3L), `dblrotr(n$3R, $3)toggle($3)',
 198   `rotr($3)toggle($3)I(n$2L., .n$2R, `', `toggle($2)')')')')
 199 define(`_bal3', `I(n$3P, n$2P, `toggle($2)I($4, `', `',
 200   $5, $6, `bal3($2, $4)')', n$3P.parity(n$3L), parity(n$3R).n$3P, `toggle(
 201   $2)toggle($3)I($4, `', `', $5, $6, `bal3($2, $4)')', `fix3($1, $2,
 202   $3)')')
 203 define(`bal3', `_$0($1, $2, sibling($1, $2), n$2p, n$2P, parity(n$2p))')
 204 define(`bal2', `I(n$1P, parity(n$1p), `toggle($1)bal3($1, n$1p)',
 205   `toggle($1)')')
 206 define(`resize', `I($1, `', `', `Def(`n$1s',
 207   eval(size(n$1L)+size(n$1R)+1))$0(n$1p)')')
 208 define(`rembal', `I($5, `', `', $1, $2, `bal3($4, $5)', $4.n$5L, .n$5R,
 209   `bal2($5)')resize($5)')
 210 define(`_remove_', `I($3, `', `', `D(`n$3p', n$2p)')rembal(I($4,
 211   `', `0,1D(`r', $3)', `n$2P,n$4P`'I($2, n$4L, `D(`n$4L',
 212   $3)', `D(`n$4R', $3)')'), $2, $3, I($1, $2, $4, `swap($1,
 213   $2)I($1, $4, $2, $4)'))')
 214 define(`_remove', `$0_($1, $2, I(n$2L, `', `n$2R', `n$2L'), n$2p)')
 215 define(`remove', `_$0($1, I(n$1L, `', $1, n$1R, `', $1,
 216   `_succ(n$1R)'))D(`n$1L')D(`n$1R')D(`n$1p')D(`n$1P', 0)')
 217 define(`_build_1', `D(`n$1L')D(`n$1R')D(`n$1P', 0)Def(`n$1s', 1)$1')
 218 define(`_build_2', `D(`n$1L')D(`n$1R', $2)D(`n$1P', 1)Def(`n$1s',
 219   2)D(`n$2L')D(`n$2R')D(`n$2p', $1)D(`n$2P', 0)Def(`n$2s', 1)$1')
 220 define(`_build_3', `D(`n$2L', $1)D(`n$1p', $2)D(`n$2R', $3)D(`n$3p',
 221   $2)D(`n$2P', defn(`t'n$3P))Def(`n$2s', eval(n$1s+n$3s+1))$2')
 222 define(`_build', `I($1, $3, `$0_1($1)', $1, $2, `$0_2($1, $3)',
 223   `$0_3(build($1, decr($2)), $2, build(incr($2), $3))')')
 224 define(`build', `_$0($1, eval(($1+$2)/2), $2)')
 225
 226 # Mostly useful for debugging my implementation:
 227 define(`nop')
 228 define(`dump', `errprintn(`node:$1 depth:$2 left:'n$1L` right:'n$1R(
 229   )` parent:'n$1p` parity:'n$1P` size:'n$1s)')
 230 define(`_walk', `ifelse(`$1', `', `', `$3($1, $2)`'$0(n$1L, incr($2), `$3',
 231   `$4', `$5')$4($1, $2)`'$0(n$1R, incr($2), `$3', `$4', `$5')$5($1, $2)`'')')
 232 # walk(pre, in, post) => preorder, inorder, postorder walk of tree
 233 # each func takes node and depth parameters; nop and dump are predefined
 234 define(`walk', `_$0(r, 0, $@)')
 235
 236 # Now to make use of the WAVL tree.
 237 define(`a', `ifelse(a$1, 0, `', `insert(eval((a$1+pos($1))%''decr(cnt)``),
 238   remove($1)$1)')')
 239 define(`_reset', `define(`a$1', eval((i$1$2%$3+$3)%$3))')
 240 define(`reset', `define(`r', build(0, decr(cnt)))define(`n'r`p')forloop(0,
 241   decr(cnt), `_$0(', `, `$1', ''decr(cnt)``)')')
 242 define(`coord3', `+i$1')
 243 define(`coord2', `+i$1`'coord3(at(eval((pos($1)+1000)%cnt)))')
 244 define(`coord1', `+i$1`'coord2(at(eval((pos($1)+1000)%cnt)))')
 245 define(`coord', `coord1(at(eval((pos(z)+1000)%cnt)))')
 246 define(`account', `output(2, `effort: 'effort)')
 247
 248 ', `fatal(`unknown scan algorithm')')
 249
 250 define(`mix', `define(`effort', 0)reset(`$2')forloop(1, $1, `output(1, ...',
 251   `)forloop_arg(0, 'decr(cnt)`, `a')')account($1)')
 252
 253 mix(1, `')
 254 define(`part1', eval(coord))
 255
 256 mix(10, `*'eval(811589153%(cnt-1)))
 257 include(`math64.m4')
 258 define(`part2', mul64(eval(coord), 811589153))
 259
 260 divert`'part1
 261 part2