Baru-baru ini saya telah memainkan game bernama Alcazar. Ini adalah permainan puzzle papan di mana tujuan Anda adalah masuk dari satu pintu, melewati semua kotak, dan keluar melalui pintu lain. Satu-satunya aturan adalah:
- Masukkan sekali, tinggalkan sekali;
- Lewati semua kotak;
- Jangan melewati kotak lebih dari sekali
Gambar di bawah ini menunjukkan contoh papan Alcazar dan, di sebelah kanannya, puzzle yang dipecahkan (tentu saja ini mudah):
Anda dapat menemukan lebih banyak teka-teki di http://www.theincrediblecompany.com/try-alcazar dan unduh game di PlayStore (PS: Bukan iklan).
Masalah saya adalah saya hampir menyelesaikan permainan, kecuali satu level. Saya tidak bisa menemukan cara untuk menyelesaikannya. Jadi tantangan yang saya usulkan adalah: membuat algoritma yang memecahkan level 1 Alcazar normal 1 yang dapat dipecahkan .
Tentu saja, saya tidak meminta siapa pun untuk membangun juru bahasa gambar untuk membaca gambar dan memecahkan teka-teki (atau saya?). Jadi saya menggambar ulang puzzle di atas menggunakan karakter menggambar kotak. Teka-teki dan solusinya akan seperti ini:
╔═══════╗ ╔═══════╗
║▒ ▒ ▒ ▒║ ║┌─┐ ┌─┐║
║ ║ ║ ║│ │ │║│║
╣▒ ▒ ▒║▒╠ ╣│ └─┘║└╠
║ ══╦═╩═╣ ║│══╦═╩═╣
║▒ ▒║▒ ▒║ ║└─┐║┌─┐║
║ ║ ║ ==> ║ │║│ │║
╣▒ ▒║▒ ▒║ ╣┐ │║│ │║
║ ║ ║ ║ ║│║│║│ │║
╣▒║▒ ▒ ▒║ ╣│║└─┘ │║
║ ║ ║ ║│║ │║
║▒ ▒ ▒ ▒║ ║└─────┘║
╚═══════╝ ╚═══════╝
Pada papan di atas, ▒
adalah sel yang harus diisi.
Seseorang dapat mengamati bahwa ada gab vertikal dan horizontal antara sel-sel. Ini karena saya harus memasukkan ruang di antara sel untuk menambahkan dinding. Ini berarti bahwa satu-satunya sel penting adalah yang di atas, di bawah, di sebelah kiri, dan di sebelah kanan setiap sel. Diagonal dapat dihapus tanpa kehilangan informasi. Misalnya, di papan di bawah, keduanya mewakili teka-teki yang sama:
╔════╩╗ ═ ═ ╩
║▒ ▒ ▒║ ║▒ ▒ ▒║
║ ═══ ║ ═
║▒ ▒ ▒║ == ║▒ ▒ ▒║
║ ║
║▒ ▒ ▒║ ║▒ ▒ ▒║
╚╦════╝ ╦═ ══
Ini juga berlaku untuk solusinya. Artinya, tidak diperlukan untuk menghubungkan sel:
╔════╩╗ ╔════╩╗ ╔════╩╗
║▒ ▒ ▒║ ║┌───┘║ ║┌ ─ ┘║
║ ═══ ║ ║│═══ ║ ║ ═══ ║
║▒ ▒ ▒║ == ║└───┐║ => ║└ ─ ┐║
║ ║ ║ │║ ║ ║
║▒ ▒ ▒║ ║┌───┘║ ║┌ ─ ┘║
╚╦════╝ ╚╦════╝ ╚╦════╝
Dalam contoh di atas, kedua solusi memiliki arti yang sama.
Ya, kasus uji. Di sini mereka:
Teka-teki 1
╔════╩╗ ╔════╩╗
║▒ ▒ ▒║ ║┌ ─ ┘║
║ ═══ ║ ║ ═══ ║
║▒ ▒ ▒║ => ║└ ─ ┐║
║ ║ ║ ║
║▒ ▒ ▒║ ║┌ ─ ┘║
╚╦════╝ ╚╦════╝
Teka-teki 2
╔═════╗ ╔═════╗
║▒ ▒ ▒║ ║┌ ─ ┐║
║ ║ ║ ║ ║ ║
╣▒ ▒║▒║ ╣└ ┐║│║
║ ║ ║ ║ => ║ ║ ║ ║
╣▒║▒ ▒╠ ╣┐║│ │╠
║ ║ ║ ║ ║ ║
║▒ ▒ ▒║ ║└ ┘ │║
╚════╦╝ ╚════╦╝
Teka-teki 3
╔════╩══╗ ╔════╩══╗
║▒ ▒ ▒ ▒║ ║┌ ┐ └ ┐║
║ ║ ║ ║ ║ ║ ║ ║
╣▒║▒ ▒║▒╠ ╣┘║└ ┐║│╠
║ ╚══ ║ ║ ║ ╚══ ║ ║
║▒ ▒ ▒ ▒╠ => ║┌ ─ ┘ │╠
║ ═══ ║ ║ ═══ ║
║▒ ▒ ▒ ▒║ ║│ ┌ ┐ │║
║ ║ ║ ║ ║ ║
║▒ ▒║▒ ▒║ ║└ ┘║└ ┘║
╚═══╩═══╝ ╚═══╩═══╝
puzzle 4
╔═══════╗ ╔═══════╗
║▒ ▒ ▒ ▒║ ║┌ ┐ ┌ ┐║
║ ║ ║ ║ ║ ║
╣▒ ▒ ▒║▒╠ ╣│ └ ┘║└╠
║ ══╦═╩═╣ ║ ══╦═╩═╣
║▒ ▒║▒ ▒║ ║└ ┐║┌ ┐║
║ ║ ║ => ║ ║ ║
╣▒ ▒║▒ ▒║ ╣┐ │║│ │║
║ ║ ║ ║ ║ ║ ║ ║
╣▒║▒ ▒ ▒║ ╣│║└ ┘ │║
║ ║ ║ ║ ║ ║
║▒ ▒ ▒ ▒║ ║└ ─ ─ ┘║
╚═══════╝ ╚═══════╝
Teka-teki 5
╔══╩══════╗ ╔══╩══════╗
║▒ ▒ ▒ ▒ ▒║ ║┌ ─ ┐ ┌ ┐║
║ ║ ║ ║ ║ ║
║▒ ▒║▒ ▒ ▒╠ ║└ ┐║└ ┘ │╠
║ ╠════ ║ ║ ╠════ ║
║▒ ▒║▒ ▒ ▒║ => ║┌ ┘║┌ ─ ┘║
║ ║ ║ ║ ║ ║
║▒ ▒║▒ ▒ ▒╠ ║└ ┐║└ ─ ─╠
║ ╠═════╣ ║ ╠═════╣
║▒ ▒║▒ ▒ ▒║ ║┌ ┘║┌ ─ ┐║
║ ║ ║ ║ ║ ║
║▒ ▒ ▒ ▒ ▒║ ║└ ─ ┘ ┌ ┘║
╚══╦═══╦══╝ ╚══╦═══╦══╝
Teka-teki 6
╔═══════════╗ ╔═══════════╗
║▒ ▒ ▒ ▒ ▒ ▒║ ║┌ ┐ ┌ ┐ ┌ ┐║
║ ║ ║ ║
║▒ ▒ ▒ ▒ ▒ ▒║ ║│ └ ┘ └ ┘ │║
║ ═══ ║ ║ ═══ ║
║▒ ▒ ▒ ▒ ▒ ▒║ ║└ ┐ ┌ ─ ─ ┘║
║ ═══ ║ ║ ═══ ║
╣▒ ▒ ▒ ▒ ▒ ▒╠ => ╣┐ │ │ ┌ ┐ ┌╠
║ ║ ║ ║
║▒ ▒ ▒ ▒ ▒ ▒║ ║│ │ │ │ │ │║
║ ║ ║ ║ ║ ║ ║ ║
║▒ ▒║▒ ▒║▒ ▒║ ║│ │║│ │║│ │║
║ ║ ║ ║ ║ ║ ║ ║
║▒ ▒ ▒ ▒ ▒ ▒║ ║└ ┘ └ ┘ └ ┘║
╚═══════════╝ ╚═══════════╝
Teka-teki 7
╔════╩════════╦╩╗ ╔════╩════════╦╩╗
║▒ ▒ ▒ ▒ ▒ ▒ ▒║▒║ ║┌ ─ ─ ─ ─ ─ ┐║│║
║ ║ ║ ║ ║ ║ ║ ║ ║ ║
║▒║▒ ▒ ▒ ▒║▒ ▒ ▒║ ║│║┌ ─ ─ ┐║┌ ┘ │║
║ ║ ║ ═══ ║ ║ ║ ║ ║ ═══ ║ ║
║▒ ▒║▒ ▒ ▒ ▒ ▒ ▒╠ ║│ │║┌ ─ ┘ └ ┐ │╠
║ ║ ║ ║ ║ ║
║▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒║ ║│ │ └ ┐ ┌ ┐ └ ┘║
║ ║ ║ ══╣ ║ ║ ║ ══╣
║▒ ▒ ▒║▒║▒ ▒ ▒ ▒║ ║│ └ ┐║│║│ └ ─ ┐║
║ ║ ║ ║ ║ ║ ║ ║
║▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒║ ║│ ┌ ┘ │ └ ┐ ┌ ┘║
║ ║ ══╣ => ║ ║ ══╣
║▒ ▒ ▒ ▒ ▒ ▒║▒ ▒║ ║└ ┘ ┌ ┘ ┌ ┘║└ ┐║
╠══ ║ ╚══ ║ ╠══ ║ ╚══ ║
║▒ ▒ ▒ ▒ ▒║▒ ▒ ▒║ ║┌ ┐ └ ┐ │║┌ ─ ┘║
║ ║ ║ ║ ║ ║ ║ ║ ║ ║
║▒ ▒ ▒║▒║▒ ▒ ▒ ▒║ ║│ └ ┐║│║│ └ ─ ┐║
║ ║ ║ ║ ╔══ ║ ║ ║ ║ ║ ╔══ ║
║▒║▒ ▒ ▒ ▒║▒ ▒ ▒║ ║│║┌ ┘ │ │║┌ ┐ │║
║ ║ ║ ║ ║ ║ ║ ║ ║ ║
║▒ ▒ ▒ ▒║▒ ▒ ▒ ▒║ ║│ └ ─ ┘║└ ┘ │ │║
║ ╚══ ║ ║ ╚══ ║
║▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒║ ║└ ─ ─ ─ ─ ─ ┘ │║
╚════╦═╦═╦═════╦╝ ╚════╦═╦═╦═════╦╝
Puzzle 8 (Maaf, saya benar-benar tidak punya solusi untuk yang ini)
╔══╩╦══╩═══╩═╩═╩═══╩╗
║▒ ▒║▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒║
║ ║ ║
╣▒ ▒║▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒║
║ ╚══ ╔══ ╔═══╣
╣▒ ▒ ▒ ▒║▒ ▒ ▒ ▒║▒ ▒╠
║ ║ ╔══ ║ ║
╣▒ ▒ ▒ ▒ ▒ ▒║▒ ▒ ▒ ▒╠
║ ║ ║
║▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒╠
║ ║ ║
╣▒ ▒ ▒ ▒ ▒ ▒║▒ ▒ ▒ ▒╠
║ ╔═══╗ ╚══ ║
╣▒ ▒║▒ ▒║▒ ▒ ▒ ▒ ▒ ▒║
║ ║ ║ ║
╣▒ ▒║▒ ▒║▒ ▒ ▒ ▒ ▒ ▒╠
║ ══╝ ║ ╔══ ║
║▒ ▒ ▒ ▒║▒ ▒ ▒ ▒║▒ ▒║
║ ══╗ ╚══ ╔══ ║ ║
╣▒ ▒ ▒║▒ ▒ ▒║▒ ▒ ▒ ▒╠
║ ║ ║ ║ ║
╣▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒║▒ ▒║
║ ═══ ══╗ ║ ║
╣▒ ▒ ▒ ▒ ▒ ▒║▒ ▒ ▒ ▒╠
╠══ ║ ║ ╔══ ║
║▒ ▒║▒ ▒ ▒ ▒ ▒ ▒║▒ ▒╠
║ ╚══ ║ ║ ║ ║
╣▒ ▒ ▒ ▒║▒ ▒║▒ ▒ ▒ ▒╠
║ ║ ║ ║
║▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒║
╚══╦═══╦═══╦═╦═╦═╦═╦╝
Memasukkan
Input kode Anda dapat memiliki representasi apa pun asalkan mengikuti aturan ini:
Itu harus berupa input grafis. Jadi tidak mungkin untuk membaca daftar koordinat, misalnya.
Dinding horisontal, dinding vertikal, dan pintu harus berbeda, dan harus dibuat dari karakter yang terlihat (tidak ada karakter kosong).
The
▒
dapat diganti dengan kosong. Saya hanya menggunakan karakter yang berbeda untuk menyorotnya.
Keluaran
Output juga dapat memiliki representasi apa pun asalkan mengikuti aturan-aturan ini:
Itu harus berupa keluaran grafis. Artinya, seseorang dapat melihat jalan dengan melihatnya.
Aturan nomor satu menyiratkan bahwa karakter jalur berbeda. Artinya, akan ada setidaknya 6 karakter jalur; horisontal, vertikal, dan sudut.
Agar jawaban menjadi valid, output harus papan yang sama dengan input (jelas) dengan semua sel (dalam representasi saya, the
▒
) diisi. Mengisi celah di antara sel adalah opsional.
Mencetak gol
Ini adalah kode-golf , jadi kode terpendek dalam byte menang.
1 Ada beberapa level Alcazar yang memiliki sel dan terowongan opsional. Ini tidak akan dipertimbangkan.
2 Ada beberapa papan Alcazar yang tidak mungkin.
sumber
Jawaban:
Python 3 ,
809728723714693688684663657641639627610571569 byteSunting: Disimpan 55 byte berkat @Felipe Nardi Batista
Tidak menjalankan test case terakhir dalam 60 detik pada TIO, tetapi harus bekerja dengan benar. Mengembalikan daftar koordinat untuk jalur. Sekitar 400 byte digunakan untuk mendapatkan daftar data dari I / O.
Cobalah online!
sumber
exec(...)
string Anda ada lima baris baru, direpresentasikan sebagai\n
, 5 * 2 = 10 byte. Menggunakan string yang dikutip tiga kali lipat akan menambah 4 byte (...''...''...
) tetapi kemudian menghapus 5 byte, karena karakter baris baru yang sebenarnya dapat digunakan. Secara total ini bisa menghemat satu byte.APL (Dyalog Classic) , 319 byte
Cobalah online!
Input digunakan
=#F7LJ<>^v.
sebagai ganti═║╔╗╚╝╣╠╩╦▒
agar sesuai dengan charset klasik .Semua test case kecuali untuk yang terakhir lulus dalam beberapa detik.
Tes terakhir memakan waktu 47 menit di komputer saya dan tidak menghasilkan solusi.
Ketika jalur yang dihasilkan menggunakan pintu di dekat sudut, jalan itu mungkin dibuat secara tidak benar (seolah-olah jejak itu bercabang dan melewati pintu imajiner tambahan), tetapi itu masih dapat dilihat dan tidak ambigu.
sumber
JavaScript (ES6), 274 byte
Input sebagai string multiline, setiap baris diakhiri dengan karakter baris baru. Pintunya ditandai dengan karakter '2'
Output sebagai string multiline dengan lintasan yang ditandai oleh karakter '1', sangat mudah terlihat.
Ini adalah Pencarian Pertama Kedalaman , mencoba semua jalur dan backtraking saat macet. Ini tidak efisien sama sekali, tetapi dapat memecahkan teka-teki 1 .. 6 dalam waktu kurang dari 1 menit.
Kurang golf
Di dalam cuplikan tes ada solusi menggunakan DFS dengan beberapa kendala yang memecahkan puzzle 7 dalam waktu kurang dari satu menit (pada PC saya). Puzzle 8 tidak memiliki solusi. Kendala:
Uji
Hati-hati, puzzle 7 jauh melampaui batas waktu untuk eksekusi javascript di browser apa pun (menggunakan pemecah Pendek dan Lambat)
Tampilkan cuplikan kode
sumber