8
\$\begingroup\$

I have previously posted a challenge, smallest number of steps for a knight in chess.

Now I would like to go a step further by adding the possibility to choose your piece.

If you place a piece on any square of a chessboard, what is the smallest number of steps to reach every possible position?

Rules

  • It is an 8 by 8 board.
  • The given input is a coordinate (x, y) and the chosen piece. Explain in the answer how to input the piece of choice.
  • The piece starts at an arbitrary position, taken as input.
  • The pawn can not start at the bottom row, and can not move 2 steps (like when in the start-position) and travels only to the top of the board not downwards.
  • If a piece cannot reach a certain position, use a character of choice to indicate this.

Example

With input (1, 0) for a knight, we start by putting a 0 in that position:

. 0

From here on we continue to fill the entire 8x8 board.

For a knight the output will look as follows:

3 0 3 2 3 2 3 4
2 3 2 1 2 3 4 3
1 2 1 4 3 2 3 4
2 3 2 3 2 3 4 3
3 2 3 2 3 4 3 4
4 3 4 3 4 3 4 5
3 4 3 4 3 4 5 4
4 5 4 5 4 5 4 5

For a pawn with input (1, 7) the output will look like this:

. 6 . . . . . . 
. 5 . . . . . . 
. 4 . . . . . . 
. 3 . . . . . . 
. 2 . . . . . . 
. 1 . . . . . . 
. 0 . . . . . . 
. . . . . . . . 

In the examples, I start counting from zero but it does not matter if you start from zero or one.

Challenge

The pattern printed for a piece, as short as possible, in any reasonable format.

\$\endgroup\$
9
  • 4
    \$\begingroup\$ I think "." is a bad choice for indicating inability to reach a position, as that makes the result mixed-type, which is much harder for certain languages to deal with. I'd go for either something like -1, or incrementing all other values and using 0, or letting the answerer choose a value which cannot otherwise occur. \$\endgroup\$
    – Adám
    Aug 31 at 7:37
  • 5
    \$\begingroup\$ This feels like it's just 5 separate challenges since every piece is totally different \$\endgroup\$
    – mousetail
    Aug 31 at 7:39
  • 1
    \$\begingroup\$ @mousetail Maybe there are opportunities for sharing code between, say, rooks, bishops, queens, and kings… \$\endgroup\$
    – Adám
    Aug 31 at 7:41
  • 1
    \$\begingroup\$ @mousetail, it looks like it, but I have seen amazing stuff and clever solutions on other questions. This makes me curious how this will be solved. And every bit to spare is progress. \$\endgroup\$
    – Bjop
    Aug 31 at 7:52
  • 2
    \$\begingroup\$ Based on rule "The pawn can not start at the bottom row, and can not move 2 steps (like when in the start-position).", I assume a pawn will always only travel upwards? Might be good to explicitly mention that, so with a pawn input 1,1 the output will be a board with 0 and 1,1 and 1 at 0,1, instead of traveling down. \$\endgroup\$ Aug 31 at 9:01

3 Answers 3

11
\$\begingroup\$

JavaScript (ES7), 175 bytes

Expects (P, X, Y) where \$X\$ and \$Y\$ are 0-indexed and \$P \in\{3,4,5,6,7,10\}\$, as described in the Piece encoding paragraph below.

f=(P,X,Y,n=0,m=[...s='........'].map(_=>[...s]))=>m.map((r,y)=>r.map((V,x)=>V<=n||(h=(x-X)**2)==(v=(y-Y)**2)&P|h*v==(P&12)-4&&h+v<3|P&2&&y<Y|P-4&&f(P,x,y,n+1,m)),m[Y][X]=n)&&m

Try it online!

Or 171 bytes if we can fill the 'background' with the pattern "Infinity", which I think is pretty nice since it would indeed take an infinity of moves to reach these squares. ;-)

Try it online!

Piece encoding

