Sekwencje tożsamości na kostce Rubika

32

Sekwencja ruchów jest sekwencją ruchów (zakrętów) na Kostce Rubika (notacja znajduje się poniżej). Oprócz pustej sekwencji ruchów istnieje wiele innych sekwencji ruchów, które nie mają żadnego wpływu na kostkę. Te sekwencje ruchów nazywamy sekwencjami tożsamości.

Niektóre z tych sekwencji identyczności są oczywiste do ustalenia, jak U2 R R' U2lub U D2 U' D2. W pierwszym wykonywane są dwa losowe ruchy, U2 Ra następnie natychmiast cofane R' U2. Drugi jest podobny. Pierwsze dwa losowe ruchy, U D2a następnie cofane, ale w odwrotnej kolejności U' D2. Działa to tylko, ponieważ ruch Uwpływa tylko na kawałki górnej warstwy, a ruch D2tylko na kawałki dolnej warstwy. Możesz zobaczyć wizualizację tych dwóch sekwencji ruchów.

U2 RR 'U2 U D2 U 'D2

Inne sekwencje tożsamości mogą wcale nie być oczywiste. Na przykład sekwencja R' U' R' F' U F U' R' F R F' U' R U2 R. Jest dość długi, ale nie ma żadnego wpływu na kostkę.

wprowadź opis zdjęcia tutaj

Przenieś notację

Ruch opisuje obrót jednej warstwy jednej z sześciu ścian sześcianu. Ruch składa się z jednej litery reprezentującej twarz, po której następuje opcjonalny przyrostek reprezentujący kąt obrotu.

Litery i odpowiadające im twarze to U (w górę - strona skierowana w górę), D (w dół - strona skierowana w dół), R (w prawo - strona skierowana w prawo), L (w lewo - strona skierowana w lewo) , F (przód - strona skierowana do ciebie) i B (tył - strona skierowana od siebie).

Jeśli nie ma przyrostka, twarz jest obrócona o 90 stopni w prawo, przyrostek 'oznacza, twarz jest obrócona o 90 stopni w lewo, a przyrostek 2oznacza, że ​​twarz jest obrócona o 180 stopni w prawo.

Jeśli masz jakieś problemy z notacją, po prostu użyj http://alg.cubing.net , gdzie możesz wizualizować takie sekwencje ruchów.

Wyzwanie

Twoim zadaniem jest napisanie programu, który określa, czy sekwencje ruchu są tożsamością, czy nie.

Możesz napisać pełny program lub funkcję. Powinien otrzymać ciąg zawierający sekwencję ruchów (ruchy są oddzielone spacjami) jako dane wejściowe (przez STDIN, argument wiersza poleceń, argument zachęty lub funkcji), a dane wyjściowe (przez wartość zwracaną lub STDOUT) mają wartość logiczną lub odpowiednią liczbę całkowitą ( Prawda - 1 - sekwencja tożsamości / Fałsz - 0 - brak sekwencji tożsamości).

Jeśli sufiks ' powoduje problemy w języku programowania, możesz użyć innego symbolu, ale nie cyfrowo. R F2 U3nie jest dozwolone.

Jest to codegolf, dlatego wygrywa najkrótszy kod (w bajtach).

Przypadki testowe

