2023/day08.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dfile=day08.input] day08.m4
   3 # Optionally use -Dverbose=1 to see some progress
   4
   5 include(`common.m4')ifelse(common(08), `ok', `',
   6 `errprint(`Missing common initialization
   7 ')m4exit(1)')
   8
   9 define(`input', translit((include(defn(`file'))), nl`(=, )', `;'))
  10 define(`offset', index(defn(`input'), `;;'))
  11 define(`dirs', substr(defn(`input'), 0, offset))
  12 define(`nodes', substr(defn(`input'), incr(incr(offset))))
  13
  14 define(`d', 0)
  15 define(`dir', `define(`d$1', `$2')define(`d', incr($1))')
  16 define(`do', `translit(`define(`L_123', `456')define(`R_123', `789')ifelse(`3',
  17   `A', `pushdef(`starts', `123')', `3', `Z', `define(`z123')')',
  18   `123456789', `$1')')
  19
  20 ifdef(`__gnu__', `
  21   patsubst(defn(`dirs'), `.', `dir(d, `\&')')
  22   patsubst(defn(`nodes'), `\([^;]*\);', `do(`\1')')
  23 ', `
  24   define(`chew', `ifelse($1, 1, `dir(d, `$2')', `$0(eval($1/2), substr(
  25     `$2', 0, eval($1/2)))$0(eval($1-$1/2), substr(`$2', eval($1/2)))')')
  26   chew(len(defn(`dirs')), defn(`dirs'))
  27   define(`_chew', `do(substr(`$1', 0, index(`$1', `;')))define(
  28     `tail', substr(`$1', incr(index(`$1', `;'))))ifelse(index(defn(`tail'),
  29     `;'), -1, `', `$0(defn(`tail'))')')
  30   define(`chew', `ifelse(eval($1 < 20), 1, `_$0(`$2')', `$0(eval($1/2),
  31     substr(`$2', 0, eval($1/2)))$0(eval(len(defn(`tail')) + $1 - $1/2),
  32     defn(`tail')substr(`$2', eval($1/2)))')')
  33   chew(len(defn(`nodes')), defn(`nodes'))
  34 ')
  35
  36 define(`move', `ifelse(end($@), `ZZZ', `$3',
  37   `$0(defn(defn(`d$2')`_$1'), eval(`($2+1)%'''d``), incr($3))')')
  38
  39 # Observations from megathread: all input files are nice: each __A ends in
  40 # exactly one __Z on an exact multiple of the directions string.  No need
  41 # to look for cycles when we can instead look for the first hit of __Z.
  42 #ifdef(`L_AAA', `
  43 #define(`end', `$1')
  44 #define(`part1', move(`AAA', 0, 0))
  45 #', ``missing AAA'')
  46 define(`part1', ``missing AAA'')
  47
  48 define(`_end', `ifelse(`$1', `ZZZ', `define(`part1', `$3')')define(`cycles',
  49   defn(`cycles')`,$3')`ZZZ'')
  50 define(`end', `ifdef(`z$1', `_$0', `ifelse')($@)')
  51 define(`run', `popdef(`starts')output(1, `$1... 'move(`$1', 0, 0))ifdef(
  52   `starts', `$0(starts)')')
  53 run(starts)
  54
  55 include(`math64.m4')
  56 # For my input, all cycles happen to be prime multiples of the length of dirs.
  57 # But if inputs have composite-length cycles, I might need to use the
  58 # following lcm/gcd implementations, and possibly code up 64-bit division.
  59 # define(`gcd', `ifelse($2, 0, $1, `$0($2, eval(`$1 % $2'))')')
  60 # define(`lcm', `mul64(eval($1 / gcd($1, $2)), $2)')
  61 define(`check', `ifelse(eval($1%d), 0, `,eval($1/d)',
  62   `fatal(`off-kilter cycle')')')
  63 define(`part2', mul(d`'foreach(`check'cycles)))
  64
  65 divert`'part1
  66 part2