Rozwiąż kostkę Rubika

38

Napisz najkrótszy program, który rozwiązuje kostkę Rubika (3 * 3 * 3) w rozsądnym czasie i porusza się (powiedzmy, maks. 5 sekund na twoim komputerze i mniej niż 1000 ruchów).

Dane wejściowe mają format:

UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR

(to konkretne wejście reprezentuje rozwiązany moduł).
Pierwsze 12 2-znakowych ciągów to krawędzie w pozycjach UF, UR, ... BL (U = góra, F = przód, R = prawo, B = tył, L = lewy, D = dół), a następnie kolejne 8 Ciągi 3 znaków to rogi w pozycjach UFR, URB, ... DBR.

Dane wyjściowe powinny zawierać sekwencję ruchów w tym formacie:

D+ L2 U+ F+ D+ L+ D+ F+ U- F+

Gdzie D1 lub D + oznacza obrócenie powierzchni D (w dół) o 90 stopni w kierunku zgodnym z ruchem wskazówek zegara, L2 obraca powierzchnię L o 180 stopni, U3 lub U- oznacza obrócenie powierzchni U w kierunku przeciwnym do ruchu wskazówek zegara o 90 stopni.
Litery nie uwzględniają wielkości liter, a spacje są opcjonalne.

Na przykład powyższe dane wyjściowe są poprawne dla następujących danych wejściowych:

RU LF UB DR DL BL UL FU BD RF BR FD LDF LBD FUL RFD UFR RDB UBL RBU

Aby uzyskać więcej informacji, zapoznaj się z konkursem kostki Tomasa Rokickiego , z wyjątkiem tego, że ocena będzie dokonywana bezpośrednio według rozmiaru pliku, jak normalny problem z golfem. Tester Internecie wliczone jest zbyt.

Dla porównania, najkrótszym już napisanym rozwiązaniem jest ostatni wpis na liście zwycięzców konkursu kostki

Dla tych, którzy mają problemy z wizualizacją formatu układu:

0-1 2-3 4-5 6-7 8-9 10-11 12-13 14-15 16-17 18-19 20-21 22-23 24-25-26 27-28-29 30-31-32 33-34-35 36-37-38 39-40-41 42-43-44 45-46-47
UF  UR  UB  UL  DF   DR    DB   DL    FR    FL     BR    BL     UFR      URB      UBL      ULF      DRF      DFL      DLB      DBR

Front:

                 +-------+-------+-------+
                /       /       /       /|
               /  30   /   4   /  27   / |
              +-------+-------+-------+  |
             /       /       /       /|28+
            /   6   /       /   2   / | /|
           +-------+-------+-------+  |/ |
          /       /       /       /|3 +  |
         /  33   /   0   /  24   / | /|21+
        +-------+-------+-------+  |/ | /|
        |       |       |       |26+  |/ |
        |  35   |   1   |   25  | /|  +  |
        |       |       |       |/ | /|47+
        +-------+-------+-------+  |/ | /
        |       |       |       |17+  |/
        |  18   |       |  16   | /|11+
        |       |       |       |/ | /
        +-------+-------+-------+  |/
        |       |       |       |37+
        |  40   |   9   |  38   | /
        |       |       |       |/
        +-------+-------+-------+


Hidden faces:

                 +-------+-------+-------+
                /|       |       |       |
               / |  31   |   5   |  29   |
              +  |       |       |       |
             /|32+-------+-------+-------+
            / | /|       |       |       |
           +  |/ |  22   |       |  20   |
          /|7 +  |       |       |       |
         / | /|23+-------+-------+-------+
        +  |/ | /|       |       |       |
        |34+  |/ |  44   |  13   |  46   |
        | /|  +  |       |       |       |
        |/ | /|43+-------+-------+-------+
        +  |/ | /       /       /       /
        |19+  |/  42   /  12   /  45   /
        | /|15+-------+-------+-------+
        |/ | /       /       /       /
        +  |/  14   /       /  10   /
        |41+-------+-------+-------+
        | /       /       /       /
        |/  39   /   8   /   36  /
        +-------+-------+-------+
