Advent of Code 2024 solutions

A kind of K tutorial centered around my solutions to Advent of Code (AoC) 2024. If you haven’t solved these yourself, spoilers ahead!

Note: there are multiple dialects of K; I use ngn’s.

If you want just the code, that’s also on Github, albeit without syntax highlighting.

Day 1

3   4
4   3
2   5
1   3
3   9
3   3

i:+.'0:"i/1"
+/d|-d:-/(@/1<:\)'i     /part 1
(l;r):i; +/l*0^(#'=r)@l /part 2

So, to someone who knows K, nothing too weird is going on here, but presuming absolutely zero knowledge of the language, let’s go into extreme detail.

Parsing

i:+.'0:"i/1"

First off: you’ll need to read “in reverse”, from the end of the line. K has no operator precedence, and is always evaluated in right to left order. For example, 6 % 1 + 2 (where % is the symbol for division) means 6 divided by 3, which gives a result of 2.

Furthermore… % isn’t actually just the symbol for division, it (and most other symbols in K) has multiple meanings depending on context. It can be either used with two arguments, like 6%3, or with a single argument, on the right, like %4. In the single-argument case, which we call “monadic”, % means square root (so %4 returns 2).

The first line of code reads the inputs and parses it. 0: is a special command to read from a file as a list of lines, in this case the file being located at i/1 (where I put my input for day 1). We get an array of strings like this:

("3   4"
 "4   3"
 "2   5"
 "1   3"
 "3   9"
 "3   3")

From other languages, you might be used to lists being enclosed in [] square brackets, or perhaps {} curly braces. In K, they are enclosed in () parentheses, and the elements are separated by ; semicolons, or newlines.

But there are other ways to make lists! A string like "a b" is just a list of characters. And lists of numbers can be written using simple juxtaposition. Simply write multiple numbers with a space in between, for example 1 2 3 or 3.14159 2.71828 4.

So then, our next trick, an important one which sees use in most days of AoC: .'. Sorry, did I say K was read right-to-left earlier? I lied, there’s an exception: Adverbs.

The basic operations of K are verbs, most symbols like + or . do a thing. Adverbs modify those functions. Functional programmers may recognize them as “higher-order functions”, and K has 3 or 6 depending on dialect: ', /, \… and the same three with an extra colon ':, /:, \:.

Adverbs go to the right of the verb they modify. That is, .' is read left-to-right, inside of the line which is read right-to-left.

Monadic . means evaluate. It executes a string as K source code. It’s the easiest way to parse a string containing a number into an actual numeric value. Or, since it has all the power of K, including the aforementioned space-separated lists of numbers, a string containing two numbers into a list of two numbers.

The problem: . expects a string. A single string, and we have a list. That’s where ' (each) comes in. As the name implies, it makes a function apply to each element of a list instead of on the list as a whole. So, we’re executing each line of our input to get their values into a new list. We get the following:

(3 4
 4 3
 2 5
 1 3
 3 9
 3 3)

That’s a list containg 6 lists of 2 numbers. Now, we could work with this. But it’s more convenient to have it the other way: 2 lists of 6 numbers.

Monadic + is transpose. Like the matrix operation of the same name, it “flips” the axes of a two-dimensional list. At the end of all this, we : assign to i. And thus we have, as the value of i:

(3 4 2 1 3 3
 4 3 5 3 9 3)

Part 1

+/d|-d:-/(@/1<:\)'i

You’ll notice I’m not including the /part 1 at the end of the line in the earlier code block. Comments in K start with / following a space.

Now we get into the real meat of the solution. We start right back from our parsed input i.

Okay, there’s something in parentheses, with ' after it. An adverb like ' operates on verbs, so clearly what’s inside is a verb… but it’s not just one character like earlier. What’s happening here?

Remember how I said operators could be used with one or two arguments? I gave the example of %4 and 6%3… what happens with 6%, just an argument to the left? Well, it gives you a projection, practically a function, which allows you to “fill in” the right argument later. That means 6%3 and (6%) 3 are equivalent. Functional programmers might know this as “partial application”.

There’s another layer to this: you can remove the right argument from longer operations and “fill it in later” in the same way. A simple example would be 1+2*!. Monadic ! is “range” or “enum” or “iota” or “indices” (yeah, that’s a lot of names). It gives you a list of numbers from 0 until its argument. For example, !5 returns 0 1 2 3 4. K makes operating on arrays as easy as operating on any other number. It’ll automatically add as many “each”es as needed so you can e.g. multiply one number with an entire list. So 2*0 1 2 3 4 gives 0 2 4 6 8, and 1+2*!5 gives 1 3 5 7 9. Our 1+2*! example is a function that returns the first N odd numbers.

Under the hood, this is actually multiple separate projections, 1+, then 2*, then !, which when juxtaposed create a larger function which executes them in the usual right-to-left order. Functional programmers know this as composition.

Back to the AoC solution you’re here for: what the hell is @/1<:\? I’d rather explain later, so long story short: it sorts a list. K doesn’t have a direct “sort” operation, you have to go through some hoops, and this uses composition to do that.

We sort both lists individually. At this point we have (on the example input)

(1 2 3 3 3 4
 3 3 3 4 5 9)

Remember the problem statement: we want the difference between the lowest from each list, then the second-lowest from each list, and so on. We’ve sorted to match them up: now we want the difference between the first from each, the second from each left, etc.

So, we want a subtraction in the middle. If we had both lists separately we could do 1 2 3 3 3 4-3 3 3 4 5 9, but we have a list containing the two lists. Inserting an operator between every element of an array is the purpose of /, “fold”. We also use the fold adverb at the end of this part (start of the line) to +/ sum up the entire list.

So that’s what -/ does: it gives us a list with the differences by subtracting the lists:

-2 -1 0 -1 -2 -5

Oops, negative numbers! How do you get the absolute value of something? Well, it’s the | maximum between itself and its negative. We assign the result we have above a temporary variable, d, then negate it and pass it through maximum.

2 1 0 1 2 5

I’ve already explained the finale: +/ inserts + between elements to sum up the whole list. We’re finally done! By default, any line where the result isn’t assigned to anything gets printed out:

11

Part 2

(l;r):i; +/l*0^(#'=r)@l

This is arguably simpler. No details here that I’ll have to skip like sorting.

Notice the semicolon in the middle: this is two parts. I could’ve written it as two lines, but dense code is the K aesthetic.

(l;r):i

: does assignment, (l;r) looks like the creation of a list… this is destructuring. We’re assigning two variables, l and r from the two elements in our i list.

+/l*0^(#'=r)@l

The actual logic. Let’s start inside parentheses again: we start with =, “group”.

This gives us a dictionnary. Just like a HashMap, a JavaScript object, a Lua table, etc., K dictionnaries associate “keys” and “values”. ngn’s K denotes these as an array of keys, !, then an array of values. For example, 2 4!0.5 0.25 associates the key 2 with the value 0.5, and associates 4 with 0.25.

= group gives us a dictionary associating elements of a list with indices where that element appears in the list. Specifically, from our example (4 3 5 3 9 3) we get:

4 3 5 9!(,0;1 3 5;,2;,4)

You might guess that , allows you to create a single-element list, and you would be correct. Every value of this dictionary is a list. We’re not interested in the indices though, we only care about how many times the numbers appear.

Conveniently, ' each applies to dictionary on its values, so since we’re interested in how many times each element appears, i.e. how many indices it appears at… that’s the # length of each list:

4 3 5 9!1 3 1 1

Funnily enough, we’ve been manipulating arrays all this time and haven’t ever actually indexed into an array like you might in traditional imperative languages. That’s what @ does. But there’s a twist as always: just like everything in K, it works with arrays on both sides. When you provide multiple indices to the right of @, it gives you the value in the left array at each of those indices.

And the same goes with dictionaries. So now, we have associations between some elements and how often they appear in the right list. We want to know, for each number in the left list, how often it appears in the right list. That’s just @l!

3 1 0N 0N 3 3

Where’s that 0N coming from? Well, it’s null, the default value for when we couldn’t find something in the dictionary. Or in other words, it means the value from the left appeared zero times in the right list. We ^ fill those in with 0:

3 1 0 0 3 3

The last part is straightforward: we multiply with l. As all arithmetic, the each is implicit, the multiplication is element-wise. That is, multiplying 3 4 2 1 3 3 with 3 1 0 0 3 3 with do 3*3, 4*1, 2*0, and so on:

9 4 0 0 9 9

We finally sum up to obtain 31, and we’re done!

Day 2

7 6 4 2 1
1 2 7 8 9
9 7 6 2 1
1 3 2 4 5
8 6 4 4 1
1 3 6 7 9

i:.'0:"i/2"
A:1 2 3!&3
B:{&/~A(0>*x)-:/x}1_-':
+/B'i
+/{|/B'x_/:!1+#x}'i

Parsing

i:.'0:"i/2"

Same as before: each line consists of numbers separated by spaces. So, . evaluate ' each line. No transpose this time: this isn’t the kind of problem where it’s convenient. We put out two-dimensional array into i.

Part 1

A:1 2 3!&3
B:{&/~A(0>*x)-:/x}1_-':
+/B'i

We’re starting to get into problem sizes where functions are convenient, though not necessary. First, we define a dictionary. We’re using &, “where”, in kind of a perverse way, but I may as well explain it now as it will come in useful a lot in the future. Most often, we use & to go from a list of booleans to the indices of the trues (which we might then use e.g. in @ to filter a list). But it’s slightly more generic, it takes a list of integers and replicates indices according to its values.

In JS, you might write this as list.flatMap((x,i) => Array(x).fill(i)). For example, &1 0 1 4 2 returns 0 2 3 3 3 3 4 4. Or, more to the point, &0 0 3 gives 2 2 2, and &3 gives 0 0 0. The dictionary we’re actually constructing is…

A:1 2 3!0 0 0

Yes, we’ve only saved a grand total of 4 characters. But it’s an easy win, and it’s a bigger win in other situations, so it’s the kind of hack which becomes an instinct after writing K for long enough.

The second definition, B, is a function which will receive one line, or “report” as AoC lore will have it, and determine whether it is “safe”. It’s a composition ending with a lambda, which you don’t see often. Let’s go in order.

1_-': is a K and AoC classic. ': is each-prior. It applies a function with pairs of consecutive elements. In other languages’ libraries, -': might be called “deltas”. A quirk of eachprior is that it keeps the first element unmodified in its result, which means if we want just differences, we need to _ drop the first (1) element.

We haven’t talked about lambdas yet, so let’s do that now. Sometimes you’re going to need to make a function where you need to use an argument in multiple places, not necessarily just at the start (right of the last operator). K uses {} curly braces for its functions. And inside, you have two options: name the function’s arguments, or let K automatically detect them.

If I wanted to make a function to square a number, it would make sense to write {[n]n*n}, explicitly defining that my function takes one argument named n. If I wanted to generalize, make a function to take a number to an arbitrary power, maybe I’d do {[n;p] */p#n} (# take the number p times, insert multiplications). But there’s a default: x, y, and z. If you do {x*x}, you get the exact same square function. Your usage of x but not y is detected to mean there’s only one argument. The same goes for {*/y#x}, we use y to refer to our second argument, everything is automatically detected.

Back to AoC: {&/~A(0>*x)-:/x} doesn’t define its arguments, but it does use x and only x, meaning it has one argument. It starts with a very interesting form: (0>*x)-:/x. You might expect from previously that / would be fold, but not here. Folding, inserting an operation between elements, requires a function which takes two arguments after all… and the : in -: means we only want the monadic version of -.

Even knowing this doesn’t tell us exactly what / means in this context: it could be f/ converge, or f f/ while, or i f/ n-do… because despite -: being only monadic, -:/, a monad modified by an adverb, can be used with two arguments!

Here, to the left is (0>*x): is 0 > greater than the * first element of x (reminder: x here is the deltas of the one “report” line we’re assessing).

K does not actually have booleans; >, “greater than” returns, like other conditionals in K, either 0 for false or 1 for true. So we have an integer! That identifies our mystery / adverb as i f/ n-do.

Putting it all together: we apply - to x either 0 or 1 times, according to whether its first element is negative. This handles the fact that the puzzle description requires us to handle both ascending and descending sequences: we just rectify all-negative sequences into all-positive sequences. We don’t want to get absolute values using | max here like earlier, because we still want to notice if there’s a negative delta among an otherwise all-positive sequence.

Now we’re left with &/~A. A might seem out of place… wasn’t that a dictionary? Yes, it was, but here’s another trick up K’s sleeves: arrays and functions are treated one and the same (this will become more of a pattern later). @ isn’t just for indexing into arrays, it’s also function application! And the other way around, you haven’t seen me use @ as function application yet because you don’t need it unless it serves a syntax purpose. Well, the syntax is clear here, the indexing is implicit.

At this point in time, we’re going from a list of differences, for example 1 3 3 or 3 -1 4 1 to, when that difference is between 1 and 3, 0 (because A’s keys are 1 2 3 and its values are all 0), and otherwise 0N.

The next verb in the chain is ~ not. It gives 1 when you pass 0, and 0 for everything else. In other words, it inverts our previous 0/0N into 1 where the difference is within 1 2 3, and 0 otherwise.

Last is & min. As opposed to | max. The choice of the same symbols other languages use for “and” and “or” is not a coincidence: when you use 0 and 1 to represent booleans, “and” is just a special case of minimum. The same goes for or/max. And we do have booleans here: we’re taking a list of “is this one difference between 1 and 3”, and turning it into one boolean corresponding to whether the entire list is only made up of 1 2 3.

That’s basically it for the logic! +/B'i should be obvious now: for each ' line in the input, is it safe? We get an array of “booleans”, zeros and ones. How many are 1? Just sum up the list and we get our count.

Part 2

+/{|/B'x_/:!1+#x}'i

The logic here is mostly the same, except instead of checking “is this report safe”, we need to check whether the report, with any one of its values removed, becomes safe.

!1+#x is the range one longer than the indices of x. There are two things to consider for the x_/: two make sense.

First, X_i is “delete”, it removes one element from a list. Importantly, it requires for its right argument to be a single integer, not an array. And on the right we have an array of indices to individually remove. Remember how I said verbs modified by adverbs can be used with two arguments? You might guess it’s time again for ' each… but when used with arrays on both sides, it assumes the arrays are of the same length and pairs up the values from both. We want something different here: /:, each-right.

/: (each right) and \: (each left) have simple jobs, they pass individual elements of an array on one side, but just pass along the full array on the other side. In pseudo-JS, y.map(e => f(x, e)) and x.map(e => f(e, y)) respectively, whereas ' with arrays on both sides is basically x.map((_,i) => f(x[i], y[i])) (except it gives an error if x and y aren’t the same length).

So, we get an array with: x except its 0th element removed, x except with its 1st element removed, and so on… and at the end x unmodified because removing the #xth element of x does nothing (x does not have an element at that index).

Again, B' to check the safety of each of those new “reports”. We consider the report safe if any single one of the element-removed reports is safe, and that’s |/ or-fold to get the final safety value for x.

The final part is the same: an array of booleans we can just count with a +/ sum. That’s it for day 2!

Day 3

Day 3 is, in simple words, “this year’s regex problem”. Every year, AoC has a regex problem. Some K wizards solve it in K! I could very well be one of those, that does not mean an explanation of the necessary complicated tricks would be interesting.

If I find an elegant K solution, I may update this section, but until then, see you tomorrow.