2015/day9.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dfile=day9.input] day9.m4
   3
   4 include(`common.m4')ifelse(common(9), `ok', `',
   5 `errprint(`Missing common initialization
   6 ')m4exit(1)')
   7
   8 define(`input', translit(include(defn(`file')), nl, `;'))
   9 define(`part1', 0)define(`part2', 0)define(`n', 0)
  10 define(`lookup', `ifdef(`$1_', `', `define(`n', incr(n))define(`$1_',
  11   n)')$1_()')
  12 define(`line', `_$0(translit(`$1', ` ', `,'))')
  13 define(`_line', `define(`part1', eval(part1 + $5))define(
  14   `d'lookup(`$1')`_'lookup(`$3'), $5)')
  15 ifdef(`__gnu__', `
  16   patsubst(defn(`input'), `\([^;]*\);', `line(`\1')')
  17 ',`
  18   define(`chew', `line(substr(`$1', 0, index(`$1', `;')))define(`tail',
  19     substr(`$1', incr(index(`$1', `;'))))ifelse(index(defn(
  20     `tail'), `;'), -1, `', `$0(defn(`tail'))')')
  21   define(`split', `ifelse(eval($1 < 65), 1, `chew(`$2')', `$0(eval($1/2),
  22     substr(`$2', 0, eval($1/2)))$0(eval(len(defn(`tail')) + $1 - $1/2),
  23     defn(`tail')substr(`$2', eval($1/2)))')')
  24   split(len(defn(`input')), defn(`input'))
  25 ')
  26
  27 # Lifted from Sawada-Williams' sigma-tau algorithm, mentioned at
  28 # https://en.wikipedia.org/wiki/Permutation#Generation_with_minimal_changes
  29 # Hard-coded to 8 here for less expansion of n, but could easily be extended
  30 ifelse(n, 8, `', `errprintn(`unexpected input length')m4exit(1)')
  31 define(`swap', `ifelse($1, 'n`, `define(`next', $3)', $2, 'n`,
  32   `define(`next', $1)', next, $1, `define(`next', $2)')$2,$1,shift(shift($@))')
  33 define(`rot', `shift($@),$1')
  34 define(`fact', `ifelse($1, 1, 1, `eval($1 * fact(decr($1)))')')
  35 define(`base', quote(shift(forloop_rev(n, 1, `,'))))
  36 define(`check', `_$0(ifelse($1, 'n`, $3, next), $2)')
  37 define(`_check', `eval($2 == $1 * ($1 < 'decr(n)`) + 1)')
  38 define(`permute', `_$0(fact(n), (swap(base)))')
  39 define(`_permute', `ifelse($1, 0, `', `try$2$0(decr($1), (ifelse(`$2',
  40   ''dquote(dquote((base)))``, `rot', check$2, 1, `swap', `rot')$2))')')
  41
  42 define(`d', `defn(`d$1_$2')defn(`d$2_$1')')
  43 define(`try', `_$0(eval(d($1, $2) + d($2, $3) + d($3, $4) + d($4, $5) +
  44   d($5, $6) + d($6, $7) + d($7, $8)))')
  45 define(`_try', `ifelse(eval($1 < part1), 1, `define(`part1', $1)')ifelse(
  46   eval($1 > part2), 1, `define(`part2', $1)')')
  47 permute(n)
  48
  49 divert`'part1
  50 part2