2019 APL Problem Solving Competition: Phase I Problems Sample Solutions

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 functionsand [] 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 asor
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 functioncould 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 whereis 1 and 1 whereis 0.
c×⍵ c whereis 1 and 0 whereis 0.
c+⍵×d-c   c whereis 0 and d whereis 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 mixand rotatefunctions will probably be useful here.

   f7← {(⌈¯0.5×0⌈⍺-≢¨⍵)⌽↑⍺↑¨⍵}∘⊆

As in problem 5, a prefatory application of nestconverts 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 usingorin 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 rotateand 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 firstfunction.

First place the vertices in order above each other:
2 4
3 ¯8
1 2
2 4
Sum the products of the numbers connected by the diagonal lines going down and to the right:

      (2ׯ8)+(3×2)+(1×4)
¯6
      
2 4
3 ¯8
1 2
2 4
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
      
2 4
3 ¯8
1 2
2 4

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.

Ascending and Descending

Lexicographic Ordering

Lexicographic ordering is what the APL primitives and provide:

   ⎕io←0     ⍝ ⎕io delenda est
   ⎕rl←7*5   ⍝ to get reproducible random results

   a←?11 3⍴3

   a          a ⌷⍨⊂ ⍋a
2 1 0      0 1 0
0 2 2      0 2 2
1 1 1      1 0 0
1 0 0      1 0 1
1 1 1      1 0 1
1 2 1      1 1 0
1 0 1      1 1 1
1 0 1      1 1 1
1 1 0      1 2 1
0 1 0      1 2 2
1 2 2      2 1 0

First order by column 0, resulting in groups of rows with the same values in column 0. Then, within each group, order by column 1, getting subgroups with the same values in columns 0 and 1. Then, within each subgroup, order by column 2, getting subsubgroups with the same values in columns 0, 1, and 2. In general, for each subsub…subgroup, order by column k, getting groups with identical values in columns ⍳k.

The preceding discourse is descriptive rather than prescriptive—algorithms for can use more efficient and more straightforward approaches. As well, for ease of understanding, the description is for a matrix and speaks of columns and rows. In general, any non-scalar array can be ordered, whence instead of rows, think major cells, instead of column, think item in a major cell. Symbolically and more succinctly, ⍋⍵ ←→ ⍋⍪⍵.

can be used if the orderings in the process are all ascending, or if all descending. The problem to be solved here is where the orderings are a mix of ascending and descending.

Numeric Arrays

Since ⍒⍵ ←→ ⍋-⍵ if is numeric, for such multiply each descending column by ¯1 and each ascending column by 1, then apply . This induces a “control array” having the same shape as a major cell of the argument, with a ¯1 for descending and a 1 for ascending.

   adn←{⍵ ⌷⍨⊂ ⍋ ⍺ ×⍤99 ¯1 ⊢⍵}

For the array a in the previous section:

   a              1 ¯1 1 adn a        ¯1 1 1 adn a
2 1 0          0 2 2               2 1 0  
0 2 2          0 1 0               1 0 0  
1 1 1          1 2 1               1 0 1  
1 0 0          1 2 2               1 0 1  
1 1 1          1 1 0               1 1 0  
1 2 1          1 1 1               1 1 1  
1 0 1          1 1 1               1 1 1  
1 0 1          1 0 0               1 2 1  
1 1 0          1 0 1               1 2 2  
0 1 0          1 0 1               0 1 0  
1 2 2          2 1 0               0 2 2  

In 1 ¯1 1 adn a, column 0 is ascending, and within that, column 1 is descending, and within that, column 2 is ascending. In ¯1 1 1 adn a, column 0 is descending, and within that, column 1 is ascending, and within that, column 2 is ascending.

Ordinals

An array to be sorted can be converted to an order-equivalent integer array by assigning to each item an ordinal (an integer) which has the same ordering relationship as the original item relative to other items in the array:

   sort    ← {(⊂⍋⍵)⌷⍵}
   ordinal ← {⎕ct←0 ⋄ ⍵⍳⍨sort,⍵}

That is, the ordinals obtain as the indices of the original array in the sorted list of the ravelled elements, using exact comparisons. (Exact comparisons are used because sorting necessarily uses exact comparisons.)
For example:

   ⊢ d←¯1 'syzygy' (3 ¯5) 1j2 'chthonic' (¯1)
┌──┬──────┬────┬───┬────────┬──┐
│¯1│syzygy│3 ¯5│1J2│chthonic│¯1│
└──┴──────┴────┴───┴────────┴──┘
   ordinal d
