The following are my attempts at the Phase I problems of the 2019 APL Problem Solving Competition. There are not necessarily “right answers” as personal style and taste come into play. More explanation of the code is provided here than common practice. All solutions pass all the tests specified in the official problem description.
1. Chunky Monkey
Write a function that, given a scalar or vector as the right argument and a positive (>0) integer chunk size n as the left argument, breaks the array’s items up into chunks of size n. If the number of elements in the array is not evenly divisible by n, then the last chunk will have fewer than n elements.
💡Hint: The partitioned enclose function ⊂ could be helpful for this problem.
f1←{((≢⍵)⍴⍺↑1)⊂⍵}
Basically, the problem is to construct an appropriate boolean left argument to ⊂. For this the reshape function ⍺⍴⍵ is apt, which repeats the items of ⍵ up to length ⍺.
9 ⍴ 1 0 0 (9 ⍴ 1 0 0) ⊂ 'ABCDEFGHI'
1 0 0 1 0 0 1 0 0 ┌───┬───┬───┐
│ABC│DEF│GHI│
└───┴───┴───┘
11 ⍴ 1 0 0 (11 ⍴ 1 0 0) ⊂ 'ABCDEFGHIJK'
1 0 0 1 0 0 1 0 0 1 0 ┌───┬───┬───┬──┐
│ABC│DEF│GHI│JK│
└───┴───┴───┴──┘
2. Making the Grade
| Score Range |
Letter Grade |
| 0-64 |
F |
| 65-69 |
D |
| 70-79 |
C |
| 80-89 |
B |
| 90-100 |
A |
|
|
Write a function that, given an array of integer test scores in the inclusive range 0–100, returns an identically-shaped array of the corresponding letter grades according to the table to the left.
💡Hint: You may want to investigate the interval index function ⍸.
|
f2← {'FDCBA'[0 65 70 80 90⍸⍵]}
For example:
range← 0 65 70 80 90
score← 0 65 89 64 75 100
range ⍸ score range ⍸ 2 3⍴score
1 2 4 1 3 5 1 2 4
1 3 5
'FDCBA'[1 2 4 1 3 5] 'FDCBA'[2 3⍴1 2 4 1 3 5]
FDBFCA FDB
FCA
f2 score f2 2 3⍴score
FDBFCA FDB
FCA
The examples on the right illustrate that the functions ⍸ and [] extend consistently to array arguments.
In APL, functions take array arguments, and so too indexing takes array arguments, including the indices (the “subscripts”). This property is integral to the template
Y indexing (X index ⍵)
where
| |
X |
domain for looking things up |
Y |
range where you want to end up; “aliases” corresponding to X |
| index |
a function to do the looking up, such as ⍳ or ⍸ |
| indexing |
a function to do indexing into X , such as [] or ⌷ or (dyadic) ⊃ |
|
3. Grade Distribution
Given a non-empty character vector of single-letter grades, produce a 3-column, 5-row, alphabetically-sorted matrix of each grade, the number of occurrences of that grade, and the percentage (rounded to 1 decimal position) of the total number of occurrences of that grade. The table should have a row for each grade even if there are no occurrences of a grade. Note: due to rounding the last column might not total 100%.
💡Hint: The key operator ⌸ could be useful for this problem.
f3←{a,k,1⍕⍪100×k÷+⌿k←¯1+{≢⍵}⌸⍵⍪⍨a←'ABCDF'}
The result of f⌸ is ordered by the unique major cells in the keys. If a particular order is required, or if a particular set of keys is required (even when some keys don’t occur in the argument), the computation can be effected by prefacing keys to the argument (here ,⍨a←'ABCDF') and then applying an inverse function (here ¯1+) to the result of ⌸.
For the key operator ⌸, in particular cases, for example the letter distribution in a corpus of English text, the universe of letters and their ordering are known (A-Z); in principle, it is not possible to “know” the complete universe of keys, or their ordering.
The function f3x illustrates the complications. f3 is the same as above; extra spaces are inserted into both functions to facilitate comparison.
f3 ← {a, k,1⍕⍪100×k÷+⌿k←¯1+{≢⍵}⌸⍵⍪⍨a←'ABCDF'}
f3x← {(∪⍵),k,1⍕⍪100×k÷+⌿k← {≢⍵}⌸⍵ }
⊢ g1← 9 3 8 4 7/'DABFC'
DDDDDDDDDAAABBBBBBBBFFFFCCCCCCC
f3x g1 f3 g1
D 9 29.0 A 3 9.7
A 3 9.7 B 8 25.8
B 8 25.8 C 7 22.6
F 4 12.9 D 9 29.0
C 7 22.6 F 4 12.9
⊢ g2← ('F'≠grade)⌿grade
DDDDDDDDDAAABBBBBBBBCCCCCCC
f3x g2 f3 g2
D 9 33.3 A 3 11.1
A 3 11.1 B 8 29.6
B 8 29.6 C 7 25.9
C 7 25.9 D 9 33.3
F 0 0.0
4. Knight Moves
┌───┬───┬───┬───┬───┬───┬───┬───┐
│1 1│1 2│1 3│1 4│1 5│1 6│1 7│1 8│
├───┼───┼───┼───┼───┼───┼───┼───┤
│2 1│2 2│2 3│2 4│2 5│2 6│2 7│2 8│
├───┼───┼───┼───┼───┼───┼───┼───┤
│3 1│3 2│3 3│3 4│3 5│3 6│3 7│3 8│
├───┼───┼───┼───┼───┼───┼───┼───┤
│4 1│4 2│4 3│4 4│4 5│4 6│4 7│4 8│
├───┼───┼───┼───┼───┼───┼───┼───┤
│5 1│5 2│5 3│5 4│5 5│5 6│5 7│5 8│
├───┼───┼───┼───┼───┼───┼───┼───┤
│6 1│6 2│6 3│6 4│6 5│6 6│6 7│6 8│
├───┼───┼───┼───┼───┼───┼───┼───┤
│7 1│7 2│7 3│7 4│7 5│7 6│7 7│7 8│
├───┼───┼───┼───┼───┼───┼───┼───┤
│8 1│8 2│8 3│8 4│8 5│8 6│8 7│8 8│
└───┴───┴───┴───┴───┴───┴───┴───┘
|
|
Consider a chess board as an 8×8 matrix with square (1 1) in the upper left corner and square (8 8) in the lower right corner. For those not familiar with the game a chess, the knight, generally depicted as a horse (♞), can move 2 spaces right or left and then 1 space up or down, or 2 spaces up or down and then 1 space right or left. For example, this means that a knight on the square (5 4) can move to any of the underscored squares.
Given a 2-element vector representing the current square for a knight, return a vector of 2-element vectors representing (in any order) all the squares that the knight can move to.
💡Hint: The outer product operator ∘. could be useful for generating the coordinates.
|
f4← {↓(∧/q∊⍳8)⌿q←⍵+⍤1⊢(3=+/|t)⌿t←↑,∘.,⍨¯2 ¯1 1 2}
f4 derives as follows: First, generate all 16 combinations t of moves involving 1 and 2 steps, left and right and up and down, then select move combinations which total exactly 3 squares regardless of direction.
(3=+/|t)⌿t←↑,∘.,⍨¯2 ¯1 1 2
¯2 ¯1
¯2 1
¯1 ¯2
¯1 2
1 ¯2
1 2
2 ¯1
2 1
The resultant 8-row matrix (call this mv) is added to ⍵, the coordinates of the current square, and then pruned to discard squares which fall outside of the chess board. The following examples illustrate the computation for ⍵≡5 4 and ⍵≡1 2 :
mv←(3=+/|t)⌿t←↑,∘.,⍨¯2 ¯1 1 2
⊢ q←5 4+⍤1⊢mv ⊢ q←1 2+⍤1⊢mv
3 3 ¯1 1
3 5 ¯1 3
4 2 0 0
4 6 0 4
6 2 2 0
6 6 2 4
7 3 3 1
7 5 3 3
↓(∧/q∊⍳8)⌿q ↓(∧/q∊⍳8)⌿q
┌───┬───┬───┬───┬───┬───┬───┬───┐ ┌───┬───┬───┐
│3 3│3 5│4 2│4 6│6 2│6 6│7 3│7 5│ │2 4│3 1│3 3│
└───┴───┴───┴───┴───┴───┴───┴───┘ └───┴───┴───┘
An alterative solution is to precomputing an 8×8 table of the possible knight moves for each chess square, and then picking from the table:
f4i← (f4¨ ⍳8 8) ⊃⍨ ⊂
The table look-up version would be more efficient in situations (such as in the Knight’s Tour puzzle) where the knight moves are computed repeatedly.
5. Doubling Up
Given a word or a list of words, return a Boolean vector where 1 indicates a word with one or more consecutive duplicated, case-sensitive, letters. Each word will have at least one letter and will consist entirely of either uppercase (A-Z) or lowercase (a-z) letters. Words consisting of a single letter can be scalars.
💡Hint: The nest function ⊆ could be useful.
f5← (∨⌿2=⌿' ',⊢)¨∘⊆
A solution obtains by solving it for one word and then applying it to each word via the each operator. Since a single word argument can be a string of letters, and we don’t want to apply the single word solution to each letter, that argument must first be converted in an enclosed word with nest. Thus the overall solution is of the form f¨∘⊆.
For a single word, what is required is to detect consecutive duplicate letters, whence the operator 2=⌿⍵ is apt.
2 =⌿ 'bookkeeper' 2 =⌿ 'radar'
0 1 0 1 0 1 0 0 0 0 0 0 0
∨⌿ 2 =⌿ 'bookkeeper' ∨⌿ 2 =⌿ 'radar'
1 0
As usual, the link function {⍺⍵} can be used as a generic dyadic operand function to gain additional insight into the workings of an operator:
2 {⍺⍵}⌿ 'bookkeeper' 2 {⍺⍵}⌿ 'radar'
┌──┬──┬──┬──┬──┬──┬──┬──┬──┐ ┌──┬──┬──┬──┐
│bo│oo│ok│kk│ke│ee│ep│pe│er│ │ra│ad│da│ar│
└──┴──┴──┴──┴──┴──┴──┴──┴──┘ └──┴──┴──┴──┘
2 f⌿⍵ signals error on single-item arguments; moreover, it is problematic to compare a single letter against itself. Both problems are finessed by first prefacing the argument with a space ' '.
In f5, the train (∨⌿2=⌿' ',⊢) can also be written as the equivalent dfn {∨⌿2=⌿' ',⍵} as a matter of personal style. The display of a train does provide more information about how it is structured than the display of a dfn.
(∨⌿2=⌿' ',⊢) {∨/2=⌿' ',⍵}
┌─────┬─────────────────┐ {∨⌿2=⌿' ',⍵}
│┌─┬─┐│┌─┬─────┬───────┐│
││∨│⌿│││2│┌─┬─┐│┌─┬─┬─┐││
│└─┴─┘││ ││=│⌿│││ │,│⊢│││
│ ││ │└─┴─┘│└─┴─┴─┘││
│ │└─┴─────┴───────┘│
└─────┴─────────────────┘
6. Telephone Names
┌────┬───┬────┐
│ │ABC│DEF │
│ 1 │ 2 │ 3 │
├────┼───┼────┤
│GHI │JKL│MNO │
│ 4 │ 5 │ 6 │
├────┼───┼────┤
│PQRS│TUV│WXYZ│
│ 7 │ 8 │ 9 │
├────┼───┼────┤
│ │ │ │
│ * │ 0 │ # │
└────┴───┴────┘
|
|
Some telephone keypads have letters of the alphabet embossed on their keytops. Some people like to remember phone numbers by converting them to an alphanumeric form using one of the letters on the corresponding key. For example, in the keypad shown, 'ALSMITH' would correspond to the number 257-6484 and '1DYALOGBEST' would correspond to 1-392-564-2378. Write an APL function that takes a character vector right argument that consists of digits and uppercase letters and returns an integer vector of the corresponding digits on the keypad.
💡Hint: Your solution might make use of the membership function ∊.
|
f6← {(⍵⍸⍨⎕d,'ADGJMPTW')-9*⍵∊⎕a}
Letters and digits alike are mapped to integer indices using the interval index function ⍸, which neatly handles the irregularly-sized intervals (see problem 2 above). The indices are then decremented by 9 for letters and by 1 for digits.
The expression 9*⍵∊⎕a illustrates a common technique in APL used to implement array logic, effecting control flow without using control structures or explicit branching. In the following, c and d are scalars (usually numbers) and ⍵ is a boolean array.
c*⍵ |
c where ⍵ is 1 and 1 where ⍵ is 0.
|
c×⍵ |
c where ⍵ is 1 and 0 where ⍵ is 0.
|
c+⍵×d-c |
c where ⍵ is 0 and d where ⍵ is 1.
|
(c,d)[1+⍵] |
Same as c+⍵×d-c, but c and d can be any scalars. The 1+ is omitted if the index origin ⎕io is 0.
|
7. In the Center of It All
Given a right argument of a list of words (or possibly a single word) and a left argument of a width, return a character matrix that has width columns and one row per word, with each word is centered within the row. If width is smaller than the length of a word, truncate the word from the right. If there are an odd number of spaces to center within, leave the extra space on the right.
💡Hint: The mix ↑ and rotate ⌽ functions will probably be useful here.
f7← {(⌈¯0.5×0⌈⍺-≢¨⍵)⌽↑⍺↑¨⍵}∘⊆
As in problem 5, a prefatory application of nest ⊆ converts an argument of a single word into a more manageable standard of a list of words. Subsequently, the right argument is turned into a matrix, each row padded with spaces on the right (or truncated). Each row is then rotated so that the non-blank characters are centered. The finicky detail of an odd number of spaces is resolved by using ⌈ or ⌊ in the calculation of the amounts of rotation.
8. Going the Distance
Given a vector of (X Y) points, or a single X Y point, determine the total distance covered when travelling in a straight line from the first point to the next one, and so on until the last point, then returning directly back to the start. For example, given the points
(A B C)← (¯1.5 ¯1.5) (1.5 2.5) (1.5 ¯1.5)
the distance A to B is 5, B to C is 4 and C back to A is 3, for a total of 12.
💡Hint: The rotate ⌽ and power * functions might be useful.
f8← {+⌿ 2 {0.5*⍨+.×⍨⍺-⍵}⌿ ⍵⍪1↑⍵}
The result obtains by applying the distance function d←{0.5*⍨+.×⍨⍺-⍵} between pairs of points, taking care to return to the start.
As in problem 5, the expression 2 f⌿⍵ is just the ticket for working with consecutive items in the argument and, again, using the link function {⍺⍵} elucidates the workings of an operator:
(A B C)← (¯1.5 ¯1.5) (1.5 2.5) (1.5 ¯1.5)
2 {⍺⍵}⌿ A B C A
┌───────────────────┬──────────────────┬────────────────────┐
│┌─────────┬───────┐│┌───────┬────────┐│┌────────┬─────────┐│
││¯1.5 ¯1.5│1.5 2.5│││1.5 2.5│1.5 ¯1.5│││1.5 ¯1.5│¯1.5 ¯1.5││
│└─────────┴───────┘│└───────┴────────┘│└────────┴─────────┘│
└───────────────────┴──────────────────┴────────────────────┘
2 d⌿ A B C A
5 4 3
A d B B d C C d A
5 4 3
f8 A B C
12
9. Area Code à la Gauss
Gauss’s area formula, also known as the shoelace formula, is an algorithm to calculate the area of a simple polygon (a polygon that does not intersect itself). It’s called the shoelace formula because of a common method using matrices to evaluate it. For example, the area of the triangle described by the vertices (2 4) (3 ¯8) (1 2) can be calculated by “walking around” the perimeter back to the first vertex, then drawing diagonals between the columns. The pattern created by the intersecting diagonals resembles shoelaces, hence the name “shoelace formula”.
💡Hint: You may want to investigate the rotate first ⊖ function.
| First place the vertices in order above each other: |
|
Sum the products of the numbers connected by the diagonal lines going down and to the right:
(2ׯ8)+(3×2)+(1×4)
¯6
|
|
Next sum the products of the numbers connected by the diagonal lines going down and to the left:
(4×3)+(¯8×1)+(2×2)
8
|
|
Finally, halve the absolute value of the difference between the two sums:
0.5 × | ¯6 - 8
7
|
| 2 |
│ |
│ |
4 |
| 3 |
│ |
│ |
¯8 |
| 1 |
│ |
│ |
2 |
| 2 |
|
|
4 |
|
Given a vector of (X Y) points, or a single X Y point, return a number indicating the area circumscribed by the points.
f9← {0.5×|(+/×/¯1↓0 1⊖t)-+/×/1↓0 ¯1⊖t←↑(⊢,1∘↑)⊆⍵}
There is an alternative solution using the determinant function and the stencil operator ⌺ :
)copy dfns det ⍝ or det← (-/)∘(×/)∘(0 1∘⊖)
x← (2 4) (3 ¯8) (1 2)
{det ⍵}⌺2 ↑x⍪1↑x
¯28 14 0
2 ÷⍨| +/ {det ⍵}⌺2 ↑x⍪1↑x
7
f9 x
7
Putting it together:
f9a← {2÷⍨|+/ {det ⍵}⌺2 ↑⍵⍪1↑⍵}
f9b← {2÷⍨ +/ {det ⍵}⌺2 ↑⍵⍪1↑⍵}
f9a x
7
f9b x
¯7
f9b ⊖t
7
f9a computes the absolute area as specified by the problem. f9b computes the signed area by omitting the absolute value function | . Commonly, the signed area is positive if the vertices are ordered counterclockwise and is negative otherwise. See the Wikipedia article on polygons for more details.
Similar to 2 f⌿⍵ (problem 5), the workings of stencil can be elucidated by using {⊂⍵} as a generic monadic operand function:
{⊂⍵}⌺2 ↑x⍪1↑x
┌────┬────┬───┐
│2 4│3 ¯8│1 2│
│3 ¯8│1 2│2 4│
└────┴────┴───┘
{det ⍵}⌺2 ↑x⍪1↑x
¯28 14 0
det ↑ (2 4) (3 ¯8) det ↑ (3 ¯8) (1 2) det ↑ (1 2) (2 4)
¯28 14 0
10. Odds & Evens
Given a vector of words, separate the words into two vectors—one containing all the words that have an odd number of letters and the other containing all the words that have an even number of letters.
💡Hint: You may want to look into the dyadic form of the key operator ⌸.
f10← 1 ↓¨ (1 0,2|≢¨) {⊂⍵}⌸ 1 0∘,
The solution is required to have exactly two items, words of odd lengths and words of even lengths. This required form is ensured by prefacing the left and right argument to key by 1 0, then dropping the first item from each of the resultant two parts. (See also problem 3 above.)
Editor’s Addendum: Phase II Questions
You can watch the 2019 Grand Prize Winner Jamin Wu’s Dyalog ’19 acceptance presentation and explanation of how he approached the phase II questions on Dyalog.tv.
We are happy to announce that the full set of recordings from Dyalog ’20 online is now available. So if you missed the all or any of the talks, or would like to revisit one of the presentations, head over to https://dyalog.tv/Dyalog20!
Follow
