2023/day09.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dfile=day09.input] day09.m4
   3
   4 include(`common.m4')ifelse(common(09), `ok', `',
   5 `errprint(`Missing common initialization
   6 ')m4exit(1)')
   7
   8 # Observation from the megathread: all rows of the input file have the
   9 # same number of elements.  Instead of performing O(n^2) merge() on each
  10 # row (actually O(n^3) because of m4's overhead in reparsing arguments
  11 # each iteration), we can perform a single merge on the O(n) summation of
  12 # all input rows, and still get the same result.
  13
  14 define(`input', translit(include(defn(`file')), nl` ', `;.'))
  15 define(`_do', `define(`n$1', eval(defn(`n$1')+$2))define(`n', incr($1))')
  16 define(`do', `define(`n', 0)_foreach(`_$0(defn(`n'), ', `)', translit(`.$1',
  17   `.', `,'))')
  18
  19 ifdef(`__gnu__', `
  20   patsubst(defn(`input'), `\([^;]*\);', `do(`\1')')
  21 ', `
  22   define(`_chew', `do(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 < 240), 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 # This approach uses an O(n^2) recursion to compute both answers using only
  32 # differences.  The megathread mentions other approaches using Lagrange's
  33 # interpolation using binomial coefficients for a different amount of work
  34 # (computing comb(n,k) will still require recursion, and 20! doesn't fit in
  35 # 32 bits, so it may not be worth trying)
  36
  37 define(`_merge', `eval($1 - $2), eval($3 + $4)')
  38 define(`merge', `ifelse(`$1', `', `$0(`$2', eval($3 - $2)`,', shift(shift($@)))',
  39   `$2$3$4', `0,0', `0,', `$4', `', `_$0($1, $0(`', $2), $3)',
  40   `$0(`$1', `$2'eval($4 - $3)`,', shift(shift(shift($@))))')')
  41 define(`run', `define(`part2', `$1')define(`part1', `$2')')
  42 run(merge(forloop(0, decr(n), `,defn(`n'', `)')))
  43
  44 divert`'part1
  45 part2