Golf program lub funkcja, która daje lokalizacji gniazda gnu , który zaczyna się na placu 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ć lokalizację, pierwsze lokalizacji lub wygenerować sekwencję bez wprowadzania danych.
Zamiast tego możesz podać jej lokalizację po (lub maksymalnie) skokach, ale jeśli tak, to zaznacz to wyraźnie w swojej odpowiedzi i upewnij się, że wartość 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 położenia, kwadratowy i wielbłąd ma na swoim , kwadratowe ) na nią lokalizacja na placu . Zachowanie twojego kodu może być niezdefiniowane dla 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 -leaper) oraz jako wielbłąda (A -leaper).
W związku z tym mogła przenieść się do dowolnej z tych lokalizacji z początkowej lokalizacji :
. . . . . . . . . . .
. . . . 35 . 33 . . . .
. . . . 16 . 14 . . . .
. . 39 18 . . . 12 29 . .
. . . . . (1) . . . . .
. . 41 20 . . . 10 27 . .
. . . . 22 . 24 . . . .
. . . . 45 . 47 . . . .
. . . . . . . . . . .
Najniższa z nich to a ona jeszcze nie odwiedziła tego kwadratu, więc to drugi termin w sekwencji.
Następnie mogłaby przenieść się z 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 więc jej trzecia lokalizacja to kwadrat , najniższa, której jeszcze nie odwiedziła.
Pierwsze 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 skoków to ruchy rycerza, więc pierwsze określeń pokrywa się z A316667 .
Odpowiedzi:
JavaScript (Node.js) ,
191 ... 166164 bajtówZaoszczędzono 2 bajty dzięki @grimy .
ZwracaN ty termin.
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ą:
Co daje:
Następnie obliczamy pozycjęP w warstwie za pomocą:
Co daje:
Ostateczny indeksI podaje:
NB: Powyższy wzór daje spiralę o indeksie 0.
W kodzie JS obliczamy od razu4L2 pomocą:
A następnie odejmijP pomocą:
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:
Przechodzimy przez nie, stosując 16 par podpisanych wartości(dx,dy)
Po znalezieniu najlepszego kandydata oznaczamy go jako odwiedzonego, ustawiając flagę w obiekciesol , która jest również naszą główną funkcją rekurencyjną.
Przy pierwszej iteracji zaczynamy odx = 1 i y= 2 . Zapewnia to, że pierwsza wybrana komórka to( 0 , 0 ) i że jest to pierwsza komórka oznaczona jako odwiedzona.
źródło
Buffer
aby wymusić interpretację każdego znaku jako pojedynczego bajtu?Buffer
konstruktor nadal akceptuje ciąg znaków. Tak, jest to raczej tani sposób na przekonwertowanie go na listę bajtów - w przeciwieństwie do[..."string"].map(c=>do_something_with(c.charCodeAt()))
.Kokos ,
337276 bajtówZwraca 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!
źródło
for a,b in (
->for a,b in(
(może sam możesz zagrać w golfa krotkę delta krotek)q
a zip jest krótszy dla krotek: 306 bajtów może nadal być oczywiście w golfa0.5
->.5
for another byte save;A**2
->A*A
for one more.05AB1E,
7765585752 bytes-6 bajtów dzięki @Arnauld przy użyciu portu jego formuły.
Wysyła pierwszyn + 1 wartości jako lista (po przecinku).
Wypróbuj online (
ï
w stopce usuwa.0
się, aby wydruk był bardziej zwarty, ale możesz go usunąć, aby zobaczyć rzeczywisty wynik).Objaśnienie kodu:
Ogólne wyjaśnienie:
Trzymamy wszystkie wyniki (a zatem wartości, które już napotkaliśmy) wx , y -coordinate w zmiennej
global_array
, który początkowo zaczyna się jako[1]
.Trzymamy prąd
X
, która jest początkowo[0,0]
.Lista współrzędnych, do których możemy dotrzeć w oparciu o bieżącex , y współrzędne to:
The list I mention in the code explanation above holds these values we can jump to, after which the currentx,y (stored in variable
X
) is added.Then it will calculate the spiral values based on thesex,y -coordinates. It does this by using the following formula for a given x,y -coordinate:
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 givenx,y -coordinate, we remove all values that are already present in the x,y -coordinate of this minimum.
global_array
, and we then get the minimum of the (remaining) values.This minimum is then added to the
global_array
, and variableX
is replaced with theAfter we've looped the
input
amount of times, the program will output thisglobal_array
as result.źródło