0 5 3 2 4 0

In the example, the data items are ¯1, 'syzygy', 'chthonic', 3 ¯5, 1j2, and ¯1 again. With respect to ordering, these data items are perfectly represented by the ordinals (numbers) 0, 5, 3, 2, 4, and 0, respectively. That is, ⍋d ←→ ⍋ordinal d.

   ⍋ d
0 5 3 2 4 1
   ⍋ ordinal d
0 5 3 2 4 1

As the example illustrates, it is imperative that identical ordinals are assigned to identical items, else the ordering relationships would be changed. For example, if b←0,⍪2 1 and the 0s are assigned different ordinals,

   ⊢ b←0,⍪2 1               
0 2
0 1
   ordinal b                 ⊢ bo←0 3,⍪1 2  ⍝ faux ordinals
0 3                       0 3
0 2                       1 2
   ⍋ ordinal b               ⍋ bo
1 0                       0 1
   ⍋ b
1 0

Computation of ordinals is greatly facilitated by the total array ordering introduced in Dyalog APL version 17.0.

Non-Numeric Arrays

A general solution for the ordering problem obtains by first converting the array to an order-equivalent integer array through the use of ordinals.

   ado ← {⍵ ⌷⍨⊂ ⍋ ⍺ ×⍤99 ¯1 ordinal ⍵}

For example:

   ⎕rl←7*5   ⍝ to get reproducible random results

   x0← ?19⍴4                            
   x1← (⊂?19⍴2) ⌷ 'alpha' 'beta'          
   x2← (⊂?19⍴3) ⌷ 'abc'                   
   x3← (⊂?19⍴3) ⌷ 'able' 'baker' 'charlie'

   x ← x0,x1,x2,⍪x3

   ordinal x
13 49 19 42
10 49 32 68
13 49 63 68
 4 49 63 42
 0 27 19 23
13 49 32 42
 0 49 19 42
10 49 32 68
10 27 32 23
 4 49 32 68
 4 49 32 68
 4 27 32 23
 4 49 32 68
 0 49 63 68
13 49 63 68
 0 49 32 42
13 27 32 23
 4 27 63 42
13 49 19 42

   (⍋x) ≡ ⍋ ordinal x
1

Suppose x is to be sorted ascending in columns 0 and 2 and descending in columns 1 and 3. The control array is 1 ¯1 1 ¯1, and:

   x                       1 ¯1 1 ¯1 ado x
┌─┬─────┬─┬───────┐     ┌─┬─────┬─┬───────┐
│2│beta │b│baker  │     │0│beta │a│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│alpha│a│able   │     │0│beta │b│charlie│
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│beta │b│able   │     │0│beta │b│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│alpha│b│baker  │     │0│beta │c│charlie│
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│1│beta │b│charlie│     │0│beta │c│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│1│beta │a│baker  │     │0│alpha│c│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│0│beta │c│charlie│     │1│beta │a│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│0│beta │b│baker  │     │1│beta │b│charlie│
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│0│beta │c│able   │     │1│alpha│c│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│0│beta │a│able   │     │2│beta │a│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│alpha│a│baker  │     │2│beta │b│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│alpha│a│baker  │     │3│beta │b│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│1│alpha│c│able   │     │3│beta │b│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│0│beta │b│charlie│     │3│beta │c│charlie│
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│0│alpha│c│baker  │     │3│alpha│a│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│beta │b│able   │     │3│alpha│a│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│2│beta │a│baker  │     │3│alpha│a│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│beta │c│charlie│     │3│alpha│a│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│alpha│a│able   │     │3│alpha│b│baker  │
└─┴─────┴─┴───────┘     └─┴─────┴─┴───────┘

Finally

   (ordinal x) ≡ ordinal ordinal x
1

That is, ordinal is idempotent. Actually, this is kind of obvious, but I never miss an opportunity to use the word “idempotent”.☺

Diane’s Lasagne Problem

Making Lasagne

Participants in the SA2 Performance Tuning workshop at the Dyalog ’18 User Meeting were encouraged to bring their own problems for the group to work on. Diane Hymas of ExxonMobil brought a good one. The one-liner computation is as follows:

lasagne0 ← {groups {+⌿⍵}⌸ amts ×[⎕io] spices[inds;]}

where

   n ← 8e5
   spices ← ?6000 44⍴0
   groups ← +\(16↑1 2)[?n⍴16]
   inds   ← ?n⍴≢spices
   amts   ← ?n⍴0

