Tujuan dari tantangan ini adalah untuk membuat kode terpendek (dalam karakter) yang berhasil melakukan hal berikut:
Spesifikasi :
- Harus membuat
5x5x5 labyrinth
dengan tepat1 possible solution
(tidak lebih, tidak kurang) Labirin harus dibuatItu harus dapat menghasilkan setiap solusi yang ada jika dibiarkan berjalan selama bertahun-tahunrandomly
- The
start
danfinish
harus ditempatkan dalam*opposite corners
- Peta
output
harus dalam salah satu format berikut:
Format output opsi 1 strings, printed or alerted
:
xxxxx,xxxxx,xxxxx,xxxxx,xxxxx/
xxxxx,xxxxx,xxxxx,xxxxx,xxxxx/
xxxxx,xxxxx,xxxxx,xxxxx,xxxxx/
xxxxx,xxxxx,xxxxx,xxxxx,xxxxx/
xxxxx,xxxxx,xxxxx,xxxxx,xxxxx
Format keluaran opsi 2 arrays
:
[[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx],
[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx],
[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx],
[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx],
[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx]]
Catatan keluaran:
Gunakan
0
untukempty
dan1
untuksquares
Garis putus TIDAK perlu
Anda memutuskan apa
index
itu apa, tetapi pastikan untuk menjelaskannya dengan baik
* Ini adalah contoh dari apa yang saya maksud dengan sudut yang berlawanan:
Klarifikasi :
- TIDAK BISA pindah
diagonal
- TIDAK BISA melewati dua kali di jalur yang sama
- Memiliki
inaccessible areas
diizinkan - Anda dapat
go up/down
lebih dari satu level dalam satu baris
Kiat:
- Jangan melihatnya sebagai dinding, sebaliknya lihatlah sebagai
5x5x5
tumpukan kotak yang beberapa di antaranya hilang dan Anda dapat melewati yang hilang
code-golf
maze
generation
ajax333221
sumber
sumber
Jawaban:
C ++C,sekitar 1000670643395297248 karakterOutput sampel:
Cara kerjanya:
Program ini menggunakan Brownian Motion untuk menghasilkan solusi.Titik awal diatur. Kemudian, titik acak dipilihdan berulang kali dipindahkan secara acakhingga menyentuh satu dan hanya satu titik di cabang mulai. Titik kemudian diatur, dan jika juga menyentuh titik akhir, program keluar dan matriks ditampilkan. Karena tidak ada titik yang dapat bergabung dengan dua cabang, hanya ada satu jalur melalui labirin. Program ini menggunakan fungsi rand,dan argumen integer baris perintah sebagai seed,jadi dengan fungsi rand yang cukup, pada akhirnya mungkin untuk menghasilkan semua labirin yang valid (algoritma ini tidak akan membuat area yang tidak terhubung, jadi tidak akan menghasilkan semua mungkin labirin).Gerakan Brown dijatuhkan karena ternyata tidak dibutuhkan dan penghapusannya menyederhanakan kode secara signifikan. Saya pikir itu membuat labirin yang lebih bagus. Demikian juga, argumen seed dijatuhkan, karena membutuhkan generator nomor acak stateless lebih masuk akal bagi saya daripada seed 128-bit.
Adalah mungkin bagi program untuk terjebak dalam infinite loop, karena dimungkinkan untuk situasi di mana setiap titik yang ditambahkan ke cabang akan membuat banyak jalur. Ini bisa diperbaiki, tapi saya pikir itu cukup langka untuk tidak menjadi perhatian untuk golf kode.
Saya telah menambahkan baris baru dan lekukan ke kode yang ditampilkan agar mudah dibaca.
sumber
JavaScript,
874816788686682668637 karakteroutput sampel:
yang ini bekerja dengan mulai dari titik [0,0,0] dan secara acak menambahkan melampirkan satu lagi 0 di sebelah 0 di mana pun diizinkan (diizinkan == 0 baru tidak di sebelah 0 lainnya kecuali pencetus) sampai tidak ada lagi kemungkinan penambahan.
jika ada 0 baru di sebelah titik keluar (x * y * z == 48) maka kita membuka pintu keluar.
bermain golf
asli
sumber
Mathematica: True Labyrinth (827 chars)
Awalnya, saya membuat jalur dari {1,1,1} ke {5,5,5} tetapi karena tidak ada kesalahan yang mungkin dilakukan, saya memperkenalkan garpu atau "titik keputusan" (simpul derajat> 2) di mana orang perlu memutuskan jalan mana yang harus dilalui. Hasilnya adalah labirin atau labirin sejati.
"Jalan buntu" jauh lebih sulit untuk dipecahkan daripada menemukan jalan langsung yang sederhana. Hal yang paling menantang adalah untuk menghilangkan siklus dalam jalur sementara memungkinkan siklus dari jalur solusi.
Dua baris kode berikut hanya digunakan untuk merender grafik yang digambar, sehingga kode tidak dihitung, karena tidak digunakan dalam solusi.
Kode yang digunakan:
Output sampel
{{"oxooo", "xxooo", "xoxxo", "xoxxo", "xxoox"}, {"ooxoo", "xoooo", "ooxox", "oooxx", "xooxx"}, {"oooxx",, "ooxxo", "ooxox", "xoxoo", "xxxoo"}, {"oxxxx", "oooox", "xooox", "xoxxx", "oooxx"}, {"xxxxx", "ooxox", "oooox "," xoxoo "," oooxo "}}
Dibawah tenda
Gambar di bawah ini menunjukkan labirin atau labirin yang sesuai dengan solusi yang
({{"ooxoo",...}}
ditampilkan di atas:Berikut adalah labirin yang sama yang dimasukkan dalam 5x5x5
GridGraph
. Vertex bernomor adalah node pada jalur terpendek keluar dari labirin. Catat garpu atau titik keputusan pada 34, 64, dan 114. Saya akan memasukkan kode yang digunakan untuk membuat grafik meskipun itu bukan bagian dari solusi:Dan grafik ini hanya menunjukkan solusi untuk labirin:
Akhirnya, beberapa definisi yang dapat membantu membaca kode:
Solusi asli (432 char, Menghasilkan jalur tetapi bukan labirin atau labirin sejati)
Bayangkan sebuah kubus padat 5x5x5 besar yang terbuat dari kubus satuan yang berbeda. Berikut ini dimulai tanpa satuan kubus pada {1,1,1} dan {5,5,5}, karena kami tahu mereka harus menjadi bagian dari solusi. Kemudian menghapus kubus acak sampai ada jalan tanpa hambatan dari {1,1,1} ke {5,5,5}.
"Labirin" adalah jalur terpendek (jika lebih dari satu dimungkinkan) mengingat satuan kubus yang telah dihapus.
Contoh:
Secara teknis ini belum merupakan labirin sejati, karena tidak ada tikungan salah yang bisa dibuat. Tapi saya pikir ini menarik sebagai permulaan karena bergantung pada teori grafik.
Rutinitas sebenarnya membuat labirin tapi saya memasang semua lokasi kosong yang dapat menimbulkan siklus. Jika saya menemukan cara untuk menghapus siklus saya akan memasukkan kode itu di sini.
sumber
FindShortestPath
.