# Towards Improvements to Stencil

## Background

The stencil operator `⌺` was introduced in Dyalog version 16.0 in 2017. Recently we received some feedback (OK, complaints) that (a) stencil does padding which is unwanted sometimes and needs to be removed from the result and (b) stencil is too slow when it is not supported by special code.

First, stencil in cases supported by special code is much faster than when it is not. The special cases are as follows, from Dyalog ’17 Workshop SA3.

```   {⍵}      {⊢⍵}      {,⍵}      {⊂⍵}
{+/,⍵}    {∧/,⍵}    {∨/,⍵}    {=/,⍵}    {≠/,⍵}

{  +/,A×⍵}    {  +/⍪A×⍤2⊢⍵}
{C<+/,A×⍵}    {C<+/⍪A×⍤2⊢⍵}
```
`C:  `a single number or variable whose value is a single number
`A:  `a variable whose value is a rank-2 or 3 array
The comparison can be` < ≤ ≥ > = ≠ `
odd window size; movement 1; matrix argument

You can test whether a particular case is supported by using a circumlocution to defeat the special case recognizer.

```   )copy dfns cmpx

cmpx '{⍵}⌺3 5⊢y' '{⊢⊢⍵}⌺3 5⊢y' ⊣ y←?100 200⍴0
{⍵}⌺3 5⊢x   → 4.22E¯4 |      0%
{⊢⊢⍵}⌺3 5⊢x → 5.31E¯2 | +12477% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

cmpx '{⌽⍵}⌺3 5⊢y' '{⊢⊢⌽⍵}⌺3 5⊢y'
{⌽⍵}⌺3 5⊢y   → 2.17E¯1 |  0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
{⊢⊢⌽⍵}⌺3 5⊢y → 2.21E¯1 | +1% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
```

If the timings are the same then there is no special code.

Padding and performance improvements will take a lot of work. For example, for padding (i.e. the treatment of cells at the edge of the universe) multiple options are possible: no padding, padding, wrap from opposite edge, etc. While working on these improvements I hit upon the idea of writing a stencil function which produces the stencil cells. It only works with no padding and only for movements of 1 (which I understand are common cases), but turns out to be an interesting study.

## A Stencil Function

`⍺ stencell ⍵` produces the stencil cells of size `⍺` from `⍵` , and is equivalent to `{⍵}⌺⍺⊢⍵` after the padded cells are removed.

```stencell←{
⎕io←0                 ⍝ ⎕io delenda est!
s←(≢⍺)↑⍴⍵
f←1+s-⍺               ⍝ frame AKA outer shape
m←⊖×⍀⊖1↓s,1           ⍝ multiplier for each axis
i←⊃∘.+⌿(m,m)×⍳¨f,⍺    ⍝ indices
(⊂i) ⌷ ⍵ ⍴⍨ (×⌿(≢⍺)↑⍴⍵),(≢⍺)↓⍴⍵
}
```

For example, `stencell` is applied to `x` with cell shape `3 5` .