Applying lasagne0 to this dataset:

   ⍴ lasagne0 ⍬
100015 44
   ≢ ∪ groups
100015

   )copy dfns wsreq cmpx

   wsreq 'lasagne0 ⍬'
844799820
   cmpx  'lasagne0 ⍬'
2.12E¯1

The problem with lasagne0 is space rather than time. The 845 MB required for this dataset may be acceptable, but we can be called upon to cook up large batches of lasagne in a smallish workspace, on a machine with limited RAM. (Large n and large ≢∪groups.)

All benchmarks in this document were run in Dyalog APL version 17.0, in a 2 GB workspace, on a machine with generous RAM.

Solutions

Marshall Lochbaum solved the problem. The alternative solutions are as follows:

lasagne0 ← {groups {+⌿⍵}⌸ amts ×[⎕io] spices[inds;]}
lasagne1 ← {↑ (groups{⊂⍵}⌸amts) {+⌿⍺×[⎕io]spices[⍵;]}¨ groups{⊂⍵}⌸inds}
lasagne2 ← {↑ (groups{⊂⍵}⌸amts)      {⍺+.×spices[⍵;]}¨ groups{⊂⍵}⌸inds}
lasagne3 ← {↑ {amts[⍵]+.×spices[inds[⍵];]}¨ {⊂⍵}⌸groups}

lasagne0 is the original expression; lasagne1 and lasagne2 were derived by Marshall during the workshop; lasagne3 was suggested by a participant in the workshop. The four functions produce matching results. Comparing the space and time:

space (MB)           time
lasagne0 845 2.29e¯1 ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
lasagne1 74 3.60e¯1 ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
lasagne2 74 2.39e¯1 ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
lasagne3 74 2.93e¯1 ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

lasagne0 v  lasagne1

Nearly all of the space required to evaluate lasagne0 is accounted for by the space for computing the right argument to key:

   wsreq 'lasagne0 ⍬'
844799820

   wsreq 'amts ×[⎕io] spices[inds;]'
844799548

In fact, the array spices[inds;], all by itself, is already very large. It has shape (⍴inds),1↓⍴spices (≡ 8e5 44), each item requiring 8 bytes.

   wsreq 'spices[inds;]'
281599556

   ⍴ spices[inds;]
800000 44

   8 × ×/ ⍴ spices[inds;]
281600000

   qsize←{⎕size '⍵'}    ⍝ # bytes for array ⍵
   qsize spices[inds;]
281600040

lasagne1 avoids creating these large intermediate results, by first partitioning the arguments (groups{⊂⍵}⌸amts and groups{⊂⍵}⌸inds) and then applying a computation to each partition. In that computation, the operand function {+⌿⍺×[⎕io]spices[⍵;]}, is a partition of amts and is the corresponding partition of inds.

lasagne1, lasagne2 and lasagne3 require the same amount of space to run, so the comparison among them is on time.

lasagne1 v  lasagne2

The only change is from +⌿⍺×[⎕io]spices[⍵;] to ⍺+.×spices[⍵;], which are equivalent when is a vector. The interpreter can compute +.× in one go rather than doing +⌿ separately after doing ×[⎕io]; in such computation the interpreter can and does exploit the additional information afforded by +.× and is faster by a factor of 1.5 (= 2.39 ÷⍨ 3.60).

lasagne2 v  lasagne3

The idea in lasagne3 is doing one key operation rather than the two in lasagne2. Therefore, the changes between lasagne2 v lasagne3 are:

lasagne2 groups{⊂⍵}⌸amts
groups{⊂⍵}⌸inds
spices[⍵;]
lasagne3 {⊂⍵}⌸groups amts[⍵] spices[inds[⍵];]

All three key operations involve {⊂⍵}⌸ with groups as the key, and are roughly equally fast, each taking up no more than 7% of the total time.

   cmpx 'groups{⊂⍵}⌸amts' 'groups{⊂⍵}⌸inds' '{⊂⍵}⌸groups'
  groups{⊂⍵}⌸amts → 1.69E¯2 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
* groups{⊂⍵}⌸inds → 1.39E¯2 | -18% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
* {⊂⍵}⌸groups     → 1.36E¯2 | -20% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

lasagne3 is doing one less key operation than lasagne2 in exchange for doing, for each of the ≢∪groups (= 100015) executions of the operand function, amt[⍵] v and spices[ind[⍵];] v spices[⍵;]. Indexing is by no means slow, but it’s not as fast as references to and . Therefore, lasagne2 is faster.

