Impatient Idealist

Languages and Thoughts

AWK: day 5, day 7, day 12

AWK is a simple language for transforming text—particularly multi-field delimited text—frequently used when sed would be too painful. The general structure is "run this block of code when the current line matches this pattern," it automatically converts between strings and numbers, and it's got global variables so you can accumulate results and print them at the end. In recent years I've written some AWK code that's more complex than "print just the second column of ps", so I thought this might not involve as much language learning as I like to do in AoC, but AWK is just so good at what it does that it seemed prudent to build some runner infrastructure so I could whip a quick program out and go to bed. I did end up learning some things about AWK arrays, and I think the day 7 solution is kind of elegant.

dc: day 1 and day 6

dc is a stack-based "desk calculator" from back when people had reverse-Polish HP calculators on their desks. It's one of the oldest Unix programs (predating the C programming language), and writing code for dc feels a bit like writing in assembly. It's got two data types: numbers and strings. 256 memory registers are available, each identified by a single character. The registers are themselves stacks. Operators are one or two characters and spaces are only required to separate number literals, which is reasonable for arithmetic like 1 2 3 4*/+ but challenging to read for something like [la1+sa]sz, which is "store a macro in register z that increments the number in register a." My practice with stack programming in PostScript last year was helpful, but programming in dc is still a bit of a mind twist. Fortunately the f operator prints the stack, so it's easy to try out part of a program and see what effect it has on the stack. Since dc doesn't have a "read from standard input" operator, I used sed to turn my input file into a dc program, with macros declared at the start and a few print operators at the end. After my trip I discovered that dc is still under active development, with GNU dc gaining r and R operators to rotate several items on top of the stack. I'd used these in my program, but the macOS version on my 11-year-old Mac Mini hasn't upgraded yet, so I worked out how to implement top-3 rotation manually: [S1S2S3L2L1L3]sR [S1S2S3L1L3L2]sr.

gvpr: day 8, day 11

gvpr is an "AWK-like" language for processing graphs in Graphviz format. The dot and neato tools are very handy for visualizing your input file in AoC problems that can be represented as a directed or undirected graph. I became aware of gvpr on day 25 when I solved the main part of the problem by staring at a graph, and then wanted code to determine the size of graph subcompoents. The concept of "AWK for graphs" is appealing, but the execution is pretty painful. You know you might be in trouble when half of the time you Google for something about the language one of the top hits is a forum post titled I'm trying to use gvpr. Is that a mistake? with project devs basically saying "yes, it's poorly designed." I felt a weird sensation of writing code that looks at first like it's AWK, but as I got into details, it started to look more like programming in C. Sharp edges included a lack of safe defaults for missing attributes, awkward naming (which end of an edge is the head and which is the tail? the answer may shock you!), functions that don't respect variable scope, and the inability to use the AWK-like matching constructs if you build the graph programmatically rather than piped in as DOT. Oh, and it's kinda slow (or I could only figure out how to write an inefficient version for day 8).

jq: day 3, day 4

jq is a terse language for processing JSON input, in the tradition of tools like sed and awk. I've used jq a lot in recent years—it's great for playing with new APIs or pulling the one piece of data you need from a JSON download—but I still felt like I didn't entirely get it, particularly in correctly working with nested array data. jq is a functional language structured as pipelines, and if there's one thing a functional language loves it's small programming puzzles. On day 3 I got twisted up and spent a bunch of time banging my head on incorrect approaches. Day 4 I'd already solved inefficiently with shell pipelines, so it was a matter of functional translation and then recursive iteration. The language is still a little brain-twisty, but I think I've got the hang of it now.

Jsonnet: day 10

