Der Pfad des Gnus

23

Golf ein Programm oder eine Funktion , die das gibt Lage des Gnus , die auf Platz beginnt auf einem unendlichen Schachbrett , das in einer gegen den Uhrzeigersinn Quadrat Spirale ist nummeriert, wo die Gnus immer Besuche mit der niedrigsten Zahl Quadrat sie kann erreichen, dass sie noch nicht besucht hat.nth 11

Inspiration: The Trapped Knight und OEIS A316667 .

Bearbeiten: Diese Sequenz befindet sich jetzt im OEIS als A323763 .

Der Code kann den nth Ort, die ersten n Orte oder die Sequenz erzeugen, die keine Eingabe nimmt.

Fühlen Sie sich frei, ihren Standort nach (oder bis zu) n Sprüngen anzugeben, aber wenn ja, geben Sie dies bitte in Ihrer Antwort deutlich an und stellen Sie sicher, dass eine Eingabe von (oder falls zutreffend) ergibt .n=01[1]

Dies ist , daher ist es das Ziel, Arbeitscode in so wenigen Bytes wie möglich in der von Ihnen gewählten Sprache zu erstellen.

Hinweis: Die Gnus gefangen werden (ähnlich wie der Ritter bei seiner tut Lage, Platz und das Kamel hat in seinem , Platz ) an ihrem location on square . Das Verhalten Ihres Codes kann für größer als dieses undefiniert sein . (Danke an Deadcode für den C ++ - Code , der dies gefunden hat!)2016th20843723rd708112899744968th12851850258n

Detail

Das Board sieht wie folgt aus und wird auf unbestimmte Zeit fortgesetzt:

101 100  99  98  97  96  95  94  93  92  91
102  65  64  63  62  61  60  59  58  57  90
103  66  37  36  35  34  33  32  31  56  89
104  67  38  17  16  15  14  13  30  55  88
105  68  39  18   5   4   3  12  29  54  87
106  69  40  19   6   1   2  11  28  53  86
107  70  41  20   7   8   9  10  27  52  85
108  71  42  21  22  23  24  25  26  51  84
109  72  43  44  45  46  47  48  49  50  83
110  73  74  75  76  77  78  79  80  81  82
111 112 113 114 115 116 117 118 119 120 121

Ein wildebeest ist eine "GNU" Fee Schachfigur - eine Nicht-Standard - Schachfigur , die sowohl als bewegen kann Ritter (a (1,2) -leaper) und als Kamel (a (1,3) -leaper).
Als solche konnte sie von ihrem Startort 1 an jeden dieser Orte ziehen :

  .   .   .   .   .   .   .   .   .   .   .
  .   .   .   .  35   .  33   .   .   .   .
  .   .   .   .  16   .  14   .   .   .   .
  .   .  39  18   .   .   .  12  29   .   .
  .   .   .   .   .  (1)  .   .   .   .   .
  .   .  41  20   .   .   .  10  27   .   .
  .   .   .   .  22   .  24   .   .   .   .
  .   .   .   .  45   .  47   .   .   .   .
  .   .   .   .   .   .   .   .   .   .   .

Die niedrigste davon ist 10 und sie hat dieses Feld noch nicht besucht, also ist 10 der zweite Term in der Sequenz.

Als nächstes könnte sie von 10 zu einem dieser Orte ziehen:

  .   .   .   .   .   .   .   .   .   .   .
  .   .   .   .   .   .  14   .  30   .   .
  .   .   .   .   .   .   3   .  29   .   .
  .   .   .   .   6   1   .   .   .  53  86
  .   .   .   .   .   .   . (10)  .   .   .
  .   .   .   .  22  23   .   .   .  51  84
  .   .   .   .   .   .  47   .  49   .   .
  .   .   .   .   .   .  78   .  80   .   .
  .   .   .   .   .   .   .   .   .   .   .

Sie hat jedoch bereits Platz 1 sodass ihr dritter Standort Platz 3 , der niedrigste, den sie noch nicht besucht hat.


Die ersten 100 Begriffe des Weges des Gnus sind:

