Pecahkan kubus Rubik

38

Tulis program terpendek yang memecahkan kubus Rubik (3 * 3 * 3) dalam waktu dan gerakan yang wajar (katakanlah, maks. 5 detik pada mesin Anda dan kurang dari 1000 gerakan).

Input dalam format:

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

(input khusus ini mewakili kubus yang diselesaikan).
12 string 2-karakter pertama adalah tepi dalam posisi UF, UR, ... BL (U = atas, F = depan, R = kanan, B = belakang, L = kiri, D = bawah), kemudian 8 berikutnya String 3-karakter adalah sudut-sudut dalam posisi UFR, URB, ... DBR.

Output harus memberikan urutan gerakan dalam format ini:

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

Di mana D1 atau D + mewakili memutar wajah D (bawah) searah jarum jam 90 derajat, L2 memutar wajah L 180 derajat, U3 atau U- mewakili memutar wajah U berlawanan arah 90 derajat.
Huruf tidak peka huruf besar-kecil dan spasi opsional.

Misalnya, output di atas benar untuk input berikut:

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

Untuk detail lebih lanjut, silakan merujuk ke kontes kubus Tomas Rokicki , kecuali penilaian akan dilakukan secara langsung berdasarkan ukuran file seperti masalah kode golf normal. Penguji online juga disertakan.

Sebagai referensi, solusi terpendek yang sudah ditulis adalah entri terakhir dalam daftar pemenang kontes kubus

Bagi mereka yang kesulitan memvisualisasikan format tata letak:

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
sumber
3
Apakah bahasa selain C / C ++ / Java / Perl / Python diterima?
Egor Skriptunoff
@EgorSkriptunoff Di sini ya, gunakan apa pun yang Anda suka, hanya saja tidak ada perpustakaan yang memecahkan kubus.
aditsu
Dan bagaimana dengan mencetak gol? Penilaian kode-golf biasa (byte dalam program) atau penilaian kompleks seperti pada kontes 2004?
Egor Skriptunoff
2
@ jdstankosky, saya telah menambahkan diagram.
Peter Taylor
7
Apakah kita boleh melepas stiker dan memindahkannya?
Iszi

Jawaban:

25

C ++ - 1123

Karena tidak ada yang diposting jawaban sejauh ini, saya memutuskan untuk menyederhanakan dan golf solusi 2004 saya. Masih jauh di belakang yang terpendek yang saya sebutkan dalam pertanyaan.

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

Ini tidak acak, tetapi juga tidak berjalan dengan mudah. Ini memecahkan tepi pertama, lalu sudut. Pada setiap langkah, ia mencoba berbagai kombinasi hingga 4 algoritma dan pergantian wajah sederhana (secara berurutan, bukan secara acak), hingga menemukan peningkatan dalam jumlah potongan yang dipecahkan, kemudian diulang hingga terpecahkan. Ini menggunakan 2 algoritma untuk tepi dan 2 untuk sudut, diterjemahkan ke semua posisi kubus.

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

L2F3B2F3B1U3F1B3R2F3B1U3F1B3D2F2L3D2L1U2B1L1R3U2R1L3B1U2R1U2L1F1B3U2B1F3L1U2L3R1D3L1R3B2L3R1D3L1R3L3R1D3L1R3B2L3R1D3L1R3B3F1D3B1F3R2B3F1D3B1F3U2F3L3R1B3L1R3U2L3R1B3L1R3F1D2F1L1R3D2R1L3F1D2F3L2U1B1F3L2F1B3U1L2R3L1F3R1L3U2R3L1F3R1L3U1F2U1L1R3F2R1L3U1F2U3L3U3L1U3L3U2L1R1U1R3U1R1U2R3F3U3F1U3F3U2F1B1U1B3U1B1U2B3L1B3R3B1L3B3R1B1B3D3B1D3B3D2B1F1D1F3D1F1D2F3R1F3L3F1R3F3L1F1R3B3R1B3R3B2R1L1B1L3B1L1B2L3R1D3L3D1R3D3L1D1B3D3B1D3B3D2B1F1D1F3D1F1D2F3U3R3U1R3U3R2U1D1R1D3R1D1R2D3

