Einführung

Inspiriert von dem jüngsten Video The Trapped Knight - Numberphile , habe ich mir eine Herausforderung ausgedacht .

Die gefangene Rittersequenz ist eine endliche ganzzahlige Sequenz der Länge 2016, beginnend mit 1, und hat die folgenden Konstruktionsregeln:

1. Schreiben Sie eine Zahlenspirale folgendermaßen:

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. Setze einen Ritter auf 1.
3. Bewegen Sie den Ritter gemäß den Schachregeln (dh 2 Einheiten vertikal und 1 Einheit horizontal oder umgekehrt) auf das Gitter mit der kleinsten Anzahl, die er zuvor noch nicht besucht hat.
4. Wiederholen, bis der Ritter stecken bleibt.

Hier sind die ersten drei Schritte:

Schritt 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 

Mögliche Züge sind 10, 12, 14, 16, 18, 20, 22, 24, wobei der kleinste 10 ist, der zweite Term also 10.

Schritt 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 

Mögliche Züge sind 1 , 3, 23, 29, 47, 49, 51, 53, wobei der kleinste 3 ist, der dritte Term also 3.

Schritt 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 

Mögliche Züge sind 6, 8, 10 , 16, 28, 30, 32, 34, von denen der kleinste 6 ist, der vierte Term also 6.

Die Sequenz spielt mit:

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

und endet mit

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

Herausforderung

Schreiben Sie ein kürzestes Programm oder eine kürzeste Funktion, indem Sie eine Ganzzahl im Bereich [1, 2016](oder [0, 2015]wenn 0-indiziert verwendet wird) als Eingabe erhalten und die Nummer an diesem Index in der Sequenz der gefangenen Ritter ausgeben. Sie können wählen, ob die Sequenz mit 0 oder 1 indiziert werden soll. Sie müssen jedoch angeben, welches Indizierungsschema Sie verwenden.

Testfälle (1-indiziert)

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

Alle möglichen Ausgaben finden Sie auf dieser Seite .

Gewinnkriterien

Der kürzeste Code jeder Sprache gewinnt. Es gelten Einschränkungen für Standardlücken.

JavaScript (ES7),  182  181 Byte

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

Probieren Sie es online aus!

Wie?

Eine leicht modifizierte Version meiner Antwort auf den Pfad des Gnus ist definitiv kürzer (und schneller). Aber ich wollte einen anderen Ansatz ausprobieren. Ich denke übrigens, es könnte einfacher sein, diese Methode in einigen Esolangs zu implementieren .

Algorithmus:

1. $3199$

2. $(X,Y)$

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

   $(x,y)$

   $|x-X|=1$$|y-Y|=2$$|x-X|=2$$|y-Y|=1$

3. $(x,y)=(X,Y)$

4. Wir starten entweder in Schritt 2 neu oder geben den zuletzt gefundenen Index zurück, wenn wir fertig sind.

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)

Probieren Sie es online aus!

05AB1E , 53 Bytes

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

32θ$n+1$

Probieren Sie es online aus oder überprüfen Sie weitere Testfälle (Zeitüberschreitung für die größten Testfälle).

Erläuterung:

Siehe die Erklärung in meiner verlinkten Antwort Der Weg des Gnus . Die einzigen modifizierten Teile sind:

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

und ein nachlaufender:

θ       # Only leave the last item of the list

EDIT: Ein Port von @Arnauld 's Ansatz in seiner JavaScript (ES7) Antwort ist (derzeit):

05AB1E , 57 56 Bytes

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

Probieren Sie es online aus oder überprüfen Sie weitere Testfälle (Zeitüberschreitung für die größten Testfälle).

Erläuterung:

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

Σ·nàDtyÆ+yO·<.±*->}$x,y$

MATL , 41 37 Bytes

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

Die Eingabe basiert auf 0.

Probieren Sie es online aus!