2015/day20.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dstart=NNN] [-Dtarget=NNN] [-Dfile=day20.input] day20.m4
   3 # Optionally use -Dverbose=1 to see some progress
   4
   5 include(`common.m4')ifelse(common(20), `ok', `',
   6 `errprint(`Missing common initialization
   7 ')m4exit(1)')
   8
   9 ifdef(`target', `', `define(`target', translit(include(defn(`file')), nl))')
  10 define(`bound', eval(target / 11)0)
  11 # Per https://en.wikipedia.org/wiki/Highly_abundant_number, we want a highly
  12 # abundant (HA) number.  360360 is HA with sum 1572480, and all HA numbers
  13 # > 630 are divisible by 12; so limit our search bounds.
  14 ifelse(eval(target / 10 < 1572480), 1, `errprintn(`unexpected input')m4exit(1)')
  15 define(`start', ifdef(`start', `eval((start + 11) / 12)', 360360))
  16
  17 define(`n2', 3)define(`n3', 5)define(`n5', 7)
  18 define(`nextp', `ifdef(`n$1', `', `define(`n$1', _$0(incr(incr($1))))')n$1')
  19 define(`_nextp', `ifelse(eval($1 % 3 && $1 % 5), 0, `$0(incr(incr($1)))',
  20   `ifelse(nargs(factor($1)), 2, $1, `$0(incr(incr($1)))')')')
  21 define(nargs, `$#')
  22 define(`factor', `ifelse($1, 1, `', `ifelse(eval($1 & 1), 0,
  23   `,2$0(eval($1 >> 1))', `_$0($1, 3)')')')
  24 define(`_factor', `ifelse($1, 1, `', `ifelse(eval($2 * $2 > $1), 1, `,$1',
  25   `ifelse(eval($1 % $2), 0, `,$2$0(eval($1 / $2), $2)',
  26   `$0($1, nextp($2))')')')')
  27
  28 define(`total', `_$0(10, $2, shift($@))')
  29 define(`_total', `ifelse(`$#', 3, `eval($1 * (($2 * $3) - 1) / ($3 - 1))', $3,
  30   $4, `$0($1, $2 * $3, shift(shift(shift($@))))', `$0(eval($1 * (($2 * $3) - 1)
  31   / ($3 - 1)), $4, shift(shift(shift($@))))')')
  32 define(`best', 10)
  33 define(`try', `_$0($1factor($1))')
  34 define(`_try', `ifelse(eval(`$# > 8'), 1, `_$0(total($@), $1)')')
  35 define(`__try', `ifelse(eval($1 > best), 1, `define(`best', $1)')ifdef(
  36   `start', `', `ifelse(eval($1 > bound), 1, `define(`start', $2)')')')
  37 define(`iter', `ifelse(eval($1 % 6000), 0, `output(1, `$1 'best)')try(
  38   $1)ifelse(eval(best < target), 1, `$0(eval($1 + 12), `$2')',
  39   `define(`$2', $1)')')
  40 iter(start`'popdef(`start'), `part1')
  41
  42 define(`divisors50', `eval(11 * (_$0($1, 50)))')
  43 define(`_divisors50', `$1ifelse(eval($1 & 1), 0, `_$0($1, $2, 2)')_$0($1,
  44   $2, 3)')
  45 define(`__divisors50', `ifelse(eval($3 > $2), 1, `', `ifelse(eval($1 % $3), 0,
  46   `+ eval($1 / $3)')$0($1, $2, incr(incr($3)))')')
  47 define(`best', 10)
  48 define(`try', `_$0(divisors50($1))')
  49 define(`_try', `ifelse(eval($1 > best), 1, `define(`best', $1)')')
  50 iter(start, `part2')
  51
  52 divert`'part1
  53 part2