day 14 semi-golf, with missing fifth glyph

[aoc_eblake.git] / 2023 / day05.m4

divert(-1)dnl -*- m4 -*-
# Usage: m4 [-Dfile=day05.input] day05.m4

# Welcome to my ELI5 submission.
#
# I suspect you've never coded in m4 before, even though the language
# has been around since 1977.  So this particular solution is
# extra-verbose compared to what I usually do.
#
# m4 is a macro processing language: you can define(`name', `value')
# to create a macro, which you later call by name(arg1, arg2...) which
# expands into `value' modified by inlining argN into $N substrings.
# $@ is shorthand for all the args at once.  M4 uses asymmetric
# quoting `', so that quoting can nest.  When a macro is expanded, the
# resulting text is scanned for further macros, unless the output was
# quoted.  In this manner, it is possible to write recursive macros.
# When you see call(bare), you are asking to expand the 'bare' code
# prior to calling 'call' (and sometimes, bare can create more than
# one argument, if its expansion includes an unquoted comma); while
# call(`quoted') is asking to use the literal string, but no longer
# quoted (unless the use of $1 in the expansion was itself quoted).
# This lets you write both stack recursion (a macro does not produce
# output until helper macros called within its parameter list expand
# first) and tail recursion (a macro produces output which will then
# trigger another round of macro expansion at the same stack level).
#
# The only data structure in m4 is macros, which is basically a
# hashtable between names and values; but it allows you to create a
# stack of definitions sharing the same name.  This comes in handy: I
# store the list of seeds in a variable stack name l0; each
# pushdef(`l0', seed) pushes another seed into the stack, and each
# popdef(`l0') retrieves the most-recently-pushed seed.  This puzzle
# does not care about ordering (seeds can be processed in any order),
# so rather than trying to sort things or preserve input order, I just
# destructively consume a stack, meaning my list of seed ranges ends
# up reversing itself across iterations.  This works because the
# target is a minimum result from the list, regardless of what
# ordering I used.
#
# That was a lot to cover at once; but hopefully it helps you
# understand the gist of the code below, I'll use the notation:
#  macro(args) - a macro that runs for its side-effects with no output,
#   such as altering the definition of another macro
#  macro(args)->return - a macro called to produce output
# With that introduction, here we go!

# Section 1: general setup
# Boilerplate that helps me reuse framework code for all of my m4
# solutions.  For example, m4 does NOT have a native loop operand;
# instead, it lets you write your own macros to achieve looping.  I
# use forloop below, so this saves me the effort of open-coding it yet
# another time in this file.
include(`common.m4')ifelse(common(05), `ok', `',
`errprint(`Missing common initialization
')m4exit(1)')

# The input file uses unsigned 32-bit integers, but m4 eval() only
# does 32-bit signed math; input values overflow to negative.  But
# rather than pull out arbitrary precision math64.m4 library that I
# wrote in previous years, I can skew all inputs into the signed
# range, then skew the answer back; it is extremely likely that the
# final answer will not be more than 2G.
#include(`math64.m4')