Each bit in the piece code nibble encodes a specific property used by the move generator.

                    piece  |  P | as binary
                   --------+----+-----------
                    bishop |  3 |  0 0 1 1
                    pawn   |  4 |  0 1 0 0
                    king   |  5 |  0 1 0 1
                    rook   |  6 |  0 1 1 0
                    queen  |  7 |  0 1 1 1
                    knight | 10 |  1 0 1 0
                                   ^ ^ ^ ^
                                   | | | |
             moves like a knight --+ | | |
     moves along ranks and files ----+ | |
can move farther than one square ------+ |
           moves along diagonals --------+

For a pawn, the move generator applies an additional constraint which is not explicitly encoded in the bit mask: it may only move upwards.

Move generator

A move between \$(X,Y)\$ and \$(x,y)\$ is valid if the following test succeeds:

(h = (x - X) ** 2)  // h = squared difference between x and X
==                  // is it equal to ...
(v = (y - Y) ** 2)  // v = squared difference between y and Y?
                    // if yes, this is a move along a diagonal
& P                 // which is valid if bit #0 is set in P
|                   //
h * v ==            // test whether h * v is equal to:
(P & 12) - 4        //   0 if bit #2 is set (move along ranks/files)
                    //   4 if bit #3 is set (knight move)
                    //  -4 otherwise (which always fails)
                    //
&&                  // additional conditions:
  h + v < 3 | P & 2 //   either h + v is less than 3 or bit #1 is set
&&                  //
  y < Y | P - 4     //   either y is less than Y or this is not a pawn
\$\endgroup\$
6
  • \$\begingroup\$ Out of curiosity, why are the numbers of the pieces what they are? (why 3-5-6-7-12 and 19) \$\endgroup\$
    – Bjop
    Aug 31 at 15:27
  • 2
    \$\begingroup\$ @Bjop I've added a description of the (updated) piece encoding. \$\endgroup\$
    – Arnauld
    Aug 31 at 16:12
  • \$\begingroup\$ It is a very interesting approach. \$\endgroup\$
    – Bjop
    Sep 1 at 12:42
  • 1
    \$\begingroup\$ @Bjop About your edit suggestion: it looks great on my PC, but breaks the formatting on my mobile. \$\endgroup\$
    – Arnauld
    Sep 19 at 13:03
  • 1
    \$\begingroup\$ @Bjop Yes \$\endgroup\$
    – Arnauld
    Sep 19 at 13:11
7
\$\begingroup\$

APL (Dyalog APL), 133 127 108 100 91 81 80 bytes

{(⊂∘.(⍺⌷9*(××(×,,,1⍺≠+)⍥|-×+),1 0≢,)⍨8-⍳15){⍵⌊s↑⌊⌿↑,(8-⍳s)↓¨⍺+⍵}⍣≡9×⍵≢¨⍳s←8 8}∘⊂

Attempt This Online!

Update: -19 bytes (127 → 108) by compressing the move matrices
Update: -8 bytes (108 → 100) by simplifying single move function
Update: -9 bytes (100 → 91) by changing the move matrix format
Update: -10 bytes (91 → 81)

I/O

This is a function that takes as arguments

  • the starting square coordinates (Note that APL uses 1-based indexing by default and matrix indices are row number first. So the knight example in the OP has starting coordinates 1 2); and
  • an integer 1~6 for the piece choice, where they correspond to queen, rook, bishop, king, knight, and pawn respectively

The output is an 8×8 matrix, where the starting square is marked as 0 and unreachable squares are marked as 9. This is unambiguous since no piece takes more than 7 moves to reach any reachable square on an 8×8 board.

Explanation

Algorithm Overview

This challenge boils down to a shortest paths problem on an unweighted directed graph, where squares are nodes and edges connect between squares that the chosen piece can move between. It's a directed graph solely because the pawn's move is not reversible.