```   ⊢ x←6 10⍴⍳60                    ⍝ (a)
0  1  2  3  4  5  6  7  8  9
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
30 31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 48 49
50 51 52 53 54 55 56 57 58 59

c←3 5 stencell x                ⍝ (b)
⍴c
4 6 3 5

c ≡ 1 2 ↓ ¯1 ¯2 ↓ {⍵}⌺3 5 ⊢x    ⍝ (c)
1

⊢ e←⊂⍤2 ⊢c                      ⍝ (d)
┌──────────────┬──────────────┬──────────────┬──────────────┬──────────────┬──────────────┐
│ 0  1  2  3  4│ 1  2  3  4  5│ 2  3  4  5  6│ 3  4  5  6  7│ 4  5  6  7  8│ 5  6  7  8  9│
│10 11 12 13 14│11 12 13 14 15│12 13 14 15 16│13 14 15 16 17│14 15 16 17 18│15 16 17 18 19│
│20 21 22 23 24│21 22 23 24 25│22 23 24 25 26│23 24 25 26 27│24 25 26 27 28│25 26 27 28 29│
├──────────────┼──────────────┼──────────────┼──────────────┼──────────────┼──────────────┤
│10 11 12 13 14│11 12 13 14 15│12 13 14 15 16│13 14 15 16 17│14 15 16 17 18│15 16 17 18 19│
│20 21 22 23 24│21 22 23 24 25│22 23 24 25 26│23 24 25 26 27│24 25 26 27 28│25 26 27 28 29│
│30 31 32 33 34│31 32 33 34 35│32 33 34 35 36│33 34 35 36 37│34 35 36 37 38│35 36 37 38 39│
├──────────────┼──────────────┼──────────────┼──────────────┼──────────────┼──────────────┤
│20 21 22 23 24│21 22 23 24 25│22 23 24 25 26│23 24 25 26 27│24 25 26 27 28│25 26 27 28 29│
│30 31 32 33 34│31 32 33 34 35│32 33 34 35 36│33 34 35 36 37│34 35 36 37 38│35 36 37 38 39│
│40 41 42 43 44│41 42 43 44 45│42 43 44 45 46│43 44 45 46 47│44 45 46 47 48│45 46 47 48 49│
├──────────────┼──────────────┼──────────────┼──────────────┼──────────────┼──────────────┤
│30 31 32 33 34│31 32 33 34 35│32 33 34 35 36│33 34 35 36 37│34 35 36 37 38│35 36 37 38 39│
│40 41 42 43 44│41 42 43 44 45│42 43 44 45 46│43 44 45 46 47│44 45 46 47 48│45 46 47 48 49│
│50 51 52 53 54│51 52 53 54 55│52 53 54 55 56│53 54 55 56 57│54 55 56 57 58│55 56 57 58 59│
└──────────────┴──────────────┴──────────────┴──────────────┴──────────────┴──────────────┘

∪¨ ,¨ e-⍬⍴e                    ⍝ (e)
┌──┬──┬──┬──┬──┬──┐
│0 │1 │2 │3 │4 │5 │
├──┼──┼──┼──┼──┼──┤
│10│11│12│13│14│15│
├──┼──┼──┼──┼──┼──┤
│20│21│22│23│24│25│
├──┼──┼──┼──┼──┼──┤
│30│31│32│33│34│35│
└──┴──┴──┴──┴──┴──┘
```
 (a) The matrix `x` is chosen to make stencil results easier to understand. (b) `stencell` is applied to `x` with cell shape `3 5` . (c) The result of `stencell` is the same as that for `{⍵}⌺` after cells with padding are dropped. (d) Enclose the matrices in `c` (the cells) to make the display more compact and easier to understand. (e) Subsequent discussion is based on the observation that each cell is some scalar integer added to the first cell.

## Indices

The key expression in the computation is

`   ⊃∘.+⌿(m,m)×⍳¨f,⍺ `

where

`   m:  10 1; ` multiplier for each axis
`   f:  4 6; ` multiplier for each axis
`   ⍺:  3 5; ` multiplier for each axis

We discuss a more verbose but equivalent version of this expression,

`   (⊃∘.+⌿m×⍳¨f)∘.+(⊃∘.+⌿m×⍳¨⍺)`

and in particular the right half,` ⊃∘.+⌿m×⍳¨⍺` , which produces the first cell.

```   ⍳⍺               ⍝ ⍳3 5
┌───┬───┬───┬───┬───┐
│0 0│0 1│0 2│0 3│0 4│
├───┼───┼───┼───┼───┤
│1 0│1 1│1 2│1 3│1 4│
├───┼───┼───┼───┼───┤
│2 0│2 1│2 2│2 3│2 4│
└───┴───┴───┴───┴───┘
(⍴⍵)∘⊥¨⍳⍺        ⍝ 6 10∘⊥¨ ⍳3 5
0  1  2  3  4
10 11 12 13 14
20 21 22 23 24
```

Alternatively, this last result obtains by multiplying by `m` the corresponding indices for each axis, where an element of `m` is the increment for a unit in an axis. That is, `m←⊖×⍀⊖1↓s,1` where `s←(≢⍺)↑⍴⍵` is a prefix of the shape of `⍵` . The multipliers are with respect to the argument `⍵` because the indices are required to be with respect to the argument `⍵` .