The trade-off may differ for different values of groups. In this case groups are small-range integers so operations using it as the key value are fast.

Progressive Index-Of

⎕io=0 is assumed throughout.

A recent Forum post motivated investigations into the progressive index-of functions in the FinnAPL Idiom Library:

pix  ← {((⍴⍺)⍴⍋⍋⍺⍳⍺,⍵) ⍳ ((⍴⍵)⍴⍋⍋⍺⍳⍵,⍺)}   ⍝ FinnAPL Idiom 1
pixa ← {((⍋⍺⍳⍺,⍵)⍳⍳⍴⍺) ⍳ ((⍋⍺⍳⍵,⍺)⍳⍳⍴⍵)}   ⍝ FinnAPL Idiom 5

In this note, we:

  • explain what is progressive index-of
  • explain why the two functions work
  • investigate the performance of the two functions
  • provide a more general solution

Progressive Index-Of

Progressive index-of is like index-of () except that each find “uses up” the target of that find. There are no duplicates in the result with the possible exception of ≢⍺ (for “not found”). Thus:

      x←'mississippi'
      y←'dismiss'

      x pix y
11 1 2 0 4 3 5

The following chart illustrates a step-by-step derivation of each progressive index:

0 1 2 3 4 5 6 7 8 9 10

m i s s i s s i p p  i      d i s m i s s
                           11
m i s s i s s i p p  i      d i s m i s s
                           11 1
m i s s i s s i p p  i      d i s m i s s
                           11 1 2
m i s s i s s i p p  i      d i s m i s s
                           11 1 2 0
m i s s i s s i p p  i      d i s m i s s
                           11 1 2 0 4
m i s s i s s i p p  i      d i s m i s s
                           11 1 2 0 4 3
m i s s i s s i p p  i      d i s m i s s
                           11 1 2 0 4 3 5

It is possible to compute the progressive index without looping or recursion, as the two FinnAPL functions demonstrate.

Why It Works

The basic idea of ⍺ pix ⍵ is to substitute for each item of and an equivalent representative, collectively c and d, whence the result obtains as c⍳d. The equivalent representative used here is ranking, specifically the ranking of the indices in .

The ranking of an array is a permutation of order ≢⍵. The smallest major cell is assigned 0; the next smallest is assigned 1; and so on. Ties are resolved by favoring the earlier-occurring cell. The ranking can be computed by ⍋⍋⍵. For example:

      x ⍪ ⍉⍪ ⍋⍋x
m i s s i s  s i p p i
4 0 7 8 1 9 10 2 5 6 3

      y ⍪ ⍉⍪ ⍋⍋y
d i s m i s s
0 1 4 3 2 5 6

⍺ pix ⍵ works on two different rankings of indices in :

⍋⍋⍺⍳⍺,⍵    rankings of indices in of and , favoring
⍋⍋⍺⍳⍵,⍺    rankings of indices in of and , favoring

The first ⍴⍺ items of the former are those for and the first ⍴⍵ of the latter are those for , and we get

pix ← {((⍴⍺)⍴⍋⍋⍺⍳⍺,⍵) ⍳ ((⍴⍵)⍴⍋⍋⍺⍳⍵,⍺)}

The second version depends on the following properties of permutations. Let p be a permutation. Then p[⍋p] ←→ ⍳≢p, the identity permutation, and therefore ⍋p is the inverse of p. Furthermore, p[p⍳⍳≢p] ←→ ⍳≢p and so p⍳⍳≢p is also the inverse of p. The inverse is unique (that’s why it’s called the inverse), therefore ⍋p ←→ p⍳⍳≢p.

      p←97?97         ⍝ a random permutation

      p[⍋p]    ≡ ⍳≢p
1
      p[p⍳⍳≢p] ≡ ⍳≢p
1
      (⍋p)     ≡ p⍳⍳≢p
1

The two rankings are permutations (because the leftmost functions are ) and we just need the first ⍴⍺ items of the former and the first ⍴⍵ items of the latter. Thus:

pixa ← {((⍋⍺⍳⍺,⍵)⍳⍳⍴⍺) ⍳ ((⍋⍺⍳⍵,⍺)⍳⍳⍴⍵)}

Performance

We note that both versions of pix contain the expressions ⍺⍳⍺,⍵ and ⍺⍳⍵,⍺, but the latter is just a rotation of the former. Thus:

