2023/day11.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dfile=day11.input] [-Dgap=N] day11.m4
   3 # where gap=N defaults to 1000000
   4
   5 include(`common.m4')ifelse(common(11), `ok', `',
   6 `errprint(`Missing common initialization
   7 ')m4exit(1)')
   8
   9 ifdef(`gap', `', `define(`gap', 1000000)')
  10
  11 # https://www.geeksforgeeks.org/sum-manhattan-distances-pairs-points/
  12 # Using radix sort, since number of galaxies > number of rows
  13
  14 define(`input', translit(include(defn(`file')), nl`#', `;*'))
  15 define(`x', 0)define(`y', 0)
  16 define(`bump', `define(`$1', eval(defn(`$1')+$2))')
  17 define(`do', `define(`x', incr($1))ifelse(`$3', `;', `define(`maxx', $1)define(
  18   `x', 0)define(`y', incr($2))', `$3', `*', `bump(`x$1', 1)bump(`y$2', 1)')')
  19
  20 ifdef(`__gnu__', `
  21   patsubst(defn(`input'), `.', `do(x, y, `\&')')
  22 ',`
  23   define(`chew', `ifelse($1, 1, `do(x, y, `$2')', `$0(eval($1/2), substr(
  24     `$2', 0, eval($1/2)))$0(eval($1-$1/2), substr(`$2', eval($1/2)))')')
  25   chew(len(defn(`input')), defn(`input'))
  26 ')
  27
  28 include(`math64.m4')
  29 define(`visit', `,add64(mul64($2,i),-s)bump(`s', $2)bump(`i', 1)ifelse($1, 1,
  30   `', `$0(decr($1), $2)')')
  31 define(`_dsum', `ifdef(`$1$2', `visit($1$2, eval(o+$2))', `bump(`o', `$3')')')
  32 define(`dsum', `define(`i', 0)define(`o')define(`s', 0)forloop(0, $1,
  33   `define(`$3', add($3`'_$0(`$2', ', `, 'decr(`$4')`)))')')
  34 define(`part1', 0)define(`part2', 0)
  35 dsum(maxx, `x', `part1', 2)dsum(y, `y', `part1', 2)
  36 dsum(maxx, `x', `part2', gap)dsum(y, `y', `part2', gap)
  37
  38 divert`'part1
  39 part2