"" -> True
"U2 R R' U2" -> True
"U D2 U' D2" -> True
"U2 R U2 R'" -> False
"R' U' R' F' U F U' R' F R F' U' R U2 R" -> True
"L'" -> False
"B B2 B' B2" -> True
"D D2 D'" -> False
"R F' D2 U B' F2 B' U2 D2 F2 B2 U F R'" -> True
"D2 U' R2 U F2 D2 U' R2 U' B' L2 R' B' D2 U B2 L' D' R2" -> False
"R U R' U' R' F R2 U' R' U' R U R' F' R2 U R2 U' R2 U' D R2 U' R2 U R2 D'" -> True
"R U R' U' R' F R2 U' R' U' R U R' F' R2 U' R2 U R2 U' D R2 U' R2 U R2 D'" -> False
"B2 F2 U' F2 U R2 F2 U2 B D' R' D' R2 D' F2 U' F U R2 U R B D B D2 L2 D' F2 U D' R' D B R2 D2 F2 R' F2 D2" -> True
"R U2 R' U R' U2 R U2 R U R' U' R' U R U2" -> False
"U F B' R' U F' R U' F' B L U' F L'" -> False
"R2 U' R' U' R U R U R U' R" -> False
"R' F R' B2 R F' R' B2 R2" -> False
Jakube
źródło
Co jest nie tak z R F2 U3?
John Dvorak
2
Chcę tylko upewnić się, że wszyscy mają takie same warunki wstępne. Jeśli pozwolę U3, to możesz po prostu dodać sufiks do cyfry.
Jakube
3
Jestem bardziej przyzwyczajony do notacji, która używa T-Top, B-Bottom i P-Posterior (z tyłu). Ludzie prawdopodobnie lubili oglądać sekwencję R2 D2.
mbomb007
2
@ mbomb007 Rozumiem T dla góry, ale nigdy nie widziałem P dla tylnej i nie zrozumiałbym jego znaczenia, gdyby nie twój komentarz ...
John Dvorak
2
@ mbomb007 Widziałem też tę notację, ale nie jest ona tak powszechna ani tak stara jak oryginalna notacja Singmaster i nie wiem, dlaczego ludzie chcą zadzierać z oryginałem. Chociaż David Singmaster (o ile mi wiadomo) nie wspomniał o tym, zauważyłem, że wszystkie twarze są idealnie spójne i bez żadnych starć, jeśli są traktowane jako wskazówki, a nie pozycje. That is F(orward), B(ackward), L(eft), R(ight), U(p), D(own)
Level River St

Odpowiedzi:

14

Haskell, 263 261 247 243 znaków

c[x]=[x]
c(x:"2")=[x,x]
c(x:_)=[x,x,x]
s!a@[x,y,z]=case s of
 'R'|x>0->[x,-z,y]
 'B'|y>0->[z,y,-x]
 'U'|z>0->[-y,x,z]
 'L'|x<0->[x,z,-y]
 'F'|y<0->[-z,y,x]
 'D'|z<0->[y,-x,z]
 _->a
r=[-2..2]
i=mapM id[r,r,r]
f w=i==foldr(map.(!))i(c=<<words w)

Raczej prosty algorytm; każdy sześcian składa się z 1,2,4 lub 8 części kodujących jego położenie i orientację; 4 kawałki na sześcian krawędzi, 8 na narożnik, 7 szafek są nieruchome.

c c przekształca każde słowo wejścia w sekwencję zwojów CW i !wysyła każdy fragment zgodnie z zakrętem. ijest mi stanowisko dentity. fjest głównym F maść.

Nie jestem zbyt zadowolony z cfunkcji homp, ale nie mogę znaleźć sposobu, aby ją skrócić (jednak @Nimi zrobił)

John Dvorak
źródło
Co powiesz na c(x:"2")=[x,x]i c(x:_)=[x,x,x]. Oszczędza 2 bajty.
nimi
Jeśli użyjesz i=sequence[s,s,s]i zmienisz wszystkie krotki na listy (tzn.: (x,y,z)Staje się [x,y,z]) - zapisuje ~ 9 znaków. Wstawienie oszczędza jeszcze 4. Usunięcie _skrzynki z !zapisuje kolejne 11.
MtnViewMark
@MtnViewMark zrobione i ulepszone i, dzięki. Nie jestem pewien, co masz na myśli przez wstawianie i- pamiętaj, że pojawia się dwukrotnie w definicji dla f. Nie jestem pewien, co masz na myśli mówiąc o opuszczeniu _skrzynki - _->acałkowite pominięcie lub przeniesienie jej na górę daje niewyczerpujący wyjątek wzoru, a przeniesienie jej na górę i tak nie uratuje żadnych postaci. Udało mi się jednak zapisać tam 5 znaków.
John Dvorak,
Świetne rozwiązanie. Sprawdziłem wszystkie przypadki testowe.
Jakube,
Jeszcze raz gratulacje dla twojego rozwiązania. Ponieważ przedstawiłeś najkrótszy kod, otrzymasz nagrodę wartą 100 reputacji.
Jakube,
4