pixb ← {i←⍺⍳⍺,⍵ ⋄ ((⍴⍺)⍴⍋⍋i) ⍳ ((⍴⍵)⍴⍋⍋(⍴⍺)⌽i)}
pixc ← {i←⍺⍳⍺,⍵ ⋄ ((⍋i)⍳⍳⍴⍺) ⍳ ((⍋(⍴⍺)⌽i)⍳⍳⍴⍵)}

Which is faster? The answer may surprise.

      x←?1e6⍴3e5
      y←?2e5⍴3e5

      cmpx 'x pixb y' 'x pixc y'
  x pixb y → 9.15E¯2 |  0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  x pixc y → 9.21E¯2 |  0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

A few factors about the Dyalog APL interpreter are relevant to this performance:

  • Computing ⍺⍳⍵,⍺ as a rotation of an already computed i←⍺⍳⍺,⍵ produces a worthwhile speed-up, although only on a relatively small part of the overall computation.
          i←x⍳x,y
          cmpx '(⍴x)⌽i' 'x⍳y,x'
      (⍴x)⌽i → 5.00E¯4 |     0% ⎕⎕                            
      x⍳y,x  → 7.19E¯3 | +1337% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
    
  • Both and have special code for small range data.
          s←?1e6⍴5e5           ⍝ small range
          t←s ⋄ t[t⍳⌈/t]←2e9   ⍝ large range
    
          cmpx 's⍳s' 't⍳t'
      s⍳s → 5.87E¯3 |    0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕                     
      t⍳t → 2.00E¯2 | +240% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
    
          cmpx '⍋s' '⍋t'
      ⍋s → 3.25E¯2 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕     
      ⍋t → 3.84E¯2 | +18% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
    
  • ⍋⍵ has special code when is a permutation.
          p←1e6?1e6           ⍝ p is a permutation
          q←p ⋄ q[999999]←⊃q  ⍝ q is not; both are small-range
    
          cmpx '⍋p' '⍋q'
      ⍋p → 5.81E¯3 |    0% ⎕⎕⎕                           
    * ⍋q → 5.71E¯2 | +882% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
    
  • We saw previously that if p is a permutation then ⍋p ←→ p⍳⍳⍴p. The special code for ⍋p makes the two expressions run at roughly the same speed. The slight advantage for ⍋⍋x versus (⍋x)⍳⍳⍴x would increase if and when ⍋⍋ is recognized as an idiom.
          cmpx '⍋p' 'p⍳⍳⍴p'
      ⍋p    → 6.02E¯3 |  0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕   
      p⍳⍳⍴p → 6.57E¯3 | +9% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
    
          cmpx '⍋⍋x' '(⍋x)⍳⍳⍴x'
      ⍋⍋x      → 3.16E¯2 |  0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕ 
      (⍋x)⍳⍳⍴x → 3.25E¯2 | +2% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
    
    

A General Solution

Index-of works on cells rather than just scalars. Likewise, progressive index-of can also be extended to work on cells. The core algorithm remains the same. The generalization obtains by first reshaping to have the same rank as (having major cells with the same shape), applying the core algorithm, and then reshaping its result to have the same leading shape as the original . Thus:

pixd←{
  m←≢⍺
  r←0⌊1-⍴⍴⍺
  n←×/r↓⍴⍵
  i←⍺⍳⍺⍪(n,1↓⍴⍺)⍴⍵
  (r↓⍴⍵) ⍴ ((⍋i)⍳⍳m) ⍳ ((⍋m⌽i)⍳⍳n)
}

   xx              yy
mmmm            dddd
iiii            iiii
ssss            ssss
ssss            mmmm
iiii            iiii
ssss            ssss
ssss            ssss
iiii     
pppp     
pppp                                  x
iiii                               mississippi

   ⍴xx             ⍴yy                y
11 4            7 4                dismiss

   xx pixd yy                         x pixd y
11 1 2 0 4 3 5                     11 1 2 0 4 3 5

   xx pixd 3 5 4⍴yy                   x pixd 3 5⍴y
11  1  2  0  4                     11  1  2  0  4
 3  5 11  7  6                      3  5 11  7  6
11 10 11 11 11                     11 10 11 11 11

Postscript
After having written the above, I discovered an alternative exposition on progressive index-of by Bob Smith entitled Anatomy of an Idiom. Adám Brudzewsky has produced a Stack Exchange lesson and a Jupyter Notebook based on Smith’s text.

There is also an exposition in J on the same topic, with a more verbose but easier-to-understand derivation.

2018 APL Problem Solving Competition: Phase I Problems Sample Solutions

The following are my attempts at the Phase I problems of the 2018 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.

