Finding legal knight moves in a chessboard in APL

Question

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.

Answer 1

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 (100²) 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.

Answer 2

Generating possible moves

Assuming that the order of the elements in the output does not matter (e.g. (2 3)(3 2) and (3 2)(2 3) are equally valid outputs for the input 1 1), it suffices to generate some permutation of (1 2)(2 1)(¯1 2)(2 ¯1)(1 ¯2)(¯2 1)(¯1 ¯2)(¯2 ¯1).

Using the signs-and-offsets method you used, we want the equivalent of

signs ← (1 1)(1 ¯1)(¯1 1)(¯1 ¯1)
offsets ← (1 2)(2 1)

There are multiple ways to generate such arrays. Pick the one that reads the best for you (and, if you're not sure you'll understand the code later, add some comments). Remember, it is always better to write down the raw arrays than to generate them in a way you don't fully understand.

⍝ OP method: self outer product by pairing (,) on ¯1 1
signs ← , ∘.,⍨ ¯1 1
⍝ Example method 1: generate indexes then power of ¯1
signs ← , ¯1*⍳2 2
⍝ Example method 2: just write down the array
signs ← (1 1)(1 ¯1)(¯1 1)(¯1 ¯1)

⍝ OP method
offsets ← ((⊂⌽),⊂) 2 1
⍝ Example method 1
offsets ← (⌽¨,⊢) ⊂2 1
⍝ Example method 2
offsets ← (1 2)(2 1)

Of course, there are still other ways to get the moves array.

⍝ Example method 1: extend a starting array with reversals and negations
⍝ I did not do "negation of one element" because it is hard to express
moves ← (⊢,-)(⊢,⌽¨) (1 2)(¯1 2)
⍝ Or if you insist...
moves ← (⊢,-)(⊢,⌽¨)(⊢,-@1¨) ⊂1 2

⍝ Example method 2: generate all moves from ¯2 to 2 in both directions and
⍝ filter those whose sum of absolute values is 3
⍝ assuming ⎕IO←1
tmp ← ,¯3+⍳5 5
moves ← ({3=+/|⍵}¨tmp)/tmp

⍝ Example method 3: you can always do this!
moves ← (1 2)(2 1)(¯1 2)(2 ¯1)(1 ¯2)(¯2 1)(¯1 ¯2)(¯2 ¯1)

Nitpicking

• (¯1 1) at line 4 doesn't need parentheses, because array-forming a.k.a. stranding has higher precedence than function/operator evaluation in APL grammar.
• At line 8, you're using two different symbols ^ (ASCII caret) and ∧ (Unicode wedge, or mathematical AND symbol) to indicate the same function "boolean AND". While APL implementations may accept both, it is not consistent across implementations, so it is advised to always stick to one standard symbol.