code-golf puzzle-solver rubiks-cube restricted-time code-bowling code-golf ascii-art code-challenge code-golf c code-golf hello-world code-golf string decision-problem code-challenge primes number-theory code-golf code-golf python pi code-golf graphical-output game atomic-code-golf whitespace balanced-string code-golf geometry code-golf optimization board-game puzzle-solver fastest-code primes code-challenge code-golf hello-world polyglot code-golf cryptography code-golf javascript aditsu
źródło
3
Czy akceptowane są języki inne niż C / C ++ / Java / Perl / Python?
Egor Skriptunoff
@EgorSkriptunoff Tutaj tak, używaj tego, co chcesz, po prostu żadnych bibliotek do rozwiązywania kostek.
aditsu
A co z punktowaniem? Zwykła punktacja w golfa (bajty w programie) czy złożona punktacja jak w konkursie w 2004 roku?
Egor Skriptunoff,
2
@jdstankosky, dodałem schemat.
Peter Taylor
7
Czy wolno nam ściągać naklejki i przenosić je?
Iszi

Odpowiedzi:

25

C ++ - 1123

Ponieważ jak dotąd nikt nie opublikował żadnej odpowiedzi, postanowiłem uprościć moje rozwiązanie z 2004 roku. Nadal jest daleko w tyle za najkrótszą, o której wspomniałem w pytaniu.

#include<iostream>
#include<vector>
#define G(i,x,y)for(int i=x;i^y;i++)
#define h(x)s[a[x]/q*q+(a[x]+j)%q-42]
#define B(x)D=x;E=O.substr(j*3,3);G(i,0,3)E+=F[5-F.find(E[2-i])];G(i,0,D.length())D[i]=E[F.find(D[i++])];m.push_back(D);
#define P(a,b)G(i,0,6)G(k,49,52){e[0]=F[i];e[1]=k;m.push_back(e);}G(j,0,24){B(a)B(b)}
#define T C();z=m.size();for(b=c;b;){d=s;G(i,o=w=1,4){w*=z;if(o)G(j,0,w)if(o){s=d;u=j;G(k,0,i){f=m[u%z];G(x,0,f.length()){a=M[F.find(f[x++])];G(i,0,f[x]-48)G(l,0,2){q=3-l;p=4*l;G(j,0,q){t=h(p+3);G(k,-3,0)h(p-k)=h(p-1-k);h(p)=t;}}}u/=z;}C();if(c<b){u=j;G(k,0,i){std::cout<<m[u%z];u/=z;}b=c;o=0;}}}}
std::string s,a,D,E,d,f,e="  ",S="UFURUBULDFDRDBDLFRFLBRBLUFRURBUBLULFDRFDFLDLBDBR",F="ULFBRD",M[]={"KHEB*0.,","KRTI0<8@","KDNS*;2=","IVXG/@7>","BGWP,>4:","QNWT2468"},O=S.substr(24)+"FDRFRUFULFLDRDBRBURUFRFDBDLBLUBURBRDLDFLFULUBLBD";std::vector<std::string>m;int
w,X=8,Y=16,o,c,u,b,z,p,q,t;void C(){c=0;G(i,X,Y)c+=s[i]!=S[i];}main(int
g,char**v){G(i,1,g)s+=v[i];P("U2F1R1L3U2L1R3F1U2","L3R1F3L1R3D2L3R1F3L1R3");T;Y=24;T;X=0;T;m.clear();P("R3D3R1D3R3D2R1L1D1L3D1L1D2L3","R1F3L3F1R3F3L1F1");G(I,5,9){Y=I*6;T}}

To nie jest przypadkowe, ale też nie przebiega prosto. Najpierw rozwiązuje krawędzie, a następnie rogi. Na każdym kroku wypróbowuje różne kombinacje maksymalnie 4 algorytmów i prostych zakrętów twarzy (sekwencyjnie, nie losowo), aż znajdzie poprawę liczby rozwiązanych elementów, a następnie powtarza się do rozwiązania. Wykorzystuje 2 algorytmy dla krawędzi i 2 dla narożników, przetłumaczone na wszystkie pozycje kostki.

Przykładowe dane wyjściowe dla RU LF UB DR DL BL UL FU BD RF BR FD LDF LBD FUL RFD UFR RDB UBL RBU:

