Resolver o cubo de Rubik

Escreva o programa mais curto que resolva o cubo de Rubik (3 * 3 * 3) dentro de um período de tempo e movimentos razoável (digamos, no máximo 5 segundos em sua máquina e menos de 1000 movimentos).

A entrada está no formato:

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

(essa entrada específica representa o cubo resolvido).
As primeiras 12 seqüências de caracteres de 2 caracteres são as arestas nas posições UF, UR, ... BL (U = para cima, F = frente, R = direita, B = atrás, L = esquerda, D = baixo), depois as próximas 8 Seqüências de caracteres de 3 caracteres são os cantos nas posições UFR, URB, ... DBR.

A saída deve fornecer uma sequência de movimentos neste formato:

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

Onde D1 ou D + representa girar a face D (para baixo) no sentido horário 90 graus, L2 está girando a face L 180 graus, U3 ou U- representa girar a face U no sentido anti-horário 90 graus.
As letras não diferenciam maiúsculas de minúsculas e os espaços são opcionais.

Por exemplo, a saída acima está correta para a seguinte entrada:

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

Para mais detalhes, consulte o concurso de cubos de Tomas Rokicki , exceto que a pontuação será feita diretamente pelo tamanho do arquivo, como um problema normal de golfe no código. Um testador online também está incluído.

Para referência, a solução mais curta já escrita é a última entrada na lista de vencedores do concurso de cubos

Para aqueles que lutam para visualizar o formato do layout:

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
fonte

Idiomas diferentes de C / C ++ / Java / Perl / Python são aceitos?

Egor Skriptunoff 31 /

@EgorSkriptunoff Aqui sim, use o que quiser, apenas nenhuma biblioteca de solução de cubos.

Aditsu 12/03/2013

E quanto à pontuação? Pontuação usual de código-golfe (bytes no programa) ou pontuação complexa como no concurso de 2004?

Egor Skriptunoff 31 /

@jdstankosky, adicionei um diagrama.

Peter Taylor

Podemos retirar os adesivos e movê-los?

Iszi

Respostas:

C ++ - 1123

Como ninguém postou nenhuma resposta até agora, decidi simplificar e usar a minha solução de 2004. Ainda está muito atrás do mais curto que mencionei na pergunta.

#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}}

Não é aleatório, mas também não é direto. Ele resolve as bordas primeiro e depois os cantos. Em cada etapa, ele tenta várias combinações de até 4 algoritmos e giros simples de faces (sequencialmente, não aleatoriamente), até encontrar uma melhoria no número de peças resolvidas e depois repetir até ser resolvido. Ele usa 2 algoritmos para arestas e 2 para cantos, traduzidos para todas as posições do cubo.

Exemplo de saída para RU LF UB DR DL BL UL FU BD RF BR FD LDF LBD FUL RFD UFR RDB UBL RBU:

L2F3B2F3B1U3F1B3R2F3B1U3F1B3D2F2L3D2L1U2B1L1R3U2R1L3B1U2R1U2L1F1B3U2B1F3L1U2L3R1D3L1R3B2L3R1D3L1R3L3R1D3L1R3B2L3R1D3L1R3B3F1D3B1F3R2B3F1D3B1F3U2F3L3R1B3L1R3U2L3R1B3L1R3F1D2F1L1R3D2R1L3F1D2F3L2U1B1F3L2F1B3U1L2R3L1F3R1L3U2R3L1F3R1L3U1F2U1L1R3F2R1L3U1F2U3L3U3L1U3L3U2L1R1U1R3U1R1U2R3F3U3F1U3F3U2F1B1U1B3U1B1U2B3L1B3R3B1L3B3R1B1B3D3B1D3B3D2B1F1D1F3D1F1D2F3R1F3L3F1R3F3L1F1R3B3R1B3R3B2R1L1B1L3B1L1B2L3R1D3L3D1R3D3L1D1B3D3B1D3B3D2B1F1D1F3D1F1D2F3U3R3U1R3U3R2U1D1R1D3R1D1R2D3

(234 movimentos, 0,3 s aqui)

aditsu
fonte

O que você sabe ... outra resposta foi postada em segundos :)

aditsu

Embora isso seja mais longo que a solução Ruby, acho que ela se encaixa melhor nos critérios do problema "dentro de um período de tempo razoável e se move". Eu ainda gostaria de ver uma solução que calcula a média de menos de 50 movimentos.

Primo

@primo Obrigado :) Meu código original teve uma média de mais de 50 movimentos, para menos de 50 acho que você precisa de mais algoritmos (cubos) ou de uma abordagem diferente, como o método de Thistlethwaite. No entanto, a eficiência (no número de jogadas) não é muito compatível com o golfe. De qualquer forma, para soluções alternativas, confira os vencedores do concurso de Tomas Rokicki.

