2021/day19.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dfile=day19.input] day19.m4
   3 # Optionally use -Dverbose=1 to see some progress
   4
   5 include(`common.m4')ifelse(common(19), `ok', `',
   6 `errprint(`Missing common initialization
   7 ')m4exit(1)')
   8
   9 # `p'oint/`c'oord,`o'ctant,`d'istances,`s'canner `g'roup `b'ounds `n'ormalized
  10 define(`input', translit(nl`'(include(defn(`file')))nl, nl`,(acenrs)', `;.'))
  11 define(`count', 0)define(`start', 0)
  12 define(`scan', `define(`s', translit(`$1', `- '))popdef(`line')')
  13 define(`point', `define(`p$2c', `$3,$4,$5')define(`p$2s', $1)define(`count',
  14   incr($2))')
  15 define(`group', `define(`b$1', start`,'decr(count))define(`g$1',
  16   $1)define(`s$1g', $1)define(`n$1', 0)define(`start', count)')
  17 define(`line', `ifelse(`$1', `', `ifdef(`s', `group(s)')pushdef(`$0',
  18   defn(`scan'))', `point(s, count, translit(`$1', `.', `,'))')')
  19 ifdef(`__gnu__', `
  20   patsubst(defn(`input'), `\([^;]*\);', `line(`\1')')
  21 ', `
  22   define(`_chew', `line(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 < 40), 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 # Compute a fingerprint of all pairwise distances (~25 beacons per scanner
  31 # means ~300 distances) per scanner
  32 define(`cmp', `eval($4 - $1), eval($5 - $2), eval($6 - $3)')
  33 define(`dist', `_$0(cmp(p$1c, p$2c))')
  34 define(`_dist', `eval($1 * $1 + $2 * $2 + $3 * $3), eval($1 * $1 == $2 * $2 ||
  35   $2 * $2 == $3 * $3 || $3 * $3 == $1 * $1)')
  36 define(`prep', `_$0($1, b$1)')
  37 define(`_prep', `forloop($2, decr($3), `$0_($1, ', `, $3)')')
  38 define(`_prep_', `forloop(incr($2), $3, `finger($1, $2, ', `)')')
  39 define(`finger', `_$0($1, $2, $3, dist($2, $3))')
  40 define(`_finger', `pushdef(`s$1d', $4)pushdef(`m$1_$4', `$2,$3,'ifdef(`m$1_$4',
  41   `define(`m$1_$4', defn(`m$1_$4')1)1', $5))')
  42 forloop_arg(0, s, `prep')
  43 # Next pass finds scanners to merge: 12 common points requires at least 66
  44 # common distances.  Of those, figure out two matching points from each
  45 # scanner that hae a useful delta.
  46 define(`match', `len(stack_reverse(`s$1d', `h', `pushdef(
  47   `h'h)')_stack_foreach(`s$2d', `_$0(', `, `$3')', `t')stack_reverse(`h',
  48   `s$1d', `undefine(`h'h)'))')
  49 define(`_match', `ifdef(`h$1', `$2`-'popdef(`h$1')')')
  50 define(`merge', `ifdef(`m', `_$0($1, $2, first(`m$1_'m), first(`m$2_'m))',
  51   `errprintn(`oops')m4exit(1)')')
  52 define(`_merge', `ifelse($5, 0, `output(1,
  53   `merging $1 and $2 via $3/$4 and $6/$7')_$0(s$1g, s$2g)pushdef(`work',
  54   `$3,$4,$6,$7')', `popdef(`m')merge($1, $2)')')
  55 define(`_merge_', `ifdef(`g$2', `define(`s'g$2`g', $1)pushdef(`g$1',
  56   g$2)popdef(`g$2')$0($@)')')
  57 define(`_try', `ifelse(s$1g, s$2g, `', `undefine(`m')ifelse(eval(match($1, $2,
  58   `pushdef(`m', t)') >= 66), 1, `merge($1, $2)')')')
  59 define(`try', `forloop(incr($1), s, `_$0($1, ', `)')')
  60 forloop_arg(0, decr(s), `try')
  61 # Final step: for each pair of merge points, determine the translation to
  62 # apply to all points in the second scanner, then count total unique points.
  63 # Assumes common neighbor has distinct deltas in each dimension.
  64 define(`n0', 1)define(`n', 0)
  65 define(`maxa', 0)define(`mina', 0)define(`maxb', 0)define(`minb', 0)
  66 define(`maxc', 0)define(`minc', 0)define(`maxd', 0)define(`mind', 0)
  67 define(`bump', `ifelse(eval($1 > max$2), 1, `define(`max$2', eval($1))')ifelse(
  68   eval($1 < min$2), 1, `define(`min$2', eval($1))')')
  69 define(`order', `_$0(`$', $1, $2, $3, $4, eval(- $4))`,'_$0(`$', $1, $2, $3,
  70   $5, eval(- $5))`,'_$0(`$', $1, $2, $3, $6, eval(- $6))')
  71 define(`_order', `ifelse($2, $5, `$1'1, $2, $6, -(`$1'1), $3, $5, `$1'2, $3,
  72   $6, -(`$1'2), $4, $5, `$1'3, -(`$1'3))')
  73 define(`det', `eval($1*($5*$9- $6*$8)- $2*($4*$9- $6*$7)+$3*($4*$8- $5*$7))')
  74 define(`settle', `ifelse(n, 's`, `', `_stack_foreach(`work', `_$0(first(',
  75   `))', `w')$0()')')
  76 define(`_settle', `$0_($1, $2, $3, $4, defn(`n'p$1s), defn(`n'p$3s))')
  77 define(`_settle_', `ifelse($5$6, 01, `translate($3, $4, $1, $2, p$3s, p$1s)',
  78   $5$6, 10, `translate($1, $2, $3, $4, p$1s, p$3s)')')
  79 define(`translate', `_$0($6, $1, $2, $3, $4)define(`n$6', 1)define(`n',
  80   incr(n))')
  81 define(`_translate', `define(`shuf', order(cmp(p$4c, p$5c), cmp(p$2c,
  82   p$3c)))ifelse(det(shuf(1, 0, 0), shuf(0, 1, 0), shuf(0, 0, 1)), -1,
  83   `$0($1, $2, $3, $5, $4)', `$0_($@, cmp(p$2c, shuf(p$4c)))')')
  84 define(`_translate_', `output(1, `...scanner $1: $4,$5 to $2,$3 via 'defn(
  85   `shuf')` + $6,$7,$8')bump($6 + $7 + $8, `a')bump($6 + $7 - $8,
  86   `b')bump($6 - $7 + $8, `c')bump($6 - $7 - $8, `d')forloop(b$1,
  87   `swizzle(', `, $6, $7, $8)')')
  88 define(`swizzle', `define(`p$1c', quote(cmp($2, $3, $4, shuf(p$1c))))')
  89 settle()
  90 define(`tally', `_$0(translit(dquote(defn(`p$1c')), `-,', `n_'), $1, p$1c)')
  91 define(`_tally', `ifdef(`h$1', `', `-define(`h$1')')')
  92 define(`part1', len(forloop_arg(0, decr(count), `tally')))
  93 define(`maxe', 0)define(`mine', 0)
  94 bump(maxa - mina, `e')bump(maxb - minb, `e')bump(maxc - minc, `e')
  95 bump(maxd - mind, `e')define(`part2', maxe)
  96
  97 divert`'part1
  98 part2