2018/day25.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dfile=day25.input] day25.m4
   3 # Optionally use -Dverbose=1 to see some progress
   4 # Optionally use -Dalgo=quad|linear to choose search algorithm
   5 # Optionally use -Dunion=direct|rank to choose union-find algorithm
   6
   7 include(`common.m4')ifelse(common(25), `ok', `',
   8 `errprint(`Missing common initialization
   9 ')m4exit(1)')
  10
  11 ifdef(`algo', `', `define(`algo', `linear')')
  12 ifdef(`union', `', `define(`union', `direct')')
  13
  14 define(`input', translit((include(defn(`file'))), nl`,()', `;.'))
  15 define(`cnt', 0)define(`min', 0)define(`max', 0)
  16 define(`bump', `ifelse(eval($1<min), 1, `define(`min', $1)', eval($1>max), 1,
  17   `define(`max', $1)')')
  18 define(`line', `_$0(cnt, translit(`$1', `.', `,'))')
  19 define(`_line', `define(`p$1', `$2,$3,$4,$5')define(`cnt', incr($1))bump(
  20   $2)bump($3)bump($4)bump($5)')
  21 ifdef(`__gnu__', `
  22   patsubst(defn(`input'), `\([^;]*\);', `line(`\1')')
  23 ', `
  24   define(`_chew', `line(substr(`$1', 0, index(`$1', `;')))define(`tail',
  25     substr(`$1', incr(index(`$1', `;'))))ifelse(index(defn(`tail'), `;'), -1,
  26     `', `$0(defn(`tail'))')')
  27   define(`chew', `ifelse(eval(`$1 < 24'), 1, `_$0(`$2')', `$0(eval(`$1/2'),
  28     substr(`$2', 0, eval(`$1/2')))$0(eval(len(defn(`tail'))` + $1 - $1/2'),
  29     defn(`tail')substr(`$2', eval(`$1/2')))')')
  30   chew(len(defn(`input')), defn(`input'))
  31 ')
  32
  33 define(`progress', `ifelse(eval($1%100), 0, `output(1, ...$1)')')
  34 define(`diff', ``($1<$2)*($2- $1)+($2<$1)*($1- $2)'')
  35 define(`dist', `diff($1, $5)+diff($2, $6)+diff($3, $7)+diff($4, $8)')
  36
  37 ifelse(union, `direct', `
  38 output(1, `using linear union-find by child chaining')
  39 # Naive union-find, with worst-case O(n) find
  40 define(`makeset', `define(`c$1', $1)')
  41 define(`merge', `_$0(c$1, c$2)')
  42 define(`_merge', `ifelse($1, $2, `', eval($2>$1), 1, `define(`c$2', `c$1')',
  43   `define(`c$1', `c$2')')')
  44 define(`_sets', `ifdef(`C$1', `', `-define(`C$1')')')
  45 define(`sets', `len(forloop(0, decr(cnt), `_$0(first(`c'', `))'))')
  46
  47 ', union, `rank', `
  48 output(1, `using amortized constant union-find by rank and path compression')
  49 # Amortized O(1) Union-find with path compression and union by rank
  50 # A `r'oot node has a rank; a `c'hild node has a parent; also track sets count
  51 define(`sets', 0)
  52 define(`makeset', `define(`sets', incr(sets))define(`r$1', 0)')
  53 define(`find', `ifdef(`r$1', `$1, r$1', `_$0($1, c$1)')')
  54 define(`_find', `ifdef(`r$2', `$2, r$2', `$0_($1, c$2)')')
  55 define(`_find_', `define(`c$1', $2)find($2)')
  56 define(`merge', `_$0(find($1), find($2))')
  57 define(`_merge', `ifelse($1, $3, `', `$0_(ifelse(eval($2 < $4), 1, `$3, $1',
  58   $2, $4, `$1, $3define(`r$1', incr($2))', `$1, $3'))')')
  59 define(`_merge_', `define(`c$2', $1)popdef(`r$2')define(`sets', decr(sets))')
  60
  61 ', `fatal(`unrecognized -Dunion= value')')
  62
  63 ifelse(algo, `quad', `
  64 output(1, `using quadratic pair-wise comparison')
  65 define(`check', `progress($1)makeset($1)forloop(0, decr($1), `_$0(', `, $1)')')
  66 define(`_check', `ifelse(eval(dist(p$1, p$2) <= 3), 1, `merge($1, $2)')')
  67 makeset(0)
  68 forloop_arg(1, decr(cnt), `check')
  69
  70 ', algo, `linear', `
  71 output(1, `using linear grid comparison')
  72 # Valid input files have abs(coord)<=8; the sample file has coords [0-12]
  73 ifelse(eval(max - min > 17), 1, `fatal(`input grid too large')')
  74 define(`offset', eval(3 - min))
  75 # Map 4D points into 1D space with all positive coordinates
  76 define(`map', `_$0(p$1, 'offset`)')
  77 define(`_map', `eval(($1+$5)+($2+$5)*23+($3+$5)*23*23+($4+$5)*23*23*23)')
  78 define(`mark', `define(`g'map($1), $1)makeset($1)')
  79 forloop_arg(0, decr(cnt), `mark')
  80 # Pre-compute the list of all base-23 offsets that form all 128 neighbors
  81 # within Manhattan distance 3 of the given point. This comes from:
  82 # 0,0,0,3 * 4 orderings * 2 signs
  83 # 0,0,0,1 * 4 orderings * 2 signs
  84 # 0,0,1,1 * 6 orderings * 4 signs
  85 # 0,0,0,2 * 4 orderings * 2 signs
  86 # 0,0,1,2 * 12 orderings * 4 signs
  87 # 0,1,1,1 * 4 orderings * 8 signs
  88 # But rather than list all 128 variations manually, comb through a
  89 # 5x5x5x5 hypercube for 120 of the neighbors.
  90 _foreach(`pushdef(`list', _map(first(', `), 0))', `', `0,0,0,3', `0,0,0,-3',
  91   `0,0,3,0', `0,0,-3,0', `0,3,0,0', `0,-3,0,0', `3,0,0,0', `-3,0,0,0')
  92 define(`prep', `ifelse($1, 2222, `', `translit(`_$0(A,B,C,D)', `ABCD', $1)')')
  93 define(`_prep', `ifelse(eval(dist($1,$2,$3,$4,2,2,2,2)<=3), 1, `pushdef(`list',
  94   _map($1, $2, $3, $4, -2))')')
  95 forloop(0, eval(5*5*5*5-1), `prep(eval(', `, 5, 4))')
  96 define(`_near', ``check(eval($4$1+$3), $4$2)'')
  97 define(`near', _stack_foreach(`list', `_near(1, 2, ', `, `$')', `t'))
  98 define(`process', `progress($1)near(map($1), $1)')
  99 define(`check', `ifdef(`g$1', `merge($2, g$1)')')
 100 forloop_arg(0, decr(cnt), `process')
 101
 102 ', `fatal(`unrecognized -Dalgo= value')')
 103
 104 define(`part1', sets)
 105
 106 divert`'part1
 107 no part2