But, to simplify the implementation, we treat the graph as a complete weighted directed graph, where the weight of an edge is 1 if it represents a move of the chosen piece and ∞ otherwise. As noted above, since 9 is not a possible shortest path length, we can just use 9 as "effectively infinite" and treat everything ≥9 as such.

This way, we can use an iterative algorithm that is similar to Dijkstra's Algorithm, but without tracking visited/unvisited nodes and without node prioritization. Each iteration just processes all edges simultaneously.

Code Overview

The function first generates a 15×15 "move matrix" based on the piece choice that represents the weights of edges from the central square to other squares in relative positions.

┌→────────────────────────────┐
│1 9 9 9 9 9 9 1 9 9 9 9 9 9 1│ ⍝ Queen
│9 1 9 9 9 9 9 1 9 9 9 9 9 1 9│
│9 9 1 9 9 9 9 1 9 9 9 9 1 9 9│
│9 9 9 1 9 9 9 1 9 9 9 1 9 9 9│
│9 9 9 9 1 9 9 1 9 9 1 9 9 9 9│
│9 9 9 9 9 1 9 1 9 1 9 9 9 9 9│
│9 9 9 9 9 9 1 1 1 9 9 9 9 9 9│
│1 1 1 1 1 1 1 1 1 1 1 1 1 1 1│
│9 9 9 9 9 9 1 1 1 9 9 9 9 9 9│
│9 9 9 9 9 1 9 1 9 1 9 9 9 9 9│
│9 9 9 9 1 9 9 1 9 9 1 9 9 9 9│
│9 9 9 1 9 9 9 1 9 9 9 1 9 9 9│
│9 9 1 9 9 9 9 1 9 9 9 9 1 9 9│
│9 1 9 9 9 9 9 1 9 9 9 9 9 1 9│
│1 9 9 9 9 9 9 1 9 9 9 9 9 9 1│
└~────────────────────────────┘
┌→────────────────────────────┐
│9 9 9 9 9 9 9 1 9 9 9 9 9 9 9│ ⍝ Rook
│9 9 9 9 9 9 9 1 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 1 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 1 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 1 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 1 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 1 9 9 9 9 9 9 9│
│1 1 1 1 1 1 1 1 1 1 1 1 1 1 1│
│9 9 9 9 9 9 9 1 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 1 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 1 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 1 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 1 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 1 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 1 9 9 9 9 9 9 9│
└~────────────────────────────┘
┌→────────────────────────────┐
│1 9 9 9 9 9 9 9 9 9 9 9 9 9 1│ ⍝ Bishop
│9 1 9 9 9 9 9 9 9 9 9 9 9 1 9│
│9 9 1 9 9 9 9 9 9 9 9 9 1 9 9│
│9 9 9 1 9 9 9 9 9 9 9 1 9 9 9│
│9 9 9 9 1 9 9 9 9 9 1 9 9 9 9│
│9 9 9 9 9 1 9 9 9 1 9 9 9 9 9│
│9 9 9 9 9 9 1 9 1 9 9 9 9 9 9│
│9 9 9 9 9 9 9 1 9 9 9 9 9 9 9│
│9 9 9 9 9 9 1 9 1 9 9 9 9 9 9│
│9 9 9 9 9 1 9 9 9 1 9 9 9 9 9│
│9 9 9 9 1 9 9 9 9 9 1 9 9 9 9│
│9 9 9 1 9 9 9 9 9 9 9 1 9 9 9│
│9 9 1 9 9 9 9 9 9 9 9 9 1 9 9│
│9 1 9 9 9 9 9 9 9 9 9 9 9 1 9│
│1 9 9 9 9 9 9 9 9 9 9 9 9 9 1│
└~────────────────────────────┘
┌→────────────────────────────┐
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│ ⍝ King
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│
│9 9 9 9 9 9 1 1 1 9 9 9 9 9 9│
│9 9 9 9 9 9 1 9 1 9 9 9 9 9 9│
│9 9 9 9 9 9 1 1 1 9 9 9 9 9 9│
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│
└~────────────────────────────┘
┌→────────────────────────────┐
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│ ⍝ Knight
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│
│9 9 9 9 9 9 1 9 1 9 9 9 9 9 9│
│9 9 9 9 9 1 9 9 9 1 9 9 9 9 9│
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│
│9 9 9 9 9 1 9 9 9 1 9 9 9 9 9│
│9 9 9 9 9 9 1 9 1 9 9 9 9 9 9│
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│
└~────────────────────────────┘
┌→────────────────────────────┐
↓9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│ ⍝ pawn
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 1 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│
│9 9 9 9 9 9 9 9 9 9 9 9 9 9 9│
└~────────────────────────────┘

