Trapped Knight Sequence

Question

Introduction

Inspired by the very recent video The Trapped Knight - Numberphile, I came up with a challenge.

The trapped knight sequence is a finite integer sequence of length 2016, starting from 1, and has the following construction rules:

1. Write a number spiral in the following manner:

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

2. Place a knight on 1.
3. Move the knight to the grid with the smallest number it can go that has not been visited before, according to the rules of chess (i.e. 2 units vertically and 1 unit horizontally, or vice versa).
4. Repeat until the knight gets stuck.

Here is the first three steps:

Step 1

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

Possible moves are 10, 12, 14, 16, 18, 20, 22, 24, among which the smallest is 10, so the second term is 10.

Step 2

  4  [ 3]  12  [29]  54
( 1)   2   11   28  [53] 
  8    9  <10>  27   52 
[23]  24   25   26  [51] 
 46  [47]  48  [49]  50 

Possible moves are 1, 3, 23, 29, 47, 49, 51, 53, among which the smallest is 3, so the third term is 3.

Step 3

 35  [34]  33  [32]  31 
[16]  15   14   13  [30] 
  5    4  < 3>  12   29 
[ 6] ( 1)   2   11  [28] 
  7  [ 8]   9  (10)  27 

Possible moves are 6, 8, 10, 16, 28, 30, 32, 34, among which the smallest is 6, so the fourth term is 6.

The sequence stars with:

1 10 3 6 9 4 7 2 5 8 11 14 ...

and ends with

... 2099 2284 2477 2096 2281 2474 2675 2884 3101 2880 2467 2084

Challenge

Write a shortest program or function, receiving an integer in the range [1, 2016] (or [0, 2015] if 0-indexed is used) as input, output the number at that index in the trapped knight sequence. You can choose to index the sequence with 0-indexed or 1-indexed, but you must specify which indexing scheme you use.

Test cases (1-indexed)

n    | s(n)
-----+-----
   1 |    1
   2 |   10
   3 |    3
   6 |    4
  11 |   11
  21 |   23
  51 |   95
 101 |   65
 201 |  235
 501 |  761
1001 | 1069
2001 | 1925
2016 | 2084

For all possible outputs, please refer to this page.

Winning Criteria

The shortest code of each language wins. Restrictions on standard loopholes apply.

Answer 1

JavaScript (ES7),  182  181 bytes

f=(n,[x,y]=[2,1],a=[...Array(4e3)].map((_,n)=>[1,-1].map(s=>(i&1?-s:s)*(i+s*n-(n>0?n:-n)>>1),i=n**.5|0,n-=i*++i)))=>n--?f(n,a.find(([X,Y],j)=>(i=j,(x-X)*(y-Y))**2==4),a,a[i]=[]):i+1

Try it online!

How?

A slightly modified version of my answer to the The Path Of The Wildebeest is definitely shorter (and faster) than that. But I wanted to try a different approach. Incidentally, I think it might be easier to implement this method in some esolangs.

Algorithm:

1. Initialization: we build the full list of coordinates for the first 4000 squares of the spiral, which is enough to process all moves of the knight before it gets trapped (the highest reached square being \$3199\$).

2. We look for the first square \$(X,Y)\$ such that:

   $$((x-X)\times(y-Y))^2=4$$

   where \$(x,y)\$ are the current coordinates of the knight.

   The above condition is true only if \$|x-X|=1\$ and \$|y-Y|=2\$, or \$|x-X|=2\$ and \$|y-Y|=1\$, which covers all possible knight moves.

3. We set \$(x,y)=(X,Y)\$ and invalidate the entry in the list so that it's not picked a second time.

4. We either restart at step 2 or return the last index that was found if we're done.

---

Node.js, 155 bytes

n=>(g=(x,y)=>n--?g(Buffer('QHUbcdWJ').map(m=c=>g[i=4*((x+=c%6-2)*x>(y+=c%7-2)*y?x:y)**2,i-=(x>y||-1)*(i**.5+x+y)]|i>m||(H=x,V=y,m=i))|H,V,g[m]=1):m+1)(1,2)

Try it online!

Answer 2

05AB1E, 53 bytes

Xˆ0UF2D(Ÿ0KãʒÄ1¢}εX+}Dε·nàDtyÆ+yO·<.±*->}D¯KßDˆkèU}¯θ

Exact port of my 05AB1E answer for The Path of the Wildebeest challenge, except with the 3 replaced with a 2, and a trailing θ is added to output the 0-indexed value instead of the entire sequence of the first \$n+1\$ items.

Try it online or verify some more test cases (times out for the largest test cases).

Explanation:

See the explanation in my linked The Path of the Wildebeest answer. The only modified parts are the:

2D(Ÿ    # Get a list in the range [-2,2]: [-2,-1,0,1,2]

and a trailing:

θ       # Only leave the last item of the list

---

EDIT: A port of @Arnauld's approach in his JavaScript (ES7) answer is (currently):

05AB1E, 57 56 bytes

0D‚DˆUF64D(ŸãΣ·nàDtyÆ+yO·<.±*->}©ʒX-Pn4Q}¯¡˜2£DˆU}®J¯Jk>θ

Try it online or verify some more test cases (times out for the largest test cases).

Explanation:

‚%                # Create a pair of zeros: [0,0]
                  # (by pairing the (implicit) input with itself,
                  #  and then using modulo (implicit) input)
  DˆU             # Set both variable `X` to this, and add it to the global_array
F                 # Loop the (implicit) input amount of times:
 64D(Ÿ            #  Create a list in the range [-64,64]
      ã           #  Create each possible pair of `x,y`-coordinates
       Σ·nàDtyÆ+yO·<.±*->}
                  #  Sort this list in a spiral
        ©         #  Save it in the register (without popping)
 ʒ      }         #  Filter the list of coordinates by:
  X-              #   Subtract the coordinate of variable `X`
    P             #   Take the product
     n            #   Take the square
      4Q          #   Check if its equal to 4
                  # Since 05AB1E cannot remove inner lists, we use a workaround:
         ¯¡       # Split this list on each coordinate in the global_array
           ˜      # Flatten the entire list
            2£    # Only leave the first two integers as `x,y`-coordinate
                  # (if 05AB1E could remove inner lists, this would've been `¯Kн` instead)
              DˆU # Replace variable `X` with this, and add it to the global_array
}®                # After the loop: push all coordinates sorted in a spiral from the register
  J               # Join each coordinate together to a string
   ¯J             # Push the global_array, and also join them together to a string
                  # (if 05AB1E could index inner lists, both `J` could have been removed)
     k            # Get the index of each item of the global_array in the spiral list
      >           # Increase the 0-indexed index by 1 to make it 1-based
       θ          # And only leave the last one (which is output implicitly)

The sorting part Σ·nàDtyÆ+yO·<.±*->} is copied from my other answer. This can most likely be golfed though, since we don't need the values of the spiral, but only need to sort the \$x,y\$-coordinates.

Answer 3

MATL, 41 37 bytes

62lYLt1=i:"YYw(t5Mf'<@{}'ot_h+)X<y=])

Input is 0-based.

Try it online!