2015/day13.m4

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