Advent Of Code

I've had a few comments on my Uiua solutions asking how you're even supposed to understand them, so I thought I'd write a little explainer.

Uiua is a new language that uses the array programming paradigm (other languages in this family are APL, J, K, R and BQN). This approach recognises that a great deal of programming is about the manipulation and interrogation of arrays of data and so provides tools to handle arrays of data as fundamental units. So rather than building nested for-loops to access data items, you manipulate the array as a whole, e.g. to add 1 to every element of a multi-dimensional array A, you would simply write +1A. This approach not only makes some aspects of programming easier, it also means that the compiler can generate extremely efficient code, and in principle make use of massively parallel processes for further speedups (I don't know to what extent Uiua supports this). Array programming languages are very useful for people who want fast processing of large amounts of multidimensional data, e.g. audio, video, scientific data, or financial data.

There are three factors that can make Uiua code hard to understand.

First, as we have already seen, Uiua is an array programming language, which not only mean that it uses a very different approach to problem solving, but that it also inherits that family of language's love of using glyphs for operator names rather than ascii names. Using the Uiua online editor and learning the documentation are the only ways to deal with this massive barrier :-(

Second, Uiua is stack based, so values are normally held on the stack rather than in named variables. This introduces some of the same challenges as writing in Factor, Forth etc, where you have to build up a mental model of what's on the stack at any time. There are variables available, but idiomatic code tends to avoid them as far as possible.

Third, function application is generally in mathematic order i.e. right-to-left. This can be complicated by some operators having different numbers of arguments which affect the binding order, but you learn to see through that…

Okay, so given all of that, how does one interpret some Uiua code? Let's work though my solution to day seven.

Data   ← ⊜(□⊜⋕⊸(¬∈": "))⊸≠@\n "190: 10 19\n3267: 81 40 27\n83: 17 5\n156: 15 6\n7290: 6 8 6 15\n161011: 16 10 13\n192: 17 8 14\n21037: 9 7 18 13\n292: 11 6 16 20"
Calib! ← ≡◇⊢▽⊸≡◇(∈♭/[^0]:°⊂) # Calibration targets which can be constructed from their values.
&p/+Calib!⊃(+|×)Data
&p/+Calib!⊃(+|×|+×ⁿ:10+1⌊ₙ₁₀,)Data

What the heck does it all mean?

Let’s find out! We'll go through it step by step.

Line 1

Data ← ⊜(□⊜⋕⊸(¬∈": "))⊸≠@\n "190: 10 19\n3267: 81 …. a string ….”

⊜(…)⊸≠@\n Can be read as partition (⊜) the string by building an array of sub-strings where each char is not \n (≠@\n) then perform the first function (i.e. the code in parentheses) on each sub-string in turn, concatenating each of the results into an array.

□⊜⋕⊸(¬∈": ") For each of these sub-strings, we immediately re-partition it by only keeping those characters that are not in string “: “, and then for each of these resulting (sub-sub-)strings, parse it as a number (⋕). As each of the lines has a different number of entries, the outer partition would not be able to build a regular array, so we box (□) each line before passing it out to hide the contents away, allowing the outer array to be built successfully.

So at this point, Data has been defined as a constant looking something like [[190 10 19] [3267 81 40 27] …etc… ]

Line 2

Calib! ← ≡◇⊢▽⊸≡◇(∈♭/[^0]:°⊂)

Calib! is a ‘macro’, that is a function that takes a function as its first argument and then inserts it into its own body whenever it sees a ^0

▽⊸≡◇(…) Means only keep those lines of the array that meet a certain condition (▽⊸≡◇ reads as “keep by rows content” where 'content" means 'look inside the box').

∈♭/[^0]:°⊂ This is where the power of an array programming language really starts to show.

For each row of the input this is passed the numbers in that row as an array. First we remove the first entry (our target) and push it down the stack for later :°⊂.

Then we reduce (/) the rest of the array by repeatedly applying a function on the result so far and the next element. The function here is partially suppled by the macro substitution, so for part 1 this would be in full [⊃(+|×)] This means ’take the two arguments and fork (⊃), or perform two functions on them, wrapping the results in an array [...].

Some magic happens here: Uiua supports ‘pervasive’ application of functions, so executing + 5 [[1 2] [3 4]] gives [[6 7] [8 9]]. For each succeeding entry in the list of numbers, we’re adding, and multiplying (and concatenating for part 2) it to every existing result, and storing these new results in a new dimension of the accumulated array.

Finally, we flatten (♭) this monstrous array into a single list of numbers and check whether that target value is in this list (member ∈) . That true/false is passed out to the surrounding ‘keep’ functionality.

≡◇⊢ Now we have kept only the lines where the target can be calculated from the numbers. So all we have to do is pass back the ≡◇⊢ “rows contents first” i.e. the first number in each line.

Lines 3 and 4

&p/+Calib!⊃(+|×)Data
&p/+Calib!⊃(+|×|+×ⁿ:10+1⌊ₙ₁₀,)Data

Call the macro on the data array, with the two different sets of operators. /+ is reduce (/) by addition (i.e. sum the results).

+×ⁿ:10+1⌊ₙ₁₀, Takes a copy of the second number, get the floor of the base-10 log, adds 1, raises 10 to that power and multiplies the first number by that before adding the second number. This is an arithmetic concatenation, which works as a pervasive operator as discussed above. [N.B. I just couldn't get ⋕$"__" or similar string approaches to work in this context. If you know how to, please let me know!]

That's it. Problem seven dealt with in 72 tokens :-)

Next steps

If you want to learn more run the code, read the Uiua language tour, explore that website and documentation, or ask away here. I'm by no mean an expert, but I'm happy to help with the basics.