```   ⍳¨⍺              ⍝ ⍳¨3 5
┌─────┬─────────┐
│0 1 2│0 1 2 3 4│
└─────┴─────────┘
m×⍳¨⍺            ⍝ 10 1×⍳¨3 5
┌───────┬─────────┐
│0 10 20│0 1 2 3 4│
└───────┴─────────┘
∘.+⌿ m×⍳¨⍺       ⍝ ∘.+⌿ 10 1×⍳¨3 5
┌──────────────┐
│ 0  1  2  3  4│
│10 11 12 13 14│
│20 21 22 23 24│
└──────────────┘
((⍴⍵)∘⊥¨⍳⍺) ≡ ⊃∘.+⌿m×⍳¨⍺
1
```

This alternative computation is more efficient because it avoids creating and working on lots of small nested vectors and because the intermediate results for `∘.+⌿` grows fast from one to the next (i.e., `O(⍟n)` iterations in the main loop).

The left half, `⊃∘.+⌿m×⍳¨f` , is similar, and computes the necessary scalar integers to be added to the result of the right half.

```   ⊃ ∘.+⌿ m×⍳¨f     ⍝ ⊃ ∘.+⌿ 10 1×⍳¨4 6
0  1  2  3  4  5
10 11 12 13 14 15
20 21 22 23 24 25
30 31 32 33 34 35
```

The shorter expression derives from the more verbose one by some simple algebra.

```(⊃∘.+⌿m×⍳¨f)∘.+(⊃∘.+⌿m×⍳¨⍺)    ⍝ verbose version
⊃∘.+⌿(m×⍳¨f),m×⍳¨⍺             ⍝ ∘.+ is associative
⊃∘.+⌿(m,m)×(⍳¨f),⍳¨⍺           ⍝ m× distributes over ,
⊃∘.+⌿(m,m)×⍳¨f,⍺               ⍝ ⍳¨ distributes over ,
```

I am actually disappointed that the shorter expression was found ☺; it would have been amusing to have a non-contrived and short expression with three uses of` ∘.+` .

## Cells

Having the indices `i` in hand, the stencil cells obtain by indexing into an appropriate reshape or ravel of the right argument `⍵` . In general, the expression is

```   (⊂i) ⌷ ⍵ ⍴⍨ (×/(≢⍺)↑⍴⍵),(≢⍺)↓⍴⍵
```

`⍺` specifies the cell shape. If `(≢⍺)=≢⍴⍵` , that is, if a length is specified for each axis of `⍵` , the expression is equivalent to `(⊂i)⌷,⍵` or `(,⍵)[i]` ; if `(≢⍺)<≢⍴⍵` , that is, if there are some trailing unstencilled axes, the expression is equivalent to `(,[⍳≢⍺]⍵)[i;…;]` (the leading `≢⍺` axes are ravelled) or `↑(,⊂⍤((≢⍴⍵)-≢⍺)⊢⍵)[i]` (as if the trailing axes were shielded from indexing). The general expression covers both cases.

Application

`stencell` makes it possible to workaround current shortcomings in `⌺` . The alternative approach is to use `stencell` to get all the stencil cells, all at once, and then work on the cells using `⍤` , `+.×` , and
other efficient primitives.

The following example is from Aaron Hsu. In the original problem the size of `x` is` 512 512 64` .

```   K←?64 3 3 64⍴0
x←?256 256 64⍴0

t←1 1↓¯1 ¯1↓{+/⍪K×⍤3⊢⍵}⌺3 3⊢x
⍴t
256 256 64

cmpx '1 1↓¯1 ¯1↓{+/⍪K×⍤3⊢⍵}⌺3 3⊢x'
6.76E0
```

The computation is slow because the cells are rank-3, not supported by special code. Aaron then devised a significant speed-up using a simpler left operand to create the ravels of the cells (but still no special code):

```   t ≡ (1 1↓¯1 ¯1↓{,⍵}⌺3 3⊢x)+.×⍉⍪K
1
cmpx '(1 1↓¯1 ¯1↓{,⍵}⌺3 3⊢x)+.×⍉⍪K'
1.67E0
```

Use of `stencell` would improve the performance a bit further:

