Czczony czas przejścia pedantów polega na tym, że zdjęcia „kostek Rubika” (na koszulkach, plakatach itp.) Nie są w rzeczywistości możliwe do rozwiązania.

Pierwszą rzeczą, którą należy sprawdzić, jest to, że sześcian składa się z odpowiednich elementów. Aby rozwiązać zagadkę, sześcian potrzebuje sześciu kolorów z dziewięcioma kwadratami. Kostka potrzebuje również każdej jednostki krawędzi i narożnika (są to mniejsze kostki, które składają się na kostkę), aby była unikalna. Muszą być nie tylko wyjątkowe, ale jeśli dwa środkowe elementy są naprzeciw siebie, żadna krawędź lub narożnik nie może zawierać obu tych kolorów.

Gdy masz kostkę złożoną ze wszystkich odpowiednich elementów, musisz sprawdzić, czy można ją rozwiązać. Tutaj jest kilka zasad, więc odłożę się do eksperta, aby je wyjaśnić, spoiler poniżej wyjaśnia, jak możemy to zrobić. Jeśli chcesz samodzielnie rozwiązać problem, nie musisz odwiedzać witryny, aby zrozumieć lub wziąć udział w tym wyzwaniu.

Połączone wyjaśnienie

Twoim zadaniem jest pobranie wzorca jako danych wejściowych i ustalenie, czy jest to faktycznie sześcian Rubika do rozwiązania. Aby można go było rozwiązać, musi istnieć sposób wykonywania prawidłowych ruchów na kostce, tak aby kostka miała tylko jeden kolor na każdej powierzchni (a różne ściany miały różne kolory). Większość kostek Rubika ma standardową kolorystykę (biały jest przeciwny do żółtego itp.), Możesz nie zakładać, że stan rozwiązania odpowiada tej konkretnej kolorystyce.

Prawidłowym ruchem jest obrót w prawo lub w lewo o jedną powierzchnię sześcianu. Wraz z obrotem powierzchni sześcianu obracają się również wszystkie kwadraty graniczące z twarzą, pozostając w kontakcie z twarzą, której wcześniej dotykali.

IO

Możesz wziąć kostkę w dowolny rozsądny sposób. Jeśli twój język ma wbudowany typ „sześcianu”, co jest dobre dla ciebie, to jest dobre jako dane wejściowe, w przeciwnym razie możesz wziąć tablicę 2D sieci, kostki, 1 3 na 3 listy dla każdej twarzy. Po prostu bądź rozsądny. Jeśli chcesz wiedzieć, czy określony format jest akceptowalny, wpisz komentarz lub wyślij mi ping na czacie, a dodam wyzwanie, aby określić jego ważność.

Twój format wejściowy wymaga obsługi maksymalnie 9 możliwych kolorów.

Dla danych wyjściowych jest to problem decyzyjny, dlatego powinieneś wypisać jedną stałą wartość dla „Tak, to jest poprawna kostka Rubika” i jedną inną stałą wartość dla „Nie, to nie jest poprawna kostka Rubika”.

To jest golf golfowy, więc odpowiedzi będą liczone w bajtach, przy czym mniej bajtów będzie lepszych.

Przypadki testowe

Oto przypadki testowe. Są one sformatowane jako sieć sześcianu z każdym kwadratem jako pojedynczą literą. Różne litery reprezentują różne kolory. Na życzenie można dodać więcej przypadków testowych.

Rozpuszczalny

   RRR
   RRR
   RRR
GGGWWWBBBOOO
GGGWWWBBBOOO
GGGWWWBBBOOO
   YYY
   YYY
   YYY


   GRR
   GRR
   ORW
WWRBWYBOOGGY
GGRBWGYBBOOO
OOGRWGYWWRBB
   WYO
   YYB
   YYB

Nierozstrzygalny

   RRR
   RRR
   RRR
GGGWWWBBBOOO
GGGWWWBBBOOO
GGGWYWBBBOOO
   YWY
   YYY
   YYY


   RRR
   RRR
   RRR
GGGWWWBBBOOO
GGGWWWBBBOOO
GGGWWWBBBOOO
   YWY
   YYY
   YYY


   RRR
   RRR
   GGG
GGYWYWRBBOBO
GGYWWWROBOOO
GGYWWWRBBOOO
   BBB
   YWY
   YYY


   RRW
   RRW
   GGG
GGYWWYEOBROO
GGYWWYEBBROO
GGOWWYWBBROO
   BBB
   YYW
   YYO

Sześciennie , 1664 1631 1089 bajtów