Aditsu 20/03/2013

Python 1166 bytes

Uma quantidade considerável de espaço em branco foi deixada para facilitar a leitura. Tamanho é medido depois de remover este espaço em branco, e alterando vários níveis de recuo para Tab, Tab Space, Tab Tab, etc. Eu também evitou qualquer golfe que afetou o desempenho muito drasticamente.

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

Uso da amostra:

$ 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

Esta é uma implementação do algoritmo de Thistlethwaite, usando uma pesquisa IDA * para resolver cada etapa. Como todas as tabelas heurísticas precisam ser calculadas em tempo real, vários compromissos foram feitos, geralmente dividindo uma heurística em duas ou mais partes de tamanho relativamente igual. Isso torna o cálculo das tabelas heurísticas muitas centenas de vezes mais rápido, enquanto diminui a fase de pesquisa, geralmente apenas um pouco, mas pode ser significativo dependendo do estado inicial do cubo.

Índice variável

T - a tabela heurística principal.
S- um estado de cubo resolvido. Cada peça individual é armazenada como uma máscara de bits, representada como um personagem. Um vetor de orientação resolvido é definido como o vetor zero.
I - as várias reviravoltas, na ordem em que são eliminadas do espaço de pesquisa.
G- os grupos para permutações de torção, armazenados como pares a serem trocados. Cada byte na cadeia compactada codifica para um par. Cada torção precisa de seis swaps: três para o ciclo de borda e três para o ciclo de canto. A cadeia compactada contém apenas ascii imprimíveis (caracteres 32 a 126).
M - uma função que executa um movimento, dada por G.
N - converte uma permutação de quatro objetos em um número, para fins de codificação.
H - calcula o valor heurístico para o estado do cubo fornecido, usado para procurar a profundidade do movimento de T.
P - faça uma pesquisa em uma única profundidade de uma única fase do algoritmo.
s - o estado de permutação do cubo de entrada.
o - o vetor de orientação do cubo de entrada.

atuação

Usando o conjunto de dados de Tomas Rokicki , esse script teve uma média de 16,02 voltas por solução (máximo de 35), com um tempo médio de 472ms (CPU i5-3330 a 3,0 Ghz, PyPy 1.9.0). O tempo mínimo de resolução foi de 233ms, com um máximo de 2,97s, desvio padrão de 0,488. Usando as diretrizes de pontuação do concurso (o espaço em branco não é contado, as palavras-chave e os identificadores contam como um byte, com um comprimento de 870), a pontuação geral seria de 13.549.

Nos últimos 46 casos (os estados aleatórios), a média foi de 30,83 voltas por resolução, com um tempo médio de 721ms.

Notas sobre o algoritmo de Thistlethwaite

Para o benefício de qualquer pessoa que queira tentar uma implementação do Algoritmo de Thistlethwaite , aqui está uma breve explicação.

O algoritmo trabalha com um princípio muito simples de redução de espaço da solução. Ou seja, reduza o cubo para um estado em que um subconjunto de torções não seja necessário para resolvê-lo, reduza-o para um espaço de solução menor e, em seguida, resolva o restante usando apenas as poucas torções restantes.

Thistlethwaite sugeriu originalmente <L,R,F,B,U,D>→ <L,R,F,B,U2,D2>→ <L,R,F2,B2,U2,D2>→ <L2,R2,F2,B2,U2,D2>. No entanto, dado o formato de entrada, acho que é mais fácil reduzir para <L,R,F2,B2,U,D>(sem quarto de volta Fou B) e depois <L2,R2,F2,B2,U,D>antes de finalmente chegar ao estado de meia volta. Em vez de explicar exatamente por que isso ocorre, acho que ficará evidente após a definição dos critérios para cada estado.

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

Para eliminar Fe Bgirar em quartos de volta, apenas as bordas devem ser orientadas corretamente. Gilles Roux tem uma explicação muito boa em seu site sobre o que é a orientação 'correta' e 'incorreta', então deixarei a explicação para ele. Mas, basicamente, (e é por isso que este formato de entrada é tão propício para fazer Fe Beliminação), um cubinho borda esteja orientado corretamente se ele corresponde a seguinte regex: [^RL][^UD]. Uma orientação correta é tipicamente significada com a 0e incorreta com 1. Basicamente Ue Dadesivos podem não aparecer no Rou Lcaras, ou sobre os bordos das eventuais Uou Dborda cubinhos, ou eles podem não ser movido no lugar sem a necessidade de uma FouB torção de um quarto.

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

