2019/day2.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dfile=day2.input] day2.m4
   3
   4 include(`intcode.m4')ifelse(intcode(2), `ok', `',
   5 `errprint(`Missing IntCode initialization
   6 ')m4exit(1)')
   7
   8 parse(input)
   9 no64()
  10 define(`try', `save()define(`mem1', eval($1 / 100))define(`mem2',
  11   eval($1 % 100))run(0)mem0`'restore()')
  12 define(`part1', try(1202))
  13 # Looking at sample inputs shows a common preamble of 12 ints, then a sequence
  14 # of instructions that each modify the previous instruction's result, usually
  15 # by a constant, and exactly once by mem1 and mem2, culminating in a final
  16 # write to mem0, which simplifies to a linear equation mem0 = a + mem1*b + mem2
  17 # with a and b large enough that 2-digit mem1 and mem2 cause monotonically
  18 # increasing results.  So we can do a binary search.
  19 define(`goal', 19690720)
  20 define(`search', `_$0($1, $2, eval(($1+$2)/2))')
  21 define(`_search', `$0_($1, $3, $2, try($3))')
  22 define(`_search_', `ifelse($4, 'goal`, $2, `search(ifelse(eval($4 < ''goal``),
  23   1, `incr($2), $3', `$1, decr($2)'))')')
  24 define(`part2', search(0, 9999))
  25
  26 divert`'part1
  27 part2