Pomysł na to wyzwanie kodu jest prosty: biorąc pod uwagę macierz liczb całkowitych, posortujmy je stosując ruchy w stylu Rubika. Oznacza to, że możesz wybrać pojedynczy wiersz lub kolumnę i obrócić jej elementy w dowolnym kierunku:
[1, 3, 2, 4] => [3, 2, 4, 1] (rotate left for rows/up for columns)
[1, 3, 2, 4] => [4, 1, 3, 2] (rotate right for rows/down for columns)
Tak więc, biorąc pod uwagę macierz liczb całkowitych o dowolnym wymiarze, posortuj jej elementy stosując tylko te transformacje w stylu Rubika. Matryca
będą uważane za posortowane, jeśli jego elementy są zgodne z następującym ograniczeniem:
I / O
- Wejście będzie macierzą dodatnich liczb całkowitych bez powtarzanych wartości.
- Wyjściowe będą ruchy potrzebne do posortowania. Ponieważ nie jest to wyzwanie dla golfa kodowego i nie musisz się martwić o jego długość, proponowany format każdego ruchu to miejsce, w
#[UDLR]
którym#
znajduje się numer wiersza lub kolumny do przesunięcia (indeksowany 0) i[UDLR]
jest to pojedynczy znak zakres określający, czy ruch jest w górę / w dół (dla kolumn) czy w lewo / w prawo (dla wierszy).1U
Oznaczałoby to zatem „przesunięcie pierwszej kolumny w górę”, ale1R
oznaczałoby „przesunięcie pierwszego rzędu w prawo”. Zmiany będą rozdzielone przecinkami więc rozwiązanie będzie wyrażona w następujący sposób:1R,1U,0L,2D
.
Punktacja
Próba posortowania macierzy w ten sposób może być kosztowna, ponieważ istnieje wiele możliwych kombinacji ruchów, a także istnieje wiele możliwych list ruchów, które mogą ją posortować, więc celem jest napisanie kodu, który sortuje N * N macierzy poniżej. Wynik będzie największym rozmiarem N, który można rozwiązać w rozsądnym czasie 1 bez błędów (im większy rozmiar rozwiązanej macierzy, tym lepiej). W przypadku remisu rozstrzygającym będzie liczba ruchów na znalezionej ścieżce (im krótsza ścieżka, tym lepiej).
Przykład: jeśli użytkownik A znajdzie rozwiązanie dla N = 5, a B znajdzie rozwiązanie dla N = 6, B wygrywa niezależnie od długości obu ścieżek. Jeśli oboje znajdą rozwiązania dla N = 6, ale rozwiązanie znalezione przez A ma 50 kroków, a rozwiązanie B ma 60 kroków, A wygrywa.
Zachęcamy do wyjaśnienia, w jaki sposób działa Twój kod i opublikuj znalezione rozwiązania, abyśmy mogli je przetestować . Możesz użyć Pastebin lub podobnych narzędzi, jeśli rozwiązania są zbyt duże. Doceniony zostanie również szacunkowy czas poświęcony przez kod na znalezienie rozwiązań.
Przypadki testowe
Utworzono następujące macierze ( łącze Pastebin dla wersji bardziej wklejalnej), zaczynając od już posortowanych macierzy, mieszając je losowymi ruchami w stylu Rubika o wielkości 10K:
Plaintext Test Cases:
[[8, 5, 6], [11, 10, 1], [3, 15, 13]]
[[21, 10, 12, 16], [17, 6, 22, 14], [8, 5, 19, 26], [13, 24, 3, 1]]
[[1, 13, 8, 16, 5], [9, 40, 21, 26, 22], [11, 24, 14, 39, 28], [32, 19, 37, 3, 10], [30, 17, 36, 7, 34]]
[[34, 21, 40, 22, 35, 41], [18, 33, 31, 30, 12, 43], [19, 11, 39, 24, 28, 23], [44, 1, 36, 5, 38, 45], [14, 17, 9, 16, 13, 26], [8, 3, 47, 6, 25, 4]]
[[20, 36, 17, 1, 15, 50, 18], [72, 67, 34, 10, 32, 3, 55], [42, 43, 9, 6, 30, 61, 39], [28, 41, 54, 27, 23, 5, 70], [48, 13, 25, 12, 46, 58, 63], [52, 37, 8, 45, 33, 14, 68], [59, 65, 56, 73, 60, 64, 22]]
[[85, 56, 52, 75, 89, 44, 41, 68], [27, 15, 87, 91, 32, 37, 39, 73], [6, 7, 64, 19, 99, 78, 46, 16], [42, 21, 63, 100, 4, 1, 72, 13], [11, 97, 30, 93, 28, 40, 3, 36], [50, 70, 25, 80, 58, 9, 60, 84], [54, 96, 17, 29, 43, 34, 23, 35], [77, 61, 82, 48, 2, 94, 38, 66]]
[[56, 79, 90, 61, 71, 122, 110, 31, 55], [11, 44, 28, 4, 85, 1, 30, 6, 18], [84, 43, 38, 66, 113, 24, 96, 20, 102], [75, 68, 5, 88, 80, 98, 35, 100, 77], [13, 21, 64, 108, 10, 60, 114, 40, 23], [47, 2, 73, 106, 82, 32, 120, 26, 36], [53, 93, 69, 104, 54, 19, 111, 117, 62], [17, 27, 8, 87, 33, 49, 15, 58, 116], [95, 112, 57, 118, 91, 51, 42, 65, 45]]
Please ask for more if you solve them all. :-) And many thanks to the people who helped me refine this challenge while in the sandbox.
1 A reasonable amount of time: any amount of time that doesn't undermine our patience while testing your solution. Note that TIO only runs code for 60 seconds, any amount of time over that limit will make us test the code in our machines. Example: my rather inefficient algorithm takes a few milliseconds to solve matrices of order 3x3 and 4x4, but I have just tested it with a 5x5 matrix and it took 317 seconds to solve it (in over 5 million movements, very funny if we consider that the matrix to solve was scrambled only 10K times). I tried to reduce the number of movements to less than 10K but I surrendered after 30 minutes executing the code.
O(input size)
? W przypadku matrycy 5x5O(25)
? Wydaje się to niezwykle szybkie, więc bardzo chciałbym zobaczyć ten algorytm lub jego implementację. EDYCJA: Zdajesz sobie sprawę, że wprowadzamy matrycę „zakodowaną” i wysyłamy ruchy, prawda? Nie na odwrót.Odpowiedzi:
Nim
Wypróbuj online!
Szybka próba zaimplementowania algorytmu rozwiązania łamigłówki Torus z artykułu opublikowanego w Algorytmach 2012, 5, 18–29, o którym wspomniałem w komentarzach.
Akceptuje macierz wejściową w spłaszczonej formie, jako linię liczb rozdzielanych spacjami.
Tutaj także znajduje się walidator w Python 2 . Dane wejściowe wymagają dwóch wierszy: oryginalnej zaszyfrowanej matrycy w tej samej formie co kod główny i proponowanej sekwencji ruchów. Wyjściem walidatora jest macierz wynikająca z zastosowania tych ruchów.
Wyjaśnienie
W pierwszej części algorytmu porządkujemy wszystkie wiersze z wyjątkiem ostatniego.
Robimy to, wykonując serię „rotacji trójkątów” ([ p , q] , a następnie znajdź komórkę [ s , t ] która obecnie zawiera numer, na który należy przejść [ p , q] i ukończ właściwy trójkąt, wybierając trzeci punkt [ u , v ] zgodnie z pewnym wzorem, jak pokazano na ryc. 4 połączonego artykułu.
proc triangle
) - sekwencje ruchów, w wyniku których tylko trzy komórki zamieniają się miejscami, a cała reszta pozostaje niezmieniona. Bierzemy każdą kolejną „działającą” komórkę ze współrzędnymiNa ryc. 2 autorzy przedstawiają 8 możliwych wzorców i odpowiadające im sekwencje ruchów, ale w moim kodzie wszystkie przypadki zostały objęte jedynie 5 wzorami, więc nie. 1, 5 i 6 nie są używane.
W drugiej części ostatni rząd, z wyjątkiem dwóch ostatnich elementów, jest uporządkowany poprzez wykonanie „trzech rotacji elementów” na linii (
proc line
), która składa się z dwóch rotacji trójkątów każdy (patrz ryc. 3 artykułu).Wybieramy naszą obecną działającą komórkę[ p , q] jako lewy punkt komórka zawierająca wartość docelową [ s , t ] jako punkt centralny, oraz [ s , t + 1 ] jako właściwy punkt. Ten ruch na zachód nazywa sięT.W. w artykule, podobnie jak mój proces formowania łańcucha w tym celu. Gdybyt jest już ostatnią kolumną, więc t + 1 nie istnieje, bierzemy [ s , t - 1 ] jako trzeci punkt i odpowiednio zmodyfikuj akcję: dwa obroty trójkątów są wykonywane według wzorów 7 i 8 (zamiast 7 i 1 w oryginale T.W. sekwencja).
Wreszcie, jeślin jest dziwny, pozostałe dwa elementy muszą już być na miejscu, ponieważ gwarantujemy, że istnieje rozwiązanie. Gdybyn jest parzysty, a dwa pozostałe elementy nie są na swoim miejscu, więc zgodnie z Lematem 1 (strona 22) można je zamienić serią T.W. ruchy, a następnie jedna zmiana na wschód (= R ). Ponieważ podany przykład zamienia pierwsze dwa wpisy, a my musimy zamienić ostatnie dwa, nasze T.W. porusza się w odwrotnej kolejności.
proc swap
wykonanieW przypadku krawędzin = 2 w ogóle nie potrzebujemy tych wszystkich skomplikowanych procedur - jeśli elementy ostatniego rzędu nie są na miejscu po części 1, pojedynczym 1 R. ruch jest wystarczający, aby matryca była w pełni uporządkowana.
Aktualizacja: Dodano nowy,
proc rotations
który odwraca kierunek ruchów, jeśli spowodowałoby to mniej kroków.źródło
7L,7L,7L,7L,7D,7D,7D,7D
można zmniejszyć, a8R,8R,8R,8R,8R,8R,8R
następnie przekształcić8L,8L
w matrycę 9x9.Python 2 , rozmiar 100 w <30 sekund na TIO
Wypróbuj online! Link zawiera trzy małe przypadki testowe z pełnym wyjściem ruchu oraz plus cichy test 100 x 100, aby pokazać, że kod działa (wyjście ruchu przekroczyłoby granice TIO). Objaśnienie: Kod próbuje wykonać sortowanie wstawiania na tablicy, budując go w porządku rosnącym w miarę upływu czasu. Dla wszystkich wierszy z wyjątkiem ostatniego wiersza istnieje wiele przypadków:
Powyższe obroty są wykonywane w dowolnym kierunku, co minimalizuje liczbę kroków; kwadrat 2 zawsze rozwiązuje się za pomocą ruchów w lewo iw górę, niezależnie od powyższego opisu.
Przed zakończeniem dolnego rzędu jest on obracany, aby zminimalizować całkowitą odległość poza miejscem, ale także w celu zapewnienia, że parzystość dolnego rzędu jest równa, ponieważ nie można go zmienić w końcowej części algorytmu. Jeśli istnieje więcej niż jeden obrót przy tej samej minimalnej odległości, wybierany jest obrót z najmniejszą liczbą ruchów.
Algorytm dla dolnego rzędu opiera się na 7-operacyjnej sekwencji, która wymienia elementy w trzech kolumnach. Sekwencja jest stosowana do każdej z pozostałych liczb dolnego rzędu po kolei, aby doprowadzić je do pożądanego miejsca; jeśli to możliwe, element w tej lokalizacji jest przenoszony do pożądanej lokalizacji, ale jeśli potrzebna jest prosta zamiana, element jest po prostu przenoszony do najbliższej dostępnej kolumny, co ma nadzieję, że można go naprawić następnym razem.
źródło