2022/day19.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dfile=day19.input] day19.m4
   3 # Optionally use -Dverbose=1 to see some progress
   4 # Optionally use -Dalgo=dfs|dijkstra|astar to choose search algorithm
   5 # Optionally use -Dpriority=0|1|2|3|4|5 to choose priority queue algorithms
   6
   7 include(`common.m4')ifelse(common(19), `ok', `',
   8 `errprint(`Missing common initialization
   9 ')m4exit(1)')
  10
  11 include(`priority.m4')
  12 ifdef(`algo', `', `define(`algo', `astar')')
  13
  14 # Instead of tracking current geodes and geode robots, just track a
  15 # single score (each time a geode robot is created, it is known how many
  16 # geodes it will contribute).  Instead of directly simulating wait states,
  17 # the choice to visit a neighbor computes the number of cycles needed to
  18 # reach the chosen bot, so each _visit() can branch at most 4 times.  To
  19 # further prune things, note that it is not worth choosing a bot that
  20 # would not produce useful resources, and line up the DFS search with
  21 # the later bots first so that states can short-circuit if they cannot
  22 # possibly score better than the current max.
  23 # - geode: need at least one obsR
  24 # - obs: need at least one clayR, avoid if obsR>=cost6
  25 # - clay: avoid if clayR>=cost4
  26 # - ore: avoid if oreR>=max(cost1,cost2,cost3,cost5)
  27 # - score cap: assuming infinite ore and obsidian supply, skip any visit
  28 #   that cannot produce more geodes in time remaining than current best
  29
  30 define(`max', `ifelse(eval($2>$1), 1, $2, $1)')
  31 define(`max4', `max(max($1, $2), max($3, $4))')
  32 define(`check', `ifelse(eval($1>best), 1, `define(`best', $1)')')
  33 # wait(have, need, bots)
  34 define(`wait', `eval(`($1<$2)*($2-$1+$3-1)/$3+1')')
  35 # buildgeo(oldtime, ore, clay, obs, oreR, clayR, obsR, oldscore, deltatime)
  36 define(`buildgeo', `ifelse(eval($9>$1-1), 0, `visit(eval($1-$9),
  37   eval($2-cost5+$5*$9), eval($3+$6*$9), eval($4-cost6+$7*$9), $5, $6, $7,
  38   eval($8+$1-$9))')')
  39 # buildobs(oldtime, ore, clay, obs, oreR, clayR, obsR, oldscore, deltatime)
  40 define(`buildobs', `ifelse(eval($9>$1-3), 0, `visit(eval($1-$9),
  41   eval($2-cost3+$5*$9), eval($3-cost4+$6*$9), eval($4+$7*$9), $5, $6,
  42   incr($7), $8)')')
  43 # buildclay(oldtime, ore, clay, obs, oreR, clayR, obsR, oldscore, deltatime)
  44 define(`buildclay', `ifelse(eval($9>$1-5), 0, `visit(eval($1-$9),
  45   eval($2-cost2+$5*$9), eval($3+$6*$9), eval($4+$7*$9), $5, incr($6), $7,
  46   $8)')')
  47 # buildore(oldtime, ore, clay, obs, oreR, clayR, obsR, oldscore, deltatime)
  48 define(`buildore', `ifelse(eval($9>$1-3), 0, `visit(eval($1-$9),
  49   eval($2-cost1+$5*$9), eval($3+$6*$9), eval($4+$7*$9), incr($5), $6, $7,
  50   $8)')')
  51 # _visit(oldtime, ore, clay, obs, oreR, clayR, obsR, oldscore)
  52 define(`_visit', `ifelse($7, 0, `', `buildgeo($@, max(wait($2, cost5, $5),
  53   wait($4, cost6, $7)))')ifelse(eval(`$6 && $4+$7*($1-1) < ($1-1)*'cost6), 1,
  54   `buildobs($@, max(wait($2, cost3, $5), wait($3, cost4, $6)))')ifelse(
  55   eval(`$3+$6*($1-3) < ($1-3)*'cost4), 1, `buildclay($@, wait($2, cost2,
  56   $5))')ifelse(eval(`$3+$5*($1-1) < ($1-1)*'costm), 1, `buildore($@,
  57   wait($2, cost1, $5))')')
  58 # visit(newtime, ore, clay, obs, oreR, clayR, obsR, newscore)
  59 define(`visit', `check($8)ifelse(eval($8+$1*($1-1)/2>best), 1,
  60   `ifelse(ifdef(`v$2_$3_$4_$5_$6_$7', `eval($8>v$2_$3_$4_$5_$6_$7)',
  61   `pushdef(`state', `v$2_$3_$4_$5_$6_$7')1'), 1, `define(`v$2_$3_$4_$5_$6_$7',
  62   $8)_$0($@)')')')
  63
  64 define(`part1', 0)define(`part2', 1)
  65 ifelse(eval(verbose >1), 1, `define(`visit', `show(progress)'defn(`visit'))',
  66   `output(1, `Starting search')')
  67 define(`progress', 0)
  68 define(`rename', `define(`$2', defn(`$1'))popdef(`$1')')
  69 define(`show10000', `output(1, `...$1')rename(`show$1', `show'eval($1+10000))')
  70 define(`show', `ifdef(`$0$1', `$0$1($1)')define(`progress', incr($1))')
  71 define(`reset', `ifdef(`state', `popdef(defn(`state'))popdef(`state')$0()',
  72   `define(`best', 0)')')
  73 define(`blueprint', `define(`cost1', $2)define(`cost2', $3)define(`cost3',
  74   $4)define(`cost4', $5)define(`cost5', $6)define(`cost6', $7)define(`costm',
  75   max4(cost1, cost2, cost3, cost5))reset()visit(23, 1, 0, 0, 1, 0, 0,
  76   0)define(`part1', eval(part1 + best*$1))output(1, `...$1/24 'best)ifelse(
  77   eval($1<=3), 1, `reset()visit(31, 1, 0, 0, 1, 0, 0, 0)define(`part2',
  78   eval(part2 * best))output(1, `...$1/32 'best)')')
  79
  80 # Now, parse in the data
  81 define(`and', `.')define(`Blueprint', `_/')
  82 translit(include(defn(`file')), `/:.'nl`'alpha` 'ALPHA, `(,,)'define(`_',
  83   `blueprint($@)'))
  84
  85 define(`_use', `ifelse(ifdef(`v$3', `v$3($1)', 0), 1, `', ifdef(`d$1',
  86   `eval($2 < d$1)', 1), 1, `addwork($1, $2)show(progress)')')
  87 define(`neighbors',)
  88 dnl forloop(0, decr(count), ``check('', ``, $'`1, $'`2)'')dnl
  89 dnl `first(ifdef(`n0', `defn(`n0')undefine(`n0')undefine(`n1')', `_$0()'))')
  90 define(`_neighbors', `ifdef(`n1', `defn(`n1')popdef(`n1')$0()')')
  91 define(`distance', `output(1, `...part $2')addwork(`0000000$1$2', 0)_$0($2)')
  92
  93 dnl define(`part1', distance(init`'12341234, 1))
  94
  95 divert`'part1
  96 part2