Finding legal knight moves in a chessboard in APL I wrote a function that takes as input a vector with two integers between 1 and 8 representing a position in a chessboard and that should output a vector where each cell is a similar vector of integers, with the positions that a knight in the input position could reach.

E.g. for the input 1 1, my function should output [2 3] [3 2] (I'm using the [] to represent the boxes of the cells).

This is what I wrote:

knight_moves ← {
  ⍝ Monadic function, expects a vector with 2 integers
  ⍝ Given a chessboard position, find the legal knight moves
  signs ← , ∘.,⍨(¯1 1)
  offsets ← ((⊂⌽),⊂) 2 1
  moves ← , signs ∘.× offsets
  locations ← moves + ⊂⍵
  valid ← ^/¨(1∘≤∧≤∘8) locations
  valid/locations
}


This works and gives the expected result for a series of test cases. Since I am quite new to APL, I wanted to know what could be written in a cleaner way.

This question has been followed-up here.
Initial impression

Your code is already quite good, using idiomatic APL in short clear lines that each do a single job well. Your variable names are such that you don't really need comments other than the fine description you already have at the top.

Describe your result

You might want to add a third comment describing the result structure:

  ⍝ Returns a vector of 2-element vectors


Remove unnecessary parenthesis

The vector (¯1 1) could be written as ¯1 1

Adopt a naming convension

Consider a naming convention that makes it easier for the reader to distinguish syntactic classes; mainly variables and functions, but maybe even monadic operators and dyadic operators. One such scheme that some people like is:

variables lowerCamelCase
Functions UpperCamelCase
_Monadic _Operators _UnderscoreUpperCamelCase
_Dyadic_ _Operators_ _UnderscoreUpperCamelCaseUnderscore_


Being that you seem to prefer snake_case: An equivalent such scheme could be used too:

variables lower_snake_case
Functions Upper_snake_case
_Monadic _Operators _Underscore_upper_snake_case
_Dyadic_ _Operators_ _Underscore_upper_snake_case_underscore_


Alternatively, the cases could be swapped: My father used lowercase for functions and uppercase for variables according to the German (and previous Danish) orthography that specifies lowercase verbs and uppercase nouns, and this may also look more natural with things like X f Y rather than x F y.

Interestingly, Stack Exchange's syntax colourer seems to make a distinction between uppercase and lowercase identifiers.

Consider naming complex functions

You use two non-trivial trains. Consider giving them meaningful names, which also allows you to remove their parentheses:

  Dirs ← (⊂⌽),⊂
  offsets ← Dirs 2 1


  In_range ← 1∘≤∧≤∘8
  valid ← ^/¨In_range locations


This isn't necessarily required in this case, but could be relevant with more involved code.

Improve performance by keeping arrays flat

To avoid the overhead of pointer chasing, you can implement your function using only flat arrays, and then, as a finalising step, restructure the data as required. Here is a direct translation of your code to flat-array code:

knight_moves_flat←{
⍝ Monadic function, expects a vector with 2 integers
⍝ Given a chessboard position, find the legal knight moves
⍝ Returns a 2-column table
  signs← ,[⍳2] ,⍤1 0⍤0 1⍨ (¯1 1)
  offsets ← (⌽,[1.5]⊢) 2 1
  moves ← ,[⍳2] signs (×⍤1⍤1 2) offsets
  locations ← moves (+⍤1) ⍵
  valid ← ^/(1∘≤∧≤∘8) locations
  ↓valid⌿locations
}


Compare the performance:

      ]runtime -compare knight_moves¨all knight_moves_flat¨all

  knight_moves¨all      → 7.4E¯4 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕ 
  knight_moves_flat¨all → 5.0E¯4 | -34% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕              


The price here is that the code becomes somewhat more involved and less clear.

For an alternative algorithm with even better performance, see Roger Hui's blog post 2019 APL Problem Solving Competition: Phase I Problems Sample Solutions.

Ultimate performance through lookups

If you need to call the function many (more than 100) times, you can get the ultimate performance by pre-computing all the results (by any means). This is because the input domain is rather limited. With only 64 valid arguments, you pay a 64-fold setup cost, but after that, the only costs will be looking up an argument in a list of valid arguments and then picking the corresponding result from a list of results. However, in this case, where the argument already is a proper argument for ⊃, you can simply use the argument directly to pick a result from a vector of vectors of results, thus avoiding even the lookup cost:

all ← ⍳ 8 8
results ← ↓knight_moves¨all
knight_moves_pick ← ⊃∘results


Throughput increases with almost two orders of magnitude compared to the flat edition:

      ]runtime -c knight_moves_flat¨all knight_moves_pick¨all

  knight_moves_flat¨all → 4.4E¯4 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕ 
  knight_moves_pick¨all → 5.2E¯6 | -99%                                          