# Slurp in the input, but remap it to avoid whitespace, since that
# messes up the eat macro below.  The translit here remaps newline to
# `;', space to ` ', and discards letters, colon, and dash, since they
# don't affect anything we need to do later.
define(`input', translit(include(defn(`file')), nl` 'defn(`alpha'):-, `;.'))

# offset()->int - the separation between the seeds line and the maps data.
define(`offset', index(defn(`input'), `;'))

# skew(n)->`int' - adjust a number between signed and unsigned ranges.
# This is a bi-directional remap, thanks to the properties of
# twos-complement.  Note that this macro produces quoted output -
# that's because most seed values will be 8 or more bytes (thanks to
# the skewing), and m4 is faster at parsing `12345678' than it is
# 12345678 (for a string, it can search ahead to the close quote; but
# for an integer, it is parsing one byte at a time while computing the
# integer's value)
define(`skew', `dquote(eval(`$1-0x80000000'))')

# prep(n1, n2, ...) - parse of pairs of seed to populate pushdef
# stacks l0 (for part 1) and L0 (for part 2). Each stack element of
# [lL]N contains start,len,`l/L'.  Here is an example of performing
# iterative work: you can pass any number of arguments, a single call
# of prep processes just the first two list elements then tail
# recurses to call $0 (that is shorthand for the current macro, prep)
# with a shorter input list (shifting away the first two arguments),
# and it uses ifelse() to end recursion when the input list is empty.
#
# M4's main conditional operation is ifelse, which works 3 arguments
# at a time: if the first two arguments expand to the same text, then
# unquote the third argument as the expansion of ifelse, otherwise
# proceed to the next 3 arguments.  If no conditions ever match, a
# fourth argument provides the final default expansion. This type of
# recursion is inherently quadratic in m4 (when passing in N arguments
# to the original call, you end up making N calls that process an
# average of N/2 arguments); thankfully, the input file list of seeds
# is only 20 elements long.
define(`prep', `ifelse(`$1', `', `', `pushdef(`l0', skew(`$1')`,1,`l'')pushdef(
  `l0', skew(`$2')`,1,`l'')pushdef(`L0', skew(`$1')`,`$2',`L'')$0(shift(
  shift($@)))')')
prep(shift(translit(substr(defn(`input'), 0, offset), `.', `,')))

# Section 2: map parsing. with the macos defined in this section,
# expanding eat will define p1 through pN, with the macro p storing
# the current map (it so happens that both the example and input
# puzzles each have 7 maps, but this way I can handle an arbitrary
# number of maps).
define(`p', 0)
define(`maps', substr(defn(`input'), incr(incr(offset)));)

# append(N, text) - append text to the current definition of pN.
# Yes, this is a case of writing one macro which in turn rewrites
# another macro.  Part of the power of m4 comes from dynamically
# writing macros whose content depends on runtime input.
define(`append', `define(`p$1', defn(`p$1')`$2')')

# emit(start, len, `l/L', N) - store an entry into [lL]N
define(`emit', `pushdef(`$3$4', `$1,$2,`$3'')')

# short-circuit.  Once pN has called emit(), all remaining code in the
# expansion of pN has nothing to do.  These gracefully skip that work.
define(`xrange', `x')define(`xpushdef')

# range(curstart, curlen, `l/L', p, dest, orig, len) - the real
# workhorse of this code.  Checks a given seed range against one line
# of a mapping, possibly splitting the range in 2 if it exceeds
# bounds.  The code is careful to avoid signed integer overflow (note
# that eval(a<b+c) is NOT the same as eval(a=b+c-1) when b+c wraps
# around to INT_MIN).  Also, GNU m4 complains about 1--1 (it
# recognizes that C has a -- operator even though m4 doesn't, and
# complains rather than using my preferred parse of 1-(-1)), so I have
# to write 1- -1.
#
# More specifically, this code handles the following cases:
# No overlap: expands to nothing, proceeds to next term in pN chain
#                    orig...orig+len
# v--------------v---^-------------^--v---------------v
# curstart.+curlen                    curstart..+curlen
#
# Completely contained: calls emit(dest, len, `l/L', N) to remap the
# input into the correct spot for the next iteration, and outputs x to
# short-circuit the rest of the pN chain.
# orig..........orig+len
# ^---v-------------v--^
#     curstart...+len
#
# Start contained: calls both emit(dest, low, `l/L', N) and
# pN(orig+len, high, `l/L', N) to recurse to see if the rest of the
# input range matches anywhere else in the map. Outputs x.
# orig.......orig+len
# ^--v--------------|-------v
#    curstart....+low...+high (where low+high=curlen)
#
# End contained: calls both pN(curstart, low, `l/L', N) and
# pN(curstart+low, len-low, `l/L, N), then outputs x.  Works
# whether curstart+curlen occurs before or after orig+len.
#              orig.......orig+len
# v------------|-------v---------^
# curstart..+low...+high            (where low+high=curlen)
define(`_range', `ifelse(eval(`$1<$3'), 1, `$1p$5(eval(`$2+$1'), eval(`$3- $1'),
  `$4', $5)', `$3'), `$4', $5')
define(`range', `ifelse(eval(`$1>=$6 && $1<=$6+$7-1'), 1, `emit(eval(
  `$1+$5- $6'),_$0(eval(`$7- $1+$6'), $@))x', eval(`$1<$6 && $1+$2-1>=$6'),
  1, `p$4($1, eval(`$6- $1'), `$3', $4)p$4($6, eval($2+$1- $6), `$3', $4)x')')

# term(@, N, deststart, origstart, len) - appends `range($@, int, int,
# int)' to pN.  Note that term() requires a literal @ for its first
# parameter which is paired with $$1 in the macro value; that is the
# only way in m4 to produce a literal $@ in the expansion text which
# will itself be assigned to another macro definition (we want $@
# expanded into the arguments at the time pN() is called, and not at
# the time term() is called).  On the other hand, this definition
# intentionally stops quoting around the skew() calls - this is a case
# where we want the numbers parsed off the line of text to be munged
# up front and a single integer stored in the pN macro, rather than
# each call to pN calling skew(N) for duplicated work.  Knowing when
# to quote for late expansion, vs. intentionally underquoting for
# early expansion, is the mark of a true m4 expert.  But thankfully
# you are just reading this code, rather than writing it, so hopefully
# you get the gist even if you don't understand the nuance.
define(`term', `append($2, `range($$1, 'skew(`$3')`, 'skew(`$4')`, `$5')')')

# do(line, p) - process another line of maps while building up pN
# macros.  When a range of lines is complete, pN will be defined as
# range(...)range(...)pushdef(...)
define(`do', `ifelse(`$1', `.', `define(`p', incr($2))', `$1', `', `append($2,
  defn(`emit'))', `term(`@', $2, translit(`$1', `.', `,'))')')

# eat(data) - My parsing workhorse. I copy this segment from puzzle to
# puzzle, but fine-tune it to the specific data at hand.  In this
# case, after the translit done in creating input above, a given map
# looks like:
#  .;50.98.2;52.50.48;;
# This splits on each ; to pass a line to do(); the first variant is
# O(N) but relies on regex via patsubst, a GNU extension; the second
# variant is O(N log N) by dividing the problem into smaller halves
# until each half is below 70 characters (roughly double the max line
# length of the input file, excluding the seed line) before resorting
# to actual hunting for the line delimiter of semicolon.
ifdef(`__gnu__', `
  define(`eat', `patsubst(`$1', `\([^;]*\);', `do(`\1', p)')')
', `
  define(`_chew', `do(substr(`$1', 0, index(`$1', `;')), p)define(
    `tail', substr(`$1', incr(index(`$1', `;'))))ifelse(index(defn(`tail'),
    `;'), -1, `', `$0(defn(`tail'))')')
  define(`chew', `ifelse(eval($1 < 70), 1, `_$0(`$2')', `$0(eval($1/2),
    substr(`$2', 0, eval($1/2)))$0(eval(len(defn(`tail')) + $1 - $1/2),
    defn(`tail')substr(`$2', eval($1/2)))')')
  define(`eat', `chew(len(`$1'), `$1')')
')
eat(defn(`maps'))

# Section 3: computation
# Now that all the data is parsed, we need to execute it.
# run(`l/L', N) - calls pN() on each element in the [lL]N-1 stack.
#
# Contrast this to the recursion done in prep() above - even though
# both macros expand to $0(...$@) except when the end of recursion is
# detected, this one is O(N) rather than O(n^2) because it only parses
# 2 arguments on each of N iterations, rather than an average of N/2
# arguments.  ifdef is m4's other conditional operator; the second
# argument is only expanded when the first names a defined macro.
define(`_run', `ifdef(`$1', `p$2($1, $2)popdef(`$1')$0($@)')')
define(`run', `_$0(`$1'decr($2), $2)')

# min(a, b)->int - m4's version of a very common idiom
define(`min', `ifelse(eval(`$1 < $2'), 1, `$1', `$2')')

# _minstack(`[lL]N', best, ignored)->int
# minstack(`[lL]N')->int - determines the minimum value in the [lL]N
# stack. Very often in m4 code, you'll see a friendly public macro
# which then calls out to a companion helper macro to do actual
# recursion with an additional accumulator parameter.
define(`_minstack', `ifdef(`$1', `$0(`$1', min($2, $1)popdef(`$1'))', `$2')')
define(`minstack', `skew(_$0(`$1', $1`'popdef(`$1')))')

# Time to run it all!  forloop() is one of my own macros from
# common.m4 (if you want to study that); calling forloop(start, end,
# `prefix', `suffix') expands to "prefixNsuffix" for each N in the
# closed range [start-end]; in this case, "run(`l', `1')" through
# "run(`L', p)".
define(`part1', forloop(1, p, `run(`l', ', `)')minstack(`l'p))
define(`part2', forloop(1, p, `run(`L', ', `)')minstack(`L'p))

# Now display the results.
#
# I hope this tutorial was helpful. Thanks for reading through this.
# On my machine, if I stick the input in a file named day05.input,
# then "m4 day05.m4" spits out answers for both parts of the question
# in about 50ms, using GNU m4 1.4.19.  You can use "m4
# -Dfile=othername day05.m4" if your input lives elsewhere.  The code
# should work with any POSIX implementation of m4:
# https://pubs.opengroup.org/onlinepubs/9699919799/utilities/m4.html
# although I haven't tested it on BSD m4, so it may fail if I
# triggered a subtle implementation difference there.  With GNU m4,
# you can use "m4 -G day05.m4" to skip all GNU extensions and force
# execution of the O(N log N) parse; execution time was not noticeably
# different, so I'm spending more time in run() than in eat().
divert`'part1
part2