2019/day25.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dfile=day25.input] day25.m4
   3 # Optionally use -Dverbose=[12] to see some progress
   4 # m4 -Dinteractive to let user play the game (implies -Dverbose)
   5 # m4 -Dcalltrace to debug function calls within intcode
   6 # m4 -Dnowarp to skip hack of warping to final room
   7 # m4 -Dnobrute to skip brute force loop
   8
   9 include(`intcode.m4')ifelse(intcode(25), `ok', `',
  10 `errprint(`Missing IntCode initialization
  11 ')m4exit(1)')
  12
  13 parse(input)
  14 ifdef(`interactive', `define(`verbose', 1)')
  15 ifelse(verbose, 0, `', `ifdef(`__gnu__', `',
  16   `errprintn(`verbose mode requires GNU m4')m4exit(1)')')
  17
  18 define(`writev', ifelse(verbose, 0, `', ``ifelse(eval($1 < 128 && $1 != 96), 1,
  19   `_writev(format(``%c'',$1))')''))
  20 define(`_writev', `divert`$1'divert(-1)')
  21 define(`write', defn(`writev')`define(`window', quote(shift(window),
  22   $1))ifelse(eval($1 <= 32), 1, `check(quote(window))')')
  23 define(`read', `oneshot(`io', `divert`'`Need more input!'
  24 ')0')
  25
  26 define(`part1')
  27 define(`window', `0,0,0,0,0,0,0')
  28 define(`typing', ``116,121,112,105,110,103,32'')
  29 define(`heavier', ``101,97,118,105,101,114,32'')
  30 define(`lighter', ``105,103,104,116,101,114,32'')
  31 define(`check', `ifelse(`$1', typing, `pushdef(`write', defn(`collect'))',
  32   `$1', heavier, `rebalance(0)', `$1', lighter, `rebalance(1)')')
  33 define(`collect', defn(`writev')`ifelse($1, 32, `popdef(`write')',
  34   eval($1 >= 48 && $1 <= 57), 1,
  35   `define(`part1', defn(`part1')eval($1 - 48))', `_collectX($1)')')
  36 define(`_collectX', `errprintn(`missing collect for $1')m4exit(1)')
  37 define(`rebalance')
  38
  39 # Observations via tracing my input:
  40 # f1256 returns at 1268 after printing a character from a string at SP-1
  41 # f2585 returns at 2629 with 0 or 1 based on string equality
  42 # f1174 walks string at SP-1 using function pointer at SP-2:
  43 # either f1256 to print string, or f2585 to compare string
  44 # f1234 prints a string at SP-1
  45 # strings are encoded as len then len bytes encoded
  46 # by adding length, distance from length, and data (see findstr)
  47 # f2525 parses array of known commands
  48 # f1424 moves to a room at SP-1, then checks inventory with f1310, then
  49 # invokes any function tied to the room
  50 # f1130 is array walker with args Addr, Arraylen, Size, Fn, scratch x3
  51 # Rooms (start at 3124) are encoded as Name, Descr, Fn, N, E, S, W
  52 # For example, 4556 contains: 4563 (Pressure-Sensitive Floor), 4588 (Analyzing),
  53 # 1553 (function), 0 (nothing north), 0, 4457 (room to south), 0
  54 # Items (start at 4601) encoded as Room (or -1 if held), Name, Weight, Fn
  55 # weights are 27 + item index greater than a power of 2
  56 # f2722 checks weights, using bitwise iteration with f2763, f1702 helpers
  57
  58 define(`origop9', defn(`op9'))
  59 define(`op9', `ifelse(pc, 1256, `', pc, 1268, `',
  60   $1, 1, `_$0(get1(1), pc, base)',
  61   `errprintn(pc` has unusual op9 use')')origop9($@)')
  62 define(`_op9', `ifelse(eval($1 > 0), 1, `call', `return')($@)')
  63 define(`depth')
  64 define(`call', `pushdef(`depth', ` 'defn(`depth'))pushdef(`f',
  65   ``f$2'')errprintn(depth()f()` called with 'forloop_arg(1, $1 - 1, `arg'))')
  66 define(`arg', `mem(eval(base + $1))`, '')
  67 define(`return', `errprintn(depth()f()popdef(`f')` returned 'mem(
  68   eval($3 + $1 + 1))` at $2')popdef(`depth')')
  69 ifdef(`calltrace', `oneshot', `pushdef')(`op9', defn(`origop9'))
  70
  71 define(`feed', `ifelse($#, 1, `_$0(10)',
  72   `$0(shift($@))_$0(32)')ifdef(`$0_$1', `$0_$1()', `oops()')')
  73 define(`_feed', `oneshot(`read', `$1')')
  74 define(`feed_east', `_feed(116)_feed(115)_feed(97)_feed(101)')
  75 define(`feed_west', `_feed(116)_feed(115)_feed(101)_feed(119)')
  76 define(`feed_north', `_feed(104)_feed(116)_feed(114)_feed(111)_feed(110)')
  77 define(`feed_south', `_feed(104)_feed(116)_feed(117)_feed(111)_feed(115)')
  78 define(`feed_inv', `_feed(118)_feed(110)_feed(105)')
  79 define(`feed_drop', `_feed(112)_feed(111)_feed(114)_feed(100)')
  80 define(`feed_take', `_feed(101)_feed(107)_feed(97)_feed(116)')
  81 define(`loop', `ifdef(`script', `feed(script)popdef(`script')loop()')')
  82 # The following are hardcoded to my puzzle, and would need adjusting
  83 # or more code to be suitable for other puzzles...
  84 define(`feed_mug', `_feed(103)_feed(117)_feed(109)')
  85 define(`feed_loom', `_feed(109)_feed(111)_feed(111)_feed(108)')
  86 define(`feed_food', `_feed(100)_feed(111)_feed(111)_feed(102)')
  87 define(`feed_ration', `_feed(110)_feed(111)_feed(105)_feed(116)_feed(
  88   97)_feed(114)')
  89 define(`feed_prime', `_feed(101)_feed(109)_feed(105)_feed(114)_feed(112)')
  90 define(`feed_number', `_feed(114)_feed(101)_feed(98)_feed(109)_feed(
  91   117)_feed(110)')
  92 define(`feed_manifold', `_feed(100)_feed(108)_feed(111)_feed(102)_feed(
  93   105)_feed(110)_feed(97)_feed(109)')
  94 define(`feed_jam', `_feed(109)_feed(97)_feed(106)')
  95 define(`feed_spool', `_feed(108)_feed(111)_feed(111)_feed(112)_feed(115)')
  96 define(`feed_of', `_feed(102)_feed(111)')
  97 define(`feed_cat6', `_feed(54)_feed(116)_feed(97)_feed(99)')
  98 define(`feed_fuel', `_feed(108)_feed(101)_feed(117)_feed(102)')
  99 define(`feed_cell', `_feed(108)_feed(108)_feed(101)_feed(99)')
 100
 101 # The following script solves my puzzle, but fails hard on others. While
 102 # more elaborate coding could learn an arbitrary map, I instead chose for
 103 # my general solution to hack the binary; see below.
 104 define(`canned', `divert(-1)
 105 pushdef(`script', ``east'')
 106 pushdef(`script', ``take', `food', `ration'')
 107 pushdef(`script', ``south'')
 108 pushdef(`script', ``take', `prime', `number'')
 109 pushdef(`script', ``north'')
 110 pushdef(`script', ``east'')
 111 pushdef(`script', ``take', `manifold'')
 112 pushdef(`script', ``east'')
 113 pushdef(`script', ``east'')
 114 pushdef(`script', ``take', `jam'')
 115 pushdef(`script', ``west'')
 116 pushdef(`script', ``north'')
 117 pushdef(`script', ``east'')
 118 pushdef(`script', ``take', `spool', `of', `cat6'')
 119 pushdef(`script', ``west'')
 120 pushdef(`script', ``north'')
 121 pushdef(`script', ``take', `fuel', `cell'')
 122 pushdef(`script', ``south'')
 123 pushdef(`script', ``south'')
 124 pushdef(`script', ``west'')
 125 pushdef(`script', ``west'')
 126 pushdef(`script', ``west'')
 127 pushdef(`script', ``north'')
 128 pushdef(`script', ``north'')
 129 pushdef(`script', ``west'')
 130 pushdef(`script', ``take', `mug'')
 131 pushdef(`script', ``east'')
 132 pushdef(`script', ``north'')
 133 pushdef(`script', ``east'')
 134 pushdef(`script', ``east'')
 135 pushdef(`script', ``take', `loom'')
 136 pushdef(`script', ``west'')
 137 pushdef(`script', ``west'')
 138 pushdef(`script', ``south'')
 139 pushdef(`script', ``south'')
 140 pushdef(`script', ``west'')
 141 pushdef(`script', ``north'')
 142 pushdef(`script', ``west'')
 143 pushdef(`script', ``inv'')
 144 ')
 145
 146 # The following brute forces my puzzle, but fails on other item names.
 147 # This approach tries up to 255 combinations, and does not pay attention
 148 # to feedback from previous attempts; it takes about 1 minute to run
 149 # through enough combinations to solve my puzzle. See below for my
 150 # generic solution which hacks the binary instead, to get a solution for
 151 # any puzzle in at most 8 attempts.
 152 define(`carrying', eval((1 << 8) - 1))
 153 define(`graybit', `eval(($1 ^ ($1 >> 1)) ^ (decr($1) ^ (decr($1) >> 1)))')
 154 define(`adjust', `_$0(graybit($1))pushdef(`script', ``north'')')
 155 define(`_adjust', `pushdef(`script', ifelse(eval(carrying & $1), 0,
 156   ```take''', ```drop''')adjust$1())define(`carrying', eval(carrying ^ $1))')
 157 define(`adjust0', `errprintn(bad gray)exit(1)')
 158 define(`adjust256', defn(`adjust0'))
 159 define(`adjust1', ``, jam'')
 160 define(`adjust2', ``, loom'')
 161 define(`adjust4', ``, mug'')
 162 define(`adjust8', ``, spool, of, cat6'')
 163 define(`adjust16', ``, prime, number'')
 164 define(`adjust32', ``, food, ration'')
 165 define(`adjust64', ``, fuel, cell'')
 166 define(`adjust128', ``, manifold'')
 167 define(`brute', `forloop_arg(1, carrying, `adjust')')
 168
 169 # These commands allow -Dinteractive the chance to try a bit more,
 170 # but while it works for my puzzle, the inventory names are not supported
 171 # for other puzzles, so more work would be needed to make it generic...
 172 define(`west', `feed(`$0')run`'')
 173 define(`north', defn(`west'))
 174 define(`east', defn(`west'))
 175 define(`south', defn(`west'))
 176 define(`inv', defn(`west'))
 177 define(`take', `feed(`$0', $@)run`'')
 178 define(`drop', defn(`take'))
 179
 180 # Now for the generic solution.
 181 # While some item names vary by puzzle, other strings are always present:
 182 # Locate the room named "Hull Breach" (11 chars, ascii 72-11, 117-12, ...)
 183 # Likewise for "Pressure-Sensitive Floor" (24 chars, ascii 80-24, 114-25...)
 184 # And for the item "escape pod" (10 chars, 101-10, 115-11...)
 185 define(`findmagic', `_$0(mem($1).mem(incr($1)).mem(incr(incr($1))), $1)')
 186 define(`_findmagic', `ifelse($1, 11.61.105, `define(`hullstr', $2)',
 187   $1, 24.56.89, `define(`goalstr', $2)',
 188   $1, 10.91.104, `define(`podstr', $2)')')
 189 forloop_arg(0, pos, `findmagic')
 190 define(`hull', eval(hullstr - 7))
 191 define(`goal', eval(goalstr - 7))
 192 define(`findpod', `ifelse(mem($1), podstr, `define(`pod', decr($1))')')
 193 forloop_arg(0, pos, `findpod')
 194 define(`items', pod)
 195 define(`finditems', `ifelse(eval(mem(eval(items - 3)) > items), 1,
 196   `define(`items', eval(items - 4))$0()')')
 197 finditems()
 198 ifelse(mem(hull).mem(goal).mem(incr(pod)), hullstr.goalstr.podstr, `',
 199   `errprintn(`unable to locate essential rooms/items')')
 200 define(`_dir', `ifelse($1, 0111, ``south'', $1, 1011, ``west'', $1, 1101,
 201   ``north'', $1, 1110, ``east'', `oops()')')
 202 define(`dir', _dir(eval(!mem(eval(goal + 3)))eval(!mem(eval(goal +
 203   4)))eval(!mem(eval(goal + 5)))eval(!mem(eval(goal + 6)))))
 204 # And now for the hack: rewire to grab all non-function items, and hard-wire
 205 # north of the hull breach to warp to the pressure-sensitive goal room
 206 define(`nitems', 0)
 207 define(`sortitems', `forloop_arg(0, 12, `_$0')')
 208 define(`_sortitems', `ifelse(mem(eval(items + $1 * 4 + 3)), 0, `insert(
 209   eval(items + $1 * 4), eval(mem(eval(items + $1 * 4 + 2)) - $1 - 28))')')
 210 define(`insert', `_$0(nitems, decr(nitems), $@)define(`nitems', incr(nitems))')
 211 define(`_insert', `ifelse($1, 0, `$0_(0, $3, $4)', `ifelse(eval($4 < weight$2),
 212   1, `$0_($1, item$2, weight$2)$0($2, decr($2), $3, $4)', `$0_($1, $3, $4)')')')
 213 define(`_insert_', `define(`item$1', $2)define(`weight$1', $3)')
 214 sortitems()
 215 define(`grabsafe', `forloop_arg(0, decr(nitems), `grab')')
 216 define(`grab', `pushdef(`mem'item$1, -1)')
 217 define(`ungrab', `pushdef(`mem'item$1, 0)')
 218 ifdef(`nowarp', `', `
 219   define(`current', decr(nitems))
 220   grab(current)
 221   pushdef(`rebalance', `ifelse(current, -1, `oops()', $1, 1,
 222     `ungrab(current)')define(`current',  decr(current))grab(current)')
 223   pushdef(`mem'eval(hull + 3), goal)
 224   pushdef(`canned', `pushdef(`script', ``north'')')
 225   pushdef(`adjust', `pushdef(`script', dquote(defn(`dir')))')
 226   pushdef(`brute', `forloop_arg(0, nitems, `adjust')')
 227 ')
 228 ifdef(`nobrute', `oneshot(`brute')')
 229
 230 ifdef(`interactive', `', `canned()brute()loop()')
 231
 232 run(0)
 233 divert(-1)
 234
 235 # Debugging aids
 236 define(`findmem', `pushdef(`_$0', `ifelse(mem($'`1), $1,
 237   $'`1`nl()')')forloop_arg(ifelse($2, `', 0, $2), pos, `_$0')popdef(`_$0')')
 238 define(`isascii', `eval($1 == 10 || ($1 >= 32 && $1 < 128))')
 239 define(`findstr', `_$0($1, mem($1), mem(incr($1)), mem(incr(incr($1))),
 240   mem(eval($1 + 3)))')
 241 define(`_findstr', `ifelse(eval($2 > 0 && $2 + $1 <= pos &&
 242   isascii(eval($3 + $2)) && isascii(eval($4 + $2 + 1)) &&
 243   isascii(eval($5 + $2 + 2))), 1,
 244   `$1: dump($2, $2, incr($1))nl()')')
 245 define(`dump', `ifelse($1, 0, `',
 246   `_$0(eval($2 + mem($3)))$0(decr($1), incr($2), incr($3))')')
 247 define(`_dump', `ifelse($1, 10, ``\n'', isascii($1), 1,
 248   `changequote(<<, >>)format(<<<<%c>>>>, $1)changequote`'',
 249   `?oneshot(`dump')')')
 250
 251 define(`showroom', `_$0($1, mem($1), mem(incr($1)), mem(incr(incr($1))),
 252   mem(eval($1 + 3)), mem(eval($1 + 4)), mem(eval($1 + 5)), mem(eval($1 + 6)))')
 253 define(`_showroom', `Room $1:nl() findstr($2) findstr($3) func: $4nl(
 254   ) n: $5nl() e: $6nl() s: $7nl() w: $8nl()')
 255
 256 define(`showitem', `_$0($1, mem($1), mem(incr($1)), mem(incr(incr($1))),
 257   mem(eval($1 + 3)), mem(eval($1 + 4)))')
 258 define(`_showitem', `Item $1:nl() findstr($3) room: $2nl() weight: $4nl(
 259   ) func: $5nl()')
 260
 261 divert`'ifdef(`interactive', `', part1)