The solutions for problems 1 and 3 are due to Brian Becker, judge and supremo of the competition. They are better than the ones I had originally.

1. Oh Say Can You See?

Given a vector or scalar of skyscraper heights, compute the number of skyscrapers which can be seen from the left. A skyscraper hides one further to the right of equal or lesser height.

   visible ← {≢∪⌈\⍵}

Proceeding from left to right, each new maximum obscures subsequent equal or lesser values. The answer is the number of unique maxima. A tacit equivalent is ≢∘∪∘(⌈\).

2. Number Splitting

Split a non-negative real number into the integer and fractional parts.

   split ← 0 1∘⊤

The function ⍺⊤⍵ encodes the number in the number system specified by numeric vector (the bases). For example, 24 60 60⊤sec expresses sec in hours, minutes, and seconds. Such expression obtains by repeated application of the process, starting from the right of : the next “digit” is the remainder of the number on division by a base, and the quotient of the division feeds into the division by the next base. Therefore, 0 1⊤⍵ divides by 1; the remainder of that division is the requisite fractional part and the quotient the integer part. That integer part is further divided by the next base, 0. In APL, remaindering by 0 is defined to be the identity function.

You can have a good argue about the philosophy (theology?) of division by 0, but the APL definition in the context of ⍺⊤⍵ gives practically useful results: A 0 in essentially says, whatever is left. For example, 0 24 60 60⊤sec expresses sec as days/hours/minutes/seconds.

3. Rolling Along

Given an integer vector or scalar representing a set of dice, produce a histogram of the possible totals that can be rolled.

   roll ← {{⍺('*'⍴⍨≢⍵)}⌸,+/¨⍳⍵}

   roll 5 3 4
3  *
4  ***
5  ******
6  *********
7  ***********
8  ***********
9  *********
10 ******
11 ***
12 *

⍳⍵ produces all possible rolls for the set of dice (the cartesian product of ⍳¨⍵) whence further application of +/¨ and then , produce a vector of all possible totals. With the vector of possible totals in hand, the required unique totals and corresponding histogram of the number of occurrences obtain readily with the key operator . (And rather messy without the key operator.) For each unique total, the operand function {⍺('*'⍴⍨≢⍵)} produces that total and a vector of * with the required number of repetitions.

The problem statement does not require it, but it would be nice if the totals are listed in increasing order. At first, I’d thought that the totals would need to be explicitly sorted to make that happen, but on further reflection realized that the unique elements of ,+/¨⍳⍵ (when produced by taking the first occurrence) are guaranteed to be sorted.

4. What’s Your Sign?

Find the Chinese zodiac sign for a given year.

   zodiac_zh ← {(1+12|⍵+0>⍵) ⊃ ' '(≠⊆⊢)' Monkey Rooster Dog Pig Rat Ox Tiger Rabbit Dragon Snake Horse Goat'}

Since the zodiac signs are assigned in cycles of 12, the phrase 12| plays a key role in the solution. The residue (remainder) function | is inherently and necessarily 0-origin; the 1+ accounts for the 1-origin indexing required by the competition. Adding 0>⍵ overcomes the inconvenient fact that there is no year 0.

Essentials of the computation are brought into sharper relief if each zodiac sign is denoted by a single character:

   zzh ← {(1+12|⍵+0>⍵)⊃'猴雞狗豬鼠牛虎兔龍蛇馬羊'}

The Chinese Unicode characters were found using https://translate.google.com and then copied and pasted into the Dyalog APL session.

5. What’s Your Sign? Revisited

Find the Western zodiac sign for a given month and day.

   zodiac_en←{
     d←12 2⍴ 1 20  2 19  3 21  4 20  5 21  6 21  7 23  8 23  9 23  10 23  11 22  12 22
     s←13⍴' '(≠⊆⊢)' Capricorn Aquarius Pisces Aries Taurus Gemini Cancer Leo Virgo Libra Scorpio Sagittarius'
     (1+d⍸⍵)⊃s
   }

For working with irregular-sized non-overlapping intervals, the pre-eminent function is , interval index. As with the Chinese zodiac, essentials of the computation are brought into sharper relief if each zodiac sign is denoted by a single character:

   zen←{
     d←12 2⍴ 1 20  2 19  3 21  4 20  5 21  6 21  7 23  8 23  9 23  10 23  11 22  12 22
     (1+d⍸⍵)⊃13⍴'♑♒♓♈♉♊♋♌♍♎♏♐'
   }