L2F3B2F3B1U3F1B3R2F3B1U3F1B3D2F2L3D2L1U2B1L1R3U2R1L3B1U2R1U2L1F1B3U2B1F3L1U2L3R1D3L1R3B2L3R1D3L1R3L3R1D3L1R3B2L3R1D3L1R3B3F1D3B1F3R2B3F1D3B1F3U2F3L3R1B3L1R3U2L3R1B3L1R3F1D2F1L1R3D2R1L3F1D2F3L2U1B1F3L2F1B3U1L2R3L1F3R1L3U2R3L1F3R1L3U1F2U1L1R3F2R1L3U1F2U3L3U3L1U3L3U2L1R1U1R3U1R1U2R3F3U3F1U3F3U2F1B1U1B3U1B1U2B3L1B3R3B1L3B3R1B1B3D3B1D3B3D2B1F1D1F3D1F1D2F3R1F3L3F1R3F3L1F1R3B3R1B3R3B2R1L1B1L3B1L1B2L3R1D3L3D1R3D3L1D1B3D3B1D3B3D2B1F1D1F3D1F1D2F3U3R3U1R3U3R2U1D1R1D3R1D1R2D3

(234 ruchy, tutaj 0.3 sekundy)

aditsu
źródło
2
Co wiesz ... inna odpowiedź została opublikowana w ciągu kilku sekund :)
aditsu
Chociaż jest to dłuższe niż rozwiązanie Ruby, uważam, że lepiej pasuje ono do kryteriów problemu „w rozsądnym czasie i ruchach”. Jednak nadal chciałbym znaleźć rozwiązanie, które średnio wynosi mniej niż ~ 50 ruchów.
primo,
2
@primo Dzięki :) Mój oryginalny kod uśredniał ponad 50 ruchów, dla mniej niż 50 myślę, że potrzebujesz albo więcej algorytmów (kostki), albo innego podejścia, takiego jak metoda Thistlethwaite. Jednak wydajność (liczba ruchów) nie jest zbyt zgodna z golfem. W każdym razie, aby znaleźć alternatywne rozwiązania, sprawdź zwycięzców konkursu Tomasa Rokickiego.
aditsu
23

Python 1166 bajtów

Znaczna ilość białych znaków została pozostawiona ze względu na czytelność. Wielkość mierzona po usunięciu tej spacje i zmieniając różne poziomy wcięć do Tab, Tab Space, Tab Tab, itd. Mam również unikać jakichkolwiek golfa co wpłynęło na wydajność zbyt drastycznie.

T=[]
S=[0]*20,'QTRXadbhEIFJUVZYeijf',0
I='FBRLUD'

G=[(~i%8,i/8-4)for i in map(ord,'ouf|/[bPcU`Dkqbx-Y:(+=P4cyrh=I;-(:R6')]
R=range

def M(o,s,p):
 z=~p/2%-3;k=1
 for i,j in G[p::6]:i*=k;j*=k;o[i],o[j]=o[j]-z,o[i]+z;s[i],s[j]=s[j],s[i];k=-k

N=lambda p:sum([i<<i for i in R(4)for j in R(i)if p[j]<p[i]])

def H(i,t,s,n=0,d=()):
 if i>4:n=N(s[2-i::2]+s[7+i::2])*84+N(s[i&1::2])*6+divmod(N(s[8:]),24)[i&1]
 elif i>3:
  for j in s:l='UZifVYje'.find(j);t[l]=i;d+=(l-4,)[l<4:];n-=~i<<i;i+=l<4
  n+=N([t[j]^t[d[3]]for j in d])
 elif i>1:
  for j in s:n+=n+[j<'K',j in'QRab'][i&1]
 for j in t[13*i:][:11]:n+=j%(2+i)-n*~i
 return n

def P(i,m,t,s,l=''):
 for j in~-i,i:
  if T[j][H(j,t,s)]<m:return
 if~m<0:print l;return t,s
 for p in R(6):
  u=t[:];v=s[:]
  for n in 1,2,3:
   M(u,v,p);r=p<n%2*i or P(i,m+1,u,v,l+I[p]+`n`)
   if r>1:return r

s=raw_input().split()
o=[-(p[-1]in'UD')or p[0]in'RL'or p[1]in'UD'for p in s]
s=[chr(64+sum(1<<I.find(a)for a in x))for x in s]

for i in R(7):
 m=0;C={};T+=C,;x=[S]
 for j,k,d in x:
  h=H(i,j,k)
  for p in R(C.get(h,6)):
   C[h]=d;u=j[:];v=list(k)
   for n in i,0,i:M(u,v,p);x+=[(u[:],v[:],d-1)]*(p|1>n)
 if~i&1:
  while[]>d:d=P(i,m,o,s);m-=1
  o,s=d

Przykładowe użycie:

