Waktu luang para pedant yang terhormat adalah untuk menunjukkan bahwa foto-foto "Rubik's Cubes" (pada kaos, poster, dll.) Sebenarnya tidak dapat dipecahkan.
Hal pertama yang harus diperiksa adalah kubus terdiri dari potongan yang tepat. Untuk dipecahkan kubus membutuhkan enam warna masing-masing dengan sembilan kotak. Kubus juga membutuhkan setiap unit tepi dan sudut (ini adalah kubus kecil yang membentuk kubus) untuk menjadi unik. Tidak hanya mereka harus unik tetapi jika dua bagian tengah saling berhadapan satu sama lain tidak ada bagian tepi atau sudut dapat mengandung kedua warna tersebut.
Setelah Anda memiliki kubus yang terdiri dari semua bagian yang tepat, Anda masih perlu memverifikasinya agar dapat dipecahkan. Ada beberapa aturan di sini, jadi saya akan meminta ahli untuk menjelaskannya, spoiler di bawah ini menjelaskan bagaimana kita bisa melakukan ini. Jika Anda tertarik untuk menyelesaikan masalah Anda sendiri, Anda tidak perlu mengunjungi situs untuk memahami atau berpartisipasi dalam tantangan ini.
Tugas Anda adalah mengambil pola sebagai input dan menentukan apakah itu sebenarnya kubus Rubik yang dapat dipecahkan. Untuk dipecahkan harus ada cara untuk melakukan gerakan yang valid pada kubus sehingga kubus hanya memiliki satu warna pada setiap wajah (dan wajah yang berbeda memiliki warna yang berbeda). Sebagian besar kubus Rubik memiliki pewarnaan standar (Putih berlawanan Kuning, dll.) Anda mungkin tidak menganggap bahwa kondisi penyelesaian mengikuti pewarnaan khusus ini.
Langkah yang valid adalah rotasi searah jarum jam atau berlawanan arah jarum jam dari satu permukaan kubus. Dengan rotasi muka kubus setiap kotak yang membatasi wajah diputar juga, tetap terhubung ke wajah yang sebelumnya mereka sentuh.
IO
Anda dapat mengambil kubus dengan cara yang masuk akal. Jika bahasa Anda memiliki beberapa tipe "kubus-wajah" bawaan, bagus untuk Anda, itu bagus sebagai input, jika tidak Anda dapat mengambil array 2D dari jaring, kubus, daftar 1 3 dengan 3 untuk setiap wajah. Masuk akal saja. Jika Anda ingin tahu apakah format tertentu dapat diterima komentar atau ping saya dalam obrolan dan saya akan menambah tantangan untuk menyatakan validitasnya.
Format input Anda hanya perlu mendukung hingga 9 warna yang memungkinkan.
Untuk output, ini adalah masalah keputusan sehingga Anda harus menampilkan satu nilai konstan untuk "Ya, ini adalah kubus Rubik yang valid" dan satu nilai konstanta berbeda untuk "Tidak, ini bukan kubus Rubiks yang valid".
Ini adalah kode-golf sehingga jawaban akan dinilai dalam byte dengan lebih sedikit byte lebih baik.
Uji Kasus
Berikut ini adalah contoh-contoh uji. Mereka diformat sebagai jaring kubus dengan setiap kotak sebagai satu huruf. Huruf yang berbeda mewakili warna yang berbeda. Setiap testcases lagi dapat ditambahkan atas permintaan.
Larut
RRR
RRR
RRR
GGGWWWBBBOOO
GGGWWWBBBOOO
GGGWWWBBBOOO
YYY
YYY
YYY
GRR
GRR
ORW
WWRBWYBOOGGY
GGRBWGYBBOOO
OOGRWGYWWRBB
WYO
YYB
YYB
Tidak dapat diselesaikan
RRR
RRR
RRR
GGGWWWBBBOOO
GGGWWWBBBOOO
GGGWYWBBBOOO
YWY
YYY
YYY
RRR
RRR
RRR
GGGWWWBBBOOO
GGGWWWBBBOOO
GGGWWWBBBOOO
YWY
YYY
YYY
RRR
RRR
GGG
GGYWYWRBBOBO
GGYWWWROBOOO
GGYWWWRBBOOO
BBB
YWY
YYY
RRW
RRW
GGG
GGYWWYEOBROO
GGYWWYEBBROO
GGOWWYWBBROO
BBB
YYW
YYO
sumber
Jawaban:
Secara kubik ,
166416311089 byteOutput jika dipecahkan:
Solved!
Output jika tidak dapat dipecahkan: (kosong, tidak ada output)
Input harus diformat sebagai kubus-dump Cubically (lihat
Debug
bagian). Ini secara eksplisit diizinkan oleh OP.Penjelasan
Program ini mengambil pendekatan menggunakan Algoritma Iblis untuk beralih ke setiap keadaan yang mungkin dari kubus dalam kelompok yang sama dengan kubus yang diselesaikan. Jika kubus dipecahkan, itu akan diselesaikan di beberapa titik sebelum algoritma selesai (dengan asumsi algoritma yang saya gunakan berfungsi dengan baik).
Setiap baris yang diawali dengan
⇒
(0x84 dalam codepage Cubically) adalah definisi fungsi; fungsi-fungsi ini membangun satu sama lain untuk membentuk Algoritma Iblis yang sebenarnya. Baris pertama yang dieksekusi adalah yang terakhir:r
membaca sebuah kubus dari stdin dan mengatur kubus memori untuk itu.s
menempatkan interpreter ke "solvemode", yang berarti ia keluar dan mencetakSolved!
jika kubus dipecahkan (setelah tidak terpecahkan) di titik mana pun. Sisa dari perintah (yang hanya mengulangf36f71
8 kali) sesuai dengan algoritma terakhir di bagian bawah halaman yang ditautkan:Bagaimana saya bisa menjalankannya?
Anda dapat mencobanya secara online , tetapi tautan itu tidak berfungsi. TIO hampir pasti akan kehabisan waktu sebelum algoritma ini selesai (runtime maksimum untuk seorang juru bahasa adalah 60 detik). Jika kubus tidak dapat dipecahkan, algoritme ini akan memakan waktu hingga 11 juta tahun untuk diselesaikan secara kubik (pada ~ 15,2 juta gerakan per detik, yang didapat dari IDE Cloud9 saya ).
Selain itu, Anda membutuhkan banyak memori untuk melakukan 3 sextillion move. Secara kubik dapat melakukan sekitar 4 juta gerakan per detik, tetapi prosesnya kemungkinan besar akan mati karena memori yang terlalu padat . Mati setelah 15 detik pada VM saya dengan memori 512MB.Mengapa melakukan perpindahan pada memori biaya flat array yang sudah dialokasikan? Menemukan kebocoran memori (atau dua puluh) dan memperbaikinya .Berikut adalah versi yang jauh lebih mudah dibaca yang berperilaku dengan cara yang sama.
Tetapi saya benar-benar ingin melihat bahwa itu berhasil!
Langkah aktual pertama yang dieksekusi dalam algoritma iblis ini adalah
F2
, jadi kubus tercepat untuk dipecahkan adalah yang diacak denganF2
:Ini memang dijalankan dalam 0,007 detik pada TIO .
Bagaimana ini bisa diperbaiki?
Tentu saja ada lebih banyak algoritma iblis; Saya telah menemukan yang menggunakan kurang dari tigapuluh dari langkah yang satu ini. Namun, itu akan memakan biaya beberapa ribu byte (sekitar 100MB lebih) dan beberapa lusin jam mengubah sirkuit Hamiltonian yang kompleks menjadi kode Cubically.
Dimungkinkan juga untuk menghapus beberapa fungsi dan meluruskannya di loop di bagian bawah. Namun, saya akan mengorbankan beberapa byte untuk dibaca.
Selain itu, saya sedang mempertimbangkan modifikasi perilaku looping Cubically sehingga saya dapat lebih mudah mengulangi algoritma 7 atau 8 kali (daripada hanya mengkodekan mereka dengan panggilan fungsi yang diulang 7 atau 8 kali dalam sumber). Atau saya akan mengerjakan beberapa keajaiban dengan notepad, dan bermain golf ini menggunakan lebih banyak loop.
Perhatikan bahwa saya akan terus mengoptimalkan apa pun yang mungkin dalam juru bahasa, jadi ini mungkin bekerja pada PC biasa di masa depan!
Secara kubik, 2 byte
Saya suka jawaban di atas lebih baik jadi saya menambahkan ini sebagai solusi alternatif. Ini berjalan di bawah satu detik, dibandingkan dengan beberapa juta tahun.
Output jika kubus dipecahkan: (tidak ada)
Output jika kubus tidak dapat dipecahkan:
Error: The cube has reached an unsolvable state.
sumber
APL (Dyalog Classic) ,
190174 bytesCobalah online!
Argumennya adalah matriks 3x2 (row0: depan belakang, row1: kiri kanan, row2: atas ke bawah) dari matriks karakter 3x3. Mengembalikan 1 untuk kubus Rubik yang dapat dipecahkan, 0 sebaliknya.
Dalam tautan TIO, fungsi
t
, yang tidak termasuk dalam jumlah karakter, membaca 9 baris input, mengubahnya dari format input default (jaring) ke matriks 3x2 x 3x3 yang diperlukan, memanggil solusi dan mencetak OK jika hasilnya seperti yang diharapkan.Algoritma membagi kubus yang diberikan menjadi 26 cubies - string dengan panjang 3 (sudut), 2 (tepi), dan 1 (tengah). Ini juga menghasilkan 26 kubus kubus diselesaikan dengan 6 kubus pusat yang sama. Semua kriteria berikut harus dipenuhi:
tidak ada duplikat di antara 6 pusat
set kubus yang diberikan / diselesaikan cocok, hingga rotasi - mis. pertimbangkan
'WBR'
dan'BRW'
kubie yang sama, tetapi tidak'BWR'
paritas dari permutasi sudut dan permutasi tepi adalah genap
Modulo-3 jumlah indeks rotasi sudut (misalnya mengambil "terkecil" surat
B
sebagai titik acuan kita memiliki:'BRW'→0
,'WBR'→1
,'RWB'→2
) pertandingan antara kubus yang diberikan dan diselesaikan; sama untuk sudut-sudut modulo 2sumber