1, 10, 3, 6, 9, 4, 7, 2, 5, 8, 11, 14, 18, 15, 12, 16, 19, 22, 41, 17, 33, 30, 34, 13, 27, 23, 20, 24, 44, 40, 21, 39, 36, 60, 31, 53, 26, 46, 25, 28, 32, 29, 51, 47, 75, 42, 45, 71, 74, 70, 38, 35, 59, 56, 86, 50, 78, 49, 52, 80, 83, 79, 115, 73, 107, 67, 64, 68, 37, 61, 93, 55, 58, 54, 84, 48, 76, 43, 69, 103, 63, 66, 62, 94, 57, 87, 125, 82, 118, 77, 113, 72, 106, 148, 65, 97, 137, 91, 129, 85

Die ersten 11 Sprünge sind Ritterzüge, sodass die ersten 12 Begriffe mit A316667 übereinstimmen .

Jonathan Allan
quelle
Kommentare sind nicht für eine längere Diskussion gedacht. Diese Unterhaltung wurde in den Chat verschoben .
Mego

Antworten:

21

JavaScript (Node.js) ,  191 ... 166  164 Bytes

2 Bytes dank @grimy gespart .

Gibt den N ten Term zurück.

n=>(g=(x,y)=>n--?g(Buffer('QPNP1O?O@242Q3C3').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! oder Eine formatierte Version anzeigen

Wie?

Spiralindizes

Um die Koordinaten (x,y) in den Spiralindex I umzuwandeln , berechnen wir zunächst die Schicht L mit:

L=max(|x|,|y|)

Welches gibt:

3210+1+2+333333333232222231321112303210123+13211123+23222223+33333333

Wir berechnen dann die Position P in der Ebene mit:

P={2L+x+yif x>y(2L+x+y)if xy

Welches gibt:

3210+1+2+330123456210123471210125803210369+143234710+254567811+36789101112

Der endgültige Index I ist gegeben durch:

I=4L2P

Anmerkung: Die obige Formel ergibt eine 0-indexierte Spirale.

Im JS-Code berechnen wir tatsächlich sofort 4L2 mit:

i = 4 * (x * x > y * y ? x : y) ** 2

Und dann subtrahiere P mit:

i -= (x > y || -1) * (i ** 0.5 + x + y)

Bewegungen des Gnus

Anhand der aktuellen Position (x,y) werden die 16 möglichen Zielquadrate des Gnus in der folgenden Reihenfolge getestet:

321x+1+2+3-3911-2810-1761213y+1541415+220+331

Wir gehen durch sie, indem wir 16 Paare von vorzeichenbehafteten Werten (dx,dy) anwenden . Jedes Paar ist als einzelnes ASCII-Zeichen codiert.

 ID | char. | ASCII code | c%6-2 | c%7-2 | cumulated
----+-------+------------+-------+-------+-----------
  0 |  'Q'  |     81     |   +1  |   +2  |  (+1,+2)
  1 |  'P'  |     80     |    0  |   +1  |  (+1,+3)
  2 |  'N'  |     78     |   -2  |   -1  |  (-1,+2)
  3 |  'P'  |     80     |    0  |   +1  |  (-1,+3)
  4 |  '1'  |     49     |   -1  |   -2  |  (-2,+1)
  5 |  'O'  |     79     |   -1  |    0  |  (-3,+1)
  6 |  '?'  |     63     |   +1  |   -2  |  (-2,-1)
  7 |  'O'  |     79     |   -1  |    0  |  (-3,-1)
  8 |  '@'  |     64     |   +2  |   -1  |  (-1,-2)
  9 |  '2'  |     50     |    0  |   -1  |  (-1,-3)
 10 |  '4'  |     52     |   +2  |   +1  |  (+1,-2)
 11 |  '2'  |     50     |    0  |   -1  |  (+1,-3)
 12 |  'Q'  |     81     |   +1  |   +2  |  (+2,-1)
 13 |  '3'  |     51     |   +1  |    0  |  (+3,-1)
 14 |  'C'  |     67     |   -1  |   +2  |  (+2,+1)
 15 |  '3'  |     51     |   +1  |    0  |  (+3,+1)

Wir verfolgen den minimal angetroffenen Wert in m und die Koordinaten der entsprechenden Zelle in (H,V) .

Sobald der beste Kandidat gefunden wurde, markieren wir ihn als besucht, indem wir ein Flag im Objekt G , das auch unsere Hauptrekursivfunktion ist.

x=1y=2(0,0)

Arnauld
quelle
3
So viel Golfspielen, ich kann es kaum erwarten, wie die Magie funktioniert!
Jonathan Allan
Mussten Sie verwenden, um Bufferzu erzwingen, dass jedes Zeichen als ein einzelnes Byte interpretiert wird?
Jonah
1
@Jonah Obwohl es veraltet ist, Bufferakzeptiert der Konstruktor immer noch eine Zeichenfolge. Also, ja, dies ist eine ziemlich billige Möglichkeit, es in eine Liste von Bytes umzuwandeln - im Gegensatz zu [..."string"].map(c=>do_something_with(c.charCodeAt())).
Arnauld
1
-2 Bytes bei der Koordinatenkodierung: TIO
Grimmy
@ Grimy Schön gemacht!
Arnauld
8

Kokosnuss , 337 276 Bytes

import math
def g((x,y))=
 A=abs(abs(x)-abs(y))+abs(x)+abs(y)
 int(A**2+math.copysign(A+x-y,.5-x-y)+1)
def f():
 p=x,y=0,0;s={p};z=[2,3,1,1]*2
 while 1:yield g(p);p=x,y=min(((a+x,b+y)for a,b in zip((1,1,2,-2,-1,-1,3,-3)*2,z+[-v for v in z])if(a+x,b+y)not in s),key=g);s.add(p)

Gibt einen Wertegenerator zurück. Könnte wahrscheinlich mehr Golf gespielt werden. (Insbesondere die Folge der Differenztupel.) Spiralalgorithmus aus dieser math.se-Antwort .

Probieren Sie es online!

Solomon Ucko
quelle
1
for a,b in (-> for a,b in((vielleicht können Sie das Delta-Tupel von Tupeln selbst auch Golf spielen)
Jonathan Allan
1
Keine Notwendigkeit qund ein Reißverschluss ist kürzer für die Tupel: 306 Bytes können natürlich noch golfen
Jonathan Allan
1
... wie wäre es damit für 284? BEARBEITEN ... dies für 278
Jonathan Allan
1
FWIW, diese math.se-Antwort hat x und y vertauscht und beide relativ zum Koordinatensystem in dieser Herausforderung negativ (wobei positives x richtig ist und y nach oben ist). Nicht, dass es aufgrund der Symmetrien einen Unterschied machen würde, aber dennoch.
Deadcode
1
0.5-> .5für ein weiteres Byte speichern; A**2-> A*Azum einen mehr.
Jonathan Allan
8

05AB1E , 77 65 58 57 52 Bytes

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

-6 Bytes dank @Arnauld mit einem Port seiner Formel.

n+1

Probieren Sie es online aus (das ïSymbol in der Fußzeile entfernt das Symbol .0, um die Ausgabe zu kompakter zu gestalten. Sie können es jedoch auch entfernen, um das tatsächliche Ergebnis zu sehen).

Code Erklärung:

Xˆ             # Put integer 1 in the global_array (global_array is empty by default)
0U             # Set variable `X` to 0 (`X` is 1 by default)
F              # Loop the (implicit) input amount of times:
 3D          #  Push the list in the range [-3,3]: [-3,-2,-1,0,1,2,3]
     0K        #  Remove the 0: [-3,-2,-1,1,2,3]
       ã       #  Cartesian product with itself, creating each possible pair: [[3,3],[3,2],[3,1],[3,-1],[3,-2],[3,-3],[2,3],[2,2],[2,1],[2,-1],[2,-2],[2,-3],[1,3],[1,2],[1,1],[1,-1],[1,-2],[1,-3],[-1,3],[-1,2],[-1,1],[-1,-1],[-1,-2],[-1,-3],[-2,3],[-2,2],[-2,1],[-2,-1],[-2,-2],[-2,-3],[-3,3],[-3,2],[-3,1],[-3,-1],[-3,-2],[-3,-3]]
        ʒ   }  #  Filter this list of pairs by:
         Ä     #   Where the absolute values of the pair
          1¢   #   Contains exactly one 1
               #  (We now have the following pairs left: [[3,1],[3,-1],[2,1],[2,-1],[1,3],[1,2],[1,-2],[1,-3],[-1,3],[-1,2],[-1,-2],[-1,-3],[-2,1],[-2,-1],[-3,1],[-3,-1]])
 εX+}          #  Add the variable `X` (previous coordinate) to each item in the list
 D             #  Duplicate this list of coordinates
  ε            #  Map each `x,y`-coordinate to:
   ·           #   Double both the `x` and `y` in the coordinate
    n          #   Then take the square of each
     à         #   And then pop and push the maximum of the two
   Dt          #   Duplicate this maximum, and take its square-root
     yÆ        #   Calculate `x-y`
       +       #   And add it to the square-root
   yO          #   Calculate `x+y`
     ·         #   Double it
      <        #   Decrease it by 1
             #   And pop and push its signum (-1 if < 0; 0 if 0; 1 if > 0)
   *           #   Multiply these two together
    -          #   And subtract it from the duplicated maximum
   >           #   And finally increase it by 1 to make it 1-based instead of 0-based
  }D           #  After the map: Duplicate that list with values
    ¯K         #  Remove all values that are already present in the global_array
      ß        #  Pop the list of (remaining) values and push the minimum
       Dˆ      #  Duplicate this minimum, and pop and add the copy to the global_array
         k     #  Then get its index in the complete list of values
          è    #  And use that index to get the corresponding coordinate
           U   #  Pop and store this coordinate in variable `X` for the next iteration
             # After the outer loop: push the global_array (which is output implicitly)

Allgemeine Erklärung:

global_array[1]
x,yX[0,0]

x,y

[[x+3,y+1], [x+3,y-1], [x+2,y+1], [x+2,y-1], [x+1,y+3], [x+1,y+2], [x+1,y-2], [x+1,y-3], [x-1,y+3], [x-1,y+2], [x-1,y-2], [x-1,y-3], [x-2,y+1], [x-2,y-1], [x-3,y+1], [x-3,y-1]]

x,yX

x,yx,y

T=meinx((2x)2,(2y)2)
R=T-(x-y+T)sichGnum((x+y)2-1)+1

Welches ist die gleiche Formel, die @Arnauld in seiner Antwort verwendet , die jedoch anders geschrieben wurde, um die eingebauten Funktionen von 05AB1E für double, square, -1, +1 usw. zu nutzen.

(Wenn Sie nur diesen spiralförmigen Teil des Codes in Aktion sehen möchten: Probieren Sie es online aus .)

Nachdem wir alle Werte erreicht haben, die wir für die gegebene erreichen können x,y-Koordinate entfernen wir alle Werte, die bereits in der vorhanden sind global_array, und erhalten dann das Minimum der (verbleibenden) Werte.
Dieses Minimum wird dann zum hinzugefügt global_array, und die Variable Xwird durch das ersetztx,y-Koordinate dieses Minimums.

Nachdem wir die inputAnzahl der Male wiederholt haben, gibt das Programm dies global_arrayals Ergebnis aus.

Kevin Cruijssen
quelle
1
FWIW, hier ist ein Port meiner eigenen Formel, um die Koordinaten in Spiralindizes umzuwandeln. Es ist 5 Bytes kürzer, liefert aber Floats. (Ich weiß nicht, ob dies ein Problem ist oder nicht.)
Arnauld
(Beachten Sie, dass y in deinem Code ist -y in meinem.)
Arnauld
@Arnauld Danke, das spart 5 zusätzliche Bytes. :) EDIT: Was du bereits in deinem ersten Kommentar erwähnt hast. ; p
Kevin Cruijssen