Advent of code 2024

So Advent of Code is done, and I made an actual effort this time. Of course I used Kap, and the final tally ended up being 32 out of 50 stars. I may solve some more later if I feel bored.

The Advent of Code problems tend to be very good fits for array languages, and array language solutions are often much shorter than solutions in other languages. In particular, the parsing which is often annoying in many languages often reduce down to a few characters in Kap.

Let's take a look at day 1 and solve it in Kap. I will attempt to describe the steps like one would solve it interactively in the REPL, rather than show a program and explaining how it works.

In practice, most of the you use Kap to solve problems, it is used as an interactive calculator. Compared to most other languages, the point at which one has to leave the REPL and open an editor instead is much later. Many of the early Advent of Code problems can be solved this way, for example. Day 1 is certainly one such example.

The description for day 1 basically boils down to the following problem:

Given a text file containing a 2-column list of numbers, match up the smallest number in each column and take the difference between them, then do the same with the second-smallest pair and so on. Finally sum up all the differences.

What this means is that we want to do the following:

Let's write the Kap code to do each of these steps:

Parse in the input file

We'll store the input in a file called part01.txt, which has the following form. I'll include 3 lines of input in order to make the examples small, but the actual input data contains 1000 pairs of numbers.

3   4
15  3
2   10

Kap provides a handy function called io:read which accepts a filename and returns a list of strings, where each string is one line from the input file. Thus, we can type the following:

    io:read "part01.txt"
┌→────────────────────────┐
│"3   4" "15   3" "2   10"│
└─────────────────────────┘

For each line, we want to split the string on spaces. This can be done using a Regex, but since this is such a simple split, we'll use a more traditional approach.

The function ⊂ takes a bitmap on the left, and an array on the right, and returns a new array where the elements are grouped based on the values on the right (the function can do more than that, but for example, this is all we need). Here's an example:

    1 1 0 1 1 ⊂ "abcde"
┌→────────┐
│"ab" "de"│
└─────────┘

To use this, all we need to do is to somehow create a bitmap that contains 0 wherever there is a space, and 1 otherwise. This is achieved by comparing the entire string with a space. The space character is represented using @\s, and we'll use the not equals function to compare each character in the string with a space. We can then put all of this together in a dfn. This is nothing more than a function where the right argument is assigned to the variable ⍵, and the left ⍺. In the below example, we don't pass a left argument, so only ⍵ is used:

    {(@\s≠⍵) ⊂ ⍵} "this is a test string"
┌→──────────────────────────────┐
│"this" "is" "a" "test" "string"│
└───────────────────────────────┘

Since we have an array of strings that we read from the file, we want to call this function once per element, which is achieved using the for each operator: ¨.

    rows ← {(@\s≠⍵) ⊂ ⍵}¨ io:read "part01.txt"
┌→──────────────────────────────┐
│┌→──────┐ ┌→───────┐ ┌→───────┐│
││"3" "4"│ │"15" "3"│ │"2" "10"││
│└───────┘ └────────┘ └────────┘│
└───────────────────────────────┘

We'll also convert the list of pairs into a 2-dimensional array, using ⊃ (documentation):

    rows ← ⊃rows
rows ← ⊃rows
┌→────────┐
↓ "3"  "4"│
│"15"  "3"│
│ "2" "10"│
└─────────┘

We also want to convert each string to a number, which is done using the parse number function: ⍎. We'll call this function on each element:

    numbers ← ⍎¨ rows
┌→────┐
↓ 3  4│
│15  3│
│ 2 10│
└─────┘

This code can of course be put together in a single line without having to store the intermediate results in variables. This is left as an exercise for the reader (or just look at the Codeberg repository).

Sorting the lists

There are many ways in which this can be solved, but this example will use a very straightforward approach by extracting the columns into individual variables and work with them independently. This works because the problem only has two columns. If there were more columns, this would of course not be practical.

To extract values from a given dimension, we can use the monadic version of ⊂. The monadic version is very different from the dyadic case that was used above. We'll use the axis form, which allows you to specify the axis by which the values should be extracted. In this case, we want to extract the values across the rows, meaning the first axis (axis 0). Thus, we'll type the following to obtain the two columns and assigned them to two variables, a and b:

    (a b) ← ⊂[0] numbers
┌→────────────────┐
│┌→─────┐ ┌→─────┐│
││3 15 2│ │4 3 10││
│└──────┘ └──────┘│
└─────────────────┘

a now contains 3 15 2 and b contains 4 3 10. But we also want to sort them, so let's do that:

a ← ∧a
b ← ∧b

Compute the differences

Now that we have the two sorted lists in a pair of variables, computing the differences is very simple. All we have to do is to subtract one from the other:

    a - b
┌→──────┐
│-1 -1 5│
└───────┘

We also want to take the absolute value of these numbers, which is achieved using the magnitude function: |:

    | a - b
┌→────┐
│1 1 5│
└─────┘

Sum the resulting values

Taking the sum of an array in Kap (or most other array languages) is one of those things that is used to demonstrate the flexibility of the language, and how you can leverage operators to express complex operations with very key keypresses, which is very useful when working interactively like we're doing here. In this case, we perform a reduction over the add function on the numbers in the list:

    +/ | a - b
7

And there you have it! The solution to the first part. The second part is a small extension to the first one, which we'll solve later.