A queen's walk across a spiral In a far-off kingdom, a chess queen takes a daily walk across a spiral path, numbered from 1 to n, not caring to follow the spiral itself, but simply making queen's moves as she would on a chessboard. The queen is beloved by her subjects, and they make a note of every square she visits on her path. Given that the queen can start her walk on any square and ends it on any square, what is the shortest queen's walk that she can take?

The challenge

Given a spiral of integers on a rectangular grid, write a function that returns one of the shortest possible paths (counted by number of cells travelled) between two numbers on this spiral grid using a chess queen's moves.

For example, from 16 to 25:

25 10 11 12 13
24  9  2  3 14
23  8  1  4 15
22  7  6  5 16
21 20 19 18 17


Some possible paths include 16, 4, 2, 10, 25 and 16, 5, 1, 9, 25.

Rules


The input will be any two positive integers.
The output will be a path of integers (including both endpoints) across the spiral using only orthogonal and diagonal moves.
The length of a path is counted by the number of cells travelled.
Your answer may be a program or a function.
This is code golf, so the smallest number of bytes wins.


As always, if the problem is unclear, please let me know. Good luck and good golfing!

Test cases

&gt;&gt;&gt; queen_spiral(4, 5)
4, 5
&gt;&gt;&gt; queen_spiral(13, 20)
13, 3, 1, 7, 20
&gt;&gt;&gt; queen_spiral(14, 14)
14
&gt;&gt;&gt; queen_spiral(10, 3)
10, 11, 3
&gt;&gt;&gt; queen_spiral(16, 25)
16, 4, 2, 10, 25
&gt;&gt;&gt; queen_spiral(80, 1)
80, 48, 24, 8, 1
APL (Dyalog Unicode), 59 57 bytesSBCS



{v⍳+\v[⍺],↓⍉↑(|⍴¨×)⊃⍵⍺-.⊃⊂v←9 11∘○¨+\0,0j1*{⍵/⍨⌈⍵÷2}⍳⍺⌈⍵}


Try it online!

-2 bytes thanks to @ngn.

Anonymous function that accepts two endpoints as left and right arguments.

Ungolfed &amp; how it works

The queen moves diagonally first, so it is sufficient to pre-compute the coordinates of each number up to max(start,end).

The coordinate-generating algorithm is inspired from several answers on the related challenge, but is slightly different from any of the existing answers:


Given the necessary bound of 10
Generate the 1-based range r=1 2 3 4 5 6 7 8 9 10
Take the ceiling of half of each number n=1 1 2 2 3 3 4 4 5 5
Replicate each item of r by n. 1 2 3 3 4 4 5 5 5 6 6 6 7 7 7 7 8 8 8 8 9 9 9 9 9 10 10 10 10 10
Take the cumulative sum of power of imaginary unit, with starting point of 0. (this part is common to various Python solutions to the linked challenge)


Then, once the vector of coordinates v is ready, we can easily convert between the spiral index and coordinates using v[i] and v⍳coord (finding the first index of coord in v).

⍝ Define a function; ⍺=start, ⍵=end
f←{
  ⍝ Construct a vector of spiral coordinates v
  v←9 11∘○¨+\0,0j1*{⍵/⍨⌈⍵÷2}⍳⍺⌈⍵
                             ⍺⌈⍵  ⍝ max of start, end
                            ⍳     ⍝ range of 1 to that number
                   {⍵/⍨⌈⍵÷2}  ⍝ for each number n of above, copy itself ceil(n/2) times
               0j1*  ⍝ raise imaginary unit to the power of above
           +\0,      ⍝ prepend 0 and cumulative sum
                     ⍝ (gives vector of coordinates as complex numbers)
    9 11∘○¨  ⍝ convert each complex number into (real, imag) pair
  v←         ⍝ assign it to v

  ⍝ Extract start and end coordinates
  a w←(⍺⊃v)(⍵⊃v)

  ⍝ Compute the path the Queen will take
  v⍳+\(⊂a),↓⍉↑(|⍴¨×)w-a
                    w-a  ⍝ coordinate difference (end-start)
              (|⍴¨×)     ⍝ generate abs(x) copies of signum(x) for both x- and y-coords
                         ⍝ e.g. 4 -&gt; (1 1 1 1), ¯3 -&gt; (¯1 ¯1 ¯1)
           ↓⍉↑  ⍝ promote to matrix (with 0 padding), transpose and split again
                ⍝ (gives list of steps the Queen will take)
    +\(⊂a),     ⍝ prepend the starting point and cumulative sum
                ⍝ (gives the path as coordinates)
  v⍳  ⍝ index into the spiral vector (gives the spiral numbers at those coordinates)
}