Then it creates the initial board state as an 8×8 matrix of 9s everywhere except 0 at the starting square.

Next, define a function that takes as arguments a "move matrix" and a current board state and "executes one move" by running one iteration of the shortest paths algorithm above.

With these, we can calculate the final output by looping the "single move" function until the output no longer changes (fixpoint).

{(⊂ ... ⍳15){ ... }⍣≡ 9× ... 8 8}∘⊂

{                               }    ⍝ Defines a function that
                      9× ... 8 8     ⍝   Generates the initial board state,
 (⊂ ... ⍳15)                         ⍝   Generates the the move matrix of the 
                                     ⍝     chosen piece, and
                   ⍣≡                ⍝   Returns the fixpoint of ...
            { ... }                  ⍝     the "single move" function
                                 ∘⊂  ⍝ Compose that function with a preprocessing
                                     ⍝   step of boxing its right argument

Move matrix generation

(⊂∘.(⍺⌷9*(××(×,,,1⍺≠+)⍥|-×+),1 0≢,)⍨8-⍳15)

To generate the move matrix, we first generate a 15-element array of numbers form 7 to -7 (8-⍳15). Then apply a function to each pair of these numbers ∘.(...)⍨, and return those results as a boxed () 15×15 matrix.

The inner function treats its two arguments as an (x,y) coordinate pair and returns 1 if the chosen piece can move to that square from (0,0) in a single move and 9 otherwise. It does this by generating the answer for all 6 pieces as a 6-element array, then indexing into that array using the piece choice (⍺⌷). The value for (0,0) does not matter as the "single move" function effectively ignores it.

For example, given (2,2) and piece choice 3 (bishop), the inner function generates 1 9 1 9 9 9 (because only the queen (1) and the bishop (3) can move to (2,2) from (0,0)), then chooses the 3rd element 1.

To generate the 6 answers, we define a tacit function ((××(×,,,1 5≠+)⍥|-×+),1 0≢,) that returns a boolean (i.e. 0 or 1) of whether the corresponding piece is unable to reach that square in one move, then exponentiate with 9 (9*) to get the desired result.

That tacit function, in turn, concatenates the results of 2 different tacit functions, one for the non-pawn pieces ((××(×,,,1 5≠+)⍥|-×+)), and one for the pawn (1 0≢,).

Pawn

1 0≢,

Simply returns whether (x,y) is not exactly () (1,0)

Other pieces

××(×,,,1⍺≠+)⍥|-×+

 ×                   ⍝ Calculate a = x × y
               -×+   ⍝ Calculate b = (x-y) × (x+y)
  (        )⍥|      ⍝ Apply a function with |a| and |b| as arguments
    , ,              ⍝ That function returns a 5-element array by concatenating:
   ×                 ⍝   1)   |a| × |b|              (queen)
     ,               ⍝   2,3) |a| and |b| themselves (rook and bishop)
       1 ≠+          ⍝   4)   whether |a| + |b| ≠ 1  (king)
        ⍺≠+          ⍝   5)   whether |a| + |b| ≠ 5  (knight)