⇒FD2F'R'D2RUR'D2RFD2F'U'
⇒Ff1F'
⇒LFf1F'L'
⇒F'f1F
⇒F2f1F2
⇒L'F2f1F2L
⇒D'F'f1FD
⇒LR'FLR'DLR'B2L'RDL'RFL'RU2
⇒LFf8F'L'
⇒R'F'f8FR
⇒Ff8F'
⇒F'f8F
⇒ULU'f8UL'U'
⇒U'R'Uf8U'RU
⇒F2f8F2
⇒Df15D'
⇒D'f15D
⇒D2f15D2
⇒UF2UF2D'L2B2U'B2DL2F2D2B2D2F2
⇒U'DL2UD'B2
⇒UF2UF2D'L2B2D'R2UR2F2D2B2U2B2
⇒BL'BU2D2F'RF'U2D2
⇒LD'F2U'B2U'RU2R'F2R2F2D'R2DF2D
⇒B2URB2D2B2RB2U'D'L2D'B2
⇒B2LF'U'B2UFL'R2B2U'D2L2D'B2U
⇒B2RB2D2B2RB2U'L2UD'F2U'F2B2
⇒D2R'FUB2U'F'RU2B2D'F2R2UF2UF2
⇒B2R2U'L'D2B2U2R'U2R2F2L2R2UR2
⇒D2L'B2U2F2RUL2U'F2R2U'R2U2F2DL2D'
⇒UB2U'L2DL2B2DB2D'B2
⇒BR'BL2B'RBL2B2
⇒UF2B2U'F2B2U'F2L2R2B2R2
⇒R2U'F2DR2UF2D'R2DF2R2D'F2
⇒U'F2DF2UL2F2DL2DF2L2D2F2
⇒U2D'L2U'F2L2U'B2L2R2U'L2B2
⇒F2D'R2U2L2B2UF2L2U2F2L2UF2R2
⇒[f1]3
⇒[f2f37]3
⇒[f3f38]3
⇒[f4f39]3
⇒[f5f40]3
⇒[f6f41]3
⇒[f7f42]3
⇒[f8f43]2
⇒[f9f44]2
⇒[f10f45]2
⇒[f11f46]2
⇒[f12f47]2
⇒[f13f48]2
⇒[f14f49]2
⇒[f15f50]2
⇒[f16f51]2
⇒[f17f52]2
⇒[f18f53]2
⇒[f19f54]2
⇒[f20f55]3
⇒[f21f56]4
⇒[f22f57]5
⇒[f23f58]6
⇒[f24f59]7
⇒[f25f60]8
⇒[f26f61]9
⇒[f27f62]9[f27f62]2
⇒[f28f63]9[f28f63]3
⇒[f29f64]9[f29f64]4
⇒[f30f65]2
⇒[f31f66]3
⇒[f32f67]4
⇒[f33f68]5
⇒[f34f69]6
⇒[f35f70]7
rs[f36f71]8

Dane wyjściowe, jeśli możliwe do rozwiązania: Dane Solved!
wyjściowe, jeżeli nie można rozwiązać: (pusty, brak danych wyjściowych)

Dane wejściowe powinny być sformatowane jako sześcienny zrzut kostki (patrz Debugsekcja). Zostało to wyraźnie dozwolone przez PO.

Wyjaśnienie

Program ten wykorzystuje podejście Diabelskiego Algorytmu do iteracji w każdym możliwym stanie kostki w tej samej grupie co rozwiązany sześcian. Jeśli sześcian da się rozwiązać, zostanie on rozwiązany w pewnym momencie przed zakończeniem algorytmu (zakładając , że użyty algorytm działa poprawnie).

Każda linia rozpoczynająca się od ⇒(0x84 na stronie kodowej Cubically) jest definicją funkcji; funkcje te łączą się ze sobą, tworząc rzeczywisty algorytm diabła. Pierwszy wiersz do wykonania to ostatni:

rs[f36f71]8

rczyta kostkę ze standardowego wejścia i ustawia do niej kostkę pamięci. sustawia interpreter w trybie „solvemode”, co oznacza, że ​​kończy działanie i drukuje, Solved!jeśli kostka zostanie rozwiązana (po nierozwiązaniu) w dowolnym momencie. Reszta poleceń (które powtarzają się f36f718 razy) odpowiada ostatecznemu algorytmowi na dole połączonej strony:

(D) = (CP) = (CPT8) = [(CPC8)(CPT7)]8 (3,847,762,288,469,010,006,992 moves)

(D) is the Devil's Algorithm. If you apply it to the cube, it will be solved at some point before you have done the algorithm once. As you can see, it is terribly long, nearly a thousand times more moves than there are possible positions.

Jak mogę to uruchomić?

Możesz spróbować online , ale ten link nie działa. TIO prawie na pewno przekroczy limit czasu przed zakończeniem działania tego algorytmu (maksymalny czas działania interpretera wynosi 60 sekund). Jeśli kostki nie da się rozwiązać, algorytm ten zajmie do 11 milionów lat, aby Cubically skończył (z prędkością około 15,2 miliona ruchów na sekundę, co dostaje mój Cloud9 IDE ).

Dodatkowo potrzebujesz dużo pamięci, aby wykonać 3 sekstyliony ruchów. Cubically może wykonać około 4 milionów ruchów na sekundę, ale proces najprawdopodobniej zostanie zabity z powodu nadmiernej pamięci . Umiera po 15 sekundach na mojej maszynie wirtualnej z 512 MB pamięci. Dlaczego wykonywanie ruchów w już przydzielonej pamięci z płaską macierzą? Znalazłem wyciek pamięci (lub dwadzieścia) i naprawiłem go .

Oto o wiele bardziej czytelna wersja, która zachowuje się w ten sam sposób.

Ale naprawdę chcę zobaczyć, że to działa!

Pierwszym faktycznym ruchem wykonanym w algorytmie tego diabła jest F2, więc najszybszą kostką do rozwiązania byłby ten, w którym zmieszano F2:

   000
   000
   555
113222133444
113222133444
113222133444
   000
   555
   555

To faktycznie działa w 0,007 sekundy na TIO .

Jak można to poprawić?

Z pewnością jest więcej algorytmów diabła; Znalazłem taki, który wykonuje mniej niż trzydzieści ruchów, jakie wykonuje ten jeden. Kosztowałoby to jednak kilka tysięcy bajtów (około 100 MB więcej) i kilkadziesiąt godzin konwersji złożonego obwodu hamiltonowskiego na kod Cubic.

Możliwe jest również usunięcie niektórych funkcji i umieszczenie ich prosto w pętli na dole. Jednak poświęcę trochę bajtów dla pewnej czytelności.

Dodatkowo zastanawiam się nad modyfikacją zachowania pętli Cubically, dzięki czemu mogę łatwiej powtarzać algorytmy 7 lub 8 razy (zamiast po prostu kodować je za pomocą wywołań funkcji powtarzanych 7 lub 8 razy w źródle). Albo popracuję nad magią z notatnikiem i zagram w golfa, używając więcej pętli.

Pamiętaj, że będę nadal optymalizował wszystko, co możliwe w tłumaczu, więc może to kiedyś działać na przeciętnym komputerze!

Sześciennie, 2 bajty

r▦

Bardziej podoba mi się powyższa odpowiedź, więc dodaję to jako alternatywne rozwiązanie. To trwa mniej niż sekundę, w przeciwieństwie do kilku milionów lat.

r    read cube from standard in
 ▦   and solve it

Dane wyjściowe, jeśli kostka jest do rozwiązania: (nic) Dane
wyjściowe, jeśli kostka jest nierozwiązywalna: Error: The cube has reached an unsolvable state.

APL (Dyalog Classic) , 190 174 bajtów

{∧/~∊(×1 2 3|+.-⌿↑⊃∘⍋¨¨¨a)({2|≢∪{⍵⌊⍵[⍵]}⍣≡⍵,0}¨⍳⌿↑⌽b)((∪≢∩)¨/b←(⊃∘⍋⌽⊢)¨¨¨a),6≢≢∪⊃⊃a←{c←4⍴⊂⍬⋄c[+/1≠i],←(≠/×i←↑⍳3⍴3){⊂⌽⍣⍺⊢⍵~' '}¨,⌿(3|∘.+⍨⍳3)⍉⍤¯1↑1 0 1\⍵⋄1↓c}¨⍵(3 3∘⍴¨1 1∘⌷¨⍵)}

Wypróbuj online!

Argumentem jest macierz 3x2 (wiersz0: przód tył, wiersz1: lewy prawy, wiersz2: góra dół) macierzy 3x3 znaków. Zwraca 1 za możliwą do rozwiązania kostkę Rubika, w przeciwnym razie 0.

W łączu TIO funkcja t, która nie jest uwzględniona w liczbie znaków, odczytuje 9 linii wejściowych, konwertuje je z domyślnego formatu wejściowego (sieci) na wymaganą macierz 3x2 x 3x3, wywołuje rozwiązanie i drukuje OK, jeśli wynik jest zgodnie z oczekiwaniami.

Algorytm dzieli dany sześcian na 26 sześcianów - ciągi o długości 3 (narożniki), 2 (krawędzie) i 1 (środkowe). Generuje również 26 kostek rozwiązanego sześcianu z tymi samymi 6 centralnymi kostkami. Wszystkie poniższe kryteria muszą być spełnione:

• wśród 6 ośrodków nie ma duplikatów

• zestawy podanych / rozwiązanych kostek pasują do rotacji - np. rozważ 'WBR'i 'BRW'ten sam sześcian, ale nie'BWR'

• parzystości zarówno permutacji narożnej, jak i permutacji krawędziowej są równe

• sumy modulo 3 wskaźników obrotu rogu (na przykład biorąc litery „najmniejszy” Bjako punktu odniesienia, mamy: 'BRW'→0, 'WBR'→1, 'RWB'→2) pasują między daną a rozwiązywanych kostki; to samo dotyczy narożników modulo 2