Niedawno dostałem naprawdę dziwną nieregularną szachownicę. Jego kwadraty są wszędzie, a nawet nie są połączone. Przynajmniej nadal są ułożone na regularnej siatce. Chcę dostosować zasady gry w szachy, aby móc grać na planszy, ale na początek potrzebuję elementu, który faktycznie może znaleźć się w dowolnym miejscu na planszy, i wydaje mi się, że najlepszym rozwiązaniem jest leaper.

Leapers to wróżka szachowa uogólnienie rycerzy. Leapers zostały zdefiniowane przez dwie liczby całkowite m i n i może poruszać m kwadratów w jednym kierunku, a następnie kolejne n kwadraty albo w kierunku prostopadłym. Dla standardowego rycerza mamy (m, n) = (2, 1) . Cały ruch jest uważany za pojedynczy skok, tak że żaden z kwadratów w drodze do celu nie musi być pusty ani nawet istnieć.

Wyzwanie

Otrzymujesz „szachownicę” w postaci listy dodatnich współrzędnych całkowitych 2D, które reprezentują kwadraty wchodzące w skład planszy. Twoim zadaniem jest znalezienie skoczka, który przy wystarczającej liczbie ruchów może dosięgnąć dowolnego pola na planszy.

Spójrzmy na kilka przykładów. Standardowa szachownica wykorzystuje regularną siatkę kwadratów 8 x 8 (pamiętaj, że w tym wyzwaniu nie rozróżniamy białych i czarnych kwadratów):

########
########
########
########
########
########
########
########

Standardowy rycerz może do nich dotrzeć, więc (2, 1)byłby to prawidłowy wynik. Jednak (1, 1)na przykład nie byłby ważny, ponieważ taki kawałek może osiągnąć tylko połowę kwadratów, bez względu na to, gdzie się zaczyna. (1, 0)z drugiej strony byłby również prawidłowy wynik, ponieważ wszystkie kwadraty są połączone ortogonalnie.

Teraz, jeśli mamy nieregularną tablicę, taką jak:

#   #
 # # #
  # # #
 # #
    #

Zatem możliwe rozwiązania to (1, 1)i (3, 1). Możemy również mieć tablicę z całkowicie odłączonymi regionami, takimi jak:

#### ####
#### ####
#### ####
#### ####

Standardowy rycerz (2, 1)wciąż może dotrzeć do wszystkich pól tutaj, co w rzeczywistości jest jedynym rozwiązaniem.

I wreszcie, następująca prosta deska nie może być w pełni osiągnięta przez żadnego skaczącego:

#
 ##

Zauważ, że formatem wejściowym nie będzie reprezentacja ASCII, lecz lista współrzędnych. Na przykład drugi przykład powyżej można podać jako:

[[1, 1], [5, 1], [2, 2], [4, 2], [6, 2], [3, 3], [5, 3], [7, 3], [2, 4], [4, 4], [5, 5]]

Zasady

Możesz napisać program lub funkcję, pobierając dane wejściowe przez STDIN (lub najbliższą alternatywę), argument wiersza poleceń lub argument funkcji i wypisując wynik przez STDOUT (lub najbliższą alternatywę), wartość zwracaną funkcji lub parametr funkcji (wyjściowej).

Współrzędne wejściowe można przyjmować w dowolnym dogodnym formacie listy (lista płaska, lista par, lista liczb całkowitych zespolonych, ciąg znaków ze spójnymi separatorami itp.).

Dane wyjściowe powinny być dwiema liczbami całkowitymi m i n, które identyfikują przeciek, jeśli istnieje rozwiązanie (jako dwie oddzielne liczby całkowite, lista, ciąg znaków z nieliczbowym ogranicznikiem itp.). Jeśli nie istnieje żadne rozwiązanie, możesz wypisać dowolną spójną wartość, która nie może być prawidłowym skokiem. Obejmuje to liczbę całkowitą (0, 0)w normalnym formacie, a także wszystko, co nie jest parą liczb całkowitych nieujemnych.

Twój program musi obsłużyć dowolny przypadek testowy w ciągu minuty . Jest to nieco rozmyte ograniczenie, ale kieruj się zdrowym rozsądkiem: jeśli zajmie to 2 minuty na twoim komputerze, myślę, że możemy założyć, że może działać w ciągu 1 na cudzym, ale jeśli zajmie 20, jest to mniej prawdopodobne. Rozwiązanie każdego przypadku testowego w ciągu kilku sekund nie powinno być trudne, więc ta reguła działa tylko w celu wykluczenia naiwnej brutalnej siły.