Since the result-picking is almost free in comparison to actually computing each result, the setup cost is paid off after less than 100 applications, and is certainly negligible in the above comparison where each expression is run well over 10000 (1002) times. Instead, you pay though additional storage space being required:

      (⍪,⎕SIZE)⎕NL 3
knight_moves       2800
knight_moves_flat  3512
knight_moves_pick 19088


The fully expanded text representation of the function is also unreadable:

knight_moves_pick ← ⊃∘(((2 3)(3 2))((3 1)(2 4)(3 3))((2 1)(3 2)(2 5)(3 4))((2 2)(3 3)(2 6)(3 5))((2 3)(3 4)(2 7)(3 6))((2 4)(3 5)(2 8)(3 7))((2 5)(3 6)(3 8))((2 6)(3 7)))(((1 3)(3 3)(4 2))((1 4)(4 1)(3 4)(4 3))((1 1)(1 5)(3 1)(4 2)(3 5)(4 4))((1 2)(1 6)(3 2)(4 3)(3 6)(4 5))((1 3)(1 7)(3 3)(4 4)(3 7)(4 6))((1 4)(1 8)(3 4)(4 5)(3 8)(4 7))((1 5)(3 5)(4 6)(4 8))((1 6)(3 6)(4 7)))(((2 3)(1 2)(4 3)(5 2))((1 1)(2 4)(1 3)(5 1)(4 4)(5 3))((2 1)(1 2)(2 5)(1 4)(4 1)(5 2)(4 5)(5 4))((2 2)(1 3)(2 6)(1 5)(4 2)(5 3)(4 6)(5 5))((2 3)(1 4)(2 7)(1 6)(4 3)(5 4)(4 7)(5 6))((2 4)(1 5)(2 8)(1 7)(4 4)(5 5)(4 8)(5 7))((2 5)(1 6)(1 8)(4 5)(5 6)(5 8))((2 6)(1 7)(4 6)(5 7)))(((3 3)(2 2)(5 3)(6 2))((2 1)(3 4)(2 3)(6 1)(5 4)(6 3))((3 1)(2 2)(3 5)(2 4)(5 1)(6 2)(5 5)(6 4))((3 2)(2 3)(3 6)(2 5)(5 2)(6 3)(5 6)(6 5))((3 3)(2 4)(3 7)(2 6)(5 3)(6 4)(5 7)(6 6))((3 4)(2 5)(3 8)(2 7)(5 4)(6 5)(5 8)(6 7))((3 5)(2 6)(2 8)(5 5)(6 6)(6 8))((3 6)(2 7)(5 6)(6 7)))(((4 3)(3 2)(6 3)(7 2))((3 1)(4 4)(3 3)(7 1)(6 4)(7 3))((4 1)(3 2)(4 5)(3 4)(6 1)(7 2)(6 5)(7 4))((4 2)(3 3)(4 6)(3 5)(6 2)(7 3)(6 6)(7 5))((4 3)(3 4)(4 7)(3 6)(6 3)(7 4)(6 7)(7 6))((4 4)(3 5)(4 8)(3 7)(6 4)(7 5)(6 8)(7 7))((4 5)(3 6)(3 8)(6 5)(7 6)(7 8))((4 6)(3 7)(6 6)(7 7)))(((5 3)(4 2)(7 3)(8 2))((4 1)(5 4)(4 3)(8 1)(7 4)(8 3))((5 1)(4 2)(5 5)(4 4)(7 1)(8 2)(7 5)(8 4))((5 2)(4 3)(5 6)(4 5)(7 2)(8 3)(7 6)(8 5))((5 3)(4 4)(5 7)(4 6)(7 3)(8 4)(7 7)(8 6))((5 4)(4 5)(5 8)(4 7)(7 4)(8 5)(7 8)(8 7))((5 5)(4 6)(4 8)(7 5)(8 6)(8 8))((5 6)(4 7)(7 6)(8 7)))(((6 3)(5 2)(8 3))((5 1)(6 4)(5 3)(8 4))((6 1)(5 2)(6 5)(5 4)(8 1)(8 5))((6 2)(5 3)(6 6)(5 5)(8 2)(8 6))((6 3)(5 4)(6 7)(5 6)(8 3)(8 7))((6 4)(5 5)(6 8)(5 7)(8 4)(8 8))((6 5)(5 6)(5 8)(8 5))((6 6)(5 7)(8 6)))(((7 3)(6 2))((6 1)(7 4)(6 3))((7 1)(6 2)(7 5)(6 4))((7 2)(6 3)(7 6)(6 5))((7 3)(6 4)(7 7)(6 6))((7 4)(6 5)(7 8)(6 7))((7 5)(6 6)(6 8))((7 6)(6 7)))


It is interesting to note that just parsing the giant constant takes about as long as computing it.