2023/day24.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dfile=day24.input] day24.m4
   3 # Optionally use -Dlo=N -Dhi=N to alter bounds
   4 # Optionally use -Dverbose=1 to see some progress
   5
   6 include(`common.m4')ifelse(common(24), `ok', `',
   7 `errprint(`Missing common initialization
   8 ')m4exit(1)')
   9
  10 include(`math64.m4')
  11
  12 define(`input', translit((include(defn(`file'))), nl`,@ ()', `;..'))
  13 define(`p', 0)
  14 define(`_do', `define(`p'p, `$*')define(`P'p, `$5, 'neg64($4)`, 'sub64(
  15   mul64($2, $4), mul64($1, $5)))define(`p', incr(p))')
  16 define(`do', `_$0(translit(`$1', `.', `,'))')
  17
  18 ifdef(`__gnu__', `
  19   patsubst(defn(`input'), `\([^;]*\);', `do(`\1')')
  20 ', `
  21   define(`_chew', `do(substr(`$1', 0, index(`$1', `;')))define(
  22     `tail', substr(`$1', incr(index(`$1', `;'))))ifelse(index(defn(`tail'),
  23     `;'), -1, `', `$0(defn(`tail'))')')
  24   define(`chew', `ifelse(eval($1 < 140), 1, `_$0(`$2')', `$0(eval($1/2),
  25     substr(`$2', 0, eval($1/2)))$0(eval(len(defn(`tail')) + $1 - $1/2),
  26     defn(`tail')substr(`$2', eval($1/2)))')')
  27   chew(len(defn(`input')), defn(`input'))
  28 ')
  29
  30 # Default bounds based on size of input
  31 ifdef(`lo', `', `define(`lo', ifelse(len(p), 1, 7, 200000000000000))')
  32 ifdef(`hi', `', `define(`hi', ifelse(len(p), 1, 27, 400000000000000))')
  33
  34 # For each row of input (x, y, z, dx, dy, dz), I have sufficient information
  35 # to build a point-slope linear equation relating x and y: y-yN = m(x-xN)
  36 # The slope m is dyN/dxN, but since I don't want division, it's easier to use:
  37 # dxN(y-yN) = dyN(x-xN).  Next, rewrite into aN*x + bN*y + cN = 0, with
  38 # aN = dyN, bN = -dxN, cN = xN*dyN - yN*dxN.  Given two coplanar lines with
  39 # coefficients a1, b1, c1, a2, b2, c2, their intersection will be at:
  40 # X = (b1*c2-b2*c1)/(a1*b2-a2*b1), Y = (a2*c1-a1*c2)/(a1*b2-a2*b1)
  41 # Again, avoiding division is useful, and both X and Y share a common
  42 # denominator, so I have three inputs: Xnum, Ynum, denom; it's easiest if
  43 # denom is positive (so I don't have to worry about flipping the direction
  44 # of the inequalities), so the bounds checks end up as:
  45 # denom*lo <= Xnum <= denom*hi
  46 # denom*lo <= Ynum <= denom*hi
  47 # Then I need one additional constraint per ray to make sure the
  48 # intersection happens in the future, not the past.  Done by:
  49 # dxN<0 ? (Xnum <= denom*xN) : (Xnum >= denom*xN).
  50
  51 define(`part1', 0)define(`prog', 0)
  52 define(`progress', `ifelse(eval(prog%500), 0, `output(1, ...prog)')define(
  53   `prog', incr(prog))')
  54 define(`ge64', `lt64($2, $1)')
  55 define(`le64', `ifelse($1, $2, 1, `lt64($1, $2)')')
  56 define(`extract', `$1, $4')
  57 define(`future', `ifelse(eval($4 < 0), 1, `le64', `ge64')($1, mul64($2, $3))')
  58 define(`_compare', `ifelse(lt64($3, 0), 1, `$0(neg64($1), neg64($2), neg64($3),
  59   $4, $5, $6, $7)', `ifelse(le64(mul64('lo`, $3), $1)le64($1, mul64('hi`,
  60   $3))future($1, $3, $4, $5).le64(mul64('lo`, $3), $2)le64($2, mul64('hi`,
  61   $3))future($1, $3, $6, $7), 111.111, `define(`part1', incr(part1))')')')
  62 define(`compare', `_$0(sub64(mul64($2, $6), mul64($5, $3)), sub64(mul64($4, $3),
  63   mul64($1, $6)), sub64(mul64($1, $5), mul64($4, $2)), extract(p$7),
  64   extract(p$8))progress()')
  65 define(`_probe', `compare(P$1, P$2, $1, $2)')
  66 define(`probe', `forloop(incr($1), 'decr(p)`, `_$0($1, ', `)')')
  67 forloop_arg(0, decr(decr(p)), `probe')
  68
  69 divert`'part1
  70 part2