Obowiązują standardowe zasady gry w golfa .

Przypadki testowe

Każdy przypadek testowy ma formę board => all valid leapers. Pamiętaj, że potrzebujesz tylko jednego z nich. Jeśli lista skaczących jest pusta, upewnij się, że zwrócisz coś, co nie jest prawidłowym skracającym.

Examples above:
[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [1, 8], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [2, 8], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [3, 6], [3, 7], [3, 8], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [4, 6], [4, 7], [4, 8], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], [5, 7], [5, 8], [6, 1], [6, 2], [6, 3], [6, 4], [6, 5], [6, 6], [6, 7], [6, 8], [7, 1], [7, 2], [7, 3], [7, 4], [7, 5], [7, 6], [7, 7], [7, 8], [8, 1], [8, 2], [8, 3], [8, 4], [8, 5], [8, 6], [8, 7], [8, 8]] => [[0, 1], [1, 2], [1, 4], [2, 3], [3, 4]]
[[1, 1], [5, 1], [2, 2], [4, 2], [6, 2], [3, 3], [5, 3], [7, 3], [2, 4], [4, 4], [5, 5]] => [[1, 1], [1, 3]]
[[1, 1], [2, 2], [3, 2]] => []
[[1, 1], [1, 2], [1, 3], [1, 4], [2, 1], [2, 2], [2, 3], [2, 4], [3, 1], [3, 2], [3, 3], [3, 4], [4, 1], [4, 2], [4, 3], [4, 4], [6, 1], [6, 2], [6, 3], [6, 4], [7, 1], [7, 2], [7, 3], [7, 4], [8, 1], [8, 2], [8, 3], [8, 4], [9, 1], [9, 2], [9, 3], [9, 4]] => [[1, 2]]

Square boards:
[[1, 1], [1, 2], [2, 1], [2, 2]] => [[0, 1]]
[[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]] => [[0, 1]]
[[1, 1], [1, 2], [1, 3], [1, 4], [2, 1], [2, 2], [2, 3], [2, 4], [3, 1], [3, 2], [3, 3], [3, 4], [4, 1], [4, 2], [4, 3], [4, 4]] => [[0, 1], [1, 2]]
[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5]] => [[0, 1], [1, 2]]
[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [2, 6], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [3, 6], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [4, 6], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], [6, 1], [6, 2], [6, 3], [6, 4], [6, 5], [6, 6]] => [[0, 1], [1, 2], [2, 3]]
[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [3, 6], [3, 7], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [4, 6], [4, 7], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], [5, 7], [6, 1], [6, 2], [6, 3], [6, 4], [6, 5], [6, 6], [6, 7], [7, 1], [7, 2], [7, 3], [7, 4], [7, 5], [7, 6], [7, 7]] => [[0, 1], [1, 2], [2, 3]]

Miscellaneous:
[[1, 1], [2, 1]] => [[0, 1]]
[[1, 1], [1, 2]] => [[0, 1]]
[[1, 1], [12, 35]] => [[11, 34]]
[[1, 1], [1, 2], [2, 1], [2, 2], [6, 1], [6, 2], [6, 3], [6, 4], [7, 1], [7, 2], [7, 3], [7, 4], [8, 1], [8, 2], [8, 3], [8, 4], [9, 1], [9, 2], [9, 3], [9, 4]] => []
[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [2, 6], [3, 1], [3, 2], [3, 5], [3, 6], [4, 1], [4, 2], [4, 5], [4, 6], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], [6, 1], [6, 2], [6, 3], [6, 4], [6, 5], [6, 6]] => [[0, 1], [1, 2], [1, 4]]
[[2, 2], [2, 4], [2, 6], [2, 8], [4, 2], [4, 4], [4, 6], [4, 8], [6, 2], [6, 4], [6, 6], [6, 8], [8, 2], [8, 4], [8, 6], [8, 8]] => [[0, 2], [2, 4]]

