Wprowadzenie

Zainspirowany najnowszym filmem The Trapped Knight - Numberphile , podjąłem wyzwanie.

Uwięziony sekwencja Knight jest skończoną liczbą całkowitą sekwencję o długości 2016, począwszy od dnia 1 i składa się z następujących zasad konstrukcyjnych:

1. Napisz spiralę liczbową w następujący sposób:

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. Umieść rycerza na 1.
3. Przenieś rycerza na planszę z najmniejszą możliwą liczbą, która nie była wcześniej odwiedzana, zgodnie z zasadami szachów (tj. 2 jednostki w pionie i 1 jednostka w poziomie lub odwrotnie).
4. Powtarzaj, aż rycerz utknie.

Oto trzy pierwsze kroki:

Krok 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 

Możliwe ruchy to 10, 12, 14, 16, 18, 20, 22, 24, wśród których najmniejszy to 10, więc drugi człon to 10.

Krok 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 

Możliwe ruchy to 1 , 3, 23, 29, 47, 49, 51, 53, z których najmniejszy to 3, więc trzeci semestr to 3.

Krok 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 

Możliwe ruchy to 6, 8, 10 , 16, 28, 30, 32, 34, wśród których najmniejszy to 6, więc czwarty człon to 6.

Sekwencja zawiera:

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

i kończy się na

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

Wyzwanie

Napisz najkrótszy program lub funkcję, przyjmując jako liczbę całkowitą z zakresu [1, 2016](lub [0, 2015]jeśli zastosowano indeksowanie 0), wypisz liczbę o tym indeksie w sekwencji rycerza w pułapce. Możesz wybrać indeksowanie sekwencji za pomocą indeksowania 0 lub indeksowania 1, ale musisz określić, którego schematu indeksowania używasz.

Przypadki testowe (indeksowane 1)

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

Wszystkie możliwe dane wyjściowe znajdują się na tej stronie .

Zwycięskie kryteria

Wygrywa najkrótszy kod każdego języka. Obowiązują ograniczenia dotyczące standardowych luk.

JavaScript (ES7),  182  181 bajtów

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

Wypróbuj online!

W jaki sposób?

Nieco zmodyfikowana wersja mojej odpowiedzi na The Path Of The Wildebeest jest zdecydowanie krótsza (i szybsza) niż to. Ale chciałem spróbować innego podejścia. Nawiasem mówiąc, myślę, że może być łatwiej zaimplementować tę metodę w niektórych esolangach.

Algorytm:

1. Inicjalizacja: budujemy pełną listę współrzędnych dla pierwszych 4000 kwadratów spirali, co wystarcza do przetworzenia wszystkich ruchów rycerza, zanim zostanie on uwięziony (najwyższy osiągnięty kwadrat to ).$3199$

2. Szukamy pierwszego kwadratu takiego, że:$(X,Y)$

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

   gdzie są bieżącymi współrzędnymi rycerza.$(x,y)$

   Powyższy warunek jest spełniony tylko wtedy, gdy i lub i , który obejmuje wszystkie możliwe ruchy rycerza.$|x-X|=1$$|y-Y|=2$$|x-X|=2$$|y-Y|=1$

3. Ustawiamy i unieważniamy pozycję na liście, aby nie została wybrana po raz drugi.$(x,y)=(X,Y)$

4. Albo uruchamiamy ponownie w kroku 2, albo zwracamy ostatni znaleziony indeks, jeśli skończyliśmy.

Node.js , 155 bajtów

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)

Wypróbuj online!

05AB1E , 53 bajty

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

Dokładny port mojej odpowiedzi 05AB1E dla wyzwania Ścieżka GNU , z wyjątkiem 3zastąpionego przez a 2i θdodaje się trailing w celu uzyskania wartości indeksowanej 0 zamiast całej sekwencji pierwszych elementów.$n+1$

Wypróbuj online lub zweryfikuj więcej przypadków testowych (przekroczone limity czasu dla największych przypadków testowych).

Wyjaśnienie:

Patrz wyjaśnienia w moim połączonej ścieżce Gnu odpowiedź . Jedyne zmodyfikowane części to:

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

i końcowe:

θ       # Only leave the last item of the list

EDYCJA: Port podejścia @Arnauld w jego odpowiedzi na JavaScript (ES7) to (obecnie):

05AB1E , 57 56 bajtów

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

Wypróbuj online lub zweryfikuj więcej przypadków testowych (przekroczone limity czasu dla największych przypadków testowych).

Wyjaśnienie:

‚%                # 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)

Część sortująca Σ·nàDtyÆ+yO·<.±*->}została skopiowana z mojej drugiej odpowiedzi. Można to jednak najprawdopodobniej pograć w golfa, ponieważ nie potrzebujemy wartości spirali, a jedynie musimy posortować współrzędne .$x,y$

MATL , 41 37 bajtów

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

Dane wejściowe są oparte na 0.

Wypróbuj online!