2021/day18.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dfile=day18.input] day18.m4
   3 # Optionally use -Dverbose=1 to see some progress
   4 # Optionally use -Dalgo=recurse|flat to choose an algorithm
   5
   6 include(`common.m4')ifelse(common(18), `ok', `',
   7 `errprint(`Missing common initialization
   8 ')m4exit(1)')
   9
  10 ifdef(`algo', `', `define(`algo', `flat')')
  11
  12 define(`input', translit((include(defn(`file'))), nl`,()', `;.'))
  13 define(`cat', `$*')
  14 define(`reduce', `_$0(split(explode(`$1')))')
  15 define(`_reduce', `ifelse($2, 1, `reduce(`$1')', `$1')')
  16
  17 ifelse(algo, `recurse', `
  18 output(1, `Using recursive algorithm')
  19 define(`convert', `translit(`$1', `[.]', `(,)')')
  20
  21 define(`explode', `_$0(exp($1, 0, `', 0, 0))')
  22 define(`_explode', `ifelse($2, 0, `$1', `explode(`$1')')')
  23 define(`exp', `ifelse(index(`$1', `('), -1, `eval($1+$4+$5), $2,0,0', $2$3,
  24   0----, `0, 1,cat$1', $2$4$5, 100, ``$1', 1,0,0',
  25   `_$0(cat$1, $2, $3-, $4, $5)')')
  26 define(`_exp', `build(exp(`$1', $3, $4, $5, 0), `$2', $4, $6)')
  27 define(`build', `_$0(`$1', exp(`$5', $2, $6, $4, $7), $3, $6)')
  28 define(`_build', `ifelse($4, 0, `($1,$2), $3,$6,$5', `(first(exp(`$1', 1, $7,
  29   0, $4)),`$2'), 1,$6,$5')')
  30
  31 define(`split', `spl($1, 0)')
  32 define(`spl', `ifelse($2, 1, `$1, 1', index(`$1', `('), 0, `_$0(cat$1)',
  33   len(`$1'), 1, `$1, 0', `(eval($1/2),eval(($1+1)/2)), 1')')
  34 define(`_spl', `join(spl(`$1', 0), `$2')')
  35 define(`join', `ifelse($2, 0, `_$0($1, spl(`$3', 0))', `($1,$3), 1')')
  36 define(`_join', `($1,$2), $3')
  37
  38 define(`magnitude', `ifelse(len(`$1'), 1, $1, _$0$1)')
  39 define(`_magnitude', `eval(3*magnitude(`$1')+2*magnitude(`$2'))')
  40 define(`add', `reduce(($1,$2))')
  41
  42 ', algo, `flat', `
  43 output(1, `Using flat algorithm')
  44 define(`convert', `flatten(0, translit(`$1', `[.]', `(,)'))')
  45 define(`d0', `~')define(`d1', `!')define(`d2', `@')
  46 define(`d3', `%')define(`d4', `^')define(`d5', `&')
  47 define(`flatten', `ifelse(len(`$2'), 1, `d$1`'1$2', `_$0(incr($1), cat$2)')')
  48 define(`_flatten', `flatten($1, $2)flatten($1, $3)')
  49
  50 define(`explode', `exp(`$1', index(`$1', `&'))')
  51 define(`exp', `ifelse($2, -1, `$1', `_$0(substr(`10$1', 0, $2),
  52   translit(`eval(AB+DE-10)^10ieval(GH+JK-10)', `ABcDEfGHiJK', substr(`10$1~10',
  53   $2, 11)), substr(`$1~10', eval($2+9)))')')
  54 define(`_exp', `explode(substr(`$1$2$3', 2, eval(len(`$1$2$3')-5)))')
  55
  56 define(`split', `spl(`$1', index(translit(`$1', `@%^&34567', `!!!!22222'),
  57   `!2'))')
  58 define(`spl', `ifelse($2, -1, `$1, 0', `_$0(substr(`$1', 0, $2),
  59   translit(substr(`$1', $2, 1), `!@%^', `@%^&'), substr(`$1', incr($2), 2),
  60   substr(`$1', eval($2+3))), 1')')
  61 define(`_spl', `$1$2eval(($3+10)/2)$2eval(($3+11)/2)$4')
  62
  63 define(`magnitude', `pushdef(`t', `0,0')_m(`$1')t()')
  64 define(`_m', `ifelse(`$1', `', `',
  65   `translit(`pr(A,C)_m(`DEFGHIJKLMNOPQRSTUVWXYZabcdefghijklnoqstuvwxy')',
  66   `ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklnoqstuvwxy', `$1')')')
  67 define(`pr', `_$0(t, translit(`$1', `!@%^', `1234'), $2)')
  68 define(`_pr', `ifelse($3, 0, `define(`t', `$4popdef(`t')')', $1, $3,
  69   `popdef(`t')$0(t, decr($3), eval(3*$2+2*$4))', `pushdef(`t', `$3,$4')')')
  70 define(`add', `reduce(translit($1`'$2, `!@%^', `@%^&'))')
  71
  72 ', `errprintn(`unrecognized algorithm 'algo)m4exit(1)')
  73
  74 define(`count', 0)
  75 define(`line', `define(`l'count, convert(`$1'))define(`count', incr(count))')
  76 ifdef(`__gnu__', `
  77   patsubst(defn(`input'), `\([^;]*\);', `line(`\1')')
  78 ', `
  79   define(`_chew', `line(substr(`$1', 0, index(`$1', `;')))define(
  80     `tail', substr(`$1', incr(index(`$1', `;'))))ifelse(index(defn(`tail'),
  81     `;'), -1, `', `$0(defn(`tail'))')')
  82   define(`chew', `ifelse(eval($1 < 120), 1, `_$0(`$2')', `$0(eval($1/2),
  83     substr(`$2', 0, eval($1/2)))$0(eval(len(defn(`tail')) + $1 - $1/2),
  84     defn(`tail')substr(`$2', eval($1/2)))')')
  85   chew(len(defn(`input')), defn(`input'))
  86 ')
  87
  88 define(`root', defn(`l0'))
  89 define(`merge', `define(`root', add(`root', `l$1'))')
  90 forloop_arg(1, decr(count), `merge')
  91 define(`part1', magnitude(root))
  92
  93 define(`part2', 0)
  94 define(`compare', `ifelse(eval($1>part2), 1, `define(`part2', $1)')')
  95 define(`_try', `ifelse($1, $2, `', `compare(magnitude(add(`l$1', `l$2')))')')
  96 define(`try', `output(1, `...$1')forloop(0, decr(count), `_$0(', `, $1)')')
  97 forloop_arg(0, decr(count), `try')
  98
  99 divert`'part1
 100 part2