2022/day17.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dfile=day17.input] [-Dlimit=N] day17.m4
   3 # Optionally use -Dverbose=1 to see some progress
   4
   5 include(`common.m4')ifelse(common(17), `ok', `',
   6 `errprint(`Missing common initialization
   7 ')m4exit(1)')
   8
   9 ifdef(`limit', `', `define(`limit', 2022)')
  10
  11 define(`input', translit(include(defn(`file')), `<>'nl, `01'))
  12 define(`n', 0)
  13 define(`do', `define(`d$1', $2)define(`n', incr($1))')
  14
  15 ifdef(`__gnu__', `
  16   patsubst(defn(`input'), `.', `do(n, `\&')')
  17 ',`
  18   define(`chew', `ifelse($1, 1, `do(n, `$2')', `$0(eval($1/2), substr(
  19     `$2', 0, eval($1/2)))$0(eval($1-$1/2), substr(`$2', eval($1/2)))')')
  20   chew(len(defn(`input')), defn(`input'))
  21 ')
  22 dnl bitmaps for rocks:                   aaaa_aaab_bbbb_bbcc_cccc_cddd_dddd
  23 define(`mask0', eval(`0x8102040'))dnl    1   _   1_    _  1 _    _ 1  _
  24 define(`mask1', eval(`0x204081'))dnl         _  1 _    _ 1  _    _1   _   1
  25 define(`rock1', eval(`0x1e'))dnl             _    _    _    _    _   1_111
  26 define(`rock2', eval(`0x20e08'))dnl          _    _ 010_    _111 _   0_10
  27 define(`rock3', eval(`0x1021c'))dnl          _    _ 001_    _001 _   1_11
  28 define(`rock4', eval(`0x2040810'))dnl      1 _    _ 1  _    _1   _   1_
  29 define(`rock0', eval(`0xc18'))dnl            _    _    _    _11  _   1_1
  30 define(`row0', eval(`0x7f'))dnl              _    _    _    _    _ 111_1111
  31 define(`h', 0)define(`t', 0)
  32
  33 define(`d', `first(`jet'defn(`d'eval($1%'n`)))')
  34 define(`get', `eval(defn(`row$2')`+0|(($1&0x1fffff)<<7)'), $2')
  35 define(`jet0', mask0`,*')define(`jet1', mask1`,/')
  36 define(`jet', `fall(eval(`$1$5(1+!($1&$4||($1$5 2)&$2))'), get($2, decr($3)),
  37   incr(t))')
  38 define(`fall', `define(`t', $4)ifelse(eval(`$1&$2'), 0, `jet(`$1', $2, $3,
  39   d($4))', `settle(`$1', incr($3))')')
  40 define(`_settle', `ifdef(`row$2', `', `define(`h', $2)')define(`row$2',
  41   defn(`row$2')`+0|($1)')')
  42 define(`settle', `ifelse(`$1', 0, `', `_$0(`$1&0x7f', $2)$0(eval(`$1>>7'),
  43   incr($2))')')
  44 define(`cycle', `output(1, `...cycle found between rocks $1/$5')define(`ch',
  45   eval(`$2-$6'))define(`cr', eval(`$1-$5'))define(`cs', $5)pushdef(`_rock')')
  46 define(`_rock', `ifelse(eval(`$1%5+($3==$4)'), 0, `ifdef(`s$4', `cycle($@,
  47   s$4)', `define(`s$4', `$1,$2')')')')
  48 define(`rock', `_$0($@)jet(defn(`rock'eval($1%5)), 0, eval(`$2+4'), d($4))')
  49 define(`run', `forloop($1, $2, `rock(', `, h, t, eval(t%''n``))')')
  50 run(1, limit)
  51 define(`part1', h)
  52
  53 include(`math64.m4')
  54 # div64 is not in math64.m4 because it is not fully generic; but it is good
  55 # enough for the one large division needed in this puzzle
  56 define(`bits', `_$0(eval($1, 2))')
  57 define(`_bits', ifdef(`__gnu__', ``shift(patsubst($1, ., `, \&'))'',
  58   ``ifelse(len($1), 1, `$1', `substr($1, 0, 1),$0(substr($1, 1))')''))
  59 define(`bits64', `ifelse(eval(len($1) < 10), 1, `bits($1)', `_$0(mul64($1,
  60   5)), eval(substr($1, decr(len($1))) & 1)')')
  61 define(`_bits64', `bits64(substr($1, 0, decr(len($1))))')
  62 define(`div64p', `ifelse($4, `', `$1,$2', `$0(_$0(add64($1, $1), add64(add64($2,
  63   $2), $4), $3), $3, shift(shift(shift(shift($@)))))')')
  64 define(`_div64p', `ifelse(lt64($2, $3), 0, `add64($1, 1), sub64($2, $3)',
  65   `$1, $2')')
  66 define(`remquo64', `ifelse(eval(`$1'), `$1', `eval(`$1/$2'),eval(`$1%$2')',
  67   `div64p(0, 0, $2, bits64(`$1'))')')
  68
  69 define(`search', `ifelse(ifdef(`cs', 1), 1, `', eval(t<2*n), 1,
  70   `run(incr(limit), define(`limit', eval(limit*2))limit)$0()')')
  71 search()
  72 ifdef(`cs', `', `fatal(`unable to detect cycle under limit 'limit)')
  73 define(`rest', `run(incr(limit), eval(limit + $2))define(`part2',
  74   add64(mul64($1, ch), h))')
  75 rest(remquo64(sub64(1000000000000, limit), cr))
  76
  77 divert`'part1
  78 part2