Jsonnet is a different purely functional language for transforming JSON input. It's inspired by an internal configuration language at Google, having removed some features that are widely considered a bad idea. Jsonnet is lazily evaluated and allows for infinite data structures: you can have an infinite array, but if you only ever access a few specific elements it won't try to figure out all the other values. It's written declaratively, and allows prototype-style inheritance: "make an object like that one, but override this property." Contrary to many of my former colleagues, I happen to enjoy the internal config language, and "find an excuse to use Jsonnet for something clever" was one of the reasons I chose to focus on glue languages this year. Part 1 of day 10 seemed like a good fit for Jsonnet's ability to make inferences, but I thought up an overcomplicated approach and kept overflowing either Jsonnet's internal stack or the underlying Go maximum stack size, depending on just how I ended up with excess recursion. I switched to Go (a language that's efficient and good at making coding mistakes obvious) and solved part 1, but then got stuck on part 2 for a couple weeks of trying to re-learn linear algebra. I still wanted to work out a Jsonnet implementation, but didn't want to figure out how to do recursive lazy matrix reduction on immutable objects, so I was pleased to read through an excellent tutorial on a bifurcation approach which reduced the problem search space in ways I was grasping for but couldn't figure out the first time. It still took some careful work to get this to work in Jsonnet, including discovering the undocumented tailstrict keyword and figuring out how to structure a tail recursive function with lazy evaluation and multiple if clauses. I fortunately chose to implement this on my Mac which had the Go Jsonnet implementation rather than the original C++ one on Debian-derived Linux. The Go interpreter finishes in a tedious minute and a half but the C++ interpreter gets completely stuck, as far as I can tell. (One downside of a lazy functional language is that the "print a debug message" function only outputs after the recursive function it wraps finishes, so "where is my program getting stuck" is tough to figure out.

Lua: day 10

Lua is a small language designed to be embedded in other programs that need an interpreter for user-written code. After two weeks of day 10 and linear algebra as my white whale, I finally got my Go implementation working. The code was full of failed attempts and half-commented-out functions, so I decided to transcribe the working solution to Lua and clean up the original Go later. I'm really glad I didn't try to do the whole month in Lua: it's got just enough to be a real language, but not enough to be very productive. Lua's only compound data type is the "table," an array that can have strings or numbers as keys. I've used languages like this before—PHP arrays are also "indexed arrays or hash maps" and JavaScript arrays are technically objects with indices as string property names—but this gets extra awkward in Lua. Integer indices are treated specially, so if you want to use it as a sparse hash map with numeric keys, you might not get all your data back when iterating. Object orientation is available, but if you want to use an object as a table key you need to go back and forth with string conversion, which gets slow. The standard library has a few useful string functions, but misses a lot of really handy utilities that you'd find in a language like Perl, Python, or Ruby. If "write your vimrc and plugins in Lua" is the compelling reason to switch to Neovim, I'll stick with Vimscript.

Perl

Perhaps the pinnacle of glue languages, Perl was the first programming language I ever got comfortable with. In high school and college I really enjoyed writing Perl code, and the quirky community around the language. In the last two decades I don't think I've edited a Perl file, but I've used it for plenty of one-liner scripts at the command line. I wrote a runner script for Advent of Code in Perl, but didn't end up using it this year. I was struck with how clunky some things felt. A simple Perl script is really slick at doing something for each line of all input files, but treating each argument as an independent list of lines—and reading stdin if no files were specified—was surprisingly verbose. Needing to explicitly use a reference (pointer) to pass a list as an argument (rather than having an operator to explicitly splat a list into multiple arguments) also felt awkward coming from any other programming language.

Ruby: day 12

Ruby was clearly inspired by Perl, but brings a strong object-oriented philosophy and borrows heavily from the functional programming community. This is a questionable inclusion as a "glue language," and many companies run multi-million user websites with just Ruby. But like other glue languages it's got functions to simplify common tasks, easy string processing, and a quick iterative development cycle. I wrote a bunch of Ruby a decade ago as part of a replacement for a Burning Man system, but then abandoned that effort. I had Ruby in my toolkit in case I encountered something that was going to be complicated, and when I read day 12's space packing puzzle while still exhausted from day 10, I decided I needed a language with a full suite of composite data types. The puzzle has a trick that I found distasteful: the example input is really hard, but if you add the right check the actual input is easy. I spent a long time trying to come up with potential optimizations and shortcuts for what I recognized was an NP-complete problem, but the code always seemed to run for an unreasonably long time on the example input. Once I realized the input trick (some lines were getting processed a lot faster than others), I got grumpy and posted a couple cheeky implementations in other glue languages. A couple weeks later I came back to the problem, since I had been enjoying trying to optimize the placement of puzzle pieces on a grid, and the ASCII art output was fun to look at. After some time learning to use the Ruby profiler, I ended up with a solution that only takes about 3 minutes on the example input, though it does leave out one axis of permutations that could in theory find a solution. Coming back to Ruby a decade later, I still like the language. It's got a few sharp edges, but I think it's still a good language to have in your toolkit. The irb interactive environment has also gotten really nice, providing syntax highlighting and autocomplete despite Ruby's very-dynamically-typed nature.

SQL (spatial): day 9

SQL is the world's most popular database query language, and there are several folks who use it to solve all AoC problems, though sometimes things get pretty awkward. The last couple years at work I spent a bunch of time working with spherical geometry, and got to know the ST_ (spatio-temporal) functions of the Simple Features standard. Google's SQL dialect and systems support these, and I even wrote a SQL function to compute the angle of the sun at the start of each GPS track in our dataset. I hadn't played with other spatial databases, though, so I bent my "you might already have installed" theme and my "standard library only" rule a bit and installed PostGIS for PostgreSQL and SpatiaLite for SQLite. When you've got a geometry library at hand, this puzzle is quite simple :-) Runtime is kinda slow, since it's doing a cross join of every point in the input. It's also important to remember that the "S" in "SQL" stands for "Structured" and not "Standard", so I had to write the query twice: SpatiaLite doesn't consistently follow SFS naming. My first attempt at day 9 was a fun use of ImageMagick a glue tool for image processing, but creating a 100,000 pixel square image (10 gigapixels) and taking slices of it was not a task my old Mac Mini was up to. I also tried using rsvg-convert in the hope that staying in vector space for image slicing would work, but it seemed to be rasterizing as well.

