day 15 golfed m4 ELI5 counterpart

[aoc_eblake.git] / 2023 / day15.eli5m4

dnl -*- m4 -*-
dnl This is my attempt to let you peer in on the internal workings of
dnl my golfed O(n^4) m4 solution for day 15.
dnl Name your input file "I" (as in the Roman numeral one), or pass
dnl the "-DI=path/to/yourinput" command line argument to m4.
dnl
dnl First things first: m4 is a macro processing language, from 1977.
dnl It is still a major player in building a Linux distro (any software
dnl that provides a configure script from Autoconf or which describes
dnl its own parse grammar using Bison used m4 under the hood on the
dnl developer's machine), but few people code natively in m4 these days.
dnl See https://pubs.opengroup.org/onlinepubs/9699919799/utilities/m4.html
dnl for the POSIX requirements on what an m4 implementation must
dnl provide; this particular solution does not require any extensions,
dnl although I only tested with GNU m4 1.4.19.
dnl
dnl In m4, you can define any macro name to another blob of text, then call
dnl name(param, param...), where the parameters will be substituted into
dnl the $1, $2, ... placeholders in the substitution text; $@ expands into
dnl all the parameters as a quoted list.  m4 also recognizes () grouping
dnl (a comma separates parameters except when embedded in (), as well as
dnl quoted strings `like this', which intentionally use mismatched delimiters
dnl to allow nesting of quotes.  More on that below.  m4 does not include
dnl any built-in looping operators; instead, you can build your own by
dnl writing a macro whose expansion invokes the same macro, but with
dnl altered arguments.  In this manner, m4 behaves as a Turing complete
dnl language.
dnl
dnl I'm going to solve the problem with just a single macro definition,
dnl although it will recursively invoke itself as many times as needed to
dnl conditionally perform various sub-tasks used in computing the final
dnl result.  It is also possible to use macros as a hashtable (mapping
dnl arbitrary text blobs to a macro name for recall later, rather than
dnl invoking those names as macros); but this solution does not use
dnl variables.  Without variables, the only thing left is a functional
dnl approach, rather than an imperative one.
dnl
dnl The dnl macro is special, in that it eats text until the next
dnl newline.  My golfed solution does not use dnl, but this one does,
dnl as my way of explaining the bits and pieces of my _ macro.  m4
dnl also includes # comments, but those cannot be used as nicely inside
dnl a macro definition (the advantage of dnl is that it is elided
dnl completely; while a # comment remains behind and would cause the
dnl expansion text to also contain the comment).  When building up a macro
dnl definition, m4 concatenates adjacent quoted strings; and when collecting
dnl arguments to a macro, m4 elides whitespace between the comma and the
dnl first non-whitespace byte (although even the dnl macro counts as such
dnl non-whitespace, despite expanding to nothing).  The golfed
dnl version does not take advantage of joining `' strings, but this
dnl version does in order to explain the pieces.  Thus, the following two
dnl contructs are identical:
dnl   define(`mymacro', `ifelse(cond1a,cond1b,`expansion1',
dnl   cond2a,cond2b,`expansion2')')
dnl and the version I use below:
dnl   define(`mymacro', `ifelse('dnl
dnl   dnl filler
dnl   `cond1a, cond1b, `expansion1','dnl
dnl   dnl more filler
dnl   `cond2a, cond2b, `expansion2''dnl
dnl   `)'
dnl
dnl Now it's time to dive into creating the definition for the one macro
dnl that we will be using; to minimize my use of letters, I named it _.
dnl
define(_,
dnl
dnl We want this macro to conditionally dispatch to a number of various
dnl subtasks, based on the first parameter.  The ifelse builtin in m4
dnl splits its input into triplets; once it finds two strings that match,
dnl the expansion of ifelse is the third argument.  All remaining parameters
dnl are still parsed, and $@ parameters expanded during that parse, but
dnl those clauses are ignored as long as they do not inject any unquoted
dnl commas into the stream to change the number of parameters seen by
dnl ifelse.  Because the _ macro uses so many triples in its lone ifelse,
dnl we are making the m4 parser do a LOT of throwaway work; but such is
dnl life when golfing a solution.
dnl
`ifelse('dnl
dnl
dnl For ease of exposition, I am going to comment each triple.  First up,
dnl my shift wrapper.  As I mentioned above, a common idiom in m4 is to do
dnl processing on the first (few) arguments of an arbitrary-length
dnl parameter list, then recurse back into the same macro with the remaining
dnl parameters (tail-recursion).  But duplicating the text shift($@)
dnl everywhere takes up valuable golfing space, so I compress it to _(^$@).
dnl Additionally, since some of my uses of _ take a (packed,list) as a single
dnl argument, while others need to get at the individual elements of that
dnl list as separate arguments, I use the idiom that every packed list starts
dnl out as (^,), so that I can then use _$2 to get at the elements inside
dnl the packed list passed in as parameter 2.
dnl
dnl The leading ^ is my one magic character, where it can be concatenated
dnl with arbitrary other text.  That is, _(^,a,b...) and _(^junk,a,b...) both
dnl expand to the sequence a,b....  All other calls to _() pass at most a
dnl single character for the first parameter.  (Having more than one magic
dnl parameter would require additional invocations of index; but unlike
dnl macros in the quoted third part of a triple, macros in the first or
dnl second position of a triple are unconditionally invoked, and must not
dnl call back into _() as that would cause infinite recursion).
dnl
dnl Note that m4 shift-recursion is INHERENTLY O(n^2) - if you want to process
dnl a list of n elements one at a time, you will tail-call the macro n times;
dnl each of those n macro calls will contain an average of n/2 parameters.
dnl This is on top of any algorithmic cost of what is being done in that
dnl recursion.  Hence, when you combine m4's O(n^2) tail-recursion with my
dnl O(n^2) list addition in _(^) below, you get O(n^4) algorithmic effects.
dnl While the example input with 11 elements completes in less than 50ms,
dnl the puzzle input with 4000 elements takes more than 26 minutes, more than
dnl four magnitudes of order slower.
dnl
`index($1,^),0,`shift($@)','dnl
dnl
dnl I've got two more builtins that I need to use frequently.  Time to
dnl write compressions for those, as well.  First is eval, for performing
dnl signed 32-bit math (thankfully, this puzzle does not exceed that),
dnl under the shortcut _($,expr)->eval(expr)->int:
dnl
`$1,$,`eval($2)','dnl
dnl
dnl Next, I need a way to split an input list element into single bytes for
dnl the HASH algorithm.  In GNU m4, substr(string,1) behaves differently
dnl than substr(string,1,) (the trailing blank causes a warning, and acts
dnl like a zero-length slice, rather than the rest of the string), so here,
dnl I need a packed argument _(~,(str,start)) or _(~,(str,start,end))
dnl ->substr(str,start...)->str
dnl
`$1,~,`substr$2','dnl
dnl
dnl With builtin wrappers out of the way, I found myself frequently doing
dnl so many shifts that I could still benefit from even more compression.
dnl This is a shift-4 macro: _(@,1,2,3,4,5,6...)->5,6,...
dnl There are 5 calls to _(^) because I also have to elide the @ in $1.
dnl
`$1,@,`_(^_(^_(^_(^_(^$@)))))','dnl
dnl
dnl The HASH algorithm takes the current hash value (always an integer) and
dnl the ASCII value of the next character to hash (possibly empty, when
dnl called to prime the hash and the first character is not yet known).
dnl The output remains raw text for now; but will eventually be passed to
dnl eval at later points in the expansion.
dnl _(&,cur,val)->int_expr
dnl This is one of the few triples with an unquoted third parameter, because
dnl there are no harmful side effects even when this branch is not selected.
dnl
`$1,&,($3+$2)*17%256,'dnl
dnl
dnl Next up, my scoring helper.  _(?,cnt,cond)1 expands to cnt+1 if cond
dnl is 0 (shown here), or to bare 1 if cond is nonzero (see below; I split
dnl the two halves of this helper solely to get nicer placement of line
dnl breaks in my golfed solution)...
dnl
`$1$3,?0,$2+,'dnl
dnl
dnl The actual scoring function.  Tail recursive: computes the score for
dnl the first triple in the list, then recurses on the rest of the list.
dnl The recursion ends when label1 is empty.  Note that the call to the
dnl scoring helper for computing nextslot  is written so that it forms a
dnl valid eval expression even when box2 is not available.
dnl _(>,slot)-> end of recursion
dnl _(>,slot,label1,box1,focal1,label2,box2,focal2...)->
dnl   output "+slot*box*focal", tail-call _(>,nextslot,label2,box2,focal2...)
dnl
`$1$3,>,,'dnl
`$1,>,`+($2)*(1+$4)*$5_(>,_(?,$2,_($,$4-$7+0))1,_(^_(@,$@)))','dnl
dnl
dnl List removal. Checking for one label to remove is O(n) on failure,
dnl although on success it can shortcut by using the rest of the list
dnl unchanged.  First, the two special cases: end of list, and name match
dnl _(-,name)-> end of recursion
dnl _(-,name,name,box,focal,name2,box2,focal2..)-> output "name2,box2,focal2.."
dnl
`$1$3,-,,'dnl
`$1$2,-$3,`,_(^_(@,$@))','dnl
dnl
dnl ...and here is the rest of the score helper, mentioned above
dnl
`?,$1,,'dnl
dnl
dnl Back to the recursive workhorse of the removal function, on name mismatch:
dnl _(-,name,name1,box1,focal1,name2,box2,focal2...)->
dnl  output "name1,box1,focal1,", tail-call _(-,name,name2,box2,focal2...)
dnl
dnl The net result is that (^,_(-,name,_LIST)) produces an updated LIST with
dnl the triple associated with name, if any, removed
dnl
`$1,-,`,$3,$4,$5_(-,$2,_(^_(@,$@)))','dnl
dnl
dnl Now a pair of mutually recursive helpers used for list addition.
dnl Ultimately, we want (^,_(+,name,box,focal,_LIST)) to produce an updated
dnl LIST with name amended in-place or added in the correct sort order (after
dnl all other triples with the same box, but before any triple with a larger
dnl box). To do this, I split up the output into two halves: the left half
dnl produced by _(*,...) contains any list elements known to be correct, plus
dnl the opening ( and possible first arguments of a final macro call, while
dnl the right half produced by _(*,...) contains the tail of the LIST
dnl unaffected by the left half, as well as the closing ) to perform that
dnl final macro call.
dnl
dnl The general form _(*,cond+,name,box,focal,name2,box2,focal2) has three
dnl subcases:
dnl _(*,1+,name,box,focal,name2,box2,focal)->
dnl   box sorts before box2, output ",name,box,focal,name2,box2,focal2" and
dnl   prepare to tail-call _(^,name3,box3,focal3...)
dnl _(*,0+,name,box,newfocal,name,box,oldfocal)->
dnl   updating box in-place, output ",name,box,newfocal" and prepare to
dnl   tail-call _(^,name3,box3,focal3...)
dnl _(*,0+,name,box,focal,name1,box1,focal1)->
dnl   no match yet, output ",name1,box1,focal1" and prepare to tail-call
dnl   _(+,name,box,focal,name3,box3,focal3...)
dnl
`$1$2,*1+,`,$3,$4,$5,$6,$7,$8,_(^','dnl
`$1$3,*$6,`,$3,$4,$5,_(^','dnl
`$1,*,`,$6,$7,$8_(+,$3,$4,$5','dnl
dnl
dnl List addition.  Uses _(*) to generate earlier elements, then proceeds to
dnl tail-call either _(^) or _(+) if there are more elements in list.
dnl _(+,name,box,focal)-> end of recursion, output ",name,box,focal"
dnl _(+,name,box,focal,name2,box2,focal2,name3,box3,focal3...)->
dnl   provides output ",name3,box3,focal3...)" to couple with tail-call started
dnl   in the _(*) helper.  We only need to shift away 7 elements, but since
dnl   we only have shift-1 _(^) or shift-4 _(@), this creates an empty 8th
dnl   element and uses shift-4 twice.
dnl Like deletion, this is worst-case O(n) for one addition (the triple needs
dnl to be added at the end), but short-circuits if it finds the right box or
dnl updates a name earlier in the list, or O(n^2) for addition of n elements.
dnl
`$1$5,+,`,$2,$3,$4','dnl
`$1,+,`_(*,_($,$3<$6)$@),_(@,_(@,,$@)))','dnl
dnl
dnl Element processing. Given an element label- or label=digit, we kick off
dnl the HASH processing for that element.
dnl _(!,prevhash,(^,LIST))-> end of recursion. Output "prevhash)" to finish
dnl   the open-ended _($ that collected all element hashes for part 1, then
dnl   output "_(>,1,name1,box1,focal1,..." to start an open-ended collection
dnl   of all scores for part 2.
dnl _(!,prevhash,(^,LIST),element1,element2...)->
dnl   output "+prevhash" to the ongoing collection of part1, then tail-call
dnl   _(!,_(%...),element2...) where _(%...) supplies both the hash and
dnl   updated LIST based on element1
`$1$4,!,`$2) _($,_(>,1,_$3)','dnl
`$1,!,`$2_(!,+_(%,0,,,$4,$3),_(@,$@))','dnl
dnl
dnl HASH processing.  Updates the hash by the value of the current character
dnl extracted from element.  Prime with _(%,0,,,(^,LIST),element), then
dnl subsequent calls are _(%,value,prefix,curchar,tail).  Recursion will
dnl always end when curchar is = (addition, tail is a single digit) or -
dnl (deletion, tail is empty); this works even when elementtail includes a
dnl trailing newline supplied with the final element of the input file.
dnl _(%,box,name,-,,(^,LIST))-> end recursion: output the result of
dnl   HASH(label-) for part 1, then ",(^,LIST)" with LIST modified to drop
dnl   name using _(-)
dnl _(%,box,name,=,focal,(^,LIST))-> end recursion: output the result of
dnl   HASH(label=focal) for part 1, then ",(^,LIST)" with LIST modified to
dnl   add or update label hashed to box with the value focal
dnl _(%,partial,oldprefix,oldchar,oldtail)-> tail-call _(%,newvalue,newprefix,
dnl   nextchar,newtail) where newvalue is determined by hashing in oldchar to
dnl   partial, newprefix is oldprefix with curchar appended, nextchar is the
dnl   first byte of oldtail, and newtail is everything else in oldtail
dnl
`$1$4,%-,`_(&,$2,45),(^_(-,$3,_$6))','dnl
`$1$4,%=,`_(&,_(&,$2,61),$5+48),(^_(+,$3,$2,$5,_$6))','dnl
`$1,%,`_(%,_(&,$2,_($4)),$3$4,_(~,($5,0,1)),_(~,($5,1)),$6)','dnl
dnl
dnl Special case for no input; useful for priming _(&) when the first
dnl character is not yet known
dnl
`$1,,,'dnl
dnl
dnl Final catchall clause, used for mapping bytes to ASCII. This conditional
dnl will only be reached if $1 is a letter, since _(%) takes care of =, -, and
dnl digits.  Only 19 letters appear in the actual puzzles (no [aeiouwy]),
dnl but the example puzzle includes a and o.  This could be made one byte
dnl shorter as index(cdef...,$1)+99 and still get the right result for _(b),
dnl but it would miscalculate the hash of _(a) in the example puzzle.
dnl
dnl It is also possible to avoid the second index(), by open-coding a series
dnl of triples, such as $1,b,98,$1,c,99,...,$1,z,122, although that takes
dnl more bytes and no longer golfs to less than 2 punchcards.
dnl
`index(bcdefghijklmnopqrstuvwxyz,$1)+98'dnl
dnl
dnl With that, the ifelse is complete, and our definition of _ is finished.
dnl
`)')dnl
dnl
dnl Now to put it all to work. Start an open-ended _($) that will collect
dnl all the output for the part 1 HASH values; when the open-ended list of
dnl elements provided by include(I) reaches the end of recursion, _(!) will
dnl then close that macro, and open another _($) to collect the output of
dnl the scoring function applied to the final value of the (^,LIST) parameter.
dnl
_($,_(!,,,include(I)))