2015/day6.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dfile=day6.input] day6.m4
   3 # Optionally use -Dverbose=1 to see some progress
   4 # Optionally use -Dalgo=list|btree to choose the list implementation
   5
   6 include(`common.m4')ifelse(common(6, 65537), `ok', `',
   7 `errprint(`Missing common initialization
   8 ')m4exit(1)')
   9
  10 define(`turn')define(`through')
  11 pushdef(`inst', `0,999,`R',0,999')
  12 define(`On', `pushdef(`inst', `$3,$6,`S',$2,$5')')
  13 define(`Off', `pushdef(`inst', `$3,$6,`C',$2,$5')')
  14 define(`Tog', `pushdef(`inst', `$3,$6,`T',$2,$5')')
  15 translit((include(defn(`file'))), ` 'nl, `,)'define(
  16   `on', `On(')define(`off', `Off(')define(`toggle', `Tog(')))
  17 define(`F', `$1')
  18 define(`D', defn(`define'))define(`I', defn(`ifelse'))
  19 define(`P', defn(`incr'))define(`M', defn(`decr'))
  20 define(`E', defn(`eval'))define(`N', defn(`defn'))
  21
  22 ifelse(ifdef(`algo', `algo', `btree'), `btree', `
  23
  24 output(1, `using 2-3 B-tree to track row')
  25 define(`n', 0)dnl counter for naming nodes
  26 dnl root: head of 2-3 range tree subdividing 0-999, nNt: type,
  27 dnl nNa: left range lo, nNA: left range hi, nNv: left value
  28 dnl nNb: right range lo, nNB: right range hi, nNV: right value
  29 dnl nNl: left child nNc: center child, nNr: right child, nNp: parent
  30 define(`type', `N(`n$1t')')dnl type: Leaf: l1, l2, Internal: 2, 3
  31 define(`partype', `ifdef(`n$1p', `type(n$1p)', ``r'')')
  32 define(`find', `_$0($1, root)')dnl find(lo, node) output node and slot
  33 define(`_find', `F(`$0'type($2))($1, $2)')
  34 define(`_findl1', `$2,`a',`A',`v'')
  35 define(`_findl2', `I(E($1 < n$2b), 1, `$2,`a',`A',`v'',
  36   `$2,`b',`B',`V'')')
  37 define(`_find2', `I(E($1 < n$2a), 1, `_find($1, n$2l)',
  38   E($1 > n$2A), 1, `_find($1, n$2r)', `$2,`a',`A',`v'')')
  39 define(`_find3', `I(E($1 < n$2a), 1, `_find($1, n$2l)',
  40   E($1 > n$2A && $1 < n$2b), 1, `_find($1, n$2c)', E($1 > n$2B), 1,
  41   `_find($1, n$2r)', E($1 <= n$2A), 1, `$2,`a',`A',`v'', `$2,`b',`B',`V'')')
  42 dnl setX(node, lo, hi, value) prep left or right of node
  43 define(`seta', `D(`n$1a', $2)D(`n$1A', $3)D(`n$1v', `$4')')
  44 define(`setb', `D(`n$1b', $2)D(`n$1B', $3)D(`n$1V', `$4')')
  45 dnl new(lo, hi, value, l, r) create new 2-node, return its number
  46 define(`new', `_$0(n, $@)')
  47 define(`_new', `seta($1, $2, $3, `$4')I(`$5$6', `', `D(`n$1t',
  48   `l1')', `D(`n$1t', 2)D(`n$1l', $5)D(`n$5p', $1)D(`n$1r',
  49   $6)D(`n$6p', $1)')popdef(`n$1p')D(`n', P($1))$1')
  50 dnl init() create new tree, assigned to root
  51 define(`init', `D(`root', new(0, 999, `0'))')
  52 dnl next(node, Slot) returns node, slot of next range, undefined at end
  53 define(`next', `ifdef(`n$1p', `F(`_$0'type($1)`$2')($1, n$1p,
  54   P(n$1$2))', `_find(P(n$1$2), $1)')')
  55 define(`_nextl1A', `I(n$2l, $1, `$2,`a',`A',`v'', n$2t.n$2c, 3.$1,
  56   `$2,`b',`B',`V'', `$0($2, n$2p, $3)')')
  57 define(`_nextl2A', `$1,`b',`B',`V'')
  58 define(`_nextl2B', N(`_nextl1A'))
  59 define(`_next2A', `_find($3, n$1r)')
  60 define(`_next3A', `_find($3, n$1c)')
  61 define(`_next3B', `_find($3, n$1r)')
  62 dnl merge(op, lo, hi) split/redefine nodes as needed to insert new subrange
  63 define(`merge', `_insert($2, $3, `$1', find($2))')
  64 define(`_insert', `I(n$4$5, $1, `I(E(n$4$6 < $2), 1,
  65   `F(`$0'type($4)`$5')($1, n$4$6, `$3', $4)$0(P(n$4$6), $2, `$3',
  66   next($4, `$6'))', `F(`$0'type($4)`$5')($1, $2, `$3', $4)')', `F(
  67   `split'type($4)`$5')($1, $4)merge(`$3', $1, $2)')')
  68 define(`_insertl1a', `I($2, n$4A, `', `splitl1a(P($2),
  69   $4)')D(`n$4v', $3($1, $2, n$4v))')
  70 define(`_insertl2a', `I($2, n$4A, `', `splitl2a(P($2),
  71   $4)')D(`n$4v', $3($1, $2, n$4v))')
  72 define(`_insertl2b', `I($2, n$4B, `D(`n$4V', $3($1, $2, n$4V))',
  73   `_splitl2b(P($2), $4, N(`n$4V')D(`n$4V', $3($1, $2, n$4V)))')')
  74 define(`_insert2a', `I($2, n$4A, `D(`n$4v', $3($1, $2, n$4v))',
  75   `D(`n$4a', P($2))F(`add'type(n$4l))(n$4l, $1, $2, $3($1, $2,
  76   n$4v))')')
  77 define(`_insert3a', N(`_insert2a'))
  78 define(`_insert3b', `I($2, n$4B, `D(`n$4V', $3($1, $2, n$4V))',
  79   `D(`n$4b', P($2))F(`add'type(n$4c))(n$4c, $1, $2, $3($1, $2,
  80   n$4V))')')
  81 dnl split(mid, node) split a range, and shuffle nodes as needed
  82 define(`splitl1a', `D(`n$2t', `l2')setb($2, $1, n$2A,
  83   N(`n$2v'))D(`n$2A', M($1))')
  84 define(`splitl2a', `F(`promote'partype($2))(N(`n$2p'), $1,
  85   n$2A`'D(`n$2A', M($1)), N(`n$2v'), $2, new(n$2b, n$2B,
  86   N(`n$2V')))D(`n$2t', `l1')')
  87 define(`splitl2b', `_$0($1, $2, N(`n$2V'))')
  88 define(`_splitl2b', `F(`promote'partype($2))(N(`n$2p'), n$2b,
  89   M($1), N(`n$2V'), $2, new($1, n$2B, `$3'))D(`n$2t', `l1')')
  90 define(`split2a', `F(`add'type(n$2l))(n$2l, n$2a`'D(`n$2a', $1),
  91   M($1), N(`n$2v'))')
  92 define(`split3a', N(`split2a'))
  93 define(`split3b', `F(`add'type(n$2c))(n$2c, n$2b`'D(`n$2b', $1),
  94   M($1), N(`n$2V'))')
  95 dnl addX(node, lo, hi, value) add range into child node
  96 define(`addl1', `D(`n$1t', `l2')setb($1, $2, $3, `$4')')
  97 define(`addl2', `_$0($1, new($2, $3, `$4'))')
  98 define(`_addl2', `F(`promote'partype($1))(N(`n$1p'), n$1b,
  99   n$1B, N(`n$1V'), $1, $2)D(`n$1t', `l1')')
 100 define(`add2', `F(`add'type(n$1r))(n$1r, $2, $3, `$4')')
 101 define(`add3', N(`add2'))
 102 dnl promoteX(node, lo, hi, value, child, new) tie just-split child into node
 103 define(`promoter', `D(`root', new($2, $3, `$4', $5, $6))')
 104 define(`promote2', `I($5, n$1l, `setb($1, n$1a, n$1A, N(`n$1v'))seta(
 105   $1, $2, $3, `$4')D(`n$1c', $6)', `setb($1, $2, $3, `$4')D(`n$1c',
 106   n$1r)D(`n$1r', $6)')D(`n$6p', $1)D(`n$1t', 3)')
 107 define(`promote3', `_$0($1, I($5, n$1l, `n$1a, n$1A, N(`n$1v'),
 108   new(n$1b, n$1B, N(`n$1V'), n$1c, n$1r), $6D(`n$1a', $2)D(`n$1A',
 109   $3)D(`n$1v', `$4')D(`n$6p', $1)', $5, n$1c, `$2, $3, `$4',
 110   new(n$1b, n$1B, N(`n$1V'), $6, n$1r), n$1c', `n$1b, n$1B, N(`n$1V'),
 111   new($2, $3, `$4', n$1r, $6), n$1c'))')
 112 define(`_promote3', `F(`promote'partype($1))(N(`n$1p'), $2, $3, `$4',
 113   $1, $5)D(`n$1t', 2)D(`n$1r', $6)')
 114
 115 define(`R', `define(`n', base)init()')
 116 define(`use', `$3')
 117 define(`prep', `define(`base', n)define(`rows', root)')
 118 define(`walk', `_$0(`$1', _find(0, I(`$2', `rows', `rows', `root')))')
 119 define(`_walk', `$1(n$2$3, n$2$4, n$2$5)I(n$2$4, 999, `', `$0(`$1',
 120   next($2, `$4'))')')
 121
 122 ', defn(`algo'), `list', `
 123
 124 output(1, `using m4 stack as list to track row')
 125 pushdef(`r', `0,999,0')
 126 define(`R', `undefine(`r')pushdef(`r', `0,999,0')')
 127 define(`merge', `D(`todo', `$2,$3')_stack_foreach(`r', `_$0(`$1',', `)',
 128   `t')')
 129 define(`_merge', `ifdef(`todo', `handle(`$1', todo, $2)')')
 130 define(`handle', `I($2, $4, `I(E($3 < $5), 1, `$1($2, $3,
 131   $6)D(`t', P($3)`,$5,$6')pushdef(`t')popdef(`todo')', $3, $5,
 132   `$1($2, $3, $6)popdef(`todo')', `$1($2, $5, $6)D(`todo',
 133   P($5)`,$3')')', E($2 <= $5), 1, `use($4, M($2), $6)D(`t',
 134   `$2,$5,$6')pushdef(`t')')')
 135 define(`use', `D(`r', `$1,$2,$3')')
 136 define(`prep', `stack_reverse(`r', `rows')')
 137 define(`walk', `_stack_foreach(I(`$2', `rows', ``rows'', ``r''),
 138   `$1(F(', `))', `tmp$2')')
 139
 140 ', `
 141 errprintn(`unrecognized -Dalgo= value')m4exit(1)
 142 ')
 143
 144 define(`set', `use($1, $2, I(index($3, `-'), 0, `M($3)', `-P($3)'))')
 145 define(`clr', `use($1, $2, I($3, 0, 0, `M(substr($3,
 146   P(index($3, `-'))))'))')
 147 define(`tgl', `use($1, $2, I(index($3, `-'), 0,
 148   `P(P(substr($3, 1)))', `-P(P($3))')))')
 149 define(`S', `merge(`set', $1, $2)')
 150 define(`C', `merge(`clr', $1, $2)')
 151 define(`T', `merge(`tgl', $1, $2)')
 152 define(`part1', 0)define(`part2', 0)define(`cnt', 0)
 153 define(`gatherX', `+($2-$1+1)*($3<0)')
 154 define(`gatherY', `+($2-$1+1)*($3*(1-2*($3<0)))')
 155 define(`do', `_$0($1)D(`part1', E(part1 + (walk(`gatherX'))` * ($2-$1+1)'))D(
 156   `part2', E(part2 + (walk(`gatherY'))` * ($2-$1+1)'))I(E(cnt % 10), 0,
 157   `output(1, `...$1')')D(`cnt', P(cnt))')
 158 define(`_do', `ifdef(`row$1', `row$1()popdef(`row$1')$0($@)')')
 159
 160 init()
 161 define(`divvy', `ifdef(`inst', `_$0(inst)popdef(`inst')$0()')')
 162 define(`_divvy', `ifelse(`$3', `R', `', `merge(`use', $1, $2)')forloop($1, $2,
 163   `pushdef(`row'', `, `$3($4,$5)')')')
 164 divvy()
 165 prep()
 166 walk(`do', `rows')
 167
 168 divert`'part1
 169 part2