Z shell: day 2, day 4, day 6, day 12, and runner infrastructure for niche languages

I've been using zsh as my login shell for more than a quarter century, but I still need to look at the man page whenever I need to do something more complex than a foreach loop. Day 2 was solved entirely with zsh builtins. Day 4 launched a pipeline of 6 commands within a loop, using head | tail | cut | tr | xargs printf to extract 3x3 sections of a grid. This took 45 seconds to run on part 1 (and 12 minutes on Android: forking a process is expensive, kids!), so I switched to jq for part 2. Day 6 used a grep | cut | pr | sed pipeline, but the loop didn't have as many iterations, so it wasn't untolerably slow. The use of dc in day 6 was just so I could be cute and not do arithmetic in the shell.

Go: day 10

This definitely doesn't count as a "glue language that might already be on your system," but it's my fallback for puzzles where I get stuck or my approach is too slow in an interpreted language. Day 10's second part requires finding the minimum number of steps to reach a goal in a rather large possible search space. I experimented with a lot of approaches to reducing the search space, and took advantage of Go's treatment of fixed-size arrays as value types to optimize performance as much as I could. Most of my approaches were some variant of "keep a priority queue of states to explore," and memory use would often grow to tens of gigabytes. Some of the lines in the input could reach a solution pretty quickly, and other lines were amenable to different approaches to space exploration. I kept a cheat map of the answer for lines I'd previously found, which let me run my program for several hours on lines I hadn't yet solved, then stop when it hit a troublesome line and try a different approach without spending hours redoing old work. Running for days is a clear sign that I didn't have the right solution, but "find a solution and then optimize" is usually a good strategy. In the end I only had half a dozen unsolved lines out of 191, but those didn't seem amenable at all to any form of state-space exploration. In the solutions thread for another day, I saw a tangential reference to day 10 as a system of equations and said "Of course!" I'm not very good at recognizing linear algebra problems, and very shaky at writing code to solve them. One challenge for linear programming in Advent of Code is that everything is an integer (and in this problem, no negative numbers), while most matrix solvers assume real numbers. Over the course of a couple days I re-read my linear algebra textbook and Wikipedia pages about Gaussian elimination. I adapted it to an integers-only system of linear equations implementation, but still got hung up on some of the inputs because the scalar factor between two rows would result in non-integer values somewhere. Through more Internet research I learned that integer linear programming (rather than the more general linear programming) is what I was doing, and wound up writing code to compute the Hermite normal form, though I then realized that making full use of the HNF matrix would get complicated. I also tried Octave and Scilab (two open-source Matlab-like languages) which count as more "glue-like." Octave refused to do matrix solving on integer-typed data. I found a library for Hermite computation for Scilab but decided that path was getting too complicated and went back to writing Go code. Eventually I realized that I could produce a triangular matrix by just repeatedly subtracting rows with a value in the column; eventually it'll end up with 1-1=0 to eliminate a cell. This finally got an answer to the whole input with just a few minutes of runtime, and later profiling and tweaking got it to the 2-digit seconds range after realizing I could swap column positions and reduce the number of free variables. I definitely spent way too much time on this bugbear of a problem, but it at least it was educational, and I'm funemployed with lots of time.

Languages I wanted to try

I've encountered a few glue languages that looked pretty interesting, but I didn't get a chance to try them out. dt is billed as "duct tape for your Unix pipes," clearly a glue language. I'd encountered it last year when researching stack-based languages; unfortunately the Nix packaging system wouldn't compile on my old Mac, so I gave up on the install. Clearly it's not yet at the "might already be on your system" level. I've seen someone (turns out to be the language's maintainer) in the r/adventofcode subreddit solving all problems with the m4 macro language, which I've mostly encountered as "the language used to generate your Sendmail config file." I spent some time reading an m4 language guide, and learned that doing math is complicated. I considered setting up in case there was a good text-transformation puzzle, but seeing that even loop constructs need a library I decided to save that bit of brain-bending for a future date. I also wanted to try Noulith, a language that wasn't actually written for the purpose of Advent of Code, but just as well could have been. I spent some time reading the docs while traveling, but didn't have time to get the interpreter set up to try it out. Maybe I'll give it a shot in 2026.