2018/day23.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dfile=day23.input] day23.m4
   3
   4 include(`common.m4')ifelse(common(23), `ok', `',
   5 `errprint(`Missing common initialization
   6 ')m4exit(1)')
   7
   8 include(`priority.m4')
   9
  10 define(`count', 0)define(`bestp', 0)define(`bestr', 0)
  11 define(`Pos', `_$0(count, $@)')
  12 define(`_Pos', `define(`p$1', `$2,$3,$4,$5')ifelse(eval($5>bestr), 1,
  13   `define(`bestp', $1)define(`bestr', $5)')define(`count', incr($1))')
  14 translit((include(defn(`file'))), `p<'nl` =r>', `P()')
  15 define(`diff', ``($1<$2)*($2- $1)+($2<$1)*($1- $2)'')
  16 define(`prep', `_$0(p$1, $1, 'defn(`p'bestp)`)')
  17 define(`_prep', `+eval(diff(`$1', `$6')+diff(`$2', `$7')+diff(`$3',
  18   `$8')`<=$9')store(eval(translit(``$1+$2+$3'', -)), `$4', `$5')')
  19 define(`store', `insert(eval(`($1-$2)*($1>$2)'), $3)insert(eval(`$1+$2+1'))')
  20 define(`part1', eval(forloop_arg(0, decr(count), `prep')))
  21
  22 define(`loop', `ifelse(`$4', `', `$3define(`max', $2)', `_$0(ifelse($5, `',
  23   `decr($1)', `incr($1)define(`i$1', defn(`i$1')`,$5,$4')'), $2, $3, $4)')')
  24 define(`_loop', `loop($1, ifelse(eval($1>$2), 1, `$1, $4', `$2, $3'), pop)')
  25 define(`part2', loop(0, 0, 0, pop))
  26 # We rely on an assumption that the input files have bots aligned such that
  27 # the highest overlap in Manhattan distance to origin without regard to
  28 # direction will work. There are smaller counterexamples where this does
  29 # not hold; try and detect those. If an actual input file fails, then the
  30 # solution can be made more robust by checking which of the top 10 or so
  31 # points starting from max downward has the most intersections, but it will
  32 # add some runtime.  The most robust would be an O(n^2) check of intersections
  33 # seen from each point, then maximize M for the set of M points with at least
  34 # M intersections, picking the distance of the furthest of those M points,
  35 # but as long as an O(n) filter gives the right answer for our input, use it!
  36 define(`sanity', `ifelse(`$4', `', `', `define(`part2',
  37   `fatal(`more than one potential best overlap: 'max`$*')')')')
  38 sanity(first(`i'decr(max)))
  39
  40 divert`'part1
  41 part2