2015/day24.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dfile=day24.input] [-Dhashsize=H] day24.m4
   3 # Optionally use -Dverbose=1 to see some progress
   4
   5 include(`common.m4')ifelse(common(24, 65537), `ok', `',
   6 `errprint(`Missing common initialization
   7 ')m4exit(1)')
   8
   9 include(`math64.m4')
  10 define(`n', 0)define(`sum', 0)define(`even', 0)
  11 define(`item', `ifelse($1, `', `', `define(`i'n, $1)define(`n',
  12   incr(n))ifelse(eval($1 % 2), 0, `define(`even', 1)')define(`sum',
  13   eval(sum + $1))$0(shift($@))')')
  14 item(translit(include(defn(`file')), nl, `,'))
  15 define(`cnt', 0)
  16 define(`bump', `ifelse(eval(cnt % 100), 0, `output(1, ...cnt)')define(`cnt',
  17   incr(cnt))')
  18
  19 define(`body1', `_$0(eval($1 + i$2), $2)')
  20 define(`_body1', `ifelse(eval(0 < $1 - target), 0, `ifdef(`li$1', `define(
  21   `li$1', defn(`li$1')`,$2')', `define(`li$1', $2)pushdef(`li', $1)')')')
  22 define(`body0', `_foreach(`body1(', `, $1)',
  23   _stack_foreach(`li', `,', `', `t'))')
  24 define(`recur', `ifdef(`r$1_$2', `', `define(`r$1_$2', _foreach(`_$0(',
  25   `, $@)', `', li$1))bump()')r$1_$2`'')
  26 define(`_recur', `ifelse($1, -1, ``, `''', eval($3 <= $1), 0,
  27   `_foreach(`body2(i$1, ', `, $4)', recur(eval($2 - i$1), $1, decr($4)))')')
  28 define(`body2', `ifelse(eval(_$0($2) <= $3), 1, ``, `$2,$1''')')
  29 define(`_body2', `$#')
  30
  31 define(`find', `_$0(incr($1), eval($2 + defn(`i'eval(n - $1 - 1))))')
  32 define(`_find', `ifelse(eval($2 >= target && (even ||
  33   (target & 1) == ($2 & 1))), 1, $1, `find($@)')')
  34 define(`prod', `ifelse($2, `', $1, `$0(mul64($1, $2), shift(shift($@)))')')
  35 define(`check', `ifelse(ifdef(`best', `lt64($1, best)', 1), 1,
  36   `define(`best', $1)')')
  37
  38 define(`clean', `ifdef(`li', `undefine(`li'li)popdef(`li')$0()',
  39   `popdef(`maxlen')popdef(`target')best`'popdef(`best')')')
  40 define(`subsets', `pushdef(`target', $1)pushdef(`maxlen', find(0, 0))output(1,
  41   `prepping groups of length 'maxlen` adding to 'target)define(`li0',
  42   -1)pushdef(`li', 0)forloop_arg(0, decr(n), `body0')output(1,
  43   `collecting groups')_foreach(`check(prod(1first(', `)))', recur($1,
  44   n, maxlen)output(1, `finding best quantum entanglement'))clean()')
  45
  46 define(`part1', subsets(eval(sum / 3)))
  47 define(`part2', subsets(eval(sum / 4)))
  48
  49 divert`'part1
  50 part2