Random boards:
[[1, 5], [1, 9], [2, 6], [2, 8], [2, 10], [2, 12], [3, 5], [3, 7], [3, 9], [3, 11], [3, 13], [4, 2], [4, 4], [4, 6], [4, 8], [4, 14], [5, 1], [5, 3], [5, 5], [5, 7], [6, 2], [6, 4], [7, 1], [8, 2]] => [[1, 1], [1, 3]]
[[1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [2, 1], [2, 2], [2, 3], [2, 4], [2, 7], [3, 1], [3, 2], [3, 3], [3, 4], [3, 6], [3, 7], [4, 2], [4, 3], [4, 4], [4, 5], [4, 6], [5, 3], [5, 4], [5, 6]] => [[0, 1], [1, 2]]
[[1, 8], [2, 6], [2, 10], [3, 3], [3, 4], [3, 8], [4, 1], [4, 11], [5, 3], [5, 9], [6, 12], [8, 11], [10, 10], [11, 12], [12, 6], [12, 8], [13, 6], [13, 8], [13, 10], [13, 11], [14, 5], [14, 7], [14, 8], [14, 13], [14, 14], [15, 7], [15, 9], [15, 11], [15, 12], [16, 6], [16, 7], [16, 9], [16, 13], [16, 14], [17, 10], [17, 12], [18, 8], [18, 12], [20, 9], [21, 11], [22, 13], [23, 10], [23, 11], [23, 15], [24, 12]] => [[1, 2]]
[[1, 17], [1, 21], [3, 11], [3, 15], [3, 19], [3, 23], [5, 13], [5, 21], [7, 11], [7, 15], [7, 19], [9, 1], [9, 13], [9, 17], [11, 3], [11, 7], [11, 15], [11, 19], [13, 5], [13, 9], [13, 13], [13, 17], [13, 21], [15, 11], [15, 15], [15, 19], [17, 13], [17, 17]] => [[2, 2], [2, 6], [2, 10]]
[[1, 3], [2, 4], [2, 5], [3, 6], [4, 1], [5, 3], [5, 6], [5, 7], [6, 12], [6, 14], [6, 21], [7, 9], [7, 19], [8, 9], [8, 15], [8, 17], [8, 18], [8, 24], [9, 12], [9, 19], [10, 12], [10, 14], [10, 17], [10, 21], [11, 22], [12, 15], [12, 17], [12, 24], [13, 16], [14, 20], [14, 21], [14, 26], [15, 13], [15, 19], [16, 18], [16, 23], [17, 16], [17, 24]] => [[2, 3]]
[[1, 11], [3, 13], [4, 10], [6, 14], [8, 12], [9, 9], [9, 15], [12, 8], [13, 5], [13, 19], [13, 21], [14, 8], [15, 1], [15, 17], [16, 4], [16, 14], [16, 18], [16, 20], [17, 21], [18, 2], [18, 16], [18, 18], [19, 9], [19, 13], [19, 15], [20, 12], [21, 1], [21, 17], [22, 4], [22, 10], [23, 7]] => [[1, 3]]
[[1, 39], [6, 37], [8, 32], [10, 27], [11, 31], [11, 35], [12, 22], [16, 21], [16, 29], [16, 33], [18, 34], [21, 3], [21, 9], [21, 19], [23, 8], [23, 14], [23, 22], [23, 24], [23, 36], [24, 6], [25, 13], [25, 17], [26, 1], [26, 11], [28, 6], [28, 20], [28, 26], [28, 30], [28, 34], [30, 11], [30, 15], [30, 21], [32, 6], [33, 28], [33, 32], [35, 13], [35, 23]] => [[2, 5]]

Jako szczególny przypadek zwróć uwagę, że w przypadku tablicy składającej się tylko z jednej komórki, każdy wyciek działa, ale twój wynik musi odpowiadać faktycznemu wyciekowi, więc [0, 0]nie jest prawidłowym wyjściem.

Pyth 41 35

hfqQu@+G+VM*s_BM*F_BMTGQ]hQ)maVhQdt

Wychodzi po błędzie, jeśli nie ma prawidłowych skoków, podając pusty ciąg, jeśli STDERR jest ignorowany.

Wypróbuj tutaj lub uruchom pakiet testowy

Oszczędność 6 bajtów dzięki isaacg ! Zasadniczo po prostu wyszukuje wszystkich najmłodszych kandydatów, wybierając każdego ważnego skoczka od pierwszego kafelka do drugiego kafelka. Następnie dla każdego z nich tworzy wszystkie osiem konfiguracji [x, y]odsunięć, które może wykonać skaczący. Następnie znajduje wszystkie ruchy, zaczynając od pierwszego kafelka, który następuje po ruchu, i odrzuca te, których nie ma na wejściu. Robi to tak długo, aż wynik się nie zmieni. Jeśli ta ostateczna lista jest taka sama jak dane wejściowe, to leaper był ważny.

Standardowa szachownica zajęła najwięcej czasu podczas testów, zajęło mi to około 3 sekund na moim niezbyt imponującym komputerze.