2018/day23.m4

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