(234 bergerak, 0,3 detik di sini)

aditsu
sumber
2
Apa yang Anda ketahui ... jawaban lain telah diposting dalam hitungan detik :)
aditsu
Meskipun ini lebih panjang daripada solusi Ruby, saya merasa lebih cocok dengan kriteria masalah "dalam jumlah waktu dan langkah yang wajar." Saya masih ingin melihat solusi yang rata-rata di bawah ~ 50 bergerak.
Primo
2
@rimo Terima kasih :) Kode asli saya rata-rata lebih dari 50 bergerak, untuk di bawah 50 saya pikir Anda memerlukan lebih banyak algoritma (kubus) atau pendekatan yang berbeda seperti metode Thistlethwaite. Namun, efisiensi (tidak ada gerakan) tidak sangat kompatibel dengan golf. Bagaimanapun, untuk solusi alternatif, periksa pemenang kontes Tomas Rokicki.
aditsu
23

Python 1166 byte

Sejumlah besar ruang kosong telah ditinggalkan demi keterbacaan. Ukuran diukur setelah menghapus spasi ini, dan mengubah berbagai tingkat lekukan Tab, Tab Space, Tab Tab, dll saya juga menghindari setiap golf yang mempengaruhi kinerja terlalu drastis.

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

Penggunaan sampel:

$ 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

Ini adalah implementasi dari Algoritma Thistlethwaite, menggunakan pencarian IDA * untuk menyelesaikan setiap langkah. Karena semua tabel heuristik perlu dihitung dengan cepat, beberapa kompromi telah dibuat, biasanya memecah heuristik menjadi dua atau lebih bagian ukuran yang cukup sama. Ini membuat perhitungan tabel heuristik ratusan kali lebih cepat, sementara memperlambat fase pencarian, biasanya hanya sedikit, tetapi ini bisa signifikan tergantung pada keadaan kubus awal.

Indeks Variabel

  • T - tabel heuristik utama.
  • S- Keadaan kubus yang terpecahkan. Setiap bagian disimpan sebagai bit mask, direpresentasikan sebagai karakter. Vektor orientasi yang diselesaikan didefinisikan sebagai vektor nol.
  • I - berbagai tikungan, dalam urutan bahwa mereka dihilangkan dari ruang pencarian.
  • G- grup untuk permutasi twist, disimpan sebagai pasangan untuk ditukar. Setiap byte dalam string terkompresi mengkodekan untuk satu pasangan. Setiap putaran membutuhkan enam swap: tiga untuk siklus tepi, dan tiga untuk siklus sudut. String yang dikompresi hanya berisi ascii yang dapat dicetak (char 32 hingga 126).
  • M - fungsi yang melakukan gerakan, yang diberikan oleh G.
  • N - Mengonversi permutasi dari empat objek ke angka, untuk tujuan pengkodean.
  • H - Menghitung nilai heuristik untuk keadaan kubus yang diberikan, digunakan untuk mencari kedalaman gerakan dari T.
  • P - Melakukan pencarian pada kedalaman satu fase tunggal dari algoritma.
  • s - Keadaan permutasi masukan kubus.
  • o - vektor orientasi kubus input.

Performa

Menggunakan kumpulan data Tomas Rokicki , skrip ini rata-rata 16,02 tikungan per pemecahan (maksimum 35), dengan waktu rata-rata 472ms (i5-3330 CPU @ 3,0 Ghz, PyPy 1.9.0). Waktu penyelesaian minimum adalah 233 ms dengan maksimum 2,97, standar deviasi 0,488. Menggunakan pedoman penilaian dari kontes (spasi putih tidak dihitung, kata kunci dan pengidentifikasi dihitung sebagai satu byte untuk panjang 870), skor keseluruhan akan menjadi 13.549.

Untuk 46 kasus terakhir (keadaan acak), rata-rata 30,83 tikungan per penyelesaian, dengan waktu rata-rata 721 ms.

Catatan tentang Algoritma Thistlethwaite

Untuk kepentingan siapa saja yang mungkin ingin mencoba implementasi Algoritma Thistlethwaite , berikut adalah penjelasan singkatnya.

Algoritma ini bekerja pada prinsip reduksi ruang solusi yang sangat sederhana. Yaitu, kurangi kubus ke keadaan di mana subset putaran tidak diperlukan untuk menyelesaikannya, kurangi kubusnya menjadi ruang solusi yang lebih kecil, dan kemudian selesaikan sisanya menggunakan hanya beberapa putaran yang tersisa.

Thistlethwaite awalnya disarankan <L,R,F,B,U,D>→ <L,R,F,B,U2,D2>→ <L,R,F2,B2,U2,D2>→ <L2,R2,F2,B2,U2,D2>. Namun, mengingat format input, saya pikir lebih mudah untuk mengurangi dulu <L,R,F2,B2,U,D>(tidak ada seperempat putaran Fatau B), dan kemudian <L2,R2,F2,B2,U,D>sebelum akhirnya mencapai kondisi setengah putaran. Alih-alih menjelaskan mengapa ini terjadi, saya pikir itu akan menjadi jelas setelah mendefinisikan kriteria untuk setiap negara.

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

Untuk menghilangkan Fdan Bseperempat putaran, hanya bagian tepi yang harus diorientasikan dengan benar. Gilles Roux memiliki penjelasan yang sangat bagus di situsnya tentang apa orientasi 'benar' dan 'salah', jadi saya akan meninggalkan penjelasan kepadanya. Tapi pada dasarnya, (dan ini adalah mengapa format masukan ini sangat kondusif untuk Fdan Beliminasi), sebuah cubie tepi diorientasikan dengan benar apakah cocok dengan regex berikut: [^RL][^UD]. Orientasi yang benar biasanya ditandai dengan 0dan salah dengan 1. Pada dasarnya Udan Dstiker mungkin tidak muncul di Ratau pada Lwajah, atau di tepi kubik apa pun Uatau Dtepi, atau tidak dapat dipindahkan ke tempatnya tanpa memerlukan FatauB twist seperempat.

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

Dua kriteria di sini. Pertama, semua sudut harus berorientasi dengan benar, dan kedua, masing-masing untuk cubies lapisan tengah ( FR, FL, BR, BL) harus berada di suatu tempat di lapisan tengah. Orientasi sudut didefinisikan dengan sangat sederhana mengingat format input: posisi pertama Uatau D. Misalnya, URBmemiliki orientasi 0(berorientasi dengan benar), LDFmemiliki orientasi 1, dan LFUmemiliki orientasi 2.

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

Kriteria di sini adalah sebagai berikut: setiap wajah hanya boleh berisi stiker dari wajahnya, atau dari wajah yang berseberangan dengannya. Misalnya, di Uwajah mungkin hanya ada Udan Dstiker, di Rwajah mungkin hanya ada Rdan Lstiker, di Fwajah mungkin hanya ada Fdan Bstiker, dll. Cara termudah untuk memastikan ini adalah dengan memeriksa apakah masing-masing bagian tepi berada di 'irisan' nya, dan setiap potongan sudut di 'orbitnya'. Selain itu, orang perlu memperhatikan paritas tepi-sudut. Meskipun, jika Anda memeriksa paritas sudut saja, tepi paritas juga dijamin, dan sebaliknya.

Bagaimana tikungan memengaruhi orientasi

Udan Dtikungan tidak mempengaruhi orientasi tepi, maupun orientasi sudut. Potongan dapat ditukar secara langsung tanpa memperbarui vektor orientasi.

Rdan Ltikungan tidak mempengaruhi orientasi tepi, tetapi mereka mempengaruhi orientasi sudut. Bergantung pada bagaimana Anda mendefinisikan siklus Anda, perubahan orientasi sudut akan menjadi +1, +2, +1, +2atau +2, +1, +2, +1, semua modulo 3. Perhatikan bahwa R2dan L2tikungan tidak mempengaruhi orientasi sudut, seperti +1+2nol modulo 3, sebagaimana adanya +2+1.

Fdan Bmempengaruhi orientasi tepi dan orientasi sudut. Orientasi tepi menjadi +1, +1, +1, +1(mod 2), dan orientasi sudut sama dengan Rdan L. Perhatikan bahwa F2dan B2tidak mempengaruhi orientasi tepi, atau orientasi sudut.

primo
sumber
Langgan yang bagus. Pernahkah Anda mendengar tentang algoritma Kociemba?
mil
Saya sudah. Pada prinsipnya, ini adalah algoritma yang sama, kecuali alih-alih empat fase, ia hanya memiliki dua: <L,R,F,B,U,D>-> <L2,R2,F2,B2,U,D>-> <I>. Ini membutuhkan maksimum 29 tikungan untuk menyelesaikan kubus (bukan 52 untuk Thistlethwaite), tetapi juga membutuhkan tabel pencarian yang sangat besar, yang tidak praktis untuk menghasilkan 'on the fly'.
primo
@ P0W format input agak membingungkan, saya kira Anda mungkin memiliki kesalahan di sana. Setiap kasus saya telah memverifikasi hasil dalam solusi.
primo
@primo Apakah Anda keberatan menerbitkan tautan ke kode non-golf jika Anda memilikinya?
Bilow
12

Ruby, 742 karakter

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}

Kode ruby ​​di atas belum golf sepenuhnya. Masih ada kemungkinan untuk meningkatkan kode lebih lanjut (tetapi sudah cukup sebagai starter).

Ini memecahkan lapisan kubus demi lapisan tetapi tidak menggunakan algoritma khusus tetapi sebaliknya melakukan urutan bergerak secara acak sampai kubus diselesaikan.

Karena sifatnya yang probabilistik, kadang-kadang dibutuhkan waktu lebih dari 5 detik untuk menyelesaikan kubus dan dalam kasus yang jarang diperlukan lebih dari 1000 gerakan.

Contoh output (untuk input 'RU LF UB DR DL BL UL FU BD RF BR FD LDF LBD FUL RFD UFR, RDB, UBL RBU') adalah 757 gerakan:

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

Dimungkinkan untuk mengurangi jumlah langkah secara signifikan jika gerakan yang sama dikelompokkan bersama. Karena itu, seseorang dapat mengganti output seperti

(c.gsub(/(.)\1*/){j=$&.size%4;$><<$1<<j<<' 'if j>0};o=z;s=t)if s>t
Howard
sumber
Bagus, tapi kadang-kadang dibutuhkan lebih dari 20 detik di komputer saya, dalam satu kasus selesai dalam 48,7 detik
aditsu
@aditsu Ya. Tapi itu juga sangat tergantung pada interpreter ruby ​​mana yang Anda gunakan. Di komputer saya biasanya membutuhkan waktu kurang dari 5 detik.
Howard
Saat ini saya menggunakan ruby 1.9.3_p392, seringkali membutuhkan waktu kurang dari 5 detik tetapi saya tidak bisa mengatakan "biasanya"
aditsu
Coba masukan ini:FU FR RU BR DB LD LU LB LF RD DF BU FRU BUR FDR DLB DFL LUB FUL DBR
aditsu
Satu permintaan: dapatkah Anda menggabungkan urutan seperti U1 U1 U1menjadi satu U3?
primo