×                     ⍝ Find the signum of those 5 results, because those
                      ⍝   results are 0 if the corresponding piece can move to
                      ⍝   (x,y) and positive otherwise

Notably, this takes advantage of the fact that the 5th entry only matters when the piece choice is 5.

Initial board

9×⍵≢¨⍳s←8 8

Generates an 8×8 matrix where each entry is its index/coordinate as a 2-element array (⍳8 8), then check each entry against the starting square coordinate (⍵≢¨). This results in an 8×8 boolean matrix in which each entry is 0 at the starting square and 1 everywhere else. Multiplying those by 9 () gives the initial board state.

This also stores the array 8 8 in variable s along the way, which saves one byte overall.

Single move function

{⍵⌊s↑⌊⌿↑,(8-⍳s)↓¨⍺+⍵}

The single move function takes an existing board state and a move matrix and runs one iteration of the shortest paths algorithm. That is, for each edge with weight w, source node value u it generates a "candidate value" u+w for the destination node. The value of each node is then set to the smallest among its original value and all its "candidates".

Note that although the algorithm loops through all edges, it effectively ignores all not-yet-reached source nodes and all edges that does not correspond to the chosen piece's movement, since u is 9 ("effectively infinite") in the former case and w is 9 in the latter case.


To explain the code, let's follow as a reduced example the first iteration of the single move function when choosing rook and starting square (1,2) on a 3×3 board (for 3×3 boards, move matrices are 5×5). The algorithm generalizes to any board size.

⍝ (Boxed) move matrix ⍺
┌─────────────┐
│ ┌→────────┐ │
│ ↓9 9 1 9 9│ │
│ │9 9 1 9 9│ │
│ │1 1 1 1 1│ │
│ │9 9 1 9 9│ │
│ │9 9 1 9 9│ │
│ └~────────┘ │
└∊────────────┘
⍝ Board state ⍵
┌→────┐
↓9 0 9│
│9 9 9│
│9 9 9│
└~────┘

First, we add the move matrix to the board state (⍺+⍵). Since the former is boxed, this results in adding the move matrix to every (scalar) element of board state and ends up returning a 3×3 matrix of 5×5 matrices.

⍝ {⍺+⍵}
┌→───────────────────────────────────────────────────┐
↓ ┌→─────────────┐ ┌→────────┐      ┌→─────────────┐ │
│ ↓18 18 10 18 18│ ↓9 9 1 9 9│      ↓18 18 10 18 18│ │
│ │18 18 10 18 18│ │9 9 1 9 9│      │18 18 10 18 18│ │
│ │10 10 10 10 10│ │1 1 1 1 1│      │10 10 10 10 10│ │
│ │18 18 10 18 18│ │9 9 1 9 9│      │18 18 10 18 18│ │
│ │18 18 10 18 18│ │9 9 1 9 9│      │18 18 10 18 18│ │
│ └~─────────────┘ └~────────┘      └~─────────────┘ │
│ ┌→─────────────┐ ┌→─────────────┐ ┌→─────────────┐ │
│ ↓18 18 10 18 18│ ↓18 18 10 18 18│ ↓18 18 10 18 18│ │
│ │18 18 10 18 18│ │18 18 10 18 18│ │18 18 10 18 18│ │
│ │10 10 10 10 10│ │10 10 10 10 10│ │10 10 10 10 10│ │
│ │18 18 10 18 18│ │18 18 10 18 18│ │18 18 10 18 18│ │
│ │18 18 10 18 18│ │18 18 10 18 18│ │18 18 10 18 18│ │
│ └~─────────────┘ └~─────────────┘ └~─────────────┘ │
│ ┌→─────────────┐ ┌→─────────────┐ ┌→─────────────┐ │
│ ↓18 18 10 18 18│ ↓18 18 10 18 18│ ↓18 18 10 18 18│ │
│ │18 18 10 18 18│ │18 18 10 18 18│ │18 18 10 18 18│ │
│ │10 10 10 10 10│ │10 10 10 10 10│ │10 10 10 10 10│ │
│ │18 18 10 18 18│ │18 18 10 18 18│ │18 18 10 18 18│ │
│ │18 18 10 18 18│ │18 18 10 18 18│ │18 18 10 18 18│ │
│ └~─────────────┘ └~─────────────┘ └~─────────────┘ │
└∊───────────────────────────────────────────────────┘

