2023/day21.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dfile=day21.input] day21.m4
   3 # Optionally use -Dstop1=N -Dstop2=N to stop each part after N steps
   4
   5 include(`common.m4')ifelse(common(21), `ok', `',
   6 `errprint(`Missing common initialization
   7 ')m4exit(1)')
   8
   9 define(`input', translit(include(defn(`file')), `#.S'nl, `0123'))
  10 define(`x', 1)define(`y', 1)
  11 define(`do0', `define(`x', incr($1))')
  12 define(`do1', `define(`g$1_$2')do0($@)')
  13 define(`do2', `define(`start', `$@')do1($@)')
  14 define(`do3', `define(`maxx', $1)define(`x', 1)define(`y', incr($2))')
  15
  16 ifdef(`__gnu__', `
  17   patsubst(defn(`input'), `.', `do\&(x, y)')
  18 ',`
  19   define(`chew', `ifelse($1, 1, `do$2(x, y)', `$0(eval($1/2), substr(
  20     `$2', 0, eval($1/2)))$0(eval($1-$1/2), substr(`$2', eval($1/2)))')')
  21   chew(len(defn(`input')), defn(`input'))
  22 ')
  23
  24 define(`t0', 1)define(`t1', `0')
  25 define(`p', `ifdef(`g$1_$2', `ifdef(`d$1_$2', `', `addwork($@)')')')
  26 define(`visit', `p(incr($1), $2, $3)p($1, incr($2), $3)p(decr($1), $2,
  27   $3)p($1, decr($2), $3)')
  28 define(`addwork', `define(`step$3', incr(step$3))define(`d$1_$2')pushdef(`d',
  29   `d$1_$2')pushdef(`set$3', `visit($1, $2, t$3)')')
  30 define(`_round', `ifdef(`set$1', `set$1()popdef(`set$1')$0($@)')')
  31 define(`round', `_$0(eval(1^$1&1), $1)')
  32 define(`_reset', `ifdef(`d', `popdef(defn(`d'))popdef(`d')$0()',
  33   `undefine(`set0')undefine(`set1')')')
  34 define(`reset', `_$0()define(`step0', 0)define(`step1', 0)addwork($1, $2, 0)')
  35 define(`pick', `ifelse(eval(($1)&1), 0, `$2'0, `$2'1)')
  36
  37 # Assumption: regular input has nice property of being a square tile, with
  38 # odd number of rows and columns, and with all center and edge row/columns
  39 # being open.  The example input does not meet this property.  I'm not
  40 # interested in solving the example input for part 2, as that's harder.
  41 ifelse(ifdef(`g'first(start)`_'incr(shift(start)), 1), 0, `
  42 ifdef(`stop1', `', `define(`stop1', 6)')
  43 define(`part2', ``detected sample input, skipping part 2'')
  44 reset(start)
  45 forloop_arg(1, stop1, `round')
  46 define(`part1', pick(stop1, `step'))
  47 ', eval(maxx != y || first(start) * 2 != y).first(start), 1.shift(start),
  48 `fatal(`unexpected input layout')', `
  49
  50 ifdef(`stop1', `', `define(`stop1', 64)')
  51 ifdef(`stop2', `', `define(`stop2', 26501365)')
  52 reset(start)
  53 forloop_arg(1, stop1, `round')
  54 define(`part1', pick(stop1, `step'))
  55
  56 # Because of the assumptions, each interior tile will be completely
  57 # visited; the problem then boils down to counting how many interior
  58 # tiles there are, plus the partial contributions of each frontier
  59 # tile based on the point where the tile is first reached.
  60 #
  61 #        4      5--1--6
  62 #       847     |..|..|
  63 #      88477    |..|..|
  64 #     333S222   2--S--3
  65 #      66155    |..|..|
  66 #       615     |..|..|
  67 #        1      7--4--8
  68 #
  69 # When maxx/y is 8, there are 7 rows/columns.  Step 0 is at S, step 4 enters
  70 # the four side tiles [1234], step 8 enters the four diagonal tiles [5678],
  71 # step 11 starts the next sides, step 15 starts the next set of diagonal tiles,
  72 # and so on.  For my input, y is 132; starting at S covers all possible
  73 # positions in the tile within y moves; but starting at any corner takes 261
  74 # steps before full coverage.  There are probably inputs with worse cases
  75 # (think of a tight spiral in one quarter), but for now I will only worry
  76 # about the outer two shells, assuming all other shells reached full coverage.
  77 # Because there are an odd number of rows/columns, every other full shell
  78 # alternates between step0 and step1 coverage values.
  79 define(`finish', `round($1)ifelse(step0.step1, $2.$3, $1, `$0(incr($1),
  80   step0, step1)')')
  81 define(`mid', first(start)) # also y/2
  82 define(`wide', decr(y))
  83 ifelse(eval(finish(incr(stop1), step0, step1)>2*wide || stop2<2*wide+mid), 1,
  84   `fatal(`unexpected bound')')
  85 define(`full0', step0)define(`full1', step1)
  86 define(`full', `pick($1, `$0')')
  87 include(`math64.m4')
  88
  89 # Contribution from tile S
  90 define(`part2', full(stop2))
  91
  92 # Contribution from tiles 1,2,3,4; occur at mid + wide*N, in row or column
  93 define(`reached', eval((stop2+mid-1)/wide))
  94 define(`part2', add64(part2, mul64(4, add64(mul64(eval(reached/2 - 1),
  95   eval(full0+full1)), eval((reached&1)*full(1^mid^stop2))))))
  96 define(`limit1', eval((stop2-mid)%wide+1))
  97 define(`limit2', eval(limit1+wide))
  98 define(`addedge', `define(`part2', add64(part2, add64(reset($@)forloop_arg(1,
  99   limit1, `round')pick(limit2, `step'), forloop_arg(incr(limit1), limit2,
 100   `round')pick(limit1, `step'))))')
 101 addedge(1, mid)addedge(mid, 1)addedge(mid, wide)addedge(wide, mid)
 102
 103 # Contribution from tiles 5,6,7,8; occur at y + wide*N, on diagonals
 104 define(`dreached', eval((stop2-1)/wide))
 105 define(`part2', add64(part2, mul64(4, add64(mul64(mul64(eval(dreached/2),
 106   eval((dreached-1)/2)), full(1^dreached^stop2)), mul64(mul64(
 107   eval((dreached-1)/2), eval((dreached-2)/2)), full(dreached^stop2))))))
 108 define(`limit3', eval((stop2-1)%wide+1))
 109 define(`limit4', eval(limit3+wide))
 110 define(`adddiag', `define(`part2', add64(part2, add64(reset($@)forloop_arg(1,
 111   limit3, `round')mul64(pick(limit4, `step'), dreached), forloop_arg(incr(
 112   limit3), limit4, `round')mul64(pick(limit3, `step'), decr(dreached)))))')
 113 adddiag(1, 1)adddiag(1, wide)adddiag(wide, 1)adddiag(wide, wide)
 114
 115 ')
 116
 117 divert`'part1
 118 part2