```   t ≡ (,⍤3 ⊢3 3 stencell x)+.×⍉⍪K
1
cmpx '(,⍤3 ⊢3 3 stencell x)+.×⍉⍪K'
1.09E0

cmpx '3 3 stencell x'
6.10E¯2
```

The last timing shows that the `stencell` computation is 6% (`6.10e¯2÷1.09e0`) of the total time.

Materializing all the cells does take more space than if the computation is incorporated in the left operand of `⌺` , and is practicable only if the workspace sufficiently large.

```   )copy dfns wsreq

wsreq '1 1↓¯1 ¯1↓{+/⍪K×⍤3⊢⍵}⌺3 3⊢x'
110649900
wsreq '(1 1↓¯1 ¯1↓{,⍵}⌺3 3⊢x)+.×⍉⍪K'
647815900
wsreq '(,⍤3 ⊢3 3 stencell x)+.×⍉⍪K'
333462260
```

## Performance

`stencell` is competitive with `{⍵}⌺` on matrices, where it is supported by special code written in C, and is faster when there is no special code. The benchmarks are done on a larger argument to reduce the effects of padding/unpadding done in `{⍵}⌺` .

```   y2←?200 300⍴0

cmpx '3 5 stencell y2' '1 2↓¯1 ¯2↓{⍵}⌺3 5⊢y2'
3 5 stencell y      → 1.85E¯3 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
1 2↓¯1 ¯2↓{⍵}⌺3 5⊢y → 2.91E¯3 | +57% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

cmpx '3 5 stencell y' '{⍵}⌺3 5⊢y'
3 5 stencell y → 1.85E¯3 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
* {⍵}⌺3 5⊢y      → 1.04E¯3 | -45% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

y3←?200 300 64⍴0

cmpx '3 5 stencell y3' '1 2↓¯1 ¯2↓{⍵}⌺3 5⊢y3'
3 5 stencell y3      → 8.90E¯2 |    0% ⎕⎕⎕
1 2↓¯1 ¯2↓{⍵}⌺3 5⊢y3 → 7.78E¯1 | +773% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

cmpx '3 5 stencell y3' '{⍵}⌺3 5⊢y3'
3 5 stencell y3 → 9.38E¯2 |    0% ⎕⎕⎕⎕⎕⎕⎕⎕
* {⍵}⌺3 5⊢y3      → 3.34E¯1 | +256% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
```

There is an interesting question of whether the shorter version of the key computation (in the Indices section above) is faster than the more verbose version.

```   m←10 1 ⋄ f←4 6 ⋄ a←3 5

cmpx '⊃∘.+⌿(m,m)×⍳¨f,a' '(⊃∘.+⌿m×⍳¨f)∘.+(⊃∘.+⌿m×⍳¨a)'
⊃∘.+⌿(m,m)×⍳¨f,a            → 3.75E¯6 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
(⊃∘.+⌿m×⍳¨f)∘.+(⊃∘.+⌿m×⍳¨a) → 5.20E¯6 | +38% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
```

In this case, it is faster, and I expect it will be faster for cases which arise in stencil calculations, where the argument size is larger than the cell size. But it is easy to think of arguments where `∘.+⌿` is slower than `∘.+` done with a different grouping:

```   cmpx '((⍳0)∘.+⍳100)∘.+⍳200' '(⍳0)∘.+((⍳100)∘.+⍳200)' '⊃∘.+/⍳¨0 100 200'
((⍳0)∘.+⍳100)∘.+⍳200   → 7.86E¯7 |     0% ⎕⎕
(⍳0)∘.+((⍳100)∘.+⍳200) → 1.05E¯5 | +1234% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
⊃∘.+/⍳¨0 100 200       → 1.11E¯5 | +1310% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
```

This question will be explored further in a later post.

# 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│
└───┴───┴───┴──┘
``````

 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)` ⊃ `

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

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'
┌──┬──┬──┬──┬──┬──┬──┬──┬──┐       ┌──┬──┬──┬──┐
└──┴──┴──┴──┴──┴──┴──┴──┴──┘       └──┴──┴──┴──┘
``````

`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:
 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.)

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.

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.

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`.

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 `≡⍥{{⍵[⍋⍵]}⍵~' '}`.