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ż 2podwó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;
}
}
}