The single-character signs, Unicode U+2648 to U+2653, were found by Google search and then confirmed by https://www.visibone.com/htmlref/char/cer09800.htm. It is possible that the single-character signs do not display correctly in your browser; the line of code can be expressed alternatively as (1+d⍸⍵)⊃13⍴⎕ucs 9800+12|8+⍳12.

6. What’s Your Angle?

Check that angle brackets are balanced and not nested.

   balanced ← {(∧/c∊0 1)∧0=⊃⌽c←+\1 ¯1 0['<>'⍳⍵]}

In APL, functions take array arguments, and so too indexing takes array arguments, including the indices (the “subscripts”). This fact is exploited to transform the argument string into a vector c of 1 and ¯1 and 0, according to whether a character is < or > or “other”. For the angles to be balanced, the plus scan (the partial sums) of c must be a 0-1 vector whose last element is 0.

The closely related problem where the brackets can be nested (e.g. where the brackets are parentheses), can be solved by checking that c is non-negative, that is, ∧/(×c)∊0 1 (and the last element is 0).

7. Unconditionally Shifty

Shift a boolean vector by , where positive means a right shift and negative means a left shift.

   shift ← {(≢⍵)⍴(-⍺)⌽⍵,(|⍺)⍴0}

The problem solution is facilitated by the rotate function ⍺⌽⍵, where a negative means rotate right and positive means rotate left. Other alternative unguarded code can use or (take or drop) where a negative means take (drop) from the right and positive means from the left.

8. Making a Good Argument

Check whether a numeric left argument to ⍺⍉⍵ is valid.

   dta ← {0::0 ⋄ 1⊣⍺⍉⍵}

This is probably the shortest possible solution: Return 1 if ⍺⍉⍵ executes successfully, otherwise the error is trapped and a 0 is returned. A longer but more insightful solution is as follows:

   dt ← {((≢⍺)=≢⍴⍵) ∧ ∧/⍺∊⍨⍳(≢⍴⍵)⌊(×≢⍺)⌈⌈⌈/⍺}

The first part of the conjunction checks that the length of is the same as the rank of . (Many APL authors would write ⍴⍴⍵; I prefer ≢⍴⍵ because the result is a scalar.) The second part checks the following properties on :

  • all elements are positive
  • the elements (if any) form a dense set of integers (from 1 to ⌈/⍺)
  • a (necessarily incorrect) large element would not cause the to error

The three consecutive ⌈⌈⌈, each interpreted differently by the system, are quite the masterstroke, don’t you think? ☺

9. Earlier, Later, or the Same

Return ¯1, 1, or 0 according to whether a timestamp is earlier than, later than, or simultaneous with another.

   ts ← {⊃0~⍨×⍺-⍵}

The functions works by returning the first non-zero value in the signum of the difference between the arguments, or 0 if all values are zero. A tacit solution of same: ts1 ← ⊃∘(~∘0)∘× - .

10. Anagrammatically Correct

Determine whether two character vectors or scalars are anagrams of each other. Spaces are not significant. The problem statement is silent on this, but I am assuming that upper/lower case is significant.

   anagram ← {g←{{⍵[⍋⍵]}⍵~' '} ⋄ (g ⍺)≡(g ⍵)}

The function works by first converting each argument to a standard form, sorted and without spaces, using the local function g, and then comparing the standard forms. In g, the idiom {⍵[⍋⍵]} sorts a vector and the phrase ⍵~' ' removes spaces and finesses the problem of scalars.

A reasonable tacit solution depends on the over operator , contemplated but not implemented:

     f⍥g ⍵  ←→  f g ⍵
   ⍺ f⍥g ⍵  ←→  (g ⍺) f (g ⍵)

A tacit solution written with over: ≡⍥((⊂∘⍋ ⌷ ⊢)∘(~∘' ')). I myself would prefer the semi-tacit ≡⍥{{⍵[⍋⍵]}⍵~' '}.

 

Is it Sorted?

Motivation

I have been working on the Dyalog APL quicksort implementation. The following programming puzzle arose in the process of doing the QA for this work.

is a simple array. Write a function sorted, without using or , such that sorted ⍵ is 1 if is sorted in ascending order and 0 otherwise.

The point about not using grade is that this is supposed to be an independent check that grade is correct (remains correct) after the new work.

Real Vectors

The simplest case is when is a numeric vector. If furthermore are not complex numbers (a case addressed later), then

   ∧/ 2≤/⍵

