Introduction
I am about half a year late to Advent of Code this year, but I recently decided to learn APL, and thought that Advent of Code would be a great way to practice. Although I will not be writing about every single solution, I did want to highlight a few that I found particularly interesting. Those interested in viewing the rest of my solutions can take a peek here.
Please note that, as an APL beginner, I make no claims about the efficiency or elegance of the APL implementations posted here. I write this post in the hopes that a walkthrough of the solution to a "real" problem in APL might help at least one other APL beginner.
The problem I want to look at here is 2021 Day 4, in which we are given a hundred bingo boards and a sequence of numbers that are called. In part 1, we wish to find the board state of the first board that wins. Then, in part 2, we wish to do the same for the last board that win.
Reading the input
input ← ⊃⎕NGET'input4.txt' 1
nums ← ⍎⊃input
boards ← {5 5⍴⍎⍕input[⍵]}¨(¯4+6×⍳100)+⊂(⍳5)
First, we need to read the input into variables that we can start to manipulate. ⊃⎕NGET'file.txt' 1 uses the ⎕NGET Dyalog system function to fetch all lines as a nested array, where each element corresponds to one line of text.
The numbers that are called are contained in the first line of input as comma-separated values, so we get the first line via ⊃input, and then "execute" it with ⍎. Conveniently, since the comma performs a catenation in APL, execution of the comma-separated list here correctly assigns an integer array to nums.
Then, to read in the boards, we first note that the first board is given on lines 3-7 of the input, the second on lines 9-13, the third on lines 15-19, etc. APL can easily generate a sequence of such sequences with a couple usages of index generation (⍳), which is what (¯4+6×⍳100)+⊂(⍳5) does.
(¯4+6×⍳100)+⊂(⍳5)
┌─────────┬─────────────┬──────────────┬─────────
│3 4 5 6 7│9 10 11 12 13│15 16 17 18 19│ ...
└─────────┴─────────────┴──────────────┴─────────
For each (¨) of these sequences, we run the anonymous function {5 5⍴⍎⍕input[⍵]}, which takes the 5 lines of input, formats (⍕) it (which effectively destructures the 5 strings into a single line of text), and then executes the resulting line to obtain a 25-element array of integers. Now that we have integers, we can reshape (⍴) this into a 5x5 matrix of integers.
Checking a bingo board
Perhaps the most natural first step is to write a function that returns whether a board has won for a given list of called numbers. I originally thought this was going to be the trickiest part of the problem, but it turns out APL makes this very easy:
isWin ← { b←⍵∊⍺ ⋄ ∨/(∧/b),(∧⌿b) }
This function takes an array of called numbers as the left argument and a 5x5 matrix representing a board as the right argument, and returns 1 if and only if an entire row or column has been called. It first computes an intermediate matrix b←⍵∊⍺, which produces a 5x5 boolean matrix with a 1 in the positions that have been called, and 0 in the other positions. Then, it performs both a row-reduction and a column-reduction over this matrix using logical AND ((∧/b) and (∧⌿b) respectively) to ultimately obtain 10 boolean values that indicate wins for each row and column.
For example, consider the boolean matrix below. (∧/b) results in the array 0 1 1 0 0, and (∧⌿b) results in the array 1 0 0 0 1.
1 0 1 0 1 → 0
1 1 1 1 1 → 1
1 1 1 1 1 → 1
1 0 0 0 1 → 0
1 0 0 1 1 → 0
↓ ↓ ↓ ↓ ↓
1 0 0 0 1
Catenating these two arrays together and then performing one final logical OR reduction then tells us whether any row or column has been filled.
As an aside, note that, unlike most bingo games, the problem clearly states that diagonals do not count here. If we wanted to include diagonals, we could extend this approach as follows:
isWinWithDiagonals ← { b←⍵∊⍺ ⋄ ∨/(∧/b),(∧⌿b),(∧/1 1⍉b),(∧/1 1⍉⌽b) }
We include 2 new elements so that we perform the OR reduction over 12 elements instead of 10. Dyadic transpose (⍉) is used to extract the top-left-to-bottom-right diagonal. The other diagonal cannot be directly extracted using dyadic transpose, but we can still obtain it by first reversing (⌽) the matrix and then taking the main diagonal of the reverse.
When does a board win?
We can now turn our attention to determining at what point a board wins. Since there are only 100 boards and 100 numbers, we take a brute force approach: for each board, check every prefix of the called numbers, and then figure out when the board switches from being a non-winner to being a winner.
steps ← (⍳100)↑¨⊂nums
winSteps ← { (steps isWin¨ ⊆⍵) ⍳ 1 }¨ boards
First, we form a sequence by taking (↑) one element from nums, then two elements, then three elements, etc. The "each" operator (¨) is used to apply the take function multiple times, and we make sure to enclose (⊂) the right argument so that APL does not erroneously try to treat each number in nums separately. Thus, steps might look something like this:
steps
┌─┬────┬───────┬──────────┬────────
│6│6 69│6 69 28│6 69 28 50│ ...
└─┴────┴───────┴──────────┴────────
Now, for each of these sequence prefixes, we can check whether a board wins via steps isWin¨ ⊆board. This produces a boolean sequence that starts with zeros and eventually switches to all ones (because when a prefix of the called numbers results in a board win, all following prefixes will also win). For example, a board that wins after six numbers are called would result in the following:
steps isWin¨ ⊆board
0 0 0 0 0 1 1 1 1 1 1 1 ...
With this sequence, a straightforward application of "index of" (⍳) to query the position of the first 1 tells us how many numbers need to be called before a given board wins. Wrapping this into a function and applying it to our collection of boards gives us the iteration at which each board wins in winSteps. For example, a winSteps as shown below means that the first board wins after 23 numbers are called, the second board wins after 89 numbers are called, and the third board wins after 56 numbers are called.
winSteps
23 89 56 ...
"Scoring" a board
One last step before we solve the problem: we need to compute the "score" of a board, defined in the problem as the sum of the unmarked numbers multipled by the last number called. This is a fairly straightforward implementation in APL:
score ← { b←⍵∊⍺ ⋄ ⍺[≢⍺]×+/+/(1-b)×⍵ }
This function takes the list of numbers called as the left argument and the 5x5 matrix board in the right argument. Again, we compute b←⍵∊⍺, which marks the called numbers, so that 1-b marks the uncalled numbers. Multiplying this by the matrix itself and then performing a double sum-reduction yields the sum of the unmarked numbers. This can then be multipled by ⍺[≢⍺] (the last called number) to obtain the score.
Putting it all together
Finally, we have all of the pieces we need. For part 1, we want the score of the fastest board. Since we have already computed above how many numbers we need for each board to win, ⌊/winSteps tells us how many numbers are required for the first board to win, and steps[⌊/winSteps] tells us which numbers were called. "Index of" can then tell us which board won using boards[winSteps ⍳ ⌊/winSteps], which gives us everything we need to call our score function described above.
(⊃steps[⌊/winSteps]) score (⊃boards[winSteps ⍳ ⌊/winSteps])
For part 2, we want to do the same thing, but for the last board to win. With the approach we have taken, this is a trivial modification: instead of looking for the minimum in winSteps, we seek the maximum: ⌈/winSteps.
(⊃steps[⌈/winSteps]) score (⊃boards[winSteps ⍳ ⌈/winSteps])
That's it! Here's the solution in its entirety:
⍝ Parse input.
input ← ⊃⎕NGET'input4.txt' 1
nums ← ⍎⊃input
boards ← {5 5⍴⍎⍕input[⍵]}¨(¯4+6×⍳100)+⊂(⍳5)
⍝ Given an array of called numbers ⍺ and board ⍵, determines
⍝ whether a bingo has occurred.
isWin ← { b←⍵∊⍺ ⋄ ∨/(∧/b),(∧⌿b) }
⍝ Computes the score of a winning board ⍵ with called numbers ⍺.
score ← { b←⍵∊⍺ ⋄ ⍺[≢⍺]×+/+/(1-b)×⍵ }
⍝ Array representing each step of the numbers called.
steps ← (⍳100)↑¨⊂nums
⍝ The number of steps required for each board to win.
winSteps ← { (steps isWin¨ ⊆⍵) ⍳ 1 }¨ boards
⍝ Part 1
(⊃steps[⌊/winSteps]) score (⊃boards[winSteps ⍳ ⌊/winSteps])
⍝ Part 2
(⊃steps[⌈/winSteps]) score (⊃boards[winSteps ⍳ ⌈/winSteps])