An oldtimer's APL code

oldtimer_APL_code.md

An oldtimer's APL code

What

Some pretty cool code from the 70s'-80s' that a Reddit user shared at this question.

Here's what u/snarkuzoid wrote:

5x5 Knight's Tour in APL

It puts an A in the middle, then randomly does a knight's tour, marking each cell with the next letter until it runs out of moves. Yes, it's terrible code by modern standards. For some reason we were obsessed with very short programs.

Here's the printout:

There's more to the story of the above code snippet:

Alas, I don't know of any other code fragments I might have laying around.

I only had this one because it was published as winner of the "Nice Knight" contest and I had a copy of the announcement.

Thanks again. This really made my day.

So apparently with this code the Reddit user had won a Leetcode competition of their time.

Pretty, cool, right?

Code

In modern Dyalog APL, v.18.0:

⎕IO←1 ⍝ If it's set to 0 instead, there's no 'A' character in the center and thus the code behaves incorrectly!
∇Z←EX2
  V←13+I←0×⍴A←25⍴'0'
  Z← 5 5 ⍴A,0⍴A[C←1↑V]←'ABCDEFGHIJKLMNOPQRSTUVWXY'[I←I+1]
  R←⍉(2,⍴V)⍴(⌊0.8+V÷5),1+5|¯1+V←(A='0')/⍳25
  T←(⌽2,⍴V)⍴(⌊0.8+C÷5),1+5|C-1
  →2×0≠⍴V←(?8)⌽((10⊥|⍉T-R)∊ 21 12)/V
∇

Results

Here are the results when run the above tradfn a couple times, with ⎕IO←1:

      EX2
00ELG
DMHQ0
IRAFK
NCJSP
0TOB0
      EX2
00000
0E0C0
00AF0
00D0B
0000G
      EX2
GBO00
N0FIP
CHALE
0MDQJ
0RK00
      EX2
GBK00
L0F0J
CHA0E
0MDI0
000N0

The above results are correct.

Correctness of the results

This requires ⎕IO←1 to be correct.

Try it out

According to Dyalog, tradfns should work on tryapl.org.

Alternatively, rewritten as a dfn, without any compression/code golfing, looks like this:

KNIGHTS←{
	⎕IO←1                                     ⍝ Guarantee indexes starting at 1

	t←⍵*2                                     ⍝ (t)otal # of spaces on the board
	s←⍵ ⍵⍴⍳t                                   ⍝ (s)paces on the board, numbered
	i←↑∪⍸s                                     ⍝ (i)ndexes of the board (2-dimensional)
	c←⍵-⍨⍵⊥⌈2⍴⍵÷2				  ⍝ (c)enter space # on the board

	valid←{⍵~⍨⍸21 12∊⍨10⊥|⍉i-t 2⍴⊃⍸s⍷⍨⊃⌽⍵}	⍝ Generate list of (valid) moves from a given space
	moves←{0=⍴v←valid ⍵:⍵⋄∇⍵,(?∘≢⊃⊢)v}	  ⍝ Generate the move list

	⍵ ⍵⍴((⍳≢)@(moves c))t⍴0			  ⍝ Fill the moves into a zeroed-out board
}

When made linear (simply by putting ⋄ in between each line), this works on tryapl.org "as is".

Just for fun, here it is as a one-liner, with the functions all embedded. I'm open to anyone's suggestions on how to code golf/go tacit/etc with this one.

{s←↑∪⍸i←⍵ ⍵⍴⍳t←⍵*2×⎕IO←1⋄⍵ ⍵⍴((⍳≢)@({0=⍴v←{⍵~⍨⍸21 12∊⍨10⊥|⍉s-t 2⍴⊃⍸i⍷⍨⊃⌽⍵}⍵:⍵⋄∇⍵,(?∘≢⊃⊢)v}⍵-⍨⍵⊥⌈2⍴⍵÷2))t⍴0}

Code Golf

KNIGHTS_cg←{
    s←↑∪⍸i←⍵ ⍵⍴⍳t←⍵*2×⎕IO←1
    ⍵ ⍵⍴((⍳≢)@({0=⍴v←{⍵~⍨⍸21 12∊⍨10⊥|⍉s-t 2⍴⊃⍸i⍷⍨⊃⌽⍵}⍵:⍵⋄∇⍵,(?∘≢⊃⊢)v}⍵-⍨⍵⊥⌈2⍴⍵÷2))t⍴0
}