$ more in.dat
RU LF UB DR DL BL UL FU BD RF BR FD LDF LBD FUL RFD UFR RDB UBL RBU

$ pypy rubiks.py < in.dat
F3R1U3D3B1
F2R1F2R3F2U1R1L1
R2U3F2U3F2U1R2U3R2U1
F2L2B2R2U2L2D2L2F2

Jest to implementacja algorytmu Thistlethwaite, wykorzystująca wyszukiwanie IDA * do rozwiązania dla każdego kroku. Ponieważ wszystkie tabele heurystyczne muszą być obliczane w locie, dokonano kilku kompromisów, zwykle dzieląc heurystykę na dwie lub więcej dość równych części. To sprawia, że ​​obliczenia tabel heurystycznych są setki razy szybsze, a jednocześnie spowalniają fazę wyszukiwania, zwykle tylko nieznacznie, ale może być znacząca w zależności od początkowego stanu kostki.

Indeks zmienny

  • T - główny stół heurystyczny.
  • S- rozwiązany stan kostki. Każdy pojedynczy element jest przechowywany jako maska ​​bitowa, reprezentowana jako postać. Rozwiązany wektor orientacji jest zdefiniowany jako wektor zerowy.
  • I - różne zwroty akcji, w kolejności, w jakiej są usuwane z przestrzeni wyszukiwania.
  • G- grupy permutacji skrętnych, przechowywane jako pary do zamiany. Każdy bajt w skompresowanym ciągu koduje jedną parę. Każdy zwrot wymaga sześciu zamian: trzech dla cyklu krawędzi i trzech dla cyklu narożnego. Skompresowany ciąg zawiera tylko ascii do wydruku (znaki od 32 do 126).
  • M - funkcja, która wykonuje ruch, nadana przez G.
  • N - konwertuje permutację czterech obiektów na liczbę w celu kodowania.
  • H - oblicza wartość heurystyczną dla danego stanu kostki, używaną do wyszukiwania głębokości ruchu z T.
  • P - wykonać wyszukiwanie na jednej głębokości pojedynczej fazy algorytmu.
  • s - stan permutacji kostki wejściowej.
  • o - wektor orientacji sześcianu wejściowego.

Wydajność

Korzystając ze zbioru danych Tomasa Rokickiego , skrypt ten uśredniał średnio 16,02 skrętu na rozwiązanie (maksymalnie 35), przy średnim czasie 472 ms (procesor i5-3330 przy 3,0 Ghz, PyPy 1.9.0). Minimalny czas rozwiązania wynosił 233 ms, maksymalnie 2,97 s, odchylenie standardowe 0,488. Przy zastosowaniu wytycznych punktacji z konkursu (białe znaki nie są liczone, słowa kluczowe i identyfikatory liczone są jako jeden bajt o długości 870), ogólny wynik wyniósłby 13,549.

W ostatnich 46 przypadkach (stany losowe) uśredniono 30,83 skrętów na rozwiązanie, przy średnim czasie wynoszącym 721 ms.

Uwagi na temat algorytmu Thistlethwaite

Dla korzyści każdego, kto może chcieć wdrożyć algorytm Thistlethwaite , oto krótkie wyjaśnienie.

Algorytm działa na bardzo prostej zasadzie redukcji przestrzeni rozwiązania. Oznacza to, że zredukuj sześcian do stanu, w którym podzbiór skrętów nie jest konieczny do jego rozwiązania, zredukuj go do mniejszej przestrzeni rozwiązania, a następnie rozwiązuj resztę, używając tylko kilku pozostałych skrętów.

Thistlethwaite pierwotnie sugerował <L,R,F,B,U,D>→ <L,R,F,B,U2,D2>→ <L,R,F2,B2,U2,D2>→ <L2,R2,F2,B2,U2,D2>. Jednak biorąc pod uwagę format wejściowy, myślę, że łatwiej jest najpierw zredukować do <L,R,F2,B2,U,D>(nie ćwierć obrotu Flub B), a następnie <L2,R2,F2,B2,U,D>, zanim ostatecznie osiągając stan pół skrętu. Zamiast dokładnie wyjaśniać, dlaczego tak jest, myślę, że stanie się to oczywiste po zdefiniowaniu kryteriów dla każdego stanu.

<L,R,F,B,U,D> ⇒ <L,R,F2,B2,U,D>