Sześciennie , 6 4 bajtów

¶=8%

Wygrywam: P

¶=8%
¶     read a string, evaluate as Cubically code
 =8   set notepad to (notepad == 8th face)
   %  print notepad

Notatnik jest inicjowany do zera. Ósma „twarz” zawiera 1, jeśli sześcian jest nierozwiązany, a 0 w przeciwnym razie.

Wypróbuj online!

MD XF
źródło
3
Wygląda na interesujący język. Ale ponieważ język został stworzony po opublikowaniu wyzwania, nie można go wygrać.
Jakube,
2
@Jakube Zgadzam się, że nie należy tego akceptować, tylko dlatego, że jest to język z wbudowanymi modułami Rubika opublikowanymi tak późno po wyzwaniu i tak w pełni dziesiątkując inne odpowiedzi. Ale technicznie kwalifikuje się do wygrania według meta (zasada niekonkurująca została nieco uchylona).
MD XF,
3

J - 232, 220, 381, 315 296 bajtów

To rozwiązanie koduje wszystkie operacje jako permutacje ścian i działa w oparciu o fakt, że wszystkie skręty ścian są w rzeczywistości takie same, przy obrocie całej kostki.

Edycja : trochę więcej gry w golfa

f=:+/~6&*
r=:4 :'y f&.>(]{^:x~)&.C.;/i.2 4'"0
t=:((r~0),_4<\44#.inv 1478253772705907911x)&C.&.
Y=:(C.(,0 2 r 4 5),;/4 f&i.8)&{^:t
X=:((,1 1 0 2 r 2 4 3 1)C.C.;/0 4 2 5 f i.8)&{^:t
61".@A."1'=: ',"#~6 3$'D0XR1YF1XU2YB3XL3Y'
T=:[:(_2".@}.'(i.48)-:'&(,,[))[:(,'^:',])/&.>@|.&.;:[:''''&=@{.`]},:&'3'

Inne niż w poprzednich próbach, to nie brać pod uwagę obrót rożny.

fjest tylko funkcją pomocniczą. rwykonuje obrót jednej twarzy. twarz jest kodowana w następujący sposób:

  1. wszystkie rogi w krokach co 6
  2. wszystkie krawędzie co sześć

ta kolejność ułatwia kodowanie obrotów i zwrotów akcji. tto przysłówek, który przekręca twarz pod pewnym obrotem sześcianu, wybierając twarz.

Xi Ysą przysłówkami, które przyjmują jako lewy argument liczbę w tym kierunku całej kostki.

Kolejny wiersz określa wszystkie obroty: 3 znaki na obrót: nazwę, liczbę obrotów i kierunek.

Ostatni wiersz definiuje czasownik testowy T, konwertując 3 i 'na notację Mocy, odwracając kolejność działania, dodając wektor testowy i ostatecznie wyliczając całość.

Więcej szczegółów na życzenie.

tests =: (] ;. _2) 0 : 0

 U2 R R' U2
 U D2 U' D2
 U2 R2 R'
 R' U' R' F' U F U' R' F R F' U' R U2 R
 L'
 B B2 B' B2
 D D2 D'
 R F' D2 U B' F2 B' U2 D2 F2 B2 U F R'
 D2 U' R2 U F2 D2 U' R2 U' B' L2 R' B' D2 U B2 L' D' R2
 R U R' U' R' F R2 U' R' U' R U R' F' R2 U R2 U' R2 U' D R2 U' R2 U R2 D'
 R U R' U' R' F R2 U' R' U' R U R' F' R2 U' R2 U R2 U' D R2 U' R2 U R2 D'
 B2 F2 U' F2 U R2 F2 U2 B D' R' D' R2 D' F2 U' F U R2 U R B D B D2 L2 D' F2 U D' R' D B R2 D2 F2 R' F2 D2
 R U2 R' U R' U2 R U2 R U R' U' R' U R U2
 U F B' R' U F' R U' F' B L U' F L'
 R2 U' R' U' R U R U R U' R
 R' F R' B2 R F' R' B2 R2
)
res =: 1 1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0
res ([,],:=) T"1 tests NB. passes all tests.
1 1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0
1 1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

NB. some handy display methods:
dispOrig=: (". ;._2) 0 :0
   _   _   _   5  29  11   _   _   _   _   _   _
   _   _   _  47  _1  35   _   _   _   _   _   _
   _   _   _  23  41  17   _   _   _   _   _   _
   3  27   9   0  24   6   1  25   7   2  26   8
  45  _3  33  42  _6  30  43  _5  31  44  _4  32
  21  39  15  18  36  12  19  37  13  20  38  14
   _   _   _   4  28  10   _   _   _   _   _   _
   _   _   _  46  _2  34   _   _   _   _   _   _
   _   _   _  22  40  16   _   _   _   _   _   _
)
ind =: dispOrig i.&, i. 48 NB. indices of i.48 in the original display

disp =: (9 12$(,dispOrig) ind}~ ])
changed =: 1 : '(u ~:&disp ]) i.48' NB. use to debug permutation verbs: L ch
vch =: 1 :'disp  ((]+_*=) u)'
NB. viewmat integration RGB
cm =: 255 * 1 0 0 , 1 1 1, 0 1 0, 1 1 0, 1 0.5 0, 0 0 1,: 0 0 0 NB. colormap
NB. use as:  "cube i. 48" for seeing a nice folded out cube.
cube =: cm viewmat (>&7 + >&15 + >&23 + >&31 + >& 39 + >&47)@|@disp@]
jpjacobs
źródło
11
„ponieważ moje wyniki testu nie odpowiadają tym podanym ...” jak w, twoje rozwiązanie nie działa? Nie opublikowałbym tego wtedy ...
John Dvorak
Masz rację. Naprawiono to teraz.
jpjacobs,
Dodałem 4 dodatkowe przypadki testowe. Dwa z nich nadal zwracają fałszywy wynik. Wygląda na to, że ignorujesz orientację narożników.
Jakube,
@jpjacobs Nagroda za powtórzenie wynosi 100 powtórzeń. Chcesz poprawić swój kod?
Jakube,
Voila, gotowe. Teraz tylko to zmniejszam.
jpjacobs
2

