To jest Hole-3 z jesiennego turnieju APL CodeGolf . Jestem oryginalnym autorem problemu i dlatego mogę go ponownie opublikować tutaj.
Dany:
liczba zwojów (proszę podać, jeśli żaden ruch nie wynosi 0, w przeciwnym razie założymy, że nazywa się to 1) i
lista jednej lub więcej pozycji początkowych (w dowolnej formie, np. 0 lub 1 indeksowanych współrzędnych lub 64 kolejnych liczb / znaków lub A1 – H8 - stan, który), na szachownicy 8 na 8,
zwróć (w dowolnej kolejności) listę unikalnych pozycji (w tym samym formacie co dane wejściowe), w których rycerze mogą znajdować się po określonej liczbie tur.
Każdy rycerz musi się poruszać z każdą turą, ale nie musisz się martwić, że wielu rycerzy zajmuje ten sam kwadrat.
Rycerz może poruszać się tylko na pozycje oznaczone X w stosunku do swojej aktualnej pozycji, oznaczonej with:
Przykłady (współrzędne 1-indeksowane)
1
przenieść z [[1,1]]
: [[2,3],[3,2]]
2
przenosi z [[1,1]]
: [[1,1],[1,3],[1,5],[2,4],[3,1],[3,5],[4,2],[4,4],[5,1],[5,3]]
1
przenieść z [[1,1],[5,7]]
: [[2,3],[3,2],[3,6],[3,8],[4,5],[6,5],[7,6],[7,8]]
2
przenosi z [[1,1],[5,7]]
: [[1,1],[1,3],[1,5],[1,7],[2,4],[2,6],[2,8],[3,1],[3,3],[3,5],[3,7],[4,2],[4,4],[4,6],[4,8],[5,1],[5,3],[5,5],[5,7],[6,4],[6,6],[6,8],[7,3],[7,7],[8,4],[8,6],[8,8]]
0
przenosi z [[3,4]]
: [[3,4]]
źródło
[[1,1]], 2 -> [[2,3],[3,2]]
Odpowiedzi:
Wolfram Language (Mathematica) , 45 bajtów
Ponieważ inne rozwiązanie jest niepoprawne (patrz komentarz Martina poniżej), więc postanawiam opublikować moje rozwiązanie:
Wypróbuj online!
Ostateczna notacja infix ...
Przyjmuje 2 dane wejściowe, pierwsza to lista liczb w zasięgu
[1,64]
opisująca początkowe pozycje rycerza, druga to liczba kroków.To rozwiązanie opiera się na wyjątkowej wygody wbudowanych funkcji Mathematica:
AdjacencyList
może pobrać listę wierzchołków po prawej stronie i zwrócić listę wierzchołków sąsiadujących z dowolnymi z nich, już usunięte duplikaty i posortowane .KnightTourGraph
jest wbudowany. Nic dziwnego.Nest
porządkuje argumentyNest[f, expr, n]
, które możemy przelać na##
prawą stronę jakoNest[f, ##]
.a~b~c~d~e
jako(a~b~c)~d~e
, więc nawias kwadratowy nie jest konieczny. Bez notacji infix i spłaszczenia##
byłobyNest[AdjacencyList[KnightTourGraph[8, 8], #] &, #, #2]&
.źródło
JavaScript (ES7), 99 bajtów
Format wejściowy / wyjściowy: wskaźniki kwadratów w [0 ... 63] .
Przypadki testowe
Ten fragment zawiera dwie funkcje pomocnicze do tłumaczenia zi do formatu dostarczonego przez OP.
Pokaż fragment kodu
W jaki sposób?
Ruch z (x, y) do (X, Y) jest prawidłowym ruchem rycerza, jeśli mamy:
Kwadrat zamiast wartości bezwzględnych można wyrazić jako:
Ponieważ 1 i 4 to jedyne idealne kwadraty, które dają 5, gdy XOR razem, mamy ważny ruch rycerza, jeśli:
(xX) ² XOR (yY) ² XOR 5 = 0
Stosujemy tę formułę do każdego kwadratu p = 8y + x na planszy i każdego kwadratu rycerza P = 8Y + X, aby wydedukować nowe możliwe kwadraty docelowe rycerza i powtarzamy ten proces n razy.
źródło
Oktawa, 69 bajtów
Demo online!
Wejście / wyjście to konfiguracja płytki na początku / końcu jako binarna matryca 8 * 8.
Wyjaśnienie:
Dla
n
kroków powtórz morfologiczne rozszerzenie planszy za pomocą następującej maski:źródło
Siatkówka ,
147102 bajtówWypróbuj online! Pobiera dane jako tablica 8x8
:
s z rycerzami oznaczonymiN
s, z cyfrą liczby zwojów w następnym wierszu (nie ma sensu mieć więcej niż 9 zwojów, ale jeśli nalegasz, mogę je wesprzeć dodatkową bajt). Zauważ, że dane wyjściowe zawierają dodatkowe białe znaki. Edycja: Zapisano 45 bajtów dzięki @MartinEnder. Objaśnienie: Pierwszy etap konwertuje liczbę zwojów na jednoargumentowe, ale przy użyciu znaków tabulacji, dzięki czemu nie zostaną one przypadkowo dopasowane później, podczas gdy drugi etap dodaje pewne spacje po prawej stronie planszy, aby zapobiec zawijaniu wyrażeń regularnych krawędź. Trzeci etap zastępuje wszystkieN
S i:
S, które są ruch rycerski odN
ze związkiemn
a czwarty etap usuwa wszelkie pozostałeN
S, zmienian
s doN
s i odejmuje 1 od liczby ruchów. To się powtarza, aż liczba ruchów wyniesie zero.źródło
Galaretka , 29 bajtów
Wypróbuj online!
Współrzędne 0-indeksowane. Niemal pewne, że jest to nieoptymalne.
-1 bajt dzięki użytkownikowi 202729
Wyjaśnienie
źródło
Ç
.05AB1E ,
2725 bajtówDzięki Emigna za uratowanie 2 bajtów!
Wykorzystuje współrzędne 1-indeksowane.
Kod:
Wykorzystuje kodowanie 05AB1E . Wypróbuj online!
Wyjaśnienie:
To daje nam następującą tablicę:
Które są deltami ruchów rycerza.
źródło
•eĆ•SÍü‚
zamiastƵ‡4в2ô<D(«
zapisać 2 bajty.Python 3, 105 bajtów
Muszę użyć nazwanej lambda do rekurencji. Nie jestem pewien, czy to dyskwalifikuje. Przechodzić w pozycjach początkowych jako lista numerów kwadratowych z indeksowaniem 0 0 liczy się jako brak ruchów.
źródło
Java (OpenJDK 8) , 124 bajty
Wypróbuj online!
Format wejścia / wyjścia
Dane wejściowe / wyjściowe są reprezentowane jako bity w
long
(64 bity): ustawione bity oznaczają, że koń jest obecny, a bity nie ustawione oznaczają brak konia. Przykład:Objaśnienia
Kredyty
(X-x)²+(Y-y)²==5
sztuczkę z odpowiedzi JavaScript Arnauldaint[]
64-bitowychlong
.źródło
(m,p)->{for(;m-->0;){int i=64,a[]=p,x,y,u[]={1,3,5,9,15,19,21,23};for(p=new int[i];i-->0;)for(int z:u)if((((x=i/8+z/5-2)|(y=i%8+z%5-2))&-8)==0)p[x*8+y]|=a[i];}return p;}
(m,p)->{for(int i,j,a[],x;m-->0;)for(a=p,p=new int[i=64];i-->0;)for(j=64;j-->0;)p[j]|=(x=i%8-j%8)*x+(x=i/8-j/8)*x==5?a[i]:0;return p;}
int[]
zlong
:(m,p)->{for(long i,j,a;m-->0;)for(a=p,p=i=0;i<64;i++)for(j=64;j-->0;)p|=(p=i%8-j%8)*p+(p=i/8-j/8)*p==5?(a>>i&1)<<j:0;return p;}
Galaretka ,
2928 bajtówWypróbuj online!
Liczba zwojów przechodzi przez STDIN, a kwadraty to argument.
To wiąże rozwiązanie Jelly @ HyperNeutrino, ale z innym podejściem.Teraz bije @HyperNeutrino o 1 cały bajt!
Potrzebne są wszelkie sugestie dotyczące usunięcia niektórych bajtów!
Link 1 (szachownica)
Link 2 (Przenieś generację)
Link 3 (sprawdzanie kwadratu)
źródło
Łuska , 18 bajtów
Wykorzystuje indeksowanie kwadratów i kroków na podstawie 1. Wypróbuj online!
Wyjaśnienie
źródło
R ,
145183134 bajtówJest to wynik doskonałego grania przez Giuseppe mojego początkowego niezbyt golfowego algo (patrz komentarz poniżej)
Wypróbuj online!
Wejścia i wyjścia są oparte na 1 ... 64. Przyjmuje wektor pozycji za pomocą notacji 1 ... 64. Odwzorowuje to na notację 1: 576, czyli super-tablica złożona z dziewięciu tablic. W tej notacji, przy każdej iteracji, każdy rycerz powinien być w stanie poruszać się o +/- 22,26,47,49. Zwrócić przyszłe pozycje z powrotem w notacji 1 ... 64, z wyjątkiem tych, które spadną z planszy. Przykład TIO wyświetla wynik przy użyciu matrycy 8x8.
źródło
[0...63]
zamiast tego weźmiesz to w notacji.[1..64]
dla danych wejściowych i wyjściowych. +1, ale jest to doskonała odpowiedź.