Golf program lub funkcja, która daje $n^{\text{th}}$ lokalizacji gniazda gnu , który zaczyna się na placu $1$ na nieskończonej szachownicy , która jest numerowany w kierunku przeciwnym do ruchu wskazówek zegara kwadratowy spirali, gdzie gnu zawsze odwiedza najniższym numerze kwadratowy może ona dotrzeć, że nie ma jeszcze odwiedziłem.

Inspiracja: Uwięziony rycerz i OEIS A316667 .

Edycja: ta sekwencja jest teraz w OEIS jako A323763 .

Kod może wygenerować $n^{\text{th}}$ lokalizację, pierwsze $n$ lokalizacji lub wygenerować sekwencję bez wprowadzania danych.

Zamiast tego możesz podać jej lokalizację po (lub maksymalnie) $n$ skokach, ale jeśli tak, to zaznacz to wyraźnie w swojej odpowiedzi i upewnij się, że wartość $n=0$ daje 1(lub w [1]razie potrzeby).

To jest golf golfowy , więc celem jest stworzenie działającego kodu w jak najmniejszej liczbie bajtów w wybranym języku.

Uwaga: gnu zostaje uwięziony (podobnie jak rycerz robi na jego $2016^{\text{th}}$ położenia, kwadratowy $2084$ i wielbłąd ma na swoim $3723^{\text{rd}}$ , kwadratowe $7081$ ) na nią $12899744968^{\text{th}}$ lokalizacja na placu $12851850258$ . Zachowanie twojego kodu może być niezdefiniowane dla $n$ większej niż to. (Dzięki Deadcode dla kodu C ++, który to znalazł!)

Szczegół

Plansza wygląda jak poniżej i trwa w nieskończoność:

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

Gnu jest "gnu" Fairy Chess kawałek - niestandardowa figurę, który może poruszać się zarówno jako rycerza (A $(1,2)$ -leaper) oraz jako wielbłąda (A $(1,3)$ -leaper).
W związku z tym mogła przenieść się do dowolnej z tych lokalizacji z początkowej lokalizacji $1$ :

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

Najniższa z nich to $10$ a ona jeszcze nie odwiedziła tego kwadratu, więc $10$ to drugi termin w sekwencji.

Następnie mogłaby przenieść się z $10$ do dowolnej z tych lokalizacji:

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

Jednak odwiedziła już kwadrat $1$ więc jej trzecia lokalizacja to kwadrat $3$ , najniższa, której jeszcze nie odwiedziła.

---

Pierwsze $100$ warunków ścieżki gnu to:

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

Pierwsze $11$ skoków to ruchy rycerza, więc pierwsze $12$ określeń pokrywa się z A316667 .

JavaScript (Node.js) ,  191 ... 166  164 bajtów

Zaoszczędzono 2 bajty dzięki @grimy .

Zwraca $N$ ^ty termin.

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)

Wypróbuj online! lub Zobacz sformatowaną wersję

W jaki sposób?

Wskaźniki spiralne

Aby przekonwertować współrzędne $(x,y)$ na indeks spiralny $I$ , najpierw obliczamy warstwę $L$ pomocą:

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

Co daje:

$$\begin{array}{c|ccccccc} &-3&-2&-1&0&+1&+2&+3\\ \hline -3&3&3&3&3&3&3&3\\ -2&3&2&2&2&2&2&3\\ -1&3&2&1&1&1&2&3\\ 0&3&2&1&0&1&2&3\\ +1&3&2&1&1&1&2&3\\ +2&3&2&2&2&2&2&3\\ +3&3&3&3&3&3&3&3 \end{array}$$

Następnie obliczamy pozycję $P$ w warstwie za pomocą:

$$P=\begin{cases} 2L+x+y&\text{if }x>y\\ -(2L+x+y)&\text{if }x\le y \end{cases}$$

Co daje:

$$\begin{array}{c|ccccccc} &-3&-2&-1&0&+1&+2&+3\\ \hline -3&0&1&2&3&4&5&6\\ -2&-1&0&1&2&3&4&7\\ -1&-2&-1&0&1&2&5&8\\ 0&-3&-2&-1&0&3&6&9\\ +1&-4&-3&-2&-3&-4&7&10\\ +2&-5&-4&-5&-6&-7&-8&11\\ +3&-6&-7&-8&-9&-10&-11&-12 \end{array}$$

Ostateczny indeks $I$ podaje:

$$I=4L^2-P$$

NB: Powyższy wzór daje spiralę o indeksie 0.

W kodzie JS obliczamy od razu $4L^2$ pomocą:

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

A następnie odejmij $P$ pomocą:

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

Ruchy GNU

Biorąc pod uwagę bieżącą pozycję $(x,y)$ , 16 możliwych kwadratów docelowych gnu testuje się w następującej kolejności:

$$\begin{array}{c|cccccccc} &-3&-2&-1&x&+1&+2&+3\\ \hline -3&\cdot&\cdot&9&\cdot&11&\cdot&\cdot\\ -2&\cdot&\cdot&8&\cdot&10&\cdot&\cdot\\ -1&7&6&\cdot&\cdot&\cdot&12&13\\ y&\cdot&\cdot&\cdot&\bullet&\cdot&\cdot&\cdot\\ +1&5&4&\cdot&\cdot&\cdot&14&15\\ +2&\cdot&\cdot&2&\cdot&0&\cdot&\cdot\\ +3&\cdot&\cdot&3&\cdot&1&\cdot&\cdot \end{array}$$

Przechodzimy przez nie, stosując 16 par podpisanych wartości $(dx,dy)$

 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)

$m$$(H,V)$.

Po znalezieniu najlepszego kandydata oznaczamy go jako odwiedzonego, ustawiając flagę w obiekcie $g$, która jest również naszą główną funkcją rekurencyjną.

Przy pierwszej iteracji zaczynamy od $x=1$ i $y=2$. Zapewnia to, że pierwsza wybrana komórka to$(0,0)$ i że jest to pierwsza komórka oznaczona jako odwiedzona.

Kokos , 337 276 bajtów

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)

Zwraca generator wartości. Prawdopodobnie można by grać w golfa więcej. (Zwłaszcza sekwencja krotek różnicowych.) Algorytm spiralny zaczerpnięty z odpowiedzi matematycznej .

Wypróbuj online!

05AB1E, 77 65 58 57 52 bytes

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

-6 bajtów dzięki @Arnauld przy użyciu portu jego formuły.

Wysyła pierwszy $n+1$ wartości jako lista (po przecinku).

Wypróbuj online ( ïw stopce usuwa .0się, aby wydruk był bardziej zwarty, ale możesz go usunąć, aby zobaczyć rzeczywisty wynik).

Objaśnienie kodu:

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)

Ogólne wyjaśnienie:

Trzymamy wszystkie wyniki (a zatem wartości, które już napotkaliśmy) w global_array, który początkowo zaczyna się jako [1].
Trzymamy prąd$x,y$-coordinate w zmiennej X, która jest początkowo [0,0].

Lista współrzędnych, do których możemy dotrzeć w oparciu o bieżące $x,y$współrzędne to:

[[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]]

The list I mention in the code explanation above holds these values we can jump to, after which the current $x,y$ (stored in variable X) is added.

Then it will calculate the spiral values based on these $x,y$-coordinates. It does this by using the following formula for a given $x,y$-coordinate:

$${T = max((2 * x) ^ 2, (2 * y) ^ 2)}$$ $${R = T - (x - y + √T) * signum((x + y) * 2 - 1) + 1}$$

Which is the same formula @Arnauld is using in his answer, but written differently to make use of 05AB1E's builtins for double, square, -1, +1, etc.

(If you want to see just this spiral part of the code in action: Try it online.)

After we've got all the values we can reach for the given $x,y$-coordinate, we remove all values that are already present in the global_array, and we then get the minimum of the (remaining) values.
This minimum is then added to the global_array, and variable X is replaced with the $x,y$-coordinate of this minimum.

After we've looped the input amount of times, the program will output this global_array as result.