What now?
Contents
What now?#
Beware of Methodologies. They are a great way to bring everyone up to a dismal, but passable, level of performance, but at the same time, they are aggravating to more talented people who chafe at the restrictions that are placed on them. –Joel Spolsky
If you stayed with it to here, well done – you’re going to Top Gun.
You should have enough skills to make a considerable dent in a problem collection such as Advent of Code, Project Euler, Perl Weekly Challenge or Project Rosalind. What you need now is practice.
A good place to start is the Dyalog Problem Solving Competition, an annual event that’s been running for a while. All the old problems are available and they are typically constructed to flatter APL’s capabilities.
Advent of Code is great – a nice ramp-up of difficulty and a Grand Tour of Computer Science 101. It’s my benchmark – I find that starting on Day01 knowing near nothing, by the time I get to Day25 I am reasonably proficient in a new language. So I thought we’d solve a couple of Advent of Code problems here. Obviously, if you don’t want to spoil it for yourself, come back here once you’ve had a go yourself.
⎕IO ← 0
⎕PP ← 34
]box on
]rows on
assert←{⍺←'assertion failure' ⋄ 0∊⍵:⍺ ⎕signal 8 ⋄ shy←0}
20/3 Toboggan Trajectory#
This one is day 3 from 2020. Note that my data will be different from yours - a feature of Advent of Code.
We have a 2D array of dots and hashes. The pattern is repeated indefinitely to the right. The example given is:
⎕←data ← 11 11⍴'..##.......#...#...#...#....#..#...#.#...#.#.#...##..#...#.##......#.#.#....#.#........##.##...#...#...##....#.#..#...#.#'
which is then assumed to repeat to the right indefinitely, the first few like so:
data,⍣3⊢data
The task is to calculate how many # we’d encounter if, starting from the top-left corner, we follow a path which for each iteration moves three steps to the right, and one step down. In this test case, we’d encounter 7, here indicated by quads, ⎕:
11 44⍴'0.##.........##.........##.........##.......#..0#...#..#...#...#..#...#...#..#...#...#...#....⎕..#..#....#..#..#....#..#..#....#..#...#.#...#0#..#.#...#.#..#.#...#.#..#.#...#.#.#...##..#..⎕...##..#..#...##..#..#...##..#...#.##.......#.⎕#.......#.##.......#.##......#.#.#....#.#.#.#.0..#.#.#.#....#.#.#.#....#.#........#.#........⎕.#........#.#........##.##...#...#.##...#...#.⎕#...#...#.##...#...#...##....##...##....##...#⎕....##...##....#.#..#...#.#.#..#...#.#.#..#...⎕.#.#..#...#.#'
We can generate the coordinates for the path directly. The y-coordinate just increases by 1. The x-coordinate increases by 3 until we “fall off” the end of the pattern, after which it resets back to zero. Let’s look at this specific case.
If we ignore the wrap-around in x, we can get our coordinates as (assuming the pattern is shape 11 11):
↓⍉↑1 3×⊂⍳11 ⍝ Remix to create y x pairs
The wrap-around is just a mod by the shape of the pattern, in our case 11 11:
↓⍉↑11 11|1 3×⊂⍳11
So we pick out the chars along this vector, look for # and sum:
+⌿'#'=data[↓⍉↑11 11|1 3×⊂⍳11]
So that works on the test data at least; good. Let’s make that generic in the pattern shape and the path offset:
data {+⌿'#'=⍺[↓⍉↑(⍴⍺)|⍵×⊂⍳⌈(≢⍺)÷⊃⍵]} 1 3
At this point we’re ready to try it on the real pattern.
data ← ↑⊃⎕NGET'../../AoCDyalog/data/2020/day03.txt'1
The real pattern is considerably larger, but as we’ve made our solution independent of pattern shape and path offset, this should not present a problem:
⍴data
⎕ ← part1 ← data {+⌿'#'=⍺[↓⍉↑(⍴⍺)|⍵×⊂⍳⌈(≢⍺)÷⊃⍵]} 1 3
assert 203=part1
That was the correct answer for part 1 (for me – you will get a different number).
For part 2, we’re given five slopes, and we need to multiply all results together. Not much left to do:
⎕ ← part2 ← ×⌿data∘{+⌿'#'=⍺[↓⍉↑(⍴⍺)|⍵×⊂⍳⌈(≢⍺)÷⊃⍵]}¨(1 1)(1 3)(1 5)(1 7)(2 1)
assert 3316272960=part2
So that was kind of APL home-court advantage - a nice, array-oriented solution.
16/6 Signals and Noise#
This one is day 6 from 2016.
Given a bunch of random-looking strings of letters of equal lengths, we’re to find the most commonly occurring letter in each position. We’re given the following test set:
data ← 'eedadn' 'drvtee' 'eandsr' 'raavrd' 'atevrs' 'tsrnev' 'sdttsa' 'rasrtv' 'nssdts' 'ntnada' 'svetve' 'tesnvt' 'vntsnd' 'vrdear' 'dvrsen' 'enarar'
↑data
Picking out the most commonly occurring letter in each column spells easter. “Most commonly occurring” should have us reach for Key, ⌸. We remix the input data so that we get a vector of the columns, which we then Key:
{⍺,≢⍵}⌸¨↓⍉↑data
Now we sort each array based on the last column, and select the element at 0 0 in each, which should be the most frequent letter:
∊{0 0⌷⍵[⍒⍵[;1];]}¨{⍺,≢⍵}⌸¨↓⍉↑data
Looks promising. Let’s try that on the real data:
data ← ⊃⎕NGET'../../AoCDyalog/data/2016/06.txt'1
⎕ ← part1 ← ∊{0 0⌷⍵[⍒⍵[;1];]}¨{⍺,≢⍵}⌸¨↓⍉↑data
assert 'qrqlznrl'≡part1
Part 2 - the same, but now pick the least frequent. All we need to do is to swap grade down for grade up:
⎕ ← part2 ← ∊{0 0⌷⍵[⍋⍵[;1];]}¨{⍺,≢⍵}⌸¨↓⍉↑data
assert 'kgzdfaon'≡part2
If we wanted to be clever, we could make that an operator:
_day6 ← {∊⍺⍺{0 0⌷⍵[⍺⍺⍵[;1];]}¨{⍺,≢⍵}⌸¨↓⍉↑⍵}
⍒_day6 data
⍋_day6 data
18/10 The Stars Align#
Back in 2018, we were treated to this gem on day 10. We have a bunch of “stars” each having a position and a velocity. At some moment in time, these stars will align, forming a message.
We can reasonably guess that the message forms when the bounding box of all the stars is at its smallest. If that isn’t the case, then this becomes much harder, so let’s try this hypothesis first.
Step one is to pick out four numbers, including negatives, from each line of the input data:
data ← ↑'-?\d+'⎕S{⍎⍵.Match}¨⊃⎕NGET'../../AoCDyalog/data/2018/10.txt'1
The first two columns are the position, and the last two columns the velocity.
pos ← ,/data[;0 1]
vel ← ,/data[;2 3]
We want to minimise the bounding box. We can use the sum of the width and height of the bounding box as a single number that we can compare. Here’s a function to compute that:
bbx ← {+/|-⌿2 2⍴(⌊⌿,⌈⌿)↑⍵} ⍝ Width + height of bounding box
So we want to repeatedly apply a function (the adding of the velocity to the position) to the output of itself until we reach a defined stopping condition – when the width plus the height of the bounding box no longer decreases. This sounds like a job for the power operator:
msg ← vel-⍨{vel+⍵}⍣{⍺>⍥bbx⍵}⊢pos ⍝ Add velocity until bounding box no longer decreases.
That’s actually it – but in order to actually see the message we need to prune it down to the bounding box, and for extra flair, use the * character, as shown in the question.
(w h) ← |-⌿2 2⍴(⌊⌿,⌈⌿)↑msg ⍝ Width and height of bounding box
(-h+1)(-w+1)↑'*'@(⊖¨msg)⊢143 203⍴' ' ⍝ Prune our display, and make stars
17/25 The Halting Problem#
The Christmas Day problem from 2017. We’re asked to solve the Halting Problem for a Turing machine. We’re given a description of the state transitions – the program, basically. The description for state A is:
In state A:
If the current value is 0:
- Write the value 1.
- Move one slot to the right.
- Continue with state B.
If the current value is 1:
- Write the value 0.
- Move one slot to the left.
- Continue with state C.
Compiling the state descriptions into a table, we get to something along the lines of
0 |
1 |
|
|---|---|---|
A |
1 R B |
0 L C |
B |
1 L A |
1 R D |
C |
1 R A |
0 L E |
D |
1 R A |
0 R B |
E |
1 L F |
1 L C |
F |
1 R D |
1 R A |
which we can translate to a neat APL 6×6 matrix:
⎕ ← STATE ← 6 6⍴1 1 1 0 ¯1 2 1 ¯1 0 1 1 3 1 1 0 0 ¯1 4 1 1 0 0 1 1 1 ¯1 5 1 ¯1 2 1 1 3 1 1 0
We’ll need a honking loooong magnetic tape, initially set to all zeros. We don’t know the exact length, but we know we are running 12919244 iterations, so let’s make the tape that size to start with.
TAPE ← 12919244⍴0
We also need a state transition function, applying the rules from the STATE table, reading from, and writing to TAPE:
]dinput
stf ← {
(pos state) ← ⍵
args ← (0 3[pos⊃TAPE])+⍳3
(nv m ns) ← STATE[state;args]
TAPE[pos] ← nv
(pos+m) ns
}
We need to run 12919244 iterations. We’ll start in the middle of the tape, and hope that it is long enough:
_ ← stf⍣12919244⊢6459622 0 ⍝ Takes ~20s
assert 4287=⎕←+/TAPE
Statsify All The Words!#
Here’s a task that I was set many, many years ago for a job interview. The original task sheet is included below, suitably redacted, although I’m sure they have moved on from this by now. They were somewhat arrogant to say “use any programming language” – I only wish I’d known APL by then…
So the task is deliberately open-ended and not fully specified; part of the expectation was to show ability to work with ambiguous requirements yadda yadda. So we’ll make a note of the assumptions we make. First we need some test data in a file; let’s make a few paragraphs of Lorem Ipsum:
data←⊃⎕NGET'/Users/stefan/work/dyalog/learnapl/loremipsum.txt'1
1↑data
This file contains Latin words, mixed case, punctuation, whitespace including empty lines. Our first assumption is that we will do all calculations case-insensitively. So we’ll pick out the words, and turn them to upper-case. There are a number of ways we could do this, but let’s use a regex solution that’s UTF-8-safe – we do want to be able to deal with not just English, right?
words←⎕←('\W' '.'⎕S 3⍠'UCP'1⊆⊢)1⎕C⊃,/data
Is that sufficient? Well, it depends if we expect the file to contain numbers, too:
('\W' '.'⎕S 3⍠'UCP'1⊆⊢) 'These are words 55, 56 and 57 in total. Number1nmiddle'
The problem statement says nothing about numbers. We could remove those first, like so:
('\W' '.'⎕S 3⍠'UCP'1⊆⊢) '\d'⎕R''⊢1⎕C'These are words 55, 56 and 57 in total. Number1nmiddle'
words←('\W' '.'⎕S 3⍠'UCP'1⊆⊢) '\d'⎕R''⊢1⎕C⊃,/data
So we wanted to know the number of words and lines in the text. That’s just
(≢words)(≢data)
Next we want to find the most frequent letter. This is a fairly standard Key pattern, and here we also assume that if there are several most frequent letters, we should return all of them.
letters⌷⍨⊂0~⍨⊢/0,⊢⌸letters←∊words
Finally, we need the average word length, to one decimal place. Let’s build a vector of word lengths and average with a neat little train:
(+/÷≢)≢¨words
Oh, and to one decimal place:
⍎1⍕(+/÷≢)≢¨words
I think we have all the pieces. Let’s golf that down to confuse the interviewers properly:
{(≢w)(≢⍵)(⍎1⍕(+/÷≢)≢¨w)(l⌷⍨⊂0~⍨⊢/0,⊢⌸l←∊w←('\W' '.'⎕S 3⍠'UCP'1⊆⊢)'\d'⎕R''⊢1⎕C⊃,/⍵)}data
If we didn’t care about numbers, and we were dealing with only the letters A-Z, we could have written the more compact
(≢w)(≢data)(⍎1⍕(+/÷≢)≢¨w)(l⌷⍨⊂0~⍨⊢/0,⊢⌸l←∊w←(∊∘⎕A⊆⊢)1⎕C⊃,/data)
Now we just have to wait for them to “assess the program for style and readability; and also look at how easy your program is to extend”. Once we’re done being smug, we could of course have structured that a bit friendlier for people new to APL (what Aaron Hsu calls “the didactic style”):
]dinput
stats ← {
words ← ('\W' '.'⎕S 3⍠'UCP'1⊆⊢) '\d'⎕R''⊢1⎕C⊃,/⍵ ⍝ Flatten, upcase, remove numbers, split on "non-word"
letters ← ∊words ⍝ Join
common ← letters⌷⍨⊂0~⍨⊢/0,⊢⌸letters ⍝ Frequency table, picking the most frequent
lengths ← ≢¨words ⍝ Vector of length of each word
ave ← ⍎1⍕(+/÷≢)lengths ⍝ Average, and round to 1 decimal place
(≢words) (≢⍵) ave common
}
stats data
Extensibility is an amorphous topic, and typically something lauded by Object Orientationists as something that has intrinsic value. Is the above function extensible? Sure! I can add another line to count (say) the number of paragraphs and tag that on the end of the returned vector. However, in an OO language, perhaps you’d created a class that could be extended through inheritance. As APLers, we’d say that this obscures the intent, hiding the functionality away in perhaps other files, instead of having all available within a line or two.
So the question you’d have to ask yourself – would the above effort have gotten you the job?
I think we know the answer to that :) They expected five pages of Java… Anyway, if you aspire to dazzle interviewers, take a leaf out of Aphyr’s book.