2023/day18.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dfile=day18.input] day18.m4
   3
   4 include(`common.m4')ifelse(common(18), `ok', `',
   5 `errprint(`Missing common initialization
   6 ')m4exit(1)')
   7
   8 changecom
   9 define(`input', translit(include(defn(`file')), nl`RDLUabcdef ()#',
  10   `;0123ABCDEF.'))
  11 changecom(`#', nl)
  12
  13 include(`math64.m4')
  14
  15 # https://en.wikipedia.org/wiki/Shoelace_formula is close for twice area;
  16 # but we are digging 1x1 squares, not points. There is length/2 additional
  17 # area oustside each line, plus 1 for all corners combined (a closed
  18 # non-intersecting loop necessarily has 4 more convex than concave corners,
  19 # since the sum of exterior angles of a polygon is always 360 degrees).
  20 define(`area1', 0)define(`perim1', 0)define(`x1', 0)define(`y1', 0)
  21 define(`area2', 0)define(`perim2', 0)define(`x2', 0)define(`y2', 0)
  22 define(`visit', `define(`area$1', add64(area$1, sub64(mul64($2, $5),
  23   mul64($3, $4))))define(`perim$1', eval(perim$1+$6))define(`x$1',
  24   $4)define(`y$1', $5)')
  25 define(`do0', `visit($1, $2, $3, eval(`$2 + $4'), $3, $4)')
  26 define(`do1', `visit($1, $2, $3, $2, eval(`$3 + $4'), $4)')
  27 define(`do2', `visit($1, $2, $3, eval(`$2 - $4'), $3, $4)')
  28 define(`do3', `visit($1, $2, $3, $2, eval(`$3 - $4'), $4)')
  29 define(`_do', `do$1(1, x1, y1, $2)first(`do'eval(`0x$3%4'))(2, x2, y2,
  30   eval(`0x$3/16'))')
  31 define(`do', `_$0(translit(`$1', `.', `,'))')
  32
  33 ifdef(`__gnu__', `
  34   patsubst(defn(`input'), `\([^;]*\);', `do(`\1')')
  35 ', `
  36   define(`_chew', `do(substr(`$1', 0, index(`$1', `;')))define(
  37     `tail', substr(`$1', incr(index(`$1', `;'))))ifelse(index(defn(`tail'),
  38     `;'), -1, `', `$0(defn(`tail'))')')
  39   define(`chew', `ifelse(eval($1 < 30), 1, `_$0(`$2')', `$0(eval($1/2),
  40     substr(`$2', 0, eval($1/2)))$0(eval(len(defn(`tail')) + $1 - $1/2),
  41     defn(`tail')substr(`$2', eval($1/2)))')')
  42   chew(len(defn(`input')), defn(`input'))
  43 ')
  44
  45 define(`_half', `substr(`$1', 0, decr(len(`$1')))')
  46 define(`half', `_$0(mul64(`$1', 5))')
  47 define(`part1', eval(translit(area1, `-')/2 + perim1/2 + 1))
  48 define(`part2', add64(half(translit(area2, `-')), eval(perim2/2 + 1)))
  49
  50 divert`'part1
  51 part2