each item being less than or equal to the next one, checks that is sorted. Since uses exact comparisons, here we must set ⎕ct←⎕dct←0. Morever, in order that decimal floating-point numbers (DECFs) be compared correctly, here ⎕fr←1287.

Real Arrays

More generally, when is a non-complex numeric matrix, we must check that each row precedes or is equal to the next row. If c and d are consecutive rows, then corresponding items are compared and at the first item where they differ, c[i] must be less than d[i].

   ~ 0 ∊ (2>⌿⍪⍵) ⍲ <\ 2≠⌿⍪⍵

The expression incorporates two refinements:

  • If is not a matrix, first apply ⍪⍵.
  • Instead of checking c[i] is less than d[i], check that c[i] is not greater than d[i]. This finesses the case where c≡d and there is no first item where they differ; that is, the case where <\2≠⌿⍪⍵ is all 0s for that row.

<\on a boolean vector has 0s after the first 1, (and is all 0 if there are no 1s). Therefore, <\2≠⌿⍪⍵ finds the first item (if any) where one cell differs from the next cell, and that item must not be greater than the corresponding item in the next cell.

For example:

   x←?97 3⍴10

   {~ 0 ∊ (2>⌿⍪⍵) ⍲ <\ 2≠⌿⍪⍵} x
0
   {~ 0 ∊ (2>⌿⍪⍵) ⍲ <\ 2≠⌿⍪⍵} x[⍋x;]
1

(Muse: since x above are random numbers, there is a possibility that it is sorted and the first test above can be 1. But: if each elementary particle in the visible universe were a computer and every nanosecond each of them creates a random matrix and tests it for sortedness as above, running from the beginning of the time to the end of our lives, it is still a very safe bet that no 1 would result.)

For integer arrays, there is an alternative of using the signs of the arithmetic difference between successive cells:

   {~ 0 ∊ 1≠t×<\0≠t← × 2-⌿⍪⍵} x[⍋x;]
1

(The sign where consecutive cells first differ must not be 1.) However, computing the difference on floating point numbers can founder on overflow:

   ⊢ x←¯1 1×⌊/⍬
¯1.79769E308 1.79769E308

   {~ 0 ∊ 1≠t×<\0≠t← × 2-⌿⍪⍵} x
DOMAIN ERROR
   {~0∊1≠t×<\0≠t←×2-⌿⍪⍵}x
                   ∧

Complex Numbers

Two complex numbers are ordered first by the real parts and then by the imaginary parts. (This is part of the TAO extension implemented in Dyalog APL version 17.0.) Therefore, a complex array can be tested for sortedness by testing an equivalent real array with each number replaced by their real and imaginary parts, thus:

   (¯1⌽⍳1+⍴⍴⍵) ⍉ 9 11∘.○⍵
   ↑9 11∘○¨⍵
   9 11○⍤1 0⊢⍵

Although the second expression is the shortest, it is less efficient in time, space, and number of getspace calls. The last expression is favored for its brevity and performance.

The number of getspace is a worthwhile measure. Part of the QA process is a rather stringent procedure called the “Shuffle QA”. The entire Shuffle QA takes several weeks to run and its running time is directly related to the number of getspace.

Character Arrays

None of the functions < ≤ ≥ > - × are permitted on characters. This is solved by application of ⎕ucs, converting characters to integers while preserving the ordering.

Putting It All Together

sorted←{
  ⎕ct←⎕dct←0
  ⎕fr←1287
  d←10|⎕dr ⍵
  d∊0 2: ∇ ⎕ucs ⍵
  d=9:   ∇ 9 11○⍤1 0⊢⍵
  ~ 0 ∊ (2>⌿⍪⍵) ⍲ <\ 2≠⌿⍪⍵
}

Other Considerations

That ⍵⌷⍨⊂⍋⍵ is sorted is a necessary but not sufficient condition that ⍋⍵ is correct. For example, an “adversary” can supply the following results for ⍋⍵ so that ⍵⌷⍨⊂⍋⍵ is sorted:

?≢⍵
(≢⍵)⍴?≢⍵
¯1↓⍋⍵
∊ i {⊂⍵[?⍨≢⍵]}⌸⍨ ⍵⌷⍨⊂i←⍋⍵

The last expression randomly permutes the grade indices of equal cells, a result which violates the requirement that grade indices of equal cells are in ascending order. That is, grade must be stable.

In Dyalog APL version 17.0, grade has been extended to work on non-simple arrays, the much discussed TAO, total array ordering. Checking that a non-simple array is sorted without using grade requires facilities discussed in the paper TAO Axioms and is beyond the scope of this note.