Home
Articles
Notes
Projects
As usual I've been participating in this year's advent of code challenge and as usual I've picked up a new language to learn. This year, I wanted to try out an array language (more specifically, an "Iversonian" array language). Dyalog APL is the most popular, but it's proprietary. This lead me to look into BQN instead with the open source CBQN implementation.
Since array languages are a completely different paradigm, this article will be mostly focused on documenting my journey with the language, walking through some simple solutions and less focus on the AOC puzzles themselves. Also, this year's AOC was rather textbook, so I don't have much algorithmic tricks to share anyways.
As usual: this article WILL contain spoilers. So if you haven't yet done this year's puzzles and want to avoid spoilers, then bookmark this article and visit later. I'll try to give a small refresher on the puzzles, but readers are assumed to be familiar with the problem already. If not, you can find each day's puzzle at the advent of code website, for example day 1 link would be https://adventofcode.com/2024/day/1.
All my solutions are available here if you'd like to just skip to the code (though I doubt you'd understand any of it unless you're a BQN programmer already).
Building CBQN was pretty straightforward, just clone the repo and run make.
One thing that really irked me though, is the fact that the build script will
automatically start cloning any submodule that isn't present.
I consider build scripts making unconfirmed internet connection to be a
massive misfeature, even if there was no malicious intent here.
If the goal is to make build process easier, a prompt asking the user would have
done just fine.
BQN - much like APL - uses special glyphs for it's primitive functions (a.k.a operators). So you need some way to type those. You've got a bunch of different options, starting from editor specific plugins to more system wide xkb layout files. I decided to just go with the vim plugin since I wasn't sure about having it enabled system wide.
This leads to another small inconvenience, the official vim plugin - instead of
being in it's own repo (or branch) - is bundled inside the editors/ directory
of the official implementation.
So if you're using git submodules to manage your vim plugins, it means having to
clone a bunch of stuff you don't actually need into your vim config dir.
Nothing fatal, but again, a small inconvenience.
With all the setup done, you're now ready to type in your first hello world:
•Out "Hello, world!"
The official documentation is pretty well done. There's also an index page for easy searching and a keymap page which is pretty helpful for beginners for getting used to all the new keybind/symbols.
There's also a tutorial focused at getting you started with the language. It's fine as an introduction, but I would've also liked to see a "learn by example" thingy where you have well commented code snippets to do common/basic operations (e.g string splitting, binary search etc). Knowing "this operator does this" is one thing but seeing it being actually applied in some real-ish situation to solve a problem is another.
The lack of any "education snippets" collection was made up by the community matrix room. Despite it's small size, the members there were very helpful in answering my questions and helping me figure out things I was having trouble with - which I'm very much thankful for.
The lack of a debugger was also a slight annoyance. If you aren't accustomed to using a debugger - which I wasn't either until an year or so ago - you might not consider this to be much of an issue. But debuggers - contrary to popular misconception - isn't just for fixing bugs, they're also an excellent tool to explore and inspect working programs. E.g stepping through someone else's solution to see how it works. Thankfully though, BQN being a terse language meant copy pasting lines into the REPL and playing with it there wasn't too much of an issue. But a good debugger would've been a nice QoL improvement.
A couple other resources that were of help:
Given how different array languages are compared to usual imperative languages, trying to give a proper introduction is way out of scope. However, I'll give a little taste of how it works just so you can follow along.
Arithmetic works as usual, using infix notation:
>> 5 + 2
7
>> 5 × 2
10
Do notice that BQN doesn't use the usual * and / for multiplication and
division, they have their special symbols: × and ÷ respectively.
Another thing that's going to be a surprise is that BQN doesn't have any "operator precedence", everything is evaluated right to left (and for good reasons, as you'll see later):
>> 2 × 5 + 1 # equal to: 2 × (5 + 1)
12
For primitive types you have Numbers, and Characters. There are no separate "integer"/"floating" types, it's all double-precision floats.
As for "aggregate types", there are only 2.
⟨1, 2, 3, 4⟩ # list of numbers
"string is a list of characters"
⟨1, ⟨"lists", "can be nested"⟩, 'x'⟩ # and contain different shaped elements
>> [⟨1, 2⟩, ⟨3, 4⟩]
┌─
╵ 1 2
3 4
┘
>> [1, 2, "hi"]
Error: […]: Incompatible element shapes (encountered shapes ⟨⟩ and ⟨2⟩)
at [1, 2, "hi"]
^^^^^^^^^^^^
Since arrays are first class, you can perform arithmetic on two arrays/lists (of same shape/length) and it works more or less as you'd expect:
>> ⟨1, 2⟩ + ⟨3, 4⟩
⟨ 4 6 ⟩
Okay, so say we have a list of numbers and we want to add 1 to every number in
the list.
In an imperative language, you'd probably write a (for) loop.
In a functional language, you'd use something like map.
In BQN, you just add 1
>> 1 + ⟨1, 2, 3⟩
⟨ 2 3 4 ⟩
This works recursively too:
>> ⟨1, 2⟩ + ⟨ ⟨3, 4⟩, ⟨5, 6, 7⟩ ⟩
⟨ ⟨ 4 5 ⟩ ⟨ 7 8 9 ⟩ ⟩
Most primitive functions are overloaded, they behave differently depending
on whether they are called monadically (i.e with a single right argument - and
btw, this has nothing to do with haskell's monads in case you're wondering) or
dyadically (with both left and right argument).
E.g ⌽ will act as Reverse or Rotate depending on whether it's given a right
argument or not.
>> ⌽ ⟨1, 2, 3, 4⟩ # Reverse when called monadically
⟨ 4 3 2 1 ⟩
>> 1 ⌽ ⟨1, 2, 3, 4⟩ # Rotate when called dyadically
⟨ 2 3 4 1 ⟩
BQN also supports tacit programming (also known as point-free in some functional programming circles) with various modifers/combinators. I won't dive into combinators since they're not necessary to use the language. But with combinators, lightweight functions & the rich set of builtin array operations, you can write some really terse code packing a lot of punch.
Unlike purely functional languages, you can modify a variable:
>> a ← 5 # Declaration & Assignment
5
>> a ↩ 10 # Modify existing variable
10
Functions have a no-nonsense syntax, you start it with a block {} and then use
the special variable 𝕩 to access the right argument and (optional) left argument
is accessed with 𝕨.
E.g an anon function which takes a single argument and negates it:
>> { -𝕩 } 5
¯5
Functions can be also be assigned similar to variables:
>> Add2 ← { 2 + 𝕩 }
(function block)
>> Add2 5
7
This is also a good time to reveal that - while I've used the word "operator" a
couple times - BQN doesn't actually have any operators in the traditional sense.
Everything is a function, and all functions can take only up to 2 arguments.
This is why in the above snippet, there's no () for the function call, it's
called the same way as if you used a unary operator.
But how do you make a function which takes more than 2 argument then? Pack them into a list. BQN also has headers, which allows you to then destructure the arguments or give different name to the implicit 𝕩 & 𝕨 arguments. E.g:
┌>> F ← { 𝕊⟨arg1, two, a3⟩:
│ •Show arg1 ⋄ •Show two ⋄ •Show a3
└ }
(function block)
>> F ⟨1, "two", ⟨3, "three"⟩⟩
1
"two"
⟨ 3 "three" ⟩
One straightforward way to do conditionals is to use the condition as an index
into an array of function.
This sounds horrifying, but thanks to BQN's lightweight function syntax it's
actually not that bad at all.
The choose primitive (◶) allows you to do basically that but with a bit
more niceties.
>> EvenOdd ← { (2⊸|)◶⟨"Even", "Odd"⟩ 𝕩 }
(function block)
>> EvenOdd 5
"Odd"
>> EvenOdd 4
"Even"
Blocks headers also allow conditionals, somewhat similar to C's ternary operator. You can use them to form if-else chains.
┌>> F ← {
│ 𝕩 = 0 ? "Zero";
│ 0 = 2 | 𝕩 ? "Even";
│ "Odd"
└ }
(function block)
>> F 0
"Zero"
>> F 1
"Odd"
>> F 2
"Even"
Block headers can also be used to get "switch case" like syntax:
>> F ← { 0: "Zero"; 1: "One"; "Other" }
(function block)
>> F 0
"Zero"
>> F 1
"One"
>> F 2
"Other"
In fact, there's an entire page in the official documentation on how to emulate various imperative control flow structures.
While BQN does have ways to emulate imperative control flow, the "array way" is
to do things to entire arrays rather than operating on individual elements.
Often times, this means thinking in masks rather than conditionals.
For example, let's say we have a list of numbers and want the sum of all the
numbers which are divisible by 3.
Let's start by calculating the mod 3 of the list (ascii bar | is the mod
function in BQN):
>> num ← ⟨2, 3, 4, 6, 9, 10⟩
⟨ 2 3 4 6 9 10 ⟩
>> 3 | num
⟨ 2 0 1 0 0 1 ⟩
If we now compare the mod array with 0 we will get a mask where the value is 1 for elements divisible by 3, and 0 otherwise.
>> mask ← 0 = 3 | num
⟨ 0 1 0 1 1 0 ⟩
>> [num, mask] # showing num on top of mask
┌─
╵ 2 3 4 6 9 10
0 1 0 1 1 0
┘
Now multiplying num with mask will zero out any number that isn't divisible by 3, then it's just a matter of doing a sum reduce.
>> mask × num
⟨ 0 3 0 6 9 0 ⟩
>> +´ mask × num
18
Although this example was contrived, simple masks can take you a long way.
Usually purely functional languages use recursion for loops. You can do that in BQN as well. However, BQN does not require tail-call-optimization, and CBQN doesn't implement it either. Worse, the default stack size in CBQN is rather small, so if you're doing anything non-trivial then you will run into stack overflow. I ran into this issue about 3 times where I had to rewrite my recursive DFS solution because it would overflow the stack.
So how do you do loops?
BQN offers a •_while_ modifier which takes a condition function as it's right
argument and "loop body" function as it's left argument:
>> { •Out "x => " ∾ •Fmt 𝕩, 𝕩 + 1 } •_while_ { 𝕩 < 4 } 0
x => 0
x => 1
x => 2
x => 3
Keep in mind that while these look like a usual block in imperative languages,
these are not blocks, they're just anon functions.
BQN does also have blocks, which can be used to create a scope or access block
header to do if-else chains, switch case emulation etc.
These immediate blocks look the exact same as function blocks.
E.g here's an immediate block which declares a local variable var and returns
it's values:
>> { var ← 5, var }
5
>> var
Error: Undefined identifier
at var
^^^
var becomes undefined/inaccessible after the block ends due to usual scoping
rules.
However, this might raise the question, how do you differentiate between a function vs an immediate block? For example, what's "wrong" with the following loop:
i ← 0
{ •Show 𝕩, i ↩ i + 1 } •_while_ { i < 4 } i
Hint: It's an infinite loop.
Whether a block is a function or an immediate block gets determined by whether
the body of the block uses any of the special implicit argument variables like
𝕩, 𝕨 etc.
Since the i < 4 body doesn't, it's an immediate block, evaluated once rather
than a function evaluated at every iteration.
Effectively, it becomes •_while_ 1 and thus an infinite loop.
Note that the same pitfall applies to the "body" block as well, if it's not a
function then it'll be evaluated once rather than every iteration.
If you wanted the above to be a function you can use the implicit variable 𝕤
which refers to the function itself.
{𝕤, i < 4 }
This implicit variable is useful if you want to write a recursive anon function.
Here, we're not doing any recursion though.
It only references the function and discards the result.
Similar to the following C code where function f has it's pointer taken and
done nothing with it:
int f(void)
{
(void)&f;
return 1;
}
Computationally the 𝕤 is not doing anything, similar to the (void)&f in the
C snippet.
But semantically it stops the block from turning into an immediate block by
using one of the implicit variable and thus turning it into a function instead.
I'd like to say this is something you'd get used to after a while, but even into my 3rd week in advent of code, I still ran into this issue of mistakenly turning what was supposed to be a function into an immediate block (especially after an edit where the block might have started out as a function).
Anon functions are everywhere so I wouldn't want their syntax to be worse. Maybe it would've been better if immediate blocks had a slightly more verbose syntax? Or maybe you just need more than 3 weeks to get adjusted to it. Regardless, I'm not necessarily complaining here, just documenting my experience.
BQN also has the typical functional trio.
I've already shown reduce (´).
It works by inserting the given function in the middle of every element in the
list.
>> +´ ⟨5, 2, 1⟩ # Same as: 5 + 2 + 1
8
However, since it works as if it turned the list into an expression, it's also subject to BQN's right to left evaluation order. Below I'm using an anon function which subtracts it's arguments after logging them first.
>> {•Show 𝕨‿"-"‿𝕩 ⋄ 𝕨 - 𝕩}´ ⟨5, 2, 1⟩ # Same as: 5 - (2 - 1)
⟨ 2 "-" 1 ⟩
⟨ 5 "-" 1 ⟩
4
If you want to do it the other way around, then you can reverse the list before folding.
This two dot thingy ¨ is the for each/map modifier.
•Fmt turns stuff into a string (similar to what gets printed on the
interactive repl sessions).
If you apply it on a list, it turns the entire list into string.
>> •Fmt ⟨1, 2, 3⟩
"⟨ 1 2 3 ⟩"
But maybe you're trying to stringify each individual element, and not the entire
string? Just add the each modifier:
>> •Fmt¨ ⟨1, 2, 3⟩
⟨ "1" "2" "3" ⟩
As for filter, BQN doesn't have filter per se.
What it does have is replicate (/), a more generalized version of filter.
It takes a replication count as it's left argument and replicates the elements
in the right argument that many times.
>> ⟨0, 1, 3⟩ / ⟨"One", "Two", "Three"⟩
⟨ "Two" "Three" "Three" "Three" ⟩
Here "One" is replicated 0 times, in other words, it got filtered out. "Two" is replicated once, and "Three" is replicated 3 times according to the left argument. If the left argument is a boolean list, then replicate works pretty much the same as traditional filter.
The first couple days were absolutely brutal. Very simple tasks like splitting a string took a herculean amount of effort to figure out how to do. Initially I considered dropping the language and going for something more familiar instead, especially since parsing would've been really rough if there was some parsing problem. BQN doesn't have builtin regex, though a there were bindings available to pcre2, I didn't use them. Thankfully other than day 3 there weren't any parsing challenges, so I got lucky.
Day 5~6 is when I started getting comfortable with the language and to some extent the paradigm. At this point I've built up my own set of common string functions like splitting, reading input, parsing ints out of a string etc.
Unlike other paradigms where you build your data structures according to the problem, array paradigm has only arrays. And so you need to reformulate the problem to fit into the array paradigm instead. How to do this is often going to be neither obvious nor straightforward. And so I found myself writing a good chunk of the solution in "imperative" style with the various escapes hatches at first and then rewriting them to be more array-like once I gained a better understanding of the problem.
But with all that being said, there are also some problems which naturally fits into array paradigm. And so if you're a "geometric" thinker, you will be able to solve a lot of problems more easily in BQN compared in imperative languages where you'd need to, for example, work with co-ordinates instead. That probably didn't make much sense if you haven't tried an array language yourself, so I'll go over a couple solutions step by step below which might give you a taste of what I'm talking about.
The problem gives us a list of lines and tells us to count how many of them are "safe". A line is safe if all the numbers are either all increasing or all decreasing. A single step also cannot be greater than 3. Let's walk through the solution using the first line of the example as a sample.
>> sample ← ⟨7, 6, 4, 2, 1⟩
⟨ 7 6 4 2 1 ⟩
We can use the shift function to shift the array one step to the right.
>> » sample
⟨ 0 7 6 4 2 ⟩
And then subtracting it from the original input will give us the deltas.
>> sample - » sample
⟨ 7 ¯1 ¯2 ¯2 ¯1 ⟩
Except, the first element doesn't have a delta associated with it.
So let's drop it and assign the result to delta.
>> delta ← 1↓ sample - » sample
⟨ ¯1 ¯2 ¯2 ¯1 ⟩
To check whether all the deltas are all increasing or all decreasing, we can use
the sign function to turn all negatives into -1 and positives into 1.
>> × delta
⟨ ¯1 ¯1 ¯1 ¯1 ⟩
Now to make sure all of these are either 1 or -1, we can compare the array with it's first element.
>> (⊑×delta) # first element
¯1
>> (⊑×delta) = ×delta
⟨ 1 1 1 1 ⟩
If the resulting array has all 1's then all the deltas were in the same
direction. So let's do an and reduce and assign the result to same_dir.
>> same_dir ← ∧´ (⊑×delta) = ×delta
1
Now to make sure all the deltas are above 0 and below or equal to 3. Let's take the absolute of all the deltas since we don't care about the sign here:
>> delta
⟨ ¯1 ¯2 ¯2 ¯1 ⟩
>> | delta # Abs
⟨ 1 2 2 1 ⟩
Now we can use member of to perform the check. Member of takes an array on the right, and returns a boolean array, with elements set to 1 where the left item appears on the right array. For example:
>> ⟨1, 2, 3⟩ ∊ ⟨0, 2, 4⟩
⟨ 0 1 0 ⟩
We can generate a list of [1, 3] by first using the range function and
then adding 1 to the resulting list:
>> ↕3
⟨ 0 1 2 ⟩
>> 1 + ↕3
⟨ 1 2 3 ⟩
Now to use it to check against the absolute deltas:
>> (| delta) ∊ 1 + ↕3
⟨ 1 1 1 1 ⟩
Similar to before, we want to and reduce the result since any single one of
the result being 0 means that the list is not safe.
Let's assign it to a variable safe_dist.
>> safe_dist ← ∧´ (| delta) ∊ 1 + ↕3
1
And now we can return the and of same_dir and safe_dist to check whether
the list is safe or not.
Putting this all in a function:
IsSafe ← {
delta ← 1↓ 𝕩 - »𝕩
same_dir ← ∧´ (⊑×delta) = ×delta
safe_dist ← ∧´ (| delta) ∊ 1 + ↕3
same_dir ∧ safe_dist
}
By using a bit of combinatoric magic, we can also just reduce it all down to a single line:
IsSafe ← ∧´∘(∊⟜(1+↕3)∘| ∾ ⊑⊸=∘×)1↓-⟜»
I'm not even going to bother trying to explain this. But this does pretty much the same thing as the verbose/explicit function above, except written tacitly with combinators.
Day 25 gives us a bunch of 2d grids. Some of these are locks and some are keys. The locks have all their top row filled.
We can extract out all the schemes by splitting on the empty lines. I'm also going to turn all the schemes into boolean instead of ascii '#' and '.' by comparing with '#' which will set all the filled positions to 1.
>> schemes ← '#' = >¨ (×≠¨)⊸SplitMask •FLines "d25_example.txt"
┌─
· ┌─ ┌─ ┌─ ┌─ ┌─
╵ 1 1 1 1 1 ╵ 1 1 1 1 1 ╵ 0 0 0 0 0 ╵ 0 0 0 0 0 ╵ 0 0 0 0 0
0 1 1 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 0 1 0 1 1 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0
0 1 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 0 0 0 0
0 1 0 1 0 0 0 0 1 0 1 0 1 0 1 1 1 1 0 1 1 0 1 0 0
0 1 0 0 0 0 0 0 1 0 1 0 1 1 1 1 1 1 0 1 1 0 1 0 1
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
┘ ┘ ┘ ┘ ┘
And then I can separate all the locks and keys by checking the first element.
I'll use the group function (⊔) for this.
⟨keys,locks⟩ ← ⊑¨⊸⊔ schemes
Now we need a function which checks whether a key and lock overlaps or not. For demo, I'll use the first lock and key from the example input.
>> lock ← ⊑schemes
┌─
╵ 1 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 0 1 0
0 1 0 0 0
0 0 0 0 0
┘
>> key ← 2⊑schemes
┌─
╵ 0 0 0 0 0
1 0 0 0 0
1 0 0 0 0
1 0 0 0 1
1 0 1 0 1
1 0 1 1 1
1 1 1 1 1
┘
Checking for overlap is very easy, just and the two arrays.
>> lock ∧ key
┌─
╵ 0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
┘
If any of the element is 1, then it overlapped.
So now just do an or reduce over the array:
>> ∨´ ⥊ lock ∧ key
1
However, we want to know the number of lock-key pair that did not overlap.
So just use a not on the result of the or reduction.
>> ¬∨´ ⥊ lock ∧ key
0
Now let's turn the above into a function and then run it for every lock and key pair instead of just the sample. This can be done with the table modifier, which runs the given function on each possible pair.
>> locks { ¬∨´ ⥊ 𝕨 ∧ 𝕩 }⌜ keys
┌─
╵ 0 0 1
0 1 1
┘
This gives us back an array, but we want the count.
So just a matter of doing a sum reduce:
>> +´ ⥊ locks { ¬∨´ ⥊ 𝕨 ∧ 𝕩 }⌜ keys
3
And that's our answer. Here's my actual day 25 solution (including the parsing) verbatim:
SplitMask ← { (0<≠¨)⊸/ 𝕩 ⊔˜ ¯1⌈ (𝕨 - ¬𝕨) × +` ¬𝕨 }
schemes ← (×≠¨)⊸SplitMask •FLines •wdpath•file.At ⊑•args
•Show +´ ⥊ ((¬∨´)∘∧)⌜´ ⊑¨⊸⊔ ('#'⊸= ∾)¨ schemes
Only 3 lines! It's following pretty much the same steps I described above but the code is golfed up with some of the usual combinator magic.
Here's an example grid where S denotes the starting position, E denotes the destination, and # are walls.
...E
..#.
.S..
.#..
Usually you'd translate them into x,y coordinates and then run DFS/BFS if you
want to find the least number of steps required to get to E.
Doing it on coordinates also means you need to do things like bounds checking,
and then checking for map[x][y] != '#' to avoid walking into wall.
With BQN, you can do the flood fill directly on the grid itself without any of
that shit.
First, let's get a grid with our starting position being 1 and everything else being 0. Easy, just compare the map to 'S'.
>> map = 'S'
┌─
╵ 0 0 0 0
0 0 0 0
0 1 0 0
0 0 0 0
┘
Now in order to move a single step, we will shift up and down.
This is done with the nudge operator (») from before.
We also need to move left and right too.
For that we'll use nudge again, but rather than applying it on the array we'll
apply it on each row of the array with the cell modifer (˘).
>> ⟨«,»,«˘,»˘⟩ {𝕎𝕩}¨ <map = 'S'
┌─
· ┌─ ┌─ ┌─ ┌─
╵ 0 0 0 0 ╵ 0 0 0 0 ╵ 0 0 0 0 ╵ 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
┘ ┘ ┘ ┘
┘
This gives us all 4 cardinal movements.
Let's or reduce it down to a single array.
>> ∨´ ⟨«,»,«˘,»˘⟩ {𝕎𝕩}¨ <map = 'S'
┌─
╵ 0 0 0 0
0 1 0 0
1 0 1 0
0 1 0 0
┘
This simulates a single step and gives us all the possible positions reachable
after exactly one step.
There's no bounds checking involved since shifting fills in the new slot with
zero and would shift any 1 out of the map.
However, we do need to avoid running into a wall.
Remember the map had a wall right below the starting position so we shouldn't be
able to move there.
To fix that, we'll just make an avail map which will be 1 on every position on
the map that isn't a wall.
>> avail ← map ≠ '#'
┌─
╵ 1 1 1 1
1 1 0 1
1 1 1 1
1 0 1 1
┘
Now we can just multiply the result of the step with this avail array which
will filter out any walls we're running into.
>> avail × ∨´ ⟨«,»,«˘,»˘⟩ {𝕎𝕩}¨ <map = 'S'
┌─
╵ 0 0 0 0
0 1 0 0
1 0 1 0
0 0 0 0
┘
And indeed it filters out the bottom step which would run into a wall. Now we can put this into a function and repeat it to simulate multiple steps.
>> Step ← { avail × ∨´ ⟨«,»,«˘,»˘⟩ {𝕎𝕩}¨ <𝕩 }
(function block)
>> Step⍟2 map = 'S'
┌─
╵ 0 1 0 0
1 0 0 0
0 1 0 1
1 0 1 0
┘
This gives us all the possible positions we can reach after exactly two steps.
Notice that there's a 1 at our starting position.
This is because we aren't maintaining any "seen" set to avoid going into the
same position twice.
If this is important, then we can simply modify the avail array every
iteration to also zero out previously seen positions.
>> Step ← { res ← avail × ∨´ ⟨«,»,«˘,»˘⟩ {𝕎𝕩}¨ <𝕩, avail ↩ avail ≠ 𝕩, res }
(function block)
>> Step⍟2 map = 'S'
┌─
╵ 0 1 0 0
1 0 0 0
0 0 0 1
1 0 1 0
┘
Now avail is pulling double weight by filtering out both walls and previously
seen positions.
All of this done directly on the grid itself, no coordinates involved!
If we want to know how many steps it takes to reach E, we can just run this in a
loop until the E position is 1 while also counting the number of iterations.
Easy.
I mentioned that a bunch of days this year contained grid problems.
The one I want to showcase here is going to be day 20, which requires you to
calculate the cost of reaching E from all the valid positions in order to
solve efficiently.
I'll use the same example map from above for the demo.
First let's initialize a cost map with all zeros.
>> cost ← 0¨map
┌─
╵ 0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
┘
This time around, instead of starting at S we will start at E and walk
backwards instead.
Taking one step from E is the same as reaching all the positions from which
E is reachable in one step since this is a unweighted and undirected graph.
>> m ← Step map='E'
┌─
╵ 0 0 1 0
0 0 0 1
0 0 0 0
0 0 0 0
┘
After taking one step, we can see there are two valid positions and their
distance to E must be one.
And so we can update our cost map by using the max function (⌈) which
will mix in our 1s into the cost map.
>> cost ↩ cost ⌈ m
┌─
╵ 0 0 1 0
0 0 0 1
0 0 0 0
0 0 0 0
┘
After another step we reach the following two positions.
>> m ← Step m
┌─
╵ 0 1 0 0
0 0 0 0
0 0 0 1
0 0 0 0
┘
We can mix them into the cost map the same as before.
However the distance of these two positions is 2 not 1, so we'll multiply m by
2 this time before taking the max.
>> m × 2
┌─
╵ 0 2 0 0
0 0 0 0
0 0 0 2
0 0 0 0
┘
>> cost ↩ cost ⌈ m × 2
┌─
╵ 0 2 1 0
0 0 0 1
0 0 0 2
0 0 0 0
┘
And now our cost map contains all the locations with a distance of 2 or less
from E.
To do it for all reachable locations, just run the same logic in a loop as long
as we have valid positions.
Copy pasted almost verbatim from my day 20 solution:
>> Step ← {∨´ ⟨«,«˘,»,»˘⟩ {𝕎𝕩}¨ <𝕩}
(function block)
┌>> cost ← 2⊑{𝕊⟨m,avail,cost,cnt⟩:
│ nxt ← (avail ≠ m) × Step m
│ ⟨nxt, avail ≠ m, cost ⌈ nxt × cnt, cnt+1⟩
└ } •_while_ (∨´∘∨˝⊑) ⟨'E'=map, '#'≠map, 0¨map, 1⟩
┌─
╵ 3 2 1 0
4 3 0 1
5 4 3 2
6 0 4 3
┘
Now we have the cost map for all that valid positions which can reach E.
The invalid positions (such as walls) have a cost of 0.
Which was fine for my purposes, but if you wanted to differentiate between
invalid positions vs E itself (which must have a cost of 0 since it takes 0
steps to reach E from E) then you can bias all the valid costs by +1.
Meaning E would cost 1 (which means 0 steps), cost of 5 would mean 4 steps and
cost of 0 would mean invalid/unreachable.
There were a lot more really fun and "visual"/"geometric" solutions I wanted to share but text is really not the best way to demonstrate these. Video would be better, but I currently don't have the setup or the interest to do so, so I'll have to cut this short.
While things were brutal at first, and many problems were somewhat harder to solve, ultimately I really enjoyed the language and the paradigm once I got my footing. This is probably biased due to my "system programming" background, but I don't think I'll be using BQN for anything "real" anytime soon. Despite that it's a really fun language for solving advent of code and other programming puzzles. If you're looking for a fun and somewhat esoteric language to try out, then I can definitely recommend giving BQN a shot.
