2022/day12.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dfile=day12.input] day12.m4
   3
   4 include(`common.m4')ifelse(common(12), `ok', `',
   5 `errprint(`Missing common initialization
   6 ')m4exit(1)')
   7
   8 # Less risk of macro collision if we swap case.
   9 define(`input', translit(include(defn(`file')), nl`'alpha`'ALPHA,
  10   `;'ALPHA`'alpha))
  11 define(`x', 1)define(`y', 1)
  12 define(`height', `index('dquote(ALPHA)`, `$1')')
  13 define(`do', `ifelse(`$3', `;', `define(`x', 1)define(`y', incr($2))',
  14   `ifelse(`$3', `s', `define(`startx', `$1')define(`starty', `$2')define(
  15   `g$1_$2', height(`A'))', `$3', `e', `define(`endx', `$1')define(`endy',
  16   `$2')define(`g$1_$2', height(`Z'))', `define(`g$1_$2', height(
  17   `$3'))')define(`x', incr($1))')')
  18
  19 ifdef(`__gnu__', `
  20   patsubst(defn(`input'), `.', `do(x, y, `\&')')
  21 ',`
  22   define(`chew', `ifelse($1, 1, `do(x, y, `$2')', `$0(eval($1/2), substr(
  23     `$2', 0, eval($1/2)))$0(eval($1-$1/2), substr(`$2', eval($1/2)))')')
  24   chew(len(defn(`input')), defn(`input'))
  25 ')
  26
  27 # BFS search from end to start. We don't care about path, just length, so
  28 # we can get away with undefining the grid as we go as our witness.  Plus,
  29 # this is an unusual puzzle where part 2 is learned before part 1!
  30 define(`good', `ifelse($1, 0, `define(`part2', $2)pushdef(`good')')')
  31 define(`_check', `ifdef(`g$1_$2', `ifelse(eval(g$1_$2>=$3-1), 1,
  32   `pushdef(`edge$4', `$1,$2,'g$1_$2)popdef(`g$1_$2')')')')
  33 define(`check', `good($3, $4)ifelse(`$1.$2', 'startx.starty`, `pushdef(
  34   `search', $4)', `_$0($1, incr($2), $3, $5)_$0($1, decr($2), $3,
  35   $5)_$0(incr($1), $2, $3, $5)_$0(decr($1), $2, $3, $5)')')
  36 define(`search', `ifdef(`edge$1', `check(edge$1, $1, $2popdef(`edge$1'))$0($@)',
  37   `$0($2, incr($2))')')
  38 _check(endx, endy, 0, 0)
  39 define(`part1', search(0, 1))
  40
  41 divert`'part1
  42 part2