Kap solution to day 2 of Advent of Code

The below is a slightly edited version of a series of posts made on the Fediverse.

Note: The below explanation was written before Kap supported addition and subtraction for characters. With this change, the calls to toCodepoints and fromCodepoints can be replaced by character-@\0 and codepoint+@\0.

For anyone not familiar with the syntax of APL and it's varations, the most important thing to keep in mind about the syntax is that for function calls, the parser binds to the right. It also evaluates its arguments from right to left.

What this means is that the following code: io:println 1 + math:sin 2 is evaluated like this:

a0 ← math:sin 2
a1 ← 1 + a0
io:println a1

Another important fact is that Kap functions are either monadic (they accept a single argument to the right of the function name) or dyadic (accepts two arguments, one on each side of the function). Some functions can be called both monadically and dyadically. One such example is - which subtracts when called dyadically but negates when called monadically.

With that in mind, let's take a look at the solution:

+/ 4 8 3 1 5 9 7 2 6 ⊇⍨ 3 (⊥⍤1) 65 88 -[1]⍨ unicode:toCodepoints 1 0 1 ⫽ ⊃ io:read "testdata.txt"

The input data is in the file testdata.txt, and the first thing that happens is that the entire file is read into an array of strings, where each element is one line from the file.

Each line is three characters, so we use the function which converts an array of arrays to a two-dimensional array of characters.

The next part is 1 0 1 ⫽. This function takes an array on the right, and uses the left argument (1 0 1) as a selector. I means to take one copy of the first column, zero copies of the second and 1 copy of the third column. In other words, this drops the centre column.

Starting with the example array we then get this:

    1 0 1 ⫽ ⊃ "A Y" "B X" "C Z"
┏━━━━━┓
┃@a @Y┃
┃@B @X┃
┃@C @Z┃
┗━━━━━┛

Example

We then call the function unicode:toCodepoints which converts the characters to the corresponding Unicode codepoints.

We then want to convert the codepoints to actual numbers from 0 to 2. This is done by subtracting 65 from the first column and 88 from the second. Naturally we use the - function to do this, but in order to avoid having to wrap the entire expression in parenthesis, we use the operator which reverses the arguments, putting value to be subtracted from on the right instead of the left.

I must also explain what the [1] means. Since the left argument is a 1-dimensional array, and the right argument is 2-dimensional, the operation will be applied along an axis. The default is that it will be applied along axis 0. If you put an axis within square brackets after the name of a mathematical function, the operation is instead performed along that axis.

The behaviour of the function when passed an axis parameter depends on the function itself. All mathematical functions use the axis parameter this way.

Let's run the code up to this point to see what happens:

    65 88 -[1]⍨ unicode:toCodepoints 1 0 1 ⫽ ⊃ "A Y" "B X" "C Z"
┏━━━┓
┃0 1┃
┃1 0┃
┃2 2┃
┗━━━┛

Example

What we see here is that each row in this array represents a binary number that uniquely identifies the game positions. All we have to do is find this number and assign each number a score, and we'll have solved the problem.

This is where the next two symbols come in. is used to decode a sequence of digits in an arbitrary base.

The other symbol, is an operator, just like , operators are is used to change the behaviour of a function. It's a higher level function if you wish. takes a function on the left, and a number on the right and derives a new function which calls the function on the left repeatedly, each with a subarray of a lower dimension. In this particular example, this means that the function will be called on each row of the input. The left argument is a scalar value, so it will always be the constant 3.

In other words, this decodes each row as a base-3 number and returns an array of these numbers:

    3 (⊥⍤1) 65 88 -[1]⍨ unicode:toCodepoints 1 0 1 ⫽ ⊃ "A Y" "B X" "C Z"
┏━━━━━┓
┃1 3 8┃
┗━━━━━┛

Example

This gives us a list of the game positions for each round, where each number is a value from 0 to 8.

Finding the scores for each position is outside the scope of the solution, but for this simple case of only 9 different combinations, doing it by hand was trivial. For larger number of combinations, one would have to write some code to do it.

There are a few different ways in which you can pick values from an array, but in this case we'll use . This function takes an array on the right, and a list of indices to the left. For each index, the corresponding value is looked up in the array and returned.

In our case, the indices are on the right, so we use to swap the arguments. Again, this is to avoid wrapping the entire expression in parentheses and putting the argument on the right.

The final function to be called is +/. This is used to sum all values in an array. For anyone familiar with functional programming, this is just a simple reduction.

The reduction operator is /, which takes a function on the left, and performs a left reduction using that function. In other words, the following: +/ 1 2 3 4 is equivalent to (((1+2)+3)+4).

For anyone familiar with APL, it's worth noting that this is different from how APL handles this operator. In APL, the above would be interpreted as: (1+(2+(3+4))). In the case of sums, this doesn't matter but for other functions it does, in particular if the function has side effects.

I can be reached on the Fediverse at @loke@functional.cafe