For instance, the 1 entry at the bottom middle of the top middle matrix corresponds to the edge from (1,2) to (3,2) (which is two squares below the source). It has value 1 because value of source node is 0 and weight of edge is 1.

However, each of those 5×5 matrices are centered at the source. We need to process the numbers by destination nodes, so we need to align them. We do so by removing elements from the left and top of each of them according to their index ((3-⍳s)↓¨), so that the top-left corner of each of the matrices correspond to the top left corner of the board. We will deal with excess stuff to the right and bottom later.

⍝ {(3-⍳s)↓¨⍺+⍵}
┌→──────────────────────────────────────────┐
↓ ┌→───────┐ ┌→─────────┐  ┌→─────────────┐ │
│ ↓10 10 10│ ↓ 2 2  2  2│  ↓10 10 10 10 10│ │
│ │10 18 18│ │10 2 10 10│  │18 18 10 18 18│ │
│ │10 18 18│ │10 2 10 10│  │18 18 10 18 18│ │
│ └~───────┘ └~─────────┘  └~─────────────┘ │
│ ┌→───────┐ ┌→──────────┐ ┌→─────────────┐ │
│ ↓10 18 18│ ↓18 10 18 18│ ↓18 18 10 18 18│ │
│ │10 10 10│ │10 10 10 10│ │10 10 10 10 10│ │
│ │10 18 18│ │18 10 18 18│ │18 18 10 18 18│ │
│ │10 18 18│ │18 10 18 18│ │18 18 10 18 18│ │
│ └~───────┘ └~──────────┘ └~─────────────┘ │
│ ┌→───────┐ ┌→──────────┐ ┌→─────────────┐ │
│ ↓10 18 18│ ↓18 10 18 18│ ↓18 18 10 18 18│ │
│ │10 18 18│ │18 10 18 18│ │18 18 10 18 18│ │
│ │10 10 10│ │10 10 10 10│ │10 10 10 10 10│ │
│ │10 18 18│ │18 10 18 18│ │18 18 10 18 18│ │
│ │10 18 18│ │18 10 18 18│ │18 18 10 18 18│ │
│ └~───────┘ └~──────────┘ └~─────────────┘ │
└∊──────────────────────────────────────────┘

Then, we promote this to a 3-dimensional array (↑,), which pads each matrix to 5×5 (the largest of them) by adding 0s to the right and bottom. The result is a 9×5×5 array.

⍝ {↑,(3-⍳s)↓¨⍺+⍵}
┌┌→─────────────┐
↓↓10 10 10  0  0│
││10 18 18  0  0│
││10 18 18  0  0│
││ 0  0  0  0  0│
││ 0  0  0  0  0│
││              │
││ 1  1  1  1  0│
││ 9  1  9  9  0│
││ 9  1  9  9  0│
││ 0  0  0  0  0│
││ 0  0  0  0  0│
││              │
││10 10 10 10 10│
││18 18 10 18 18│
││18 18 10 18 18│
││ 0  0  0  0  0│
││ 0  0  0  0  0│
││              │
││10 18 18  0  0│
││10 10 10  0  0│
││10 18 18  0  0│
││10 18 18  0  0│
││ 0  0  0  0  0│
││              │
││18 10 18 18  0│
││10 10 10 10  0│
││18 10 18 18  0│
││18 10 18 18  0│
││ 0  0  0  0  0│
││              │
││18 18 10 18 18│
││10 10 10 10 10│
││18 18 10 18 18│
││18 18 10 18 18│
││ 0  0  0  0  0│
││              │
││10 18 18  0  0│
││10 18 18  0  0│
││10 10 10  0  0│
││10 18 18  0  0│
││10 18 18  0  0│
││              │
││18 10 18 18  0│
││18 10 18 18  0│
││10 10 10 10  0│
││18 10 18 18  0│
││18 10 18 18  0│
││              │
││18 18 10 18 18│
││18 18 10 18 18│
││10 10 10 10 10│
││18 18 10 18 18│
││18 18 10 18 18│
└└~─────────────┘

