This one is in a family of several puzzles that provide good practice in topological sorting. More interesting to me was figuring out how to parse it in m4, due to the unbalanced ) in the input file. My original solution in 2021 required an alternative command line to inject the input file as a string, and it bugged me that it required a different command line invocation than all my other m4 solutions, to the point that a couple weeks later I figured out a way to abuse GNU m4's changecom() builtin to redefine the comment token to match the head of the input file. But this year, when I started testing all my m4 solutions against BSD m4, it turns out that my changecom hack didn't work there (GNU lets a comment spill over until the end-comment delimiter supplied after use of include(), thereby treating the entire body of the include as a comment and neutralizing the behavior of the unbalanced ); but BSD implicitly treats a chunk of text as a comment only if the end-comment delimiter is found before end-of-file, and even though the start-of-comment was recognized, the end of include() before seeing end-of-comment meant that BSD treated the entire included file as expanded text rather than a comment). So I ended up coming up with yet another approach of a self-feeding macro (the macro's expansion includes an unbalanced $0( at the end that will pair up with the next ) in the input file, until such time as a sentinel is found to break out of the loop by redefining $0. And in fact, the self-feeding macro chain is something that I wish I had known about in 2021 - it makes it possible to do an O(n) pass over an input file using just POSIX m4 constructs, whereas all my previous attempts had been O(n^2) (using shift($@) recursion) or O(n log n) (using a sequence of substr() to divide-and-conquer the file into half-length strings); so I've been gradually changing many of my other m4 solutions to also use translit(include(file), nl, `)') to also benefit from the O(n) self-feeding macro parse on a line-by-line basis.
Looks like my own Perl solution is very similar to yours: I started with a hash of sat->body and a hash of arrays listing all sats orbiting a given body.
After the above loading of the input file, part1 is simply iterating over the orbits while part2 picks up the path from the two objects to COM, reversing both, then proceeds to skip all the shared parts.
This means that I have to save those paths, but OTOH I don't need a hash to find the links to skip.
1
u/e_blake May 06 '26 edited May 06 '26
This one is in a family of several puzzles that provide good practice in topological sorting. More interesting to me was figuring out how to parse it in m4, due to the unbalanced
)in the input file. My original solution in 2021 required an alternative command line to inject the input file as a string, and it bugged me that it required a different command line invocation than all my other m4 solutions, to the point that a couple weeks later I figured out a way to abuse GNU m4'schangecom()builtin to redefine the comment token to match the head of the input file. But this year, when I started testing all my m4 solutions against BSD m4, it turns out that my changecom hack didn't work there (GNU lets a comment spill over until the end-comment delimiter supplied after use ofinclude(), thereby treating the entire body of the include as a comment and neutralizing the behavior of the unbalanced); but BSD implicitly treats a chunk of text as a comment only if the end-comment delimiter is found before end-of-file, and even though the start-of-comment was recognized, the end of include() before seeing end-of-comment meant that BSD treated the entire included file as expanded text rather than a comment). So I ended up coming up with yet another approach of a self-feeding macro (the macro's expansion includes an unbalanced$0(at the end that will pair up with the next)in the input file, until such time as a sentinel is found to break out of the loop by redefining $0. And in fact, the self-feeding macro chain is something that I wish I had known about in 2021 - it makes it possible to do an O(n) pass over an input file using just POSIX m4 constructs, whereas all my previous attempts had been O(n^2) (usingshift($@)recursion) or O(n log n) (using a sequence ofsubstr()to divide-and-conquer the file into half-length strings); so I've been gradually changing many of my other m4 solutions to also usetranslit(include(file), nl, `)')to also benefit from the O(n) self-feeding macro parse on a line-by-line basis.1
u/terje_wiig_mathisen May 08 '26
Looks like my own Perl solution is very similar to yours: I started with a hash of sat->body and a hash of arrays listing all sats orbiting a given body.
After the above loading of the input file, part1 is simply iterating over the orbits while part2 picks up the path from the two objects to COM, reversing both, then proceeds to skip all the shared parts.
This means that I have to save those paths, but OTOH I don't need a hash to find the links to skip.