2023/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 # Idea for optimization: write this as an NFA:
   9 # https://github.com/ConcurrentCrab/AoC/blob/main/solutions/12-2.go
  10
  11 # Assumes that the longest input line is a mask of 20 positions, followed
  12 # by at most 6 groups within those positions.
  13
  14 define(`input', translit((include(defn(`file'))), nl`.?# ,()', `;012//'))
  15 include(`math64.m4')
  16 define(`part1', 0)define(`part2', 0)
  17 define(`min', `ifelse(eval($1<$2), 1, $1, $2)')
  18
  19 # lone(len(str), str, arg1)->int # lone arg solution
  20 define(`_lone', `ifelse(eval($1<$5), 1, 0, $3$4, $1-1, `eval($1-$5+1)', $4, -1,
  21   `add64(lone($3, substr(`$2', 0, $3), $5), lone(pack(substr(`$2', $3)), $5))',
  22   eval($4>=$5), 1, `lone(pack(substr(`$2', eval($4-$5+1))), $5)', eval($3<$4),
  23   1, `lone(pack(substr(`$2', $3)), $5)', eval($3<$5), 1, 0, index(substr(`$2',
  24   $5), `2'), -1, `eval(min($4, $3-$5)+1)', $4, 0, 0, `lone(decr($1), substr($2,
  25   1), $5)')')
  26 define(`lone', `_$0(`$1', `$2', index(`$2'0, `0'), index(`$2', `2'), `$3')')
  27
  28 # check(len(str), str, minarglen, N, arg1, (arg2, ...argN))->int
  29 define(`check', `ifelse($4, 1, `lone($1, $2, $5)', eval(index(`$2'0, 0)<$5), 1,
  30   `ifelse(eval(index(`$2'2, 2)<index($2, 0)), 1, 0, `score(pack(substr($2,
  31   index($2, 0))), $3, $4, $5, `$6')')', substr($2, $5, 1), 2, `ifelse(substr($2,
  32   0, 1), 2, 0, `score(pack(substr($2, 1)), $3, $4, $5, `$6')')', `add64(score(
  33   pack(substr($2, incr($5))), eval($3-$5-1), decr($4), first$6, (shift$6)),
  34   ifelse(substr($2, 0, 1), 2, `0', `score(pack(substr($2, 1)), $3, $4, $5,
  35   `$6')'))')')
  36
  37 # score(len(str), str, minarglen, N, arg1, (arg2, ...argN))->int, memoized
  38 define(`_score', `ifdef(`$1', `', `define(`$1',  check(shift($@)))')$1()')
  39 define(`score', `ifelse(eval($3>$1 || len(translit($2, 01))>$3-$4+1), 1, 0,
  40   `_$0(`s$2_$5_'translit($6, `(,)', ``_''), $@)')')
  41
  42 # pack(str)->len, str
  43 define(`_pack', `substr(`$1', 0, $2)substr(`$1', incr($2))')
  44 define(`pack', `ifelse(index(`$1', `0'), 0, `$0(substr(`$1', 1))', index(
  45   `$1'0, `00'), -1, `len($1), `$1'', `$0(_$0(`$1', index(`$1'0, `00')))')')
  46 define(`_run', `define(`part1', eval(part1+$1))define(`part2', add64(part2,
  47   $2))')
  48 define(`run', `_$0(score(pack($1), $2, $3, first($4), (shift($4))),
  49   score(pack(`$1'1`$1'1`$1'1`$1'1`$1'), eval($2*5+4), eval($3*5), first($4),
  50   (shift($4),$4,$4,$4,$4)), $1)')
  51 define(`_do', `run($1, eval(`$7 + $6 + $5 + $4 + $3 + $2 + $# - 2'),
  52   decr(`$#'), quote(shift($@)))')
  53 define(`do', `_$0(translit(`$1', `/', `,'))')
  54
  55 ifdef(`__gnu__', `
  56   patsubst(defn(`input'), `\([^;]*\);', `do(`\1')')
  57 ', `
  58   define(`_chew', `do(substr(`$1', 0, index(`$1', `;')))define(
  59     `tail', substr(`$1', incr(index(`$1', `;'))))ifelse(index(defn(`tail'),
  60     `;'), -1, `', `$0(defn(`tail'))')')
  61   define(`chew', `ifelse(eval($1 < 68), 1, `_$0(`$2')', `$0(eval($1/2),
  62     substr(`$2', 0, eval($1/2)))$0(eval(len(defn(`tail')) + $1 - $1/2),
  63     defn(`tail')substr(`$2', eval($1/2)))')')
  64   chew(len(defn(`input')), defn(`input'))
  65 ')
  66
  67 divert`'part1
  68 part2