Dois critérios aqui. Em primeiro lugar, todos os cantos devem ser correctamente orientado, e em segundo lugar, cada um dos para cubinhos camada do meio ( FR, FL, BR, BL) tem de ser em algum lugar na camada do meio. Uma orientação de canto é definida com muita simplicidade, dado o formato de entrada: a posição do primeiro Uou D. Por exemplo, URBtem orientação 0(orientada corretamente), LDFtem orientação 1e LFUtem orientação 2.

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

Os critérios aqui são os seguintes: cada rosto pode conter apenas adesivos de seu rosto ou do rosto diretamente oposto a ele. Por exemplo, no Urosto pode haver apenas Ue Dadesivos, no Rrosto pode haver apenas Re Ladesivos, no Frosto pode haver apenas Fe Badesivos, etc. A maneira mais fácil de garantir isso é para verificar se cada aresta está em sua 'fatia' e cada peça de canto em sua 'órbita'. Além disso, é preciso prestar atenção à paridade dos cantos da borda. Embora, se você verificar apenas a paridade de canto, a paridade de borda também será garantida e vice-versa.

Como as torções afetam a orientação

Ue Dtorções não afetam nem a orientação da aresta nem a orientação do canto. As peças podem ser trocadas diretamente sem atualizar o vetor de orientação.

Re Ltorções não afetam a orientação da aresta, mas afetam a orientação do canto. Dependendo de como você define seu ciclo, a mudança na orientação do canto será +1, +2, +1, +2ou +2, +1, +2, +1, todo o módulo 3. Observe que torções R2e L2não afetam a orientação do canto, como +1+2é o módulo zero 3, como é +2+1.

Fe Bafeta as orientações da aresta e as dos cantos. As orientações da aresta se tornam +1, +1, +1, +1(mod 2), e as orientações dos cantos são as mesmas que para Re L. Observe que F2e B2não afeta as orientações da borda nem as orientações dos cantos.

primo
fonte

Ótima redação. Você já ouviu falar do algoritmo de Kociemba?

miles

Eu tenho. Em princípio, é o mesmo algoritmo, exceto que, em vez de quatro fases, ele possui apenas duas: <L,R,F,B,U,D>-> <L2,R2,F2,B2,U,D>-> <I>. Requer um máximo de 29 torções para resolver um cubo (em vez de 52 para o de Thistlethwaite), mas também exige tabelas de pesquisa muito grandes, o que seria impraticável para gerar 'on the fly'.

Primo 27/03

@ P0W o formato de entrada é um pouco confuso, eu suspeito que você pode ter um erro lá. Em todos os casos, verifiquei os resultados em uma solução.

Primo

@primo Você se importaria de publicar um link para o código que não seja de golfe, se o tiver?

Bilow

Ruby, 742 caracteres

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}

O código rubi acima ainda não foi totalmente jogado. Ainda há possibilidades de melhorar ainda mais o código (mas já é suficiente como iniciante).

Ele resolve a camada do cubo por camada, mas não usa algoritmo específico, mas executa sequências aleatórias de movimentos até que o cubo seja resolvido.

Devido à natureza probabilística, às vezes, pode demorar mais de 5 segundos para resolver o cubo e, em casos raros, são necessários mais de 1000 movimentos.

A saída de exemplo (para a entrada 'RU LF UB DR DL BL UL FU BD RF BR FD LDF LBD FUL RFD UFR RDB UBL RBU') é 757 movimentos:

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

É possível reduzir a contagem de movimentos consideravelmente se os mesmos movimentos forem agrupados. Portanto, pode-se substituir a saída como

(c.gsub(/(.)\1*/){j=$&.size%4;$><<$1<<j<<' 'if j>0};o=z;s=t)if s>t

Howard
fonte

Bom, mas às vezes leva mais de 20 segundos no meu computador, em um caso que terminou em 48,7 seg

aditsu

@aditsu Sim. Mas isso também depende fortemente de qual intérprete de rubi você usa. Na minha máquina, geralmente leva menos de 5 segundos.

21913 Howard Howard

Atualmente estou usando ruby 1.9.3_p392, que muitas vezes leva menos de 5 segundos, mas não posso dizer "normalmente"

aditsu

Tente esta entrada:FU FR RU BR DB LD LU LB LF RD DF BU FRU BUR FDR DLB DFL LUB FUL DBR

aditsu 19/03/2013

Uma solicitação: você poderia consolidar sequências como U1 U1 U1em uma única U3?

Primo

Resolver o cubo de Rubik

Respostas:

C ++ - 1123

Python 1166 bytes

Índice variável

atuação

Notas sobre o algoritmo de Thistlethwaite

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

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

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

Como as torções afetam a orientação

Ruby, 742 caracteres

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

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

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