2016/day19.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dmax=NNN] [-Dfile=day19.input] day19.m4
   3
   4 include(`common.m4')ifelse(common(19), `ok', `',
   5 `errprint(`Missing common initialization
   6 ')m4exit(1)')
   7
   8 ifdef(`max', `', `define(`max', translit(include(defn(`file')), nl))')
   9 # Josephus problem has a closed form - bitwise rotate left by 1:
  10 # https://en.wikipedia.org/wiki/Josephus_problem
  11 define(`msb', `eval(1 << len(eval($1, 2)) - 1)')
  12 define(`part1', eval(2 * (max - msb(max)) + 1))
  13 # Even the modified problem has a pattern: between each power of 3,
  14 # the first half increments by 1, the second half by 2
  15 # (ie. 10-18 -> 1-9, 19-27 -> 11-27; 28-54 -> 1-27, 55-81 -> 29-81)
  16 define(`while', `ifelse($1, 1, `$2`'$0($@)')')
  17 define(`n', 3)
  18 while(`eval(n <= max)', `define(`n', eval(n * 3))')
  19 define(`part2', ifelse(eval(max <= n/3*2), 1, `eval(max - n/3)',
  20   `eval(2 * max - n)'))
  21
  22 divert`'part1
  23 part2