Still ignoring the excess stuff for now, we now can find, for each destination node, the smallest of all 9 "candidates" (⌊⌿), as a 5×5 matrix.

⍝ {⌊⌿↑,(3-⍳s)↓¨⍺+⍵}
┌→────────┐
↓1 1 1 0 0│
│9 1 9 0 0│
│9 1 9 0 0│
│0 0 0 0 0│
│0 0 0 0 0│
└~────────┘

Now we remove the excess by only taking the first 3 rows and first 3 columns of the matrix (s↑)

⍝ {s↑⌊⌿↑,(3-⍳s)↓¨⍺+⍵}
┌→────┐
↓1 1 1│
│9 1 9│
│9 1 9│
└~────┘

Finally, we finish the iteration by finding, for each node, the smaller between it original value and the smallest "candidate" (⍵⌊)

⍝ {⍵⌊s↑⌊⌿↑,(8-⍳s)↓¨⍺+⍵}
┌→────┐
↓1 0 1│
│9 1 9│
│9 1 9│
└~────┘
\$\endgroup\$
4
\$\begingroup\$

Charcoal, 110 bytes

UO⁸ψUB.Nθ⊞υ⟦⁰NN⟧Fυ«≔⊟ιζ≔⊟ιηJζη¿¬℅KKF⁸F⁸«PIΣι≔⁺X⁻λζ²X⁻κη²ε≔⟦⁼↔⁻κη↔⁻λζ∨⁼κη⁼λζ⟧δ¿§⟦›³ε⌈δ⊟δ⊟δ⁼⁵ε∧⁼κ⊖η⁼λζ⟧θ⊞υ⟦⊕Σικλ

Try it online! Link is to verbose version of code. First input is an integer 0 King 1 Queen 2 Rook 3 Bishop 4 Knight 5 Pawn, second input is the column, third input is the row (0-indexed). Explanation:

UO⁸ψUB.

Generate nice output by marking all unreachable squares with .. UO⁸ψ only would mark all unreachable squares with spaces. ψ only would trim trailing whitespace for pawn movements (removing it completely would trim leading whitespace too, which would be unhelpful).

Nθ

Input the piece number.

⊞υ⟦⁰NN⟧

Start a breadth-first search by placing a 0 at the input coordinates.

Fυ«

Loop over the squares as they are discovered.

≔⊟ιζ≔⊟ιηJζη

Jump to the current square.

¿¬℅KK

Check that it hasn't already been visited from a different route.

F⁸F⁸«

Loop over the whole board.

PIΣι

Set the source square to the current number of steps. (This is done inside the board loop to save a byte.)

≔⁺X⁻λζ²X⁻κη²ε

Get the Euclidean distance from the source square to the current square.

≔⟦⁼↔⁻κη↔⁻λζ∨⁼κη⁼λζ⟧δ

Determine whether the source and current squares are a bishop's or a rook's move away.

¿§⟦›³ε⌈δ⊟δ⊟δ⁼⁵ε∧⁼κ⊖η⁼λζ⟧θ

Create a list of six booleans depending on whether the source and current squares are a king's, queen's, rook's, bishop's, knight's or pawn's move away, and index using the input piece number to determine whether the piece can move to the current square.

⊞υ⟦⊕Σικλ

If it can then save this as being potentially one step further away.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.