Aby wyeliminować Fi Bćwierć obrotu, tylko krawędzie muszą być odpowiednio ustawione. Gilles Roux ma bardzo dobre wyjaśnienie na swojej stronie, czym jest „poprawna” i „niepoprawna” orientacja, więc wyjaśnię mu to. Ale w zasadzie, (i dlatego ten format wejściowy jest więc dysponujące na Fi Beliminacja), cubie krawędź jest poprawnie zorientowany jeśli pasuje następujące wyrażenia regularnego: [^RL][^UD]. Prawidłowa orientacja jest zwykle oznaczana przez a, 0a niepoprawna przez 1. Zasadniczo Ui Dnalepki nie może znajdować się na Ralbo Ltwarzy lub na krawędziach żadnej Ulub Dkrawędzi cubies lub nie mogą być przeniesione do miejsca, bez konieczności FlubB ćwierć obrotu.

<L,R,F2,B2,U,D> ⇒ <L2,R2,F2,B2,U,D>

Tutaj dwa kryteria. Po pierwsze, wszystkie narożniki muszą być odpowiednio ustawione, a po drugie, każde z myślą o średnich cubies warstwa ( FR, FL, BR, BL) musi być gdzieś w środkowej warstwie. Orientacja narożnika jest bardzo prosta, biorąc pod uwagę format wejściowy: położenie pierwszego Ulub D. Na przykład URBma orientację 0(poprawnie zorientowaną), LDFma orientację 1i LFUma orientację 2.

<L2,R2,F2,B2,U,D> ⇒ <L2,R2,F2,B2,U2,D2>

Kryteria są następujące: każda twarz może zawierać tylko naklejki z jej twarzy lub z twarzy bezpośrednio naprzeciwko. Na przykład, na Utwarzy nie może być tylko Ui Dnaklejki na Rtwarzy może być tylko Ri Lnaklejki na Ftwarzy może być tylko Fi Bnaklejki itp Najprostszym sposobem zapewnienia tego jest, aby sprawdzić, czy każdy kawałek jest w krawędź jego „plasterek” i każdy narożny element na „orbicie”. Ponadto należy zwrócić uwagę na parytet narożny. Chociaż, jeśli sprawdzasz tylko parzystość narożnika, parzystość krawędzi jest również gwarantowana i odwrotnie.

Jak zwroty wpływają na orientację

Ua Dskręty nie wpływają ani na orientację krawędzi, ani na orientację narożną. Kawałki mogą być zamieniane bezpośrednio bez aktualizacji wektora orientacji.

Ri Lskręty nie wpływają na orientację krawędzi, ale wpływają na orientację narożnika. W zależności od tego, jak zdefiniujesz swój cykl, zmiana orientacji narożnika będzie albo, +1, +2, +1, +2albo +2, +1, +2, +1cały modulo 3. Należy pamiętać, że R2i L2skręty nie wpływają na orientację rożnego, jak +1+2jest zero modulo 3, jak jest +2+1.

Fi Bwpływają zarówno na orientacje krawędzi, jak i orientacje narożników. Orientacje krawędzi stają się +1, +1, +1, +1(mod 2), a orientacje narożników są takie same jak dla Ri L. Należy pamiętać, że F2i B2wpływa ani kierunki krawędzi, ani orientacje rożny.

primo
źródło
Świetny opis. Czy słyszałeś o algorytmie Kociemby?
mile
Mam. Zasadniczo jest to ten sam algorytm, ale zamiast czterech faz ma tylko dwie: <L,R,F,B,U,D>-> <L2,R2,F2,B2,U,D>-> <I>. Wymaga maksymalnie 29 zwrotów akcji, aby rozwiązać sześcian (zamiast 52 dla Thistlethwaite), ale wymaga również bardzo dużych tabel odnośników, których generowanie „w locie” byłoby niepraktyczne.
primo
@ P0W format wejściowy jest nieco mylący, podejrzewam, że wystąpił tam błąd. Każda weryfikowana przeze mnie sprawa daje rozwiązanie.
primo,
@primo Czy mógłbyś opublikować link do kodu nie golfowego, jeśli go posiadasz?
Bilow
12

Ruby, 742 znaków

