2016/day13.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dseed=NNN] [-Dhashsize=H] [-Dfile=day13.input] day13.m4
   3 # Optionally use -Dverbose=[12] to see some progress
   4 # Optionally use -Dpriority=1|2|3|4|5 to choose priority queue algorithms
   5
   6 include(`common.m4')ifelse(common(13, 65537), `ok', `',
   7 `errprint(`Missing common initialization
   8 ')m4exit(1)')
   9
  10 include(`priority.m4')
  11 ifdef(`seed', `', `define(`seed', translit(include(defn(`file')), nl))')
  12
  13 define(`abs', `ifelse(index(`$1', -), 0, `substr(`$1', 1)',  `$1')')
  14 define(`heur', `ifelse(eval($3 <= 50), 1, 0, `abs(eval($1 - 31)) +
  15   abs(eval($2 - 39))')')
  16 define(`at', `ifdef(`a$1_$2', `', `define(`a$1_$2', eval(len(translit(eval(
  17   `$1*$1 + 3*$1 + 2*$1*$2 + $2 + $2*$2 + 'seed, 2), `0')) % 2))a$1_$2')')
  18 define(`neighbors', `ifelse($1, 0, `', `_$0(decr($1), $2, $3)')ifelse($2, 0,
  19   `', `_$0($1, decr($2), $3)')_$0(incr($1), $2, $3)_$0($1, incr($2), $3)')
  20 define(`_neighbors', `ifelse(at($1, $2), 0, `addwork($1, $2, $3)')')
  21
  22 define(`hit', 0)
  23 define(`miss', 0)
  24 define(`iter', 0)
  25 define(`progress', `define(`$1', incr($1))ifelse(eval((hit + miss + iter) %
  26   10000), 0, `output(2, `progress:'eval(hit + miss + iter))')')
  27
  28 define(`part2', 0)
  29 define(`addwork', `ifelse(ifdef(`g$1_$2', `ifelse(eval($3 <= 50 &&
  30   g$1_$2 > 50), 1, `define(`part2', incr(part2))')eval($3 < g$1_$2)',
  31   `ifelse(eval($3 <= 50), 1, `define(`part2', incr(part2))')1'), 1,
  32   `define(`g$1_$2', `$3')_$0(eval($3 + heur($1, $2, $3)), $1, $2)')')
  33 define(`_addwork', `define(`f$2_$3', $1)progress(`hit')insert($@)')
  34 define(`distance', `addwork(1, 1, 0)loop(pop)clearall()')
  35 define(`loop', `ifelse($1, `', ``no solution possible'', eval($1 > f$2_$3), 1,
  36   `progress(`miss')loop(pop)', `$2_$3', 31_39, `$1', `progress(
  37   `iter')neighbors($2, $3, incr(g$2_$3))loop(pop)')')
  38
  39 define(`part1', distance())
  40 output(1, `hits:'hit` misses:'miss` iters:'iter)
  41
  42 divert`'part1
  43 part2