Tugas Anda adalah memainkan peran kedua karakter dalam adegan ini dari Inception. Di dalamnya, Cobb memberi Ariadne tantangan:
Anda memiliki dua menit untuk mendesain labirin yang membutuhkan waktu satu menit untuk menyelesaikannya.
Beberapa kebebasan akan diambil pada deskripsi itu. Yang paling penting, tantangan ini bukan berdasarkan waktu, tetapi skor didasarkan pada efektivitas labirin dan pemecah labirin Anda.
Saya minta maaf atas banyaknya suntingan untuk tantangan ini karena kami beralih ke format yang mudah dan adil ..
Bagian I: Format labirin
Semua labirin berbentuk bujur sangkar. Sel di maze diwakili sebagai tuple yang diindeks nol row column
.
Dinding diwakili oleh dua string biner: satu untuk dinding horizontal (yang menghalangi pergerakan antar baris) dan dinding vertikal (sebaliknya). Pada NxN
labirin, ada Nx(N-1)
kemungkinan dinding dari masing-masing jenis. Mari kita ambil contoh 3x3 di mana sel diberi label:
A B | C
---
D | E F
---
G H | I
semua dinding vertikal yang mungkin adalah: AB BC DE EF GH HI
. Diterjemahkan menjadi string, dinding yang ditampilkan adalah 011001
untuk dinding vertikal dan 010010
untuk dinding horizontal. Juga, dengan "string biner" Maksudku "karakter '0' dan '1'".
Format labirin lengkap adalah string yang berisi, dalam urutan ini:
- lebar
- mulai tupel sel
- tuple sel ujung
- dinding horisontal
- dinding vertikal
Misalnya, labirin ini:
0 1 2 3 4
_________
0 | | E| _|
1 | _|_|_ |
2 |_ _ _ | |
3 | _ _ | |
4 |____S|___|
start:(4,2)
end:(0,2)
diformat untuk ini:
5
4 2
0 2
00001011101110001100
10100110000100010010
Bagian II: Arsitek
Program Arsitek menciptakan labirin. Itu harus bermain sesuai aturan dan memberikan labirin yang valid (yang ada solusinya, dan akhirnya tidak di atas permulaan).
Input: Dua bilangan bulat positif:
size [random seed]
Di mana size
akan berada [15, 50]
. Anda didorong untuk menggunakan benih acak sehingga pertandingan dapat diputar ulang, meskipun tidak diperlukan.
Keluaran: Ukuran x ukuran (kuadrat) yang valid menggunakan format yang diuraikan dalam Bagian I. "valid" berarti ada solusi, dan sel awal tidak sama dengan sel akhir.
Nilai seorang Arsitek pada labirin yang diberikan adalah
# steps taken to solve
–––––––––––––––––––––––––––––
max(dist(start,end),(# walls))
Jadi arsitek dihargai untuk labirin yang kompleks, tetapi dihukum untuk setiap dinding yang dibangun (ini adalah pengganti pembatasan waktu Ariadne). The dist()
Fungsi memastikan bahwa labirin tanpa dinding tidak mendapatkan nilai yang tak terbatas. Batas luar labirin tidak berkontribusi pada penghitungan dinding.
Bagian III: The Solver
The Solver mencoba memecahkan labirin yang dihasilkan oleh arsitek orang lain. Ada semacam kabut perang: hanya dinding yang berdekatan dengan sel yang dikunjungi yang dimasukkan (yang lainnya diganti dengan '?')
input: format labirin yang sama, tetapi dengan '?' di mana dinding tidak diketahui, garis tambahan untuk lokasi saat ini, dan daftar pilihan valid yang dipisahkan koma dari lokasi ini. (Ini adalah suntingan besar yang dimaksudkan untuk membuatnya lebih mudah untuk menulis fungsi parsing-labirin)
contoh (sama seperti labirin 5x5 di atas setelah mengambil satu langkah ke kiri)
5
4 2
0 2
???????????????011??
????????????????001?
4 1
4 0,4 2
Yang sesuai dengan sesuatu seperti ini, di mana ?
kabut:
0 1 2 3 4
_________
0 |????E????|
1 |?????????|
2 |?????????|
3 | ?_?_????|
4 |__C_S|_?_|
output: Salah satu tupel dari daftar pilihan yang valid
Setiap skor Solver adalah kebalikan dari skor Arsitek.
Bagian IV: King of the Hill
Arsitek dan Pemecah diberi skor terpisah, sehingga berpotensi ada dua pemenang.
Setiap pasangan arsitek dan pemecah akan memiliki banyak peluang untuk saling mengecoh. Skor akan dirata-rata untuk semua tes dan lawan. Berlawanan dengan konvensi kode golf, skor rata-rata tertinggi menang!
Saya bermaksud agar ini terus berlangsung, tetapi saya tidak dapat menjamin pengujian yang berkelanjutan untuk selamanya! Katakanlah untuk saat ini bahwa seorang pemenang akan diumumkan dalam satu minggu.
Bagian V: Menyerahkan
- Saya mempertahankan hak veto atas semua pengiriman - kepintaran dianjurkan, tetapi tidak jika itu merusak kompetisi atau komputer saya! (Jika saya tidak tahu apa kode Anda, saya mungkin akan memveto)
- Munculkan nama untuk pasangan Architect / Solver Anda. Posting kode Anda bersama dengan instruksi tentang cara menjalankannya.
Segera hadir: kit uji python yang diperbarui untuk format baru. Perubahan besar terjadi untuk memungkinkan pengiriman bahasa apa pun.
sumber
Jawaban:
BuildFun dan SolveFun
Yah, ini butuh waktu cukup lama dan saya tidak sepenuhnya yakin apakah pemecahnya curang atau tidak. Meskipun memiliki akses ke seluruh labirin sepanjang waktu, ia hanya melihat sel yang ada di dalamnya, dinding yang mengelilinginya, dan jika tidak ada dinding di antara mereka, sel-sel yang bersebelahan dengannya. Jika ini melanggar aturan, beri tahu saya dan saya akan mencoba mengubahnya.
Bagaimanapun, ini kodenya:
Saya menyadari bahwa ini sangat panjang dan tidak mudah dibaca, tapi saya malas jadi begini caranya.
BuildFun
Arsiteknya, BuildFun, adalah program penghasil labirin yang cukup sederhana yang akan selalu membuat labirin 'sempurna' (satu tanpa loop dan di mana dua titik akan selalu memiliki tepat satu jalur di antara mereka). Ini mendasarkan logikanya dari input benih yang berarti bahwa labirin yang dihasilkan adalah pseudo-acak dengan apa yang sering tampak sebagai pola berulang dan, dengan benih dan ukuran yang sama, labirin yang sama akan dibuat.
Setelah labirin dihasilkan, program akan berusaha memaksimalkan skor labirin dengan mencari titik awal dan titik akhir yang menghasilkan jalur terpanjang di antara mereka. Untuk melakukan ini, ia berjalan melalui setiap titik awal, menyebar pelacak untuk menemukan titik akhir terjauh dari itu, dan memilih kombinasi dengan jalur terpanjang.
Setelah ini, ia menarik labirin, menghitung dinding dan menampilkan informasi labirin. Ini adalah titik awal, titik akhir, jarak di antara mereka, jumlah dinding dan skor. Ini juga memformat informasi ini menjadi gaya yang dijelaskan di atas untuk ukuran, mulai dan akhir, dinding horizontal dan dinding vertikal dan menyimpannya ke dalam file teks yang disebut Maze.txt untuk digunakan nanti.
SolveFun
Solver, SolveFun, menggunakan file teks Maze.txt sebagai input dan bekerja dengan cara yang sangat mirip dengan arsitek. Untuk setiap gerakan, ia akan memilih arah yang ingin ia tempuh berdasarkan posisi relatifnya sampai akhir dan kemudian ia akan melihat dinding yang mengelilinginya. Jika dinding tidak ada di sana, itu akan memeriksa untuk melihat apakah telah di sel yang berdekatan dengannya dan, jika tidak, itu akan ditambahkan sebagai opsi yang memungkinkan. Kemudian akan bergerak ke arah yang paling dekat dengan arah pilihannya asalkan memiliki opsi. Jika tidak memiliki opsi, ia akan mundur hingga tersedia. Ini berlanjut sampai mencapai akhir.
Saat bergerak, ia mencatat jalur yang diambilnya di jalur variabel yang digunakan di akhir untuk menampilkan jumlah langkah. Itu juga mencatat berapa kali harus mundur digunakan untuk menghitung langkah-langkah yang terbuang pada akhirnya. Ketika mencapai akhir, itu akan menampilkan labirin dengan jalur terpendek dari awal hingga akhir ditandai dengan
*
s.Cara Menjalankan
Karena metode menghasilkan labirin (yang termasuk menggarisbawahi karakter tertentu), ini harus dijalankan dari baris perintah dalam formulir
python -c 'import filename;filename.BuildFun(Size, Seed)'
dan
python -c 'import filename;filename.SolveFun()'
di mana Ukuran adalah bilangan bulat antara 15 dan 50 (inklusif) dan Seed adalah bilangan bulat antara 4 dan Ukuran (inklusif).
sumber