2016/day24.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dhashsize=H] [-Dfile=day24.input] day24.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(24, 65537), `ok', `',
   7 `errprint(`Missing common initialization
   8 ')m4exit(1)')
   9
  10 include(`priority.m4')
  11 define(`input', translit(include(defn(`file')), `#'nl, `@;'))
  12 define(`x', 0)define(`y', 0)define(`max', 0)
  13 define(`visit', `ifelse(`$1', `;', `define(`x', 0)define(`y', incr(y))',
  14   `ifelse(`$1', `@', `', `define(`p'x`_'y, $1)ifelse(`$1', `.', `',
  15   `define(`c$1', x`,'y)ifelse(eval($1 > max), 1, `define(`max',
  16   $1)')')')define(`x', incr(x))')')
  17 ifdef(`__gnu__', `
  18   patsubst(defn(`input'), `.', `visit(`\&')')
  19 ',`
  20   define(`split', `ifelse($1, 1, `visit(`$2')', `$0(eval($1/2), substr(`$2',
  21     0, eval($1/2)))$0(eval($1 - $1/2), substr(`$2', eval($1/2)))')')
  22   split(len(defn(`input')), defn(`input'))
  23 ')
  24
  25 define(`goal', eval((1 << (max + 1)) - 1))
  26 pushdef(`clearall')
  27 define(`clean', `ifdef(`s', `popdef(`g'defn(`s'))popdef(`f'defn(`s'))popdef(
  28   `s')$0()', `clearall()')')
  29 define(`scans', 0)
  30 define(`scan', `output(2, `scanning from $1')pushdef(`seen',
  31   eval((1 << ($1 + 1)) - 1))add(c$1, 0)_$0(0, 1, $1)popdef(`seen')clean()')
  32 define(`_scan', `ifelse(seen, 'goal`, `undefine(`s$1')', `ifdef(`s$1',
  33   `near(s$1, $1, $2, $3)popdef(`s$1')$0($@)', `$0($2, incr($2), $3)')')')
  34 define(`add', `ifdef(`p$1_$2', `ifdef(`g$1_$2', `', `define(`scans',
  35   incr(scans))define(`g$1_$2')pushdef(`s', `$1_$2')pushdef(`s$3',
  36   `$1,$2')')')')
  37 define(`near', `_$0(p$1_$2, $3, $5)add($1, decr($2), $4)add(incr($1), $2,
  38   $4)add($1, incr($2), $4)add(decr($1), $2, $4)')
  39 define(`_near', `ifelse($1, $3, `', $1, `.', `', `ifdef(`d$1_$3', `',
  40   `define(`d$1_$3', $2)define(`d$3_$1', $2)define(`seen',
  41   eval(seen | (1 << $1)))')')')
  42 forloop_arg(0, decr(max), `scan')
  43 output(1, `distances between pairs determined, scans:'scans)
  44
  45 define(`hit', 0)
  46 define(`miss', 0)
  47 define(`iter', 0)
  48 define(`progress', `define(`$1', incr($1))ifelse(eval((hit + miss + iter) %
  49   10000), 0, `output(2, `progress:'eval(hit + miss + iter))')')
  50
  51 popdef(`clearall')
  52 define(`addwork', `ifelse(ifdef(`g$1_$2', `eval($3 < g$1_$2)', 1), 1,
  53   `pushdef(`s', `$1_$2')define(`g$1_$2', `$3')_$0(eval($3 + heur($1, $2)),
  54   $1, $2)')')
  55 define(`_addwork', `define(`f$2_$3', $1)progress(`hit')insert($@)')
  56 define(`loop', `ifelse(eval($1 > f$2_$3), 1, `progress(`miss')$0(pop)',
  57   `ifelse(match($2, $3), `$1', `progress(`iter')neighbors($2, $3,
  58   g$2_$3)$0(pop)')')')
  59
  60 # State: bitmap of nodes still needed, current node
  61 # Heuristic: distance to closest node of interest
  62 define(`path', `addwork(eval((1 << (max+1)) - 2), 0, 0)loop(pop)clean()')
  63 define(`match', `$1, 0')
  64 define(`check', `ifelse(eval($1 & (1 << $2)), 0, `', `d$3_$2,')')
  65 define(`heur', `ifelse(`$1', 0, 0, $1, 1, `d0_$2', `_$0(forloop(1, max,
  66   `check(`$1', ', `, `$2')'))')')
  67 define(`_heur', `ifelse($2, `', $1, `$0(ifelse(eval($1 < $2), 1, $1, $2),
  68   shift(shift(@)))')')
  69 define(`neighbors', `ifelse($1, 1, `_$0($1, 0, $2, $3)', `forloop(1, max,
  70   `_$0($1,', `, $2, $3)')')')
  71 define(`_neighbors', `ifelse(eval($1 & (1 << $2)), 0, `', `addwork(eval(
  72   $1 & ~(1 << $2)), $2, eval(d$2_$3 + $4))')')
  73 define(`part1', path)
  74
  75 define(`path', `addwork(eval((1 << (max+1)) - 1), 0, 0)loop(pop)clean()')
  76 define(`part2', path)
  77
  78 output(1, `hits:'hit` misses:'miss` iters:'iter)
  79
  80 divert`'part1
  81 part2