APL Problem Solving Competition 2023

the first problem starts off pretty tame: write a dfn that converts a DNA sequence to RNA, where both input and outputs are character arrays. The solution doesn’t need much explanation, it’s just replacing the 'T's with 'U's.

I had a little more fun with the next one, as I avoided writing down two separate look up tables by arranging my data properly: the statement calls for a dfn that returns the reverse complement of a DNA sequence.

With a little massaging we end up with the final solution.

This task calls for a dfn that returns the protein coded by a RNA sequence, terminating at the first stop codon. Setting up a lookup table is a logical first step:

The helper function r_trs does the heavy lifting, splitting the sequence in codons of 3 (x←{↓(⌊3÷⍨≢⍵)3⍴⍵}r), looking up each one (y←r_cod⍳x) and assinging the corresponding amino-acid (amm⌷⍨∘⊂y).

the whole function can be written tacitly, and the final solution just applies it to it’s input and truncates the result at the first '$'.

This was a parsing problem, of which I’ve done entirely too many doing Advent of Code in APL last year: it all boils down to partitioning and enclosing and partition-enclosing.

We need to write a dfn that accepts the path to a fasta file and returns a list of header-sequence pairs corresponding to the DNA sequences stored in the file.

For reference, a fasta file looks something like this:

The lines starting with > are headers, and the following lines contain the DNA sequences.

The solution is fairly pedestrian:

The task is to write a function that takes a fasta file, extracts the first (only) DNA sequence, and returns all the proteins coded by it, beginning with a 'M' amino-acid and ending with a stop codon. I approached the problem by writing a helper function that would turn a sequence of DNA into the amino-acid sequences of its 6 reading frames.

Our final solution will look like this (for some definition of crf and aas):

The task is to write a dfn that computes or validates a vehicle identification number; there are quite a few details involved, but the long and short of it is that characters in the VIN contribute to a total score according to their value and position, and the score modulo 11 determines the correct value of the 9th digit.

The solution handles a few cases:

We delegate the messy part to the calc helper function, that takes a 17 character vector and returns the character that, placed at position 9, would make the VIN valid.

This task asked for a function that sorts strings representing software versions according to their release number. The structure of the input is either:

The solution leverages total array ordering, and the bulk of the problem just boils down to parsing the numbers in the string.

If the input is a flat character array, then just return it wrapped in a 1-element list. If it’s a list of strings, split each entry by - into the fields (org, package, version). Then parse the three numbers in version using ⎕vfi: this suggests a nice extension of the problem statement: if one of the fields in version is not a number, ⎕vfi will return a 0 verification bit and a 0 result: this means that the expression result-~verification returns result if valid, ¯1 otherwise.

This allows us to sort versions like foo-bar-10.x.0 in between foo-bar-9.9.9 and foo-bar-10.0.0, which is kind of nice to have.

With that out of the way, we have a list of entries in the form:

Applying ⍋ gives us a sorting permutation, which by the rules of total array ordering conforms to the problem statement.

The task is to write a dfn that, given a sorted list of coin denominations (positive integers) as left argument and a total amount (a positive integer) as right argument, returns a matrix, where each row contains the coefficients of a linear combination of the elements in the left argument which sums to the right argument. Of course, the matrix should be exhaustive and not contain any duplicates.

Another way to look at this is that it returns the tallest matrix res that satisfies the following constraints:

⍵∧.=res+.×⍺ res≡∪res

The solution I submitted is a classic recursive one, with just a little bit of care put into the performance of it:

It is a well known mathematical fact that for a finite set \(A\) of integers, there exists a linear combination in \(A\) with integer coefficients that sums to \(n\) if and only if \(\text{GCD}(A) | n\) (where the GCD of a finite set is given by the pairwise GCD reduction of the elements in some arbitrary ordering, and | is the divisibility symbol). This allows us to immediately return (0,≢⍺)⍴0 if ⍵ is not divisible by ∨/⍺, which prunes some branches.

The second line handles the general base case, and it is only reached if there is exactly one trivial solution. We can avoid checking divisibility because the first line catches the case where 0≠⍵|⊃⍺.

The third line does all the recursing:

It may look suspicious that we’re not deduplicating the lines, but it can be proven that every solution gotten this way is already unique:

The task is to write a procedure partition that returns sliding windows of the right argument, with the size, strides and starting position given by the left argument.

We start by parsing the left argument, case by case.

Then, our strategy is to generate indices into ⍵ to build up the resulting windows:

Retrospective:

I didn’t feel satisfied with this solution, mainly because it uses way too many enclosed arrays as indices. Here it is, rewritten to convert to scalar indices in ravel order. I took the opportunity to modify a couple other things I wasn’t happy with:

The result is a little longer, but arguably simpler:

If nothing else, this shows my issue with ⎕IO: as soon as you start doing arithmetic on indices it gets in the way. If ⎕IO was always 0, the solution could be simplified to:

It also exemplifies how keeping the data representation flat can simplify the reasoning, as well as improving the performance: the new version is about 28x faster than the old one on 3 3 3 partition 25 25 25⍴⎕A.