Piętnaście puzzle odznacza się tym, że tylko połowa możliwych stanów układu są rozwiązywalne. Jeśli przerzucisz płytki 14 i 15, nie ma możliwości przesunięcia bloków, aby zostały one odwrócone.
Twoim zadaniem jest zbudowanie programu, który akceptuje listę liczb całkowitych w wybranym przez Ciebie formacie (zawierającym dokładnie jedno wystąpienie każdej liczby od 0 do 15, gdzie 0 to puste miejsce) reprezentujące stan ułożenia płytek w siatka 4x4 i generuje pojedynczą wartość logiczną określającą, czy siatka jest rozwiązalna, czy nie.
Wygrywa najkrótszy kod do wykonania tego w dowolnym języku.
Odpowiedzi:
Galaretka , 9 bajtów
Monadyczny link akceptujący listę liczb całkowitych czytających w rzędzie głównym na przemian między lewą prawą a prawą lewą, która daje
0
rozwiązywalność, a1
jeśli nie (w celu odwrócenia tego dodania¬
po prawej stronie kodu).Wypróbuj online! (ten przykład to tablica, na której 12 musi tylko wsunąć się na miejsce)
W jaki sposób?
Podobnie do odpowiedzi Johna Dvoraka obliczamy parzystości i wykorzystujemy wężowy porządek wejściowy, aby uprościć parzystość szachownicy, chociaż zamiast sprawdzania równości parzystości sumujemy liczbę poza kolejnością z niezerowymi indeksami i sprawdzamy, czy to jest dziwny:
źródło
J, 28 znaków
Kolejność wprowadzania jest większa od rzędu, a wiersze odczytywane są naprzemiennie od lewej do prawej i od prawej do lewej w jednej ścieżce w poprzek tabeli. Zakłada, że zero należy do lewego górnego rogu.
Użycie w systemie Windows:
Wyjaśnienie:
<nul set /p=
służy do zapobiegania nowej linii na wejściu, żeecho
powoduje, że".
się nie podoba. Oczywiście Unix obsługujeecho /n
.v&.".&.stdin''
odczytuje „v pod analizą pod stdin”, co oznacza „wejście”, następnie parsuje dane wejściowe, następnie wykonuje v, następnie anuluje parsowanie (= format), a następnie cofa dane wejściowe (= wyjście) ”.1!:1]3
jest o jeden znak krótszy, ale nie ma zdefiniowanej odwrotności.C.!.2
oznacza „parzystość permutacji”. Zwraca albo1
(parzystość) albo_1
(nieparzystość). To jest,_1^inversions
_1^i.&0
oznacza „-1 do potęgi indeksu 0”.C.!.2=_1^i.&0
oznacza „czy parzystość permutacji jest równa parzystości pozycji otworu?”Działa to na płycie 4x4, ale jeśli pożądana pozycja końcowa jest większa od rzędu od lewej do prawej, to permutacja dla rozwiązanej pozycji ma nieparzystą liczbę inwersji, a zatem nieparzystą parzystość. Również parzystość jest odwracana (dla dowolnej kolejności wprowadzania), gdy żądana pozycja otworu przesuwa się z lewego górnego na prawy dolny. W obu przypadkach poprawka dotyczy jednego znaku: dodaj
-
po=
aby odwrócić oczekiwaną parzystość.Dowód poprawności:
Po każdym ruchu zero zmienia pozycję z pewną liczbą, odwracając parzystość permutacji. Zero zmienia się również między białymi i czarnymi pozycjami szachownicy, oznaczonymi nieparzystymi i parzystymi pozycjami w kolejności wprowadzania. Zatem warunek ten jest konieczny. Wystarczający jest również argument liczenia: powszechnie wiadomo, że dokładnie połowę pozycji można rozwiązać. Ten warunek odfiltrowuje dokładnie połowę możliwych pozycji.
źródło