Changes in the dfn:

• Takes a dimension for the board as the right argument to the function. For even dimensions, the starting point is the space immediately to the upper left of the board center, since the board center is not a space at all in those cases.
• Returns numbers in a number matrix instead of characters in a character matrix. This is because of the ability to specify higher dimensions.
• No longer fills in the board on each iteration. Rather, it creates the move list first, then uses that as an index replacement vector for the sequence. This is made possible by ⍸.

Here is a function to convert the output to a character vector as in the original.

{('0',⎕A)[,⍵+⎕IO]⍴⍨⍴⍵} ⍝ Note that this is index independent :)

Thanks

• To the user u/mlliarm who made this public and did a lot of the initial investigation.
• To the user u/snarkuzoid who trusted us with his code.
• To bubbler from APLjk discord server that found the IO bug.
• To Adám for trying to debug the tradfn error that appeared in tryapl.org.

@mlliarm

I have refined this quite a bit, and updated the gist with the code I've come up with.

Here is the Didactic version:

KNIGHTS_sm←{
    ⎕IO←1                                   ⍝ Guarantee indexes starting at 1

    t←⍵*2                                   ⍝ (t)otal # of spaces on the board
    s←⍵ ⍵⍴⍳t                                ⍝ (s)paces on the board, numbered
    i←↑∪⍸s                                  ⍝ (i)ndexes of the board (2-dimensional)
    c←⍵-⍨⍵⊥⌈2⍴⍵÷2                           ⍝ (c)enter space # on the board
    ⍝ Note that for boards of even dimension,
    ⍝   the "center" is actually the space to the upper left of the center,
    ⍝   since on such there is not proper center space, the center being
    ⍝   rather the shared corner of the four central spaces.

    valid←{⍵~⍨⍸21 12∊⍨10⊥|⍉i-t 2⍴⊃⍸s⍷⍨⊃⌽⍵}  ⍝ list of (valid) moves from a given space
        ⍝ ⊃⌽⍵            Get the "current" move (last in the moves list)
        ⍝ s⍷⍨            Find the space for that move by number
        ⍝ ⊃⍸             Get the index (row, column) of the space
        ⍝                   (⍸ returns it enclosed, so ⊃ is necessary)
        ⍝ t 2⍴           Spread out said index to match the length of the list of all the indices
        ⍝ |⍉i-           Get the absolute distances to each other index from this one
        ⍝ 10⊥            Put the two rows of the indices matrix together to form a vector of numbers
        ⍝                   This makes the next step much easier
        ⍝ ⍸21 12∊        Get the ones that constitute a 1-2 combination
        ⍝                   (This is the definition of a Knight's move, so
        ⍝                   this is basically saying, up until now,
        ⍝                   'Get the numbers of all the spaces
        ⍝                   a knight's move away
        ⍝                   from the last move'
        ⍝ ⍵~⍨            Narrow the list further by excluding any previous moves
        ⍝                   This prevents us from visiting spaces multiple times
        ⍝                   and therefore never ending.

        ⍝ The returned set of moves, if any, are the valid moves at this iteration

    moves←{0=⍴v←valid ⍵:⍵⋄∇⍵,(?∘≢⊃⊢)v}      ⍝ Generate the move list
        ⍝ 0=⍴v←valid ⍵:⍵ Stop the iteration and return the move list
        ⍝                   if there are no more valid moves
        ⍝                   Save the valid move list while we're at it,
        ⍝ (?∘≢⊃⊢)v       This is idiomatic for "Pick  random item from vector v"
        ⍝                   per https://aplcart.info
        ⍝ ∇⍵,            Concatenate the randomly selected valid move
        ⍝                   to the end of the moves list
        ⍝                   then recurse with the new moves list as argument

    b←((⍳≢)@(moves c))t⍴0                   ⍝ Fill the moves into a zeroed-out board
        ⍝ t⍴0               produces the zeroed board as a flat vector
        ⍝ moves c           produces the move list, starting from the center
        ⍝ ⍳≢                tacitly produces the move numbers,
        ⍝                     up to the total number of moves
        ⍝ (X@Y)Z            Places items X _at_ positions Y in Z.

    ⍵ ⍵⍴b                                   ⍝ output the board as a square
}

@steveAllen0112 amazing work, thanks a lots !