r=->y{y.split.map{|x|[*x.chars]}}
G=r['UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR']
o=r[gets]
x=[];[[%w{U UU UUU L LL LLL}+D=%w{D DD DDD},0],[%w{FDFFF RFDFFFRRR}+D,12],[%w{DDDRRRDRDFDDDFFF DLDDDLLLDDDFFFDF}+D,8],[%w{DFLDLLLDDDFFF RDUUUFDUUULDUUUBDUUU}+D,4],[%w{LDDDRRRDLLLDDDRD RRRDLDDDRDLLLDDD LFFFLLLFLFFFLLLF},16]].map{|q,y|x+=[*y..y+3]
3.times{q.map{|e|q|=[e.tr('LFRB','FRBL')]}}
w=->u{x.count{|t|u[t]!=G[t]}}
s=w[o]
(c=(0..rand(12)).map{q.sample}*''
z=o
c.chars{|m|z="=$'*:036\".?BOHKVGRWZ!$@*-0C69<4(E\\INQTMX!$'B-03<9*?6EHYLQPUZ!9'*-?360<$BSFKN[TWJ$'*!-0369<?BHKNEQTWZ!$'*6-039<?BEHKNTWZQ"[20*('FBLRUD'=~/#{m}/),20].bytes.map{|e|z[e/3-11].rotate e%3}}
t=w[z]
(c.chars{|e|$><<e<<'1 '};o=z;s=t)if s>t
)until s<1}

Powyższy kod ruby ​​nie jest jeszcze w pełni zagrany w golfa. Nadal istnieją możliwości dalszej poprawy kodu (ale już wystarcza jako starter).

Rozwiązuje kostkę warstwa po warstwie, ale nie używa żadnego konkretnego algorytmu, ale zamiast tego wykonuje losowe sekwencje ruchów, aż kostka zostanie rozwiązana.

Ze względu na charakter probabilistyczny rozwiązanie kostki może czasem potrwać dłużej niż 5 sekund, aw rzadkich przypadkach może zająć więcej niż 1000 ruchów.

Przykładowy wynik (dla wejścia „RU LF UB DR DL BL UL FU BD RF BR FD LDF LBD FUL RFD UFR RDB UBL RBU”) wynosi 757 ruchów:

F1 R1 R1 F1 F1 F1 R1 R1 R1 L1 L1 L1 F1 D1 L1 L1 D1 D1 D1 D1 L1 B1 D1 
B1 B1 B1 L1 L1 L1 F1 D1 F1 F1 F1 L1 D1 L1 L1 L1 B1 D1 B1 B1 B1 R1 D1 
R1 R1 R1 L1 B1 D1 B1 B1 B1 L1 L1 L1 D1 D1 B1 D1 B1 B1 B1 B1 D1 B1 B1 
B1 L1 D1 L1 L1 L1 D1 D1 D1 D1 D1 R1 D1 R1 R1 R1 R1 F1 D1 F1 F1 F1 R1 
R1 R1 R1 D1 R1 R1 R1 F1 L1 D1 L1 L1 L1 F1 F1 F1 D1 D1 D1 D1 L1 D1 L1 
L1 L1 F1 L1 D1 L1 L1 L1 F1 F1 F1 D1 D1 L1 D1 L1 L1 L1 D1 L1 D1 L1 L1 
L1 L1 D1 L1 L1 L1 D1 R1 D1 D1 D1 R1 R1 R1 D1 D1 D1 B1 B1 B1 D1 B1 D1 
L1 D1 D1 D1 L1 L1 L1 D1 D1 D1 F1 F1 F1 D1 F1 D1 D1 D1 B1 B1 B1 D1 B1 
D1 R1 D1 D1 D1 R1 R1 R1 D1 D1 D1 B1 B1 B1 D1 B1 D1 R1 D1 D1 D1 R1 R1 
R1 D1 B1 D1 D1 D1 B1 B1 B1 D1 D1 D1 L1 L1 L1 D1 L1 D1 B1 D1 D1 D1 B1 
B1 B1 D1 D1 D1 L1 L1 L1 D1 L1 D1 D1 F1 D1 D1 D1 F1 F1 F1 D1 D1 D1 R1 
R1 R1 D1 R1 D1 D1 D1 R1 R1 R1 D1 R1 D1 F1 D1 D1 D1 F1 F1 F1 D1 B1 D1 
D1 D1 B1 B1 B1 D1 D1 D1 L1 L1 L1 D1 L1 D1 D1 D1 F1 F1 F1 D1 F1 D1 L1 
D1 D1 D1 L1 L1 L1 D1 D1 D1 D1 D1 D1 F1 F1 F1 D1 F1 D1 L1 D1 D1 D1 L1 
L1 L1 D1 D1 D1 F1 F1 F1 D1 F1 D1 L1 D1 D1 D1 L1 L1 L1 D1 F1 D1 D1 D1 
F1 F1 F1 D1 D1 D1 R1 R1 R1 D1 R1 D1 D1 D1 F1 F1 F1 D1 F1 D1 L1 D1 D1 
D1 L1 L1 L1 D1 D1 D1 F1 F1 F1 D1 F1 D1 L1 D1 D1 D1 L1 L1 L1 D1 D1 D1 
D1 D1 F1 F1 F1 D1 F1 D1 L1 D1 D1 D1 L1 L1 L1 D1 D1 D1 D1 D1 D1 R1 F1 
D1 F1 F1 F1 D1 D1 D1 R1 R1 R1 D1 F1 L1 D1 L1 L1 L1 D1 D1 D1 F1 F1 F1 
D1 B1 R1 D1 R1 R1 R1 D1 D1 D1 B1 B1 B1 D1 B1 R1 D1 R1 R1 R1 D1 D1 D1 
B1 B1 B1 D1 D1 D1 D1 B1 R1 D1 R1 R1 R1 D1 D1 D1 B1 B1 B1 D1 D1 D1 D1 
D1 D1 B1 B1 B1 D1 F1 D1 D1 D1 B1 D1 F1 F1 F1 D1 D1 D1 R1 R1 R1 D1 L1 
D1 D1 D1 R1 D1 L1 L1 L1 D1 D1 D1 B1 D1 D1 D1 F1 F1 F1 D1 B1 B1 B1 D1 
D1 D1 F1 D1 B1 B1 B1 D1 F1 D1 D1 D1 B1 D1 F1 F1 F1 D1 D1 D1 L1 D1 D1 
D1 R1 R1 R1 D1 L1 L1 L1 D1 D1 D1 R1 D1 F1 R1 R1 R1 F1 F1 F1 R1 F1 R1 
R1 R1 F1 F1 F1 R1 R1 R1 R1 D1 L1 D1 D1 D1 R1 D1 L1 L1 L1 D1 D1 D1 B1 
B1 B1 D1 F1 D1 D1 D1 B1 D1 F1 F1 F1 D1 D1 D1 F1 R1 R1 R1 F1 F1 F1 R1 
F1 R1 R1 R1 F1 F1 F1 R1 F1 D1 D1 D1 B1 B1 B1 D1 F1 F1 F1 D1 D1 D1 B1 
D1 F1 R1 R1 R1 F1 F1 F1 R1 F1 R1 R1 R1 F1 F1 F1 R1 F1 F1 F1 D1 B1 D1 
D1 D1 F1 D1 B1 B1 B1 D1 D1 D1 R1 D1 D1 D1 L1 L1 L1 D1 R1 R1 R1 D1 D1 
D1 L1 D1 R1 R1 R1 D1 L1 D1 D1 D1 R1 D1 L1 L1 L1 D1 D1 D1 R1 D1 D1 D1 
L1 L1 L1 D1 R1 R1 R1 D1 D1 D1 L1 D1 F1 F1 F1 D1 B1 D1 D1 D1 F1 D1 B1 
B1 B1 D1 D1 D1 L1 L1 L1 D1 R1 D1 D1 D1 L1 D1 R1 R1 R1 D1 D1 D1

Możliwe jest znaczne zmniejszenie liczby ruchów, jeśli te same ruchy zostaną zgrupowane razem. Dlatego można zastąpić dane wyjściowe jak

(c.gsub(/(.)\1*/){j=$&.size%4;$><<$1<<j<<' 'if j>0};o=z;s=t)if s>t
Howard
źródło
Fajnie, ale czasami zajmuje to więcej niż 20 sekund na moim komputerze, w jednym przypadku skończyło się w 48,7 sekundy
aditsu
@aditsu Tak. Ale zależy to również silnie od tego, jakiego interpretera ruby ​​używasz. Na moim komputerze zwykle zajmuje to mniej niż 5 sekund.
Howard
Obecnie używam ruby 1.9.3_p392, często zajmuje to mniej niż 5 sekund, ale nie mogę powiedzieć „zwykle”
aditsu
Spróbuj tego:FU FR RU BR DB LD LU LB LF RD DF BU FRU BUR FDR DLB DFL LUB FUL DBR
aditsu
Jedna prośba: czy możesz skonsolidować sekwencje jak U1 U1 U1w jeden U3?
primo,