Python 3: 280 znaków

To nie jest uczestnik wyzwania. Po pierwsze dlatego, że sam zadałem to wyzwanie, a po drugie dlatego, że nie jest to mój kod. Wszystkie kredyty należą do Stefana Pochmanna , który odkrył ten niesamowity sposób symulowania Kostki Rubika. Zrobiłem tylko trochę golfa i kilka drobnych zmian w odniesieniu do wyzwania.

def f(a):
 s=t="UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR".split()
 for m in a.split():q="FLBR FRBL FDBU FUBD URDL ULDR".split()['UDLRFB'.index(m[0])];n=2+"2'".find(m[-1]);s=[[p,p.translate(str.maketrans(q,q[n:]+q[:n]))][m[0]in p]for p in s]
 return s==t

Idea tego jest następująca. sreprezentuje położenie kawałki UF, URi tak dalej. Na przykład:s = ['DF', 'BL', ...] oznacza, że ​​element UFjest w pozycji DF, element URjest w pozycji BL, ...

Jak zmienia się pozycja elementu podczas wykonywania ruchu. Jeśli wykonasz Uruch, wszystkie naklejki (kolory) Uwarstwy, które są skierowane do przedniej ściany, przesuwają się na lewą twarz. Naklejki lewej twarzy przesuwają się do tyłu, te po prawej i te na przednią twarz. Kodowane przez FLBR. Kilka przykładów: UFruchy do UL, UFRruchy do ULFi tak dalej. Dlatego zastosowanie ruchu jest po prostu translacją powierzchni elementów na odpowiedniej warstwie.

Jakube
źródło