2019/day14.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dfile=day14.input] day14.m4
   3
   4 include(`common.m4')ifelse(common(14), `ok', `',
   5 `errprint(`Missing common initialization
   6 ')m4exit(1)')
   7
   8 include(`math64.m4')
   9
  10 define(`goal', 1000000000000)
  11 define(`input', translit((include(defn(`file'))), nl` >,()', `;.'))
  12 define(`line', `_$0(translit(`$1', `=', `,'))')
  13 define(`_line', `define(`l'target(translit(`$2', `.', `,')),
  14   build(translit(`$1', `.', `,')))')
  15 define(`build', `ifelse(`$2', `', `', ``produce(`$2', $'`1, $1)'$0(
  16   shift(shift($@)))')')
  17 define(`target', `define(`n$3', $2)`$3'')
  18 ifdef(`__gnu__', `
  19   patsubst(defn(`input'), `\([^;]*\);', `line(`\1')')
  20 ', `
  21   define(`_chew', `line(substr(`$1', 0, index(`$1', `;')))define(`tail',
  22     substr(`$1', incr(index(`$1', `;'))))ifelse(index(defn(`tail'), `;'), -1,
  23     `', `$0(defn(`tail'))')')
  24   define(`chew', `ifelse(eval(`$1 < 175'), 1, `_$0(`$2')', `$0(eval(`$1/2'),
  25     substr(`$2', 0, eval(`$1/2')))$0(eval(len(defn(`tail'))` + $1 - $1/2'),
  26     defn(`tail')substr(`$2', eval(`$1/2')))')')
  27   chew(len(defn(`input')), defn(`input'))
  28 ')
  29
  30 # Use produce to create list as topological sort
  31 define(`produce', `ifdef(`s$1', `', `l$1(0)define(`s$1')pushdef(`t', `$1')')')
  32 define(`sORE')define(`l', `FUEL')
  33 lFUEL(0)stack_reverse(`t', `l')
  34
  35 # Now use produce to accumulate
  36 define(`produce', `define(`a$1', add64(a$1, mul64($2, $3)))')
  37 define(`bits', `_$0(eval($1, 2))')
  38 define(`_bits', ifdef(`__gnu__', ``shift(patsubst($1, ., `, \&'))'',
  39   ``ifelse(len($1), 1, `$1', `substr($1, 0, 1),$0(substr($1, 1))')''))
  40 define(`bits64', `ifelse(eval(len($1) < 10), 1, `bits($1)', `_$0(mul64($1,
  41   5)), eval(substr($1, decr(len($1))) & 1)')')
  42 define(`_bits64', `bits64(substr($1, 0, decr(len($1))))')
  43 define(`div64', `ifelse($4, `', `$1,$2', `$0(_$0(add64($1, $1), add64(add64($2,
  44   $2), $4), $3), $3, shift(shift(shift(shift($@)))))')')
  45 define(`_div64', `ifelse(lt64($2, $3), 0, `add64($1, 1), sub64($2, $3)',
  46   `$1, $2')')
  47 define(`divup', `ifelse(eval(len($1) < 10), 1, `eval(($1+$2-1)/$2)',
  48   `_$0(div64(0, 0, $2, bits64($1)))')')
  49 define(`_divup', `ifelse($2, 0, $1, `add64($1, 1)')')
  50 define(`_use', `l$1(divup(a$1, n$1))')
  51 define(`use', `define(`aORE', 0)stack_reverse(`l', `t', `define(`a'defn(`l'),
  52   0)')define(`aFUEL', $1)stack_reverse(`t', `l', `_$0(defn(`l'))')aORE')
  53 define(`part1', use(1))
  54
  55 define(`cache', `ifdef(`u$1', `', `define(`u$1', use($1))')u$1')
  56 define(`try', `_$0($1, cache($1), cache(add64($1, 1)), 'goal`)')
  57 define(`_try', `ifelse(lt64($2, $4), 1, `ifelse(lt64($4, $3), 1, $1,
  58   `try(add64($1, divup(sub64($4, $3), divup($3, $1))))')',
  59   `try(sub64($1, divup(sub64($2, $4), divup($2, $1))))')')
  60 define(`part2', try(divup(goal, part1)))
  61
  62 ')divert`'part1
  63 part2