day 25 optimize and improve heuristics

[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 orders of magnitude 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.  _(cond,cnt)1 expands to cnt+1 if cond
dnl is 1 (shown here), or to bare 1 if cond is 0 (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,1,$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_(>,_(_($,!($7-$4)),$2)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
`0,$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,..." from LIST to start an open-ended
dnl   collection of all scores for part 2.
dnl _(!,prevhash,(^,LIST),element1,element2...)->
dnl   output "+prevhash" to the ongoing collection of part1, then tail-call
dnl   _(!,[hash,LIST],element2...).  Note that the generation of the two
dnl   arguments hash and LIST is a two-step process: Calling _(%...) generates
dnl   the hash and a prefix "(^,_(OP,head...", while this supplies the suffix
dnl   ",_(^,LIST)))" to kick off either _(-) or _(+) to generate a new LIST.
dnl   This division of labor results in what appears to be unbalanced () in
dnl   the definition of _, but balances out during execution and lets m4
dnl   get away with processing fewer bytes.
`$1$4,!,`$2) _($,_(>,1,_$3)','dnl
`$1,!,`$2_(!,+_(%,0,,,$4),_$3)),_(@,$@))','dnl
dnl
dnl HASH processing.  This is a recursive helper that works with _(!) to
dnl provide the hash and updated LIST arguments for the next call to _(!).
dnl However, note that the output is split across functions: when recursion
dnl ends here, we produce only the prefix "hash,(^,_(OP,head"; the caller
dnl must provide the suffix ",name,box,focal...))" that then calls OP, either
dnl _(-) or _(+).  The caller primes with _(%,0,,,element), then subsequent
dnl calls are _(%,value,prefix,curchar,tail).  Recursion will always end
dnl when curchar is = (addition, tail is a single digit) or - (deletion, tail
dnl is empty); this works even when tail includes a trailing newline supplied
dnl 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 the prefix ",(^,_(-,name" to be joined
dnl   with the caller's suffix for producing LIST modified to drop name
dnl _(%,box,name,=,focal,(^,LIST))-> end recursion: output the result of
dnl   HASH(label=focal) for part 1, then the prefix ",(^,_(+,name,box,focal"
dnl   to be joined with the caller's suffix for producing 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','dnl
`$1$4,%=,`_(&,_(&,$2,61),$5+48),(^_(+,$3,$2,$5','dnl
`$1,%,`_(%,_(&,$2,_($4)),$3$4,_(~,($5,0,1)),_(~,($5,1)))','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 Not done in the golfed version, but done here: if your input file
dnl contains the substring ",dnl", then at some point the _(%) hash segment
dnl will unintentionally kill the rest of that line, with disastrous effects
dnl on computation.  I got lucky that my input file did not do that; and
dnl since all other m4 builtins use a vowel but the input file does not,
dnl there are no other possible collisions.  But this rename here ensures
dnl that the solution will be portable even to an unluckly input file.
dnl
define(`Dnl', defn(`dnl'))popdef(`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)))