Urutan identitas pada Rubik's Cube

32

Urutan bergerak adalah urutan gerakan (bergantian) pada Rubik's Cube (untuk notasi lihat di bawah). Di samping urutan langkah kosong, ada banyak urutan langkah lainnya, yang tidak memiliki efek pada kubus sama sekali. Kami menyebutnya urutan identitas urutan ini.

Beberapa urutan identitas ini jelas untuk ditentukan, disukai U2 R R' U2atau U D2 U' D2. Dalam yang pertama, dua gerakan acak dilakukan U2 Rdan setelah itu segera dibatalkan R' U2. Yang kedua mirip. Dua gerakan acak pertama U D2dan setelah itu dibatalkan, tetapi dalam urutan terbalik U' D2. Ini hanya berfungsi, karena bergerak Uhanya mempengaruhi potongan-potongan lapisan atas dan bergerak D2hanya efek potongan-potongan lapisan bawah. Anda dapat melihat visualisasi dari dua urutan langkah ini.

U2 RR 'U2 U D2 U 'D2

Urutan identitas lainnya mungkin tidak jelas sama sekali. Misalnya urutannya R' U' R' F' U F U' R' F R F' U' R U2 R. Cukup panjang, tetapi juga tidak memiliki efek sama sekali pada kubus.

masukkan deskripsi gambar di sini

Pindahkan Notasi

Sebuah langkah menggambarkan pergantian satu lapisan dari satu dari enam permukaan kubus. Pindah terdiri dari satu huruf yang mewakili wajah diikuti oleh akhiran opsional yang mewakili sudut belokan.

Huruf dan wajahnya yang sesuai adalah U (Atas - sisi menghadap ke atas), D (Bawah - sisi menghadap ke bawah), R (Kanan - sisi menghadap ke kanan), L (Kiri - sisi menghadap ke kiri) , F (Depan - sisi menghadap Anda) dan B (Belakang - sisi menghadap jauh dari Anda).

Jika tidak ada sufiks, wajah diputar 90 derajat searah jarum jam, sufiks 'berarti, wajah berubah 90 derajat berlawanan arah jarum jam, dan sufiks 2berarti, wajah diputar 180 derajat searah jarum jam.

Jika Anda memiliki masalah dengan notasi, cukup gunakan http://alg.cubing.net , di mana Anda dapat memvisualisasikan urutan langkah tersebut.

Tantangan

Tugas Anda adalah menulis sebuah program, yang menentukan apakah urutan langkah adalah identitas atau bukan.

Anda dapat menulis program atau fungsi lengkap. Ini harus menerima string yang berisi urutan bergerak (bergerak terpisah oleh spasi) sebagai input (melalui STDIN, argumen baris perintah, argumen cepat atau fungsi), dan output (melalui nilai balik atau STDOUT) nilai Boolean atau bilangan bulat yang sesuai ( Benar - 1 - urutan identitas / Salah - 0 - bukan urutan identitas).

Jika akhiran Anda 'menciptakan masalah dalam bahasa pemrograman Anda, Anda dapat menggunakan simbol yang berbeda, tetapi tidak pada digit. R F2 U3tidak diizinkan.

Ini codegolf, karena itu kode terpendek (dalam byte) menang.

Uji Kasus

"" -> 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
sumber
Ada apa dengan ini R F2 U3?
John Dvorak
2
Saya hanya ingin memastikan, bahwa setiap orang memiliki prasyarat yang sama. Jika saya mengizinkan U3, maka Anda bisa memasukkan sufiks ke angka.
Jakube
3
Saya lebih terbiasa dengan notasi yang menggunakan T-Top, B-Bottom, dan P-Posterior (belakang). Orang mungkin hanya suka melihat urutannya R2 D2.
mbomb007
2
@ mbomb007 Saya bisa mengerti T untuk top, tapi saya belum pernah melihat P untuk posterior dan saya tidak akan mengerti artinya kalau bukan karena komentar Anda ...
John Dvorak
2
@ mbomb007 Saya telah melihat notasi itu juga, tetapi tidak umum atau setua notasi Singmaster asli, dan saya tidak tahu mengapa orang ingin mengacaukan yang asli. Meskipun David Singmaster (sejauh yang saya tahu) tidak menyebutkannya, saya telah mengamati bahwa semua wajah sangat konsisten dan tanpa bentrokan jika dianggap sebagai arah daripada posisi. That is F(orward), B(ackward), L(eft), R(ight), U(p), D(own)
Level River St

Jawaban:

14

Haskell, 263 261 247 243 karakter

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)

Algoritma agak lurus; setiap cubelet terbuat dari 1,2,4 atau 8 chunk yang menyandikan posisi dan orientasinya; 4 potongan per cubelet tepi, 8 per cubelet sudut, 7 cubelet stasioner.

c c homps setiap kata dari input ke dalam urutan putaran CW, dan !mengirimkan setiap potongan sesuai dengan putaran. iadalah posisi i dentity. fadalah f unction utama .

Saya tidak terlalu senang dengan cfungsi homp, tapi sepertinya saya juga tidak bisa menemukan cara untuk mempersingkatnya (@Nimi melakukannya)

John Dvorak
sumber
Bagaimana dengan c(x:"2")=[x,x]dan c(x:_)=[x,x,x]. Menghemat 2 byte.
nimi
Jika Anda menggunakan i=sequence[s,s,s], dan ubah semua tupel menjadi daftar (yaitu: (x,y,z)menjadi [x,y,z]) - ini akan menghemat ~ 9 karakter. Memasukkannya menghemat 4 lebih banyak. Menjatuhkan _!
kasing
@MtnViewMark dilakukan dan ditingkatkan i, terima kasih. Tidak yakin apa yang Anda maksud dengan sebaris i- harap perhatikan itu muncul dua kali dalam definisi untuk f. Tidak yakin apa yang Anda maksud dengan menjatuhkan _kasing - meninggalkan _->aatau memindahkannya ke atas menghasilkan pengecualian pola yang tidak lengkap, dan memindahkannya ke atas tidak menyimpan karakter apa pun. Saya berhasil menyimpan 5 karakter di sana.
John Dvorak
Solusi bagus Saya memeriksa semua test case.
Jakube
Sekali lagi, selamat untuk solusi Anda. Karena Anda mempresentasikan kode terpendek, Anda menerima hadiah bernilai 100 reputasi.
Jakube
4

Secara kubik , 6 4 byte

¶=8%

Saya menang: P

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

Notepad diinisialisasi ke nol. "Wajah" ke-8 berisi 1 jika kubus tidak terpecahkan dan 0 sebaliknya.

Cobalah online!

MD XF
sumber
3
Sepertinya bahasa yang menarik. Tetapi karena bahasa itu dibuat setelah tantangan diposting, itu tidak memenuhi syarat untuk menang.
Jakube
2
@ Jakube Saya setuju bahwa itu tidak boleh diterima, hanya karena fakta bahwa itu adalah bahasa dengan Rubik's Cube builtin yang diposting sangat terlambat setelah tantangan dan sepenuhnya menipiskan jawaban lainnya. Tetapi secara teknis memenuhi syarat untuk menang sesuai meta (aturan yang tidak bersaing agak dicabut).
MD XF
3

J - 232, 220, 381, 315 296 byte

Solusi ini mengkodekan semua operasi sebagai permutasi wajah dan bekerja berdasarkan fakta bahwa semua lilitan wajah sebenarnya sama, di bawah rotasi seluruh kubus.

Sunting : beberapa lagi bermain golf

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'

Selain percobaan sebelumnya, ini memang memperhitungkan rotasi sudut.

fhanyalah fungsi pembantu. rApakah rotasi satu wajah. wajah dikodekan sebagai berikut:

  1. semua sudut dalam langkah 6
  2. semua tepi dalam langkah enam

urutan ini memfasilitasi pengkodean rotasi dan putaran. tadalah kata keterangan yang memutar wajah di bawah rotasi kubus tertentu, memilih wajah.

Xdan Yketerangan yang mengambil sebagai argumen kiri jumlah ke arah seluruh kubus.

Baris berikutnya mendefinisikan semua rotasi: 3 karakter per rotasi: nama, jumlah rotasi dan arah.

Baris terakhir mendefinisikan kata kerja tes T, mengkonversi 3 dan 'ke notasi Power, membalik urutan operasi menambahkan vektor tes dan akhirnya mengesampingkan semuanya.

Lebih detail berdasarkan permintaan.

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
sumber
11
"karena hasil pengujian saya tidak sesuai dengan yang diberikan ..." seperti, solusi Anda tidak berfungsi? Saya tidak akan mempostingnya kemudian ...
John Dvorak
Kamu benar. Perbaiki sekarang.
jpjacobs
Saya menambahkan 4 test case tambahan. Dua dari mereka masih mengembalikan hasil yang salah. Sepertinya Anda mengabaikan orientasi sudut.
Jakube
@ jpjacobs Ada hadiah 100 rep pada pertanyaan sekarang. Ingin memperbaiki kode Anda?
Jakube
Voila, selesai. Sekarang kurangi saja.
jpjacobs
2

Python 3: 280 karakter

Ini bukan peserta dalam tantangan. Pertama karena saya bertanya sendiri tantangan dan kedua karena itu bukan kode saya. Semua kredit adalah milik Stefan Pochmann , yang menemukan cara yang mengagumkan dalam mensimulasikan Rubik's Cube. Saya hanya melakukan beberapa golf dan beberapa perubahan kecil sehubungan dengan tantangan.

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

Gagasan di balik ini adalah sebagai berikut. smerupakan lokasi dari potongan-potongan UF, URdan sebagainya. Misalnya: s = ['DF', 'BL', ...]berarti, potongan UFberada di posisi DF, potongan URberada di posisi BL, ...

Bagaimana posisi sepotong berubah, ketika melakukan gerakan. Jika Anda melakukan U-move, semua stiker (warna) dari U-layer, yang menghadap wajah depan, pindah ke wajah kiri. Stiker wajah kiri bergerak ke belakang, ini ke kanan dan ini ke wajah depan. Disandikan oleh FLBR. Beberapa contoh: UFpindah ke UL, UFRpindah ke ULFdan sebagainya. Oleh karena itu, menerapkan langkah hanya menerjemahkan wajah potongan-potongan di lapisan yang sesuai.

Jakube
sumber