Bezczynnie przekręcając kostkę Rubika , mój syn zauważył, że wraca do stanu rozwiązanego. Jestem prawie pewien, że początkowo myślał, że to jakaś magia voodoo, ale wyjaśniłem, że jeśli będziesz powtarzał tę samą sekwencję ruchów, zawsze wróci do swojego pierwotnego stanu. Ostatecznie.
Oczywiście, będąc dzieckiem, musiał sam to wypróbować i wybrać „losową” sekwencję, która według niego będzie trudna. Stracił utwór po około dziesięciu powtórzeniach i zapytał mnie, ile razy będzie musiał to powtórzyć. Nie znając sekwencji, której używał, powiedziałem mu, że nie wiem, ale że możemy napisać program, aby się dowiedzieć.
Właśnie tam wchodzisz. Oczywiście mógłbym coś wymieszać, ale chciałby to napisać w sobie. Jednak nie jest jeszcze bardzo szybką maszynistką, więc potrzebuję możliwie najkrótszego programu .
Cel
Biorąc pod uwagę sekwencję zwojów, wypisz najmniejszą liczbę operacji, które należy wykonać, aby przywrócić kostkę do pierwotnego stanu. To jest kod golfowy, więc wygrywa najmniej bajtów. Możesz napisać program lub funkcję i obowiązują wszystkie inne standardowe ustawienia domyślne.
Wejście
Dane wejściowe to sekwencja ruchów, traktowana jako ciąg znaków, lista lub inny format odpowiedni dla Twojego języka. Możesz używać separatora (lub nie) między ruchami, jeśli jest w postaci łańcucha.
Istnieje sześć „podstawowych” ruchów, które należy wziąć pod uwagę, wraz z ich odwróceniami:
R - Turn the right face clockwise
L - Turn the left face clockwise
U - Turn the up (top) face clockwise
D - Turn the down (bottom) face clockwise
F - Turn the front face clockwise
B - Turn the back face clockwise
Odwrotności są reprezentowane przez dodanie znaku pierwszego '
po literze. Oznacza to, że obrócisz tę twarz przeciwnie do ruchu wskazówek zegara, więc F'
obróci przednią twarz przeciwnie do ruchu wskazówek zegara i F F'
od razu powróci do pierwotnego stanu.
Dla zainteresowanych wyzwaniem jest ograniczony zestaw notacji Singmaster . Ruwix ma fajne animacje, jeśli chcesz zobaczyć go w akcji.
Wynik
Dane wyjściowe to po prostu minimalna liczba przypadków, w których sekwencja wejściowa musi zostać wykonana.
Przykłady
Input Output
FF' -> 1
R -> 4
RUR'U' -> 6
LLUUFFUURRUU -> 12
LUFFRDRBF -> 56
LF -> 105
UFFR'DBBRL' -> 120
FRBL -> 315
Oto (dość naiwny) solver do porównywania twoich odpowiedzi, napisany w Javie. Akceptuje również 2
podwójne ruchy (więc czwarty przypadek jest równoważny L2U2F2U2R2U2
).
import java.util.ArrayList;
import java.util.List;
public class CycleCounter{
public static void main(String[] args){
int[] cube = new int[54];
for(int i=0;i<54;i++)
cube[i] = i;
String test = args.length > 0 ? args[0] : "RUR'U'";
List<Rotation> steps = parse(test);
System.out.println(steps.toString());
int count = 0;
do{
for(Rotation step : steps)
cube = step.getRotated(cube);
count++;
}while(!isSorted(cube));
System.out.println("Cycle length for " + test + " is " + count);
}
static List<Rotation> parse(String in){
List<Rotation> steps = new ArrayList<Rotation>();
for(char c : in.toUpperCase().toCharArray())
switch(c){
case 'R':steps.add(Rotation.R);break;
case 'L':steps.add(Rotation.L);break;
case 'U':steps.add(Rotation.U);break;
case 'D':steps.add(Rotation.D);break;
case 'F':steps.add(Rotation.F);break;
case 'B':steps.add(Rotation.B);break;
case '\'':
steps.add(steps.get(steps.size()-1));
case '2':
steps.add(steps.get(steps.size()-1));
break;
}
return steps;
}
static boolean isSorted(int[] in){for(int i=0;i<in.length-1;i++)if(in[i]>in[i+1])return false;return true;}
enum Rotation{
R(new int[]{-1,-1,42,-1,-1,39,-1,-1,36, -1,-1,2,-1,-1,5,-1,-1,8, 20,23,26,19,-1,25,18,21,24, -1,-1,11,-1,-1,14,-1,-1,17, 35,-1,-1,32,-1,-1,29,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,-1}),
L(new int[]{9,-1,-1,12,-1,-1,15,-1,-1, 27,-1,-1,30,-1,-1,33,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,-1, 44,-1,-1,41,-1,-1,38,-1,-1, -1,-1,6,-1,-1,3,-1,-1,0, 47,50,53,46,-1,52,45,48,51}),
U(new int[]{2,5,8,1,-1,7,0,3,6, 45,46,47,-1,-1,-1,-1,-1,-1, 9,10,11,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,-1, 18,19,20,-1,-1,-1,-1,-1,-1, 36,37,38,-1,-1,-1,-1,-1,-1}),
D(new int[]{-1,-1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,24,25,26, -1,-1,-1,-1,-1,-1,42,43,44, 29,32,35,28,-1,34,27,30,33, -1,-1,-1,-1,-1,-1,51,52,53, -1,-1,-1,-1,-1,-1,15,16,17}),
F(new int[]{-1,-1,-1,-1,-1,-1,18,21,24, 11,14,17,10,-1,16,9,12,15, 29,-1,-1,28,-1,-1,27,-1,-1, 47,50,53,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,-1, -1,-1,8,-1,-1,7,-1,-1,6}),
B(new int[]{51,48,45,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,-1, -1,-1,0,-1,-1,1,-1,-1,2, -1,-1,-1,-1,-1,-1,26,23,20, 38,41,44,37,-1,43,36,39,42, 33,-1,-1,34,-1,-1,35,-1,-1});
private final int[] moves;
Rotation(int[] moves){
this.moves = moves;
}
public int[] getRotated(int[] cube){
int[] newCube = new int[54];
for(int i=0;i<54;i++)
if(moves[i]<0)
newCube[i] = cube[i];
else
newCube[moves[i]] = cube[i];
return newCube;
}
}
}
źródło
Odpowiedzi:
Pyth,
6663 bajtówWypróbuj online: pakiet demonstracyjny lub testowy . Zauważ, że program działa trochę wolno i kompilator online nie jest w stanie obliczyć odpowiedzi
RU2D'BD'
. Ale zapewniam, że może to obliczyć na moim laptopie w około 12 sekund.Program (przypadkowo) akceptuje również
2
podwójne ruchy.Pełne objaśnienie:
Parse scramble:
Najpierw zajmę się znakami pierwszymi
'
w ciągach wejściowych. Po prostu zastępuję je3
ciągiem dekodującym ten ciąg. Ponieważ format dekodowania Pytha wymaga liczby przed znakiem, uprzednio odwracam ciąg._r_Xz\'\39
. Więc potem odwracam to z powrotem.Opisz stan rozwiązanej kostki:
=Z"UDLRFB
przypisuje ciąg ze wszystkimi 6 ruchami doZ
.Możemy opisać stan kostki, opisując lokalizację każdego kawałka kostki. Na przykład możemy powiedzieć, że krawędź, która powinna znajdować się w UL (lewy górny róg), znajduje się obecnie w FR (prawy przedni). Do tego muszę wygenerować wszystkie kawałki Prócz modułu:
f!s}RTcZ2yZ
.yZ
generuje wszystkie możliwe podzbiory"UDLRFB"
. To oczywiście generuje również podzbiór"UDLRFB"
i podzbiór"UD"
. Pierwszy nie ma żadnego sensu, ponieważ nie ma elementu widocznego ze wszystkich 6 stron, a drugi nie ma żadnego sensu, ponieważ nie ma elementu krawędzi, który byłby widoczny od góry i od dołu . Dlatego usuwam wszystkie podzbiory, które zawierają podsekwencje"UD"
,"LR"
lub"FB"
. To daje mi 27 następujących elementów:Obejmuje to również pusty ciąg i wszystkie sześć ciągów 1-literowych. Możemy zinterpretować je jako element pośrodku sześcianu i 6 elementów środkowych. Oczywiście nie są wymagane (ponieważ się nie ruszają), ale ich zatrzymam.
Robienie niektórych ruchów:
Zrobię kilka tłumaczeń ciągów, aby wykonać ruch. Aby zwizualizować ten pomysł, zajrzyj do narożnika
URF
. Co się z tym stanie, kiedy wykonamR
ruch? Naklejka naU
twarzy przesuwa się naB
twarz, nalepkaF
przesuwa się naU
twarz, a naklejka naR
twarzy pozostaje naR
twarzy. Można powiedzieć, że kawałek przyURF
przesuwa się na pozycjęBRU
. Ten wzór dotyczy wszystkich elementów po prawej stronie. Każda naklejka naF
twarzy przesuwa się naU
twarz podczas wykonywaniaR
ruchu, każda naklejka naU
twarzy przesuwa się naB
twarz, każda naklejka naB
ruchachD
i każda naklejka naD
ruchachF
. Możemy dekodować zmianyR
ruchu jakoFUBD
.Poniższy kod generuje wszystkie 6 niezbędnych kodów:
I wykonujemy przejście
H
do stanu kostkiG
w następujący sposób:Policz liczbę powtórzeń:
Reszta jest prawie banalna. Po prostu wykonuję szyfrowanie wejściowe do rozwiązanej kostki w kółko, dopóki nie osiągnę pozycji, którą wcześniej odwiedziłem.
źródło
GAP,
792 783 782749650 bajtówTo wydaje się działać. Jeśli coś z tym popsunie, daj mi znać.
Dzięki @Lynn za sugestię, że rozkładam niektóre prymitywne ruchy.
Dzięki @Neil za sugestię, że zamiast
Inverse(X)
używaćX^3
.Przykład użycia:
f("R");
Oto niepoznany kod z odrobiną wyjaśnienia
źródło
45
ze5
w twoich permutacji i zapisz trzy bajty.A:=R*L*L*L*F*F*B*B*R*L*L*L;D:=A*U*A;
jest krótszy niż twoja definicjaD
(ale nie mogę go przetestować ...)^-1
dla inwersów, BTW?Mathematica,
413401 bajtówObjaśnienia
Kostka Rubika składa się z 20 ruchomych kostek (8 rogów, 12 krawędzi). Każdy sześcian może otrzymać numer:
rogi :
krawędzie :
Zauważ, że gdy sześcian jest skręcony, zasadniczo nie są już w swoich pozycjach wyjściowych. Na przykład, po
R
zakończeniu, kostka1
przechodzi zUFR
nowej pozycjiUBR
.W takiej notacji obrót o 90 stopni można opisać 8 ruchami sześcianów. Na przykład
R
jest opisany przezPonieważ każdy sześcian ma unikalną pozycję początkową, każda pozycja ma unikalną pozycję początkową. Innymi słowy, reguła
UFR->UBR
jest po prostu1->2
(oznacza, żeR
sześcienna pozycja początkowa sześciennego1
do pozycji początkowej sześciennego2
). W ten sposóbR
można uprościć dalej do cykluAby w pełni rozwiązać Kostkę Rubika, musimy również dopasować kostki do odpowiadających im orientacji początkowych. Ściany sześcianu są pomalowane na różne kolory, schemat, którego często używam podczas rozwiązywania kostek
Analizując orientacje narożników, kolory inne niż żółty lub biały są ignorowane, a żółty i biały są uważane za ten sam kolor.
Załóżmy, że kostka
1
jest w pozycji początkowejUFR
, żółty aspekt może być wyrównany do trzech różnych ścian. Używamy liczby całkowitej do reprezentowania tych przypadków,Załóżmy, że sześcian
1
jest włączonyDFL
, jego trzy możliwe orientacje toAnalizując orientację krawędzi, czerwony i pomarańczowy są ignorowane, a żółty i biały są ignorowane tylko wtedy, gdy krawędź ma zielony lub niebieski fasetowanie.
Załóżmy, że kostka
10
jest w pozycji początkowejUR
, zielony aspekt może być wyrównany do dwóch różnych ścian. Możliwe są dwie orientacjeZałóżmy, że cubie
10
jest włączonaDF
, możliwe są dwie możliwe orientacjeTablica służy do przechowywania stanu kostki. Stan początkowy kostki to
co oznacza, że wszystkie kostki są w pozycji wyjściowej z prawidłową orientacją.
Po
R
tym stanie się sześcianco oznacza, że kostka
5
jest teraz w pozycji1
(UFR
) z orientacją2
, kostka1
jest teraz w pozycji2
(UBR
) z orientacją1
, kostka3
jest teraz w pozycji3
(UBL
) z orientacją0
i tak dalej.Przypadki testowe
źródło
Haskell, 252 bajty
Przykładowe przebiegi:
Kluczową obserwacją tutaj jest to, że łatwiej jest modelować kostkę Rubika jako siatkę punktów 5 × 5 × 5, a nie siatkę zorientowanych sześcianów 3 × 3 × 3. Narożniki stają się sześcianami o wymiarach 2 × 2 × 2 punkty, brzegi stają się kwadratami o wymiarach 2 × 2 × 1 punktów, a ruchy obracają plastry o wymiarach 5 × 5 × 2 punktów.
źródło
c:"'"
przezc:_
zapisuje dwa bajty._
pasuje również do pustej listy.Rubinowy, 225 bajtów
Podobna do odpowiedzi Anders Kaseorg i inspirowane przez Jana Dvoraka odpowiedzi na poprzednie pytanie.
Jednak w przeciwieństwie do tych odpowiedzi, nie potrzebuję 125 kostek. Używam kostki rubika złożonej z 27 sześcianów, ale o prostokątnych wymiarach. W stanie rozwiązanym rogi są
+/-1,+/-4,+/-16
.Generuję tablicę 64 sześcianów, każdy z wybranym środkiem
x=[-1,0,1,2], y=[-4,0,4,8], z=[-16-0,16,32]
. Kostki o współrzędnych 2, 8 i 32 są niepotrzebne, ale nie wyrządzają szkody, więc pozostawia się je z powodów golfowych. Fakt, że długość, szerokość i głębokość kostek są różne: (1,4,16) oznacza, że łatwo jest wykryć, czy znajdują się we właściwym miejscu, ale mają niewłaściwe ustawienie.Każdy sześcian jest śledzony, gdy jest przesuwany przez obie strony. Jeśli współrzędna sześcianu w osi odpowiadającej powierzchni (pomnożona przez
e=-1
dla U, F, R lube=1
dla D, B, L) jest dodatnia, wówczas zostanie obrócona poprzez zamianę współrzędnych na drugiej 2 osi i zastosowanie odpowiednia zmiana znaku na jedną ze współrzędnych. Jest to kontrolowane przez pomnożenie przeze*d
.Sekwencja wejściowa jest skanowana w odwrotnej kolejności. Nie robi to różnicy, o ile „normalne” obroty są wykonywane w kierunku przeciwnym do ruchu wskazówek zegara zamiast w prawo. Powodem tego jest to, że jeśli
'
zostanie znaleziony symbol, wartośćd
można zmienić z 1 na -1, aby spowodować obrót następnej powierzchni w przeciwnym kierunku.Niegolfowany w programie testowym
źródło
Python 2, 343 bajty
Dane wejściowe są pobierane ze standardowego wejścia.
Dana sekwencja skrętów jest wykonywana wielokrotnie na wirtualnej kostce, aż powróci do stanu rozwiązanego. Stan kostki jest przechowywany jako wektor orientacji i wektor permutacji, oba o długości 20.
Orientacje są nieco dowolnie zdefiniowane: sześcian brzegowy jest zorientowany poprawnie, jeśli można go przesunąć na miejsce bez wywoływania obrotu o ćwierć obrotu R lub L. Orientacja kostek narożnych jest uwzględniana względem powierzchni F i B.
Przykładowe użycie
Pakiet demonstracyjny i testowy online .
źródło
Clojure, 359 bajtów
To może być mój drugi najdłuższy codegolf. Zdając sobie sprawę, że mogę upuścić końcowe zera z wektorów,
A
abyF
bardzo mnie uszczęśliwić: DMniej golfa:
To po prostu implementuje obroty 3D wybranych podzbiorów
5 x 5 x 5
kostki. Początkowo miałem zamiar użyć3 x 3 x 3
i zajęło mi trochę czasu, aby zrozumieć, dlaczego nie otrzymałem poprawnych wyników. Dobre przypadki testowe! Niektóre dodatkowe bajty do kodowania pięści"RUR'U'"
jako"RURRRUUU"
.źródło
Sześciennie ,
96 bajtówWypróbuj online! (Nie działa, dopóki Dennis nie zaktualizuje interpretera Cubio TIO)
Wyjaśnienie:
Ten język zdominuje wszystkie wyzwania kostki rubika >: D
źródło
-7
oznaczało to odjęcie siedmiu, a nie dodanie jednego ze złością trzęsieCzysty , 255 bajtów
Pochodzi osobno od prawie identycznej odpowiedzi Haskella jako odpowiedź na to pytanie, które zostało zamknięte jako duplikat, gdy było prawie gotowe, więc opublikowałem odpowiedź tutaj.
Wypróbuj online!
źródło