Tugas Anda
.. adalah melakukan apa yang rupanya Brian Fantana tidak bisa lakukan, dan menyelesaikan Kubus Rubik 2x2x2.
Tata Letak
- - A B - - - -
- - C D - - - -
E F G H I J K L
M N O P Q R S T
- - U V - - - -
- - W X - - - -
Dan akan diberikan kepada Anda melalui stdin atau baris perintah (pilihan Anda - sebutkan dalam jawaban Anda) dalam format:
ABCDEFGHIJKLMNOPQRSTUVWX
Perhatikan bahwa AD membentuk wajah-U (atas), EFMN membentuk wajah-L (kiri), GHOP membentuk wajah-F (depan), IJQR membentuk wajah-R (kanan), KLST membuat B-face (belakang), dan UX membentuk D-face (down).
Akan ada enam karakter unik yang mewakili setiap warna, tetapi mereka dapat bervariasi, jadi persiapkan kombinasi 6 karakter ascii yang akan digunakan untuk setiap warna.
Spesifikasi
- Kode Anda harus menampilkan solusi dengan hanya menggunakan sisi Kanan (R), Atas (U), dan Depan (F), dan harus menggunakan notasi standar: R, R ', R2, U, U', U2, U2, F, F ', F2. Anda dapat menemukan info lebih lanjut di sini . Pembatasan pada subset RUF adalah standar untuk kubus 2x2 (Petunjuk: perlakukan sudut kiri-bawah sebagai basis tetap untuk bekerja).
- Kode Anda harus mampu menyelesaikan semua permutasi yang mungkin dari kubus saku.
- Setiap solusi harus selesai kurang dari 30 detik.
- Setiap solusi harus kurang dari 30 gerakan.
- Bonus -20% akan diberikan untuk solusi yang selalu memberikan jawaban kurang dari 20 gerakan (harap iklankan dalam jawaban Anda sehingga saya dapat melakukan pemeriksaan menyeluruh untuk itu)
- Bonus -50% akan diberikan untuk kode yang selalu memberikan solusi optimal. - Sekali lagi, harap beriklan di jawaban Anda
- Solusi tidak boleh mengandung dua gerakan berturut-turut pada wajah yang sama, karena mereka dapat dengan mudah digabungkan menjadi satu gerakan.
- Solusi secara opsional dapat berisi satu ruang - dan hanya satu ruang - di antara setiap gerakan.
- Urutan solusi keseluruhan, jika perlu, dapat terkandung dalam sepasang tanda kurung, tanda kutip, kawat gigi, tanda kurung, atau tanda sisipan, tetapi tidak ada output asing lainnya yang diizinkan.
- Harap berikan versi kode Anda yang berkomentar singkat atau penjelasan menyeluruh tentang kode Anda.
- Tidak ada penggunaan file eksternal. Ini termasuk internet, tabel data, dan perpustakaan / paket yang dibuat untuk masalah semacam ini.
- Kode terpendek dengan jumlah byte menang.
- Pemenang dipilih Rabu (30 Juli 2014).
code-golf
puzzle-solver
permutations
rubiks-cube
Kyle McCormick
sumber
sumber
Jawaban:
Python 2.7: 544 byte -50% = 272 byte **
Stackexchange mengganti tab dengan beberapa spasi putih. Jadi teknis versi ini memiliki 549 byte. Cukup ganti dua spasi pertama di baris 6-10 dengan tabulator.
Ide di balik program saya: Ide pertama saya adalah pencarian pertama yang menarik. Tapi ini terlalu lama. Sekitar 2 menit untuk perebutan keras (11 gerakan optimal). Jadi saya memutuskan untuk mendekati masalah dari kedua belah pihak. Saya menggunakan dua set. Saya menghasilkan semua negara secara berurutan dengan jarak 1,2,3, ... untuk mengacak dan menyimpannya di set1, dan pada saat yang sama semua negara dengan jarak 1,2,3, ... ke keadaan terpecahkan dan menyimpannya di set2. Pertama kali keadaan dalam kedua set, kami menemukan solusinya.
Untuk ini saya perlu warna kubus yang dipecahkan, yang tidak diketahui. Karakter 13, 20 dan 23 menentukan warna kiri, belakang dan bawah. Tetapi 3 warna ini cukup untuk mewakili kubus. Saya hanya mengganti 3 warna lainnya dengan spasi putih dan saya dapat mewakili kondisi terpecahkan saya sebagai '____ll____bbll____dddd'.
Oh, dan untuk memperpendek permutasi saya menggunakan ide dari /codegolf//a/34651/29577
Versi tidak disatukan:
Saya cukup senang dengan hasilnya, karena saya cukup baru di Python. Ini adalah salah satu program python pertama saya.
sunting: setengah tahun kemudian: 427 - 50% = 213.5
Punya sedikit lebih banyak pengalaman dalam Python dan golf. Jadi saya merevisi kode asli saya dan dapat menyimpan lebih dari 100 karakter.
Saya pada dasarnya menggunakan pendekatan yang sama persis. Perubahan terbesar adalah, bahwa saya tidak mendefinisikan fungsi lagi. Dari pada
dapat saya lakukan
Saya juga mengubah langkah lamda sedikit. Pertama mempersingkat, dan kemudian mengintegrasikan kode secara langsung, karena panggilan fungsi hanya muncul sekali.
Saya menyimpan untuk setiap negara daftar angka antara 0 dan 11, untuk mewakili gerakan, bukan string yang berisi gerakan. Jumlahnya dikonversi pada bagian paling akhir.
Saya juga menggabungkan dua for-loop
'for k in r(3):for j in r(3):
menjadi satufor y in r(12)
. Karena itu saya juga harus melakukan gerakanU4, R4, F4
. Tentu saja langkah seperti itu tidak muncul dalam solusi terpendek, begitu" 2'"[x%4]
berhasil. (Jikax % 4 == 3
, akan ada indeks di luar rentang pengecualian)Ini juga sedikit lebih cepat, karena saya mencari entri di set kedua sebelumnya. Sekitar 0,5 detik untuk solusi 11 langkah.
sumber
C, 366 - 50% bonus optimal = 183
Menggunakan rekursi, program mencari melalui pohon hingga 11 bergerak dalam (panjang maksimal soluton optimal menurut http://en.wikipedia.org/wiki/Pocket_Cube dan halaman yang disebutkan di bawah) dan ketika menemukan solusi itu mencetaknya (hingga 22 karakter, dilacak oleh argumen fungsi
m
.) Urutan yang digunakan adalah semacam urutan kamus, di mana semua rute mulai U, U2, U 'dicari sebelum rute mana pun mulai R atau F dicari. Dengan demikian belum tentu menemukan solusi optimal terlebih dahulu.Ketika solusi dicetak,
r
dibuat sama denganm
yang memastikan bahwa hanya solusi yang sama atau lebih pendek akan dicetak setelahnya. Menempatkanr=m-2
biaya tambahan 2 karakter tetapi memastikan hanya satu solusi dari setiap panjang yang ditemukan (turun ke optimal) dicetak. Jika Anda ingin HANYA menunjukkan solusi optimal, solusi terbaik yang ditemukan sejauh ini harus disimpan ke variabel, dan solusi optimal dicetak di akhir program (ini akan memakan biaya sekitar 15 karakter tambahan.)input dibaca ke dalam array
c[]
dari indeks 64 dan seterusnya. Ini diperlukan untuk menggunakan karakter alfabet dalam gerakan. Simbol@
melaluiW
digunakan alih-alih A sampai X per pertanyaan, karena itu perlu untuk memulai pada bilangan genap agar tes untuk solusi berfungsi.c['Z']
juga digunakan untuk penyimpanan sementara, karena untuk melakukan rotasi 4 kali lipat total 5 tugas diperlukan. Karena bagian pertama daric[]
tidak digunakan, tersedia untuk menyimpan solusi (yang diakhiri dengan byte nol, seperti semua string C.)for(i..)
melewati urutan 4 quarterturns dari wajah yang ditentukan olehn
.Yang pertama
for(j..)
melakukan swapping yang sebenarnya sesuai dengan tabelt[]
.Untuk menguji apakah kubus itu terpecahkan, Anda hanya perlu memeriksa keempat sisi sisi. Potongan-potongan URF dan DFR dapat dibedakan bahkan dengan stiker U dan D dihapus, karena satu potong membaca XRF dalam arah searah jarum jam dan XFR lainnya. Jika dua bagian dipertukarkan sehingga U menunjukkan pada wajah bawah dan sebaliknya, warna F akan ditampilkan pada wajah kanan dan sebaliknya.
Yang kedua
for(j..)
menghitung jumlah ketidakcocokan di empat sisi wajah. Misalnya untuk wajah depan, ia membandingkan G & O, H & P, dan G & H (dua kali.) Jikae
== 0, kubus diselesaikan. Jikae
<9 ataue
<13, dimungkinkan untuk menyelesaikan kubus dalam satu gerakan berikutnya atau 2 gerakan masing-masing. Kalau tidak pasti tidak mungkin untuk memecahkan kubus dalam jumlah gerakan ini. Untuk menghemat waktu, heuristik ini digunakan untuk memangkas pohon pencarian dan menghindari pemborosan waktu pada banyak cabang dengan kedalaman 10 atau 11 yang tidak akan berhasil. Dinyatakan sebagai formula, ini menjadie<45-m*2
.Kode Tidak Terkunci
Performa
Program ini diuji dengan pola 1 hingga 13 di http://www.jaapsch.net/puzzles/cube2.htm
Hasil sebagai berikut memberikan pengaturan waktu pada mesin saya untuk menemukan SEMUA solusi optimal (untuk orang yang berpikiran ingin tahu.) Juga untuk posisi yang lebih kompleks, pengaturan waktu diberikan untuk modifikasi 2-byte yang disebutkan di atas yang hanya menemukan satu solusi optimal. Untuk penentuan waktu ini diberikan baik untuk menemukan solusi pertama dan untuk program untuk mengakhiri. Solusi yang diberikan (yang umumnya berbeda dengan solusi yang diperoleh dengan membalik generator pada halaman tertaut) telah diverifikasi dengan simulator kubus online.
sumber