# Trapped Knight Sequence

## 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 ...
1. Place a knight on 1.
2. 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).
3. 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

## Winning Criteria

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

• Very closely related Commented Jan 29, 2019 at 1:23
• @Arnauld That question was inspired by mine (as indicated), only being faster to go main. Also, this sequence is finite, so some aspects in golfing may be different in that sense. Commented Jan 29, 2019 at 1:31
• The other sequence is also finite, stopping at square 12851850258
– Jo King
Commented Jan 29, 2019 at 1:35
• @JoKing Well, but because this stops quite quickly, I'd like to see answers in esolangs with smaller integer ranges (are there any esolangs implementing 16-bit integers?) Commented Jan 29, 2019 at 1:39
• Well, If this question was posted first in the sandbox, that doesn't means the dupe would be the other question? Commented Jan 29, 2019 at 14:57

# 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!

# 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.

# MATL, 41 37 bytes

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


Input is 0-based.

Try it online!