TANTANGAN
Diberi satu set surat yang dikelompokkan, atur di papan agar menutupi seluruh area.
Representasi Dewan (alias DECK KAPAL)
- Papan adalah kotak 6x6.
- Akan selalu ada total 36 kotak.
- Kolom ditandai AF.
- Baris ditandai 1-6.
Contoh:
A B C D E F
+---+---+---+---+---+---+
1 : : : : : : :
+---+---+---+---+---+---+
2 : : : : : : :
+---+---+---+---+---+---+
3 : : : : : : :
+---+---+---+---+---+---+
4 : : : : : : :
+---+---+---+---+---+---+
5 : : : : : : :
+---+---+---+---+---+---+
6 : : : : : : :
+---+---+---+---+---+---+
INPUT (alias CRATES)
- String multiline yang berisi sekumpulan huruf yang dikelompokkan.
- Peti dibuat dari kelompok huruf yang identik.
- Peti tersebut IMMUTABLE, artinya mereka tidak dapat diputar atau dibalik.
- Titik awal untuk setiap peti ada di kiri atas (harus diperhitungkan saat memindahkan peti ke geladak).
- Dari titik kiri atas kotak, kotak identik berikut ini hanya bisa ke kanan atau di bawah.
- Setiap huruf dapat digunakan untuk mewakili peti. Peti selalu dimulai dengan huruf
[a]
dan naik alfabet. - Peti diberi label dengan hurufnya (yaitu peti A, peti B, dll.)
- Jumlah peti dapat bervariasi (tidak selalu 10, terlepas dari contoh yang diberikan).
- Ada 24 karakter yang memisahkan setiap blok krat per baris. (mulai dari [a] hingga awal [b] dipisahkan oleh 24 karakter, dll.)
Contoh:
[a][a][a] [b] [c][c]
[a] [b][b][b] [c]
[a] [b][b]
[d] [e] [f][f][f][f][f]
[d][d] [e]
[d][d] [e]
[e]
[e][e]
[g] [h] [i]
[g] [i]
[i]
KELUARAN
Anda harus mencetak serangkaian perintah yang menempatkan peti pada posisi di geladak sehingga tertutup sepenuhnya (tidak ada ruang kosong).
Format perintahnya seperti ini:
HAUL <crate> TO <column> <row>
yaitu HAUL E TO A 1
Untuk klarifikasi, akan selalu ada solusi untuk input yang diberikan.
TES CASES <- Klik untuk lebih banyak.
Memasukkan
[a][a][a] [b] [c][c][c]
[a][a] [b]
[a] [b][b]
[b][b]
[d] [e] [f]
[d] [f]
[d] [f]
[d]
[d]
[g][g] [h] [i]
[i][i]
[i]
[i][i]
[j][j][j]
Keluaran
HAUL I TO A 1
HAUL B TO A 3
HAUL A TO B 1
HAUL J TO D 6
HAUL D TO F 1
HAUL F TO E 1
HAUL C TO C 5
HAUL G TO D 4
HAUL E TO D 3
HAUL H TO C 6
Hasil:
A B C D E F
+---+---+---+---+---+---+
1 : i : a : a : a : f : d :
+---+---+---+---+---+---+
2 : i : i : a : a : f : d :
+---+---+---+---+---+---+
3 : b : i : a : e : f : d :
+---+---+---+---+---+---+
4 : b : i : i : g : g : d :
+---+---+---+---+---+---+
5 : b : b : c : c : c : d :
+---+---+---+---+---+---+
6 : b : b : h : j : j : j :
+---+---+---+---+---+---+
SKOR
Ini adalah kode-golf sehingga jawaban terpendek dalam karakter menang.
code-golf
sequence
decision-problem
parsing
board-game
Jonathan Picazo
sumber
sumber
Jawaban:
Python 3.6,
435437385331 bytePanggil
F()
dengan string peti.Berhasil bermain golf lebih banyak:
re
perpustakaan.Merestrukturisasi kode untuk menghapus loop yang berlebihan.
Kode sebelumnya membuat daftar semua posisi peti
F()
dan kemudian mengulangi daftar ituR()
. Kode baru menciptakan satu posisi petiF()
danR()
mencoba semua posisi yang memungkinkan.Dalam kode sebelumnya,
R()
kumpulkan solusi yang mungkina
danF()
kemudian diulangi kembali solusi. Dalam kode baru,R()
cetak perintah HAUL secara langsungPenjelasan
Ide dasarnya adalah untuk mewakili dek kapal dan peti sebagai peta bit. Dengan menggunakan bitmap, memindahkan peti menjadi pergeseran bitmap-nya dan memeriksa tumpang tindih antar krat menjadi sedikit-bijaksana DAN dan menguji nol.
Kode tidak dikunci:
F()
mem-parsing string definisi peti dan membangun peta bit. Regex mencari (baris 9) setiap baris string definisi peti untuk peti (surat diikuti oleh ']'). Ketika kecocokan ditemukan, korespondensi (baris, kolom) ditambahkan ke kamus yang dikunci dengan huruf (baris 11-13). Sebagai contoh string definisi peti yang diberikan dalam masalah:Koordinat setiap peti dinormalisasi (baris 17), sehingga setiap peti mulai dari (0,0) dan setiap blok memiliki lebar satu unit (bukan 3 a la '[a]').
Bitmap kemudian dibuat untuk setiap peti berdasarkan koordinat dinormalisasi (baris 18).
Dek diperlakukan sebagai kisi 7 x 7. Kolom 'G' dan baris 7 digunakan untuk mendeteksi ketika sebuah bentuk memanjang dari papan. Bitmap memiliki 1 jika peti akan menempati kotak yang sesuai di dek. Bit 48 hingga bit menjadi 42 sesuai dengan kuadrat A1 ke A7, bit 41 hingga 35 sesuai dengan kuadrat B1 ke B7, dan seterusnya.
R(used, bitmaps)
kemudian menggunakan bitmap untuk secara rekursif mencari penempatan peti yang tidak mencoba menempatkan dua peti di kotak yang sama.used
adalah bitmask yang mengindikasikan kotak mana yang tidak dapat digunakan karena mereka sudah ditempati oleh peti atau karena mereka berada di luar papan (yaitu, kolom G dan baris 7).bitmaps
adalah daftar peti yang masih perlu diletakkan.Kasing dasar untuk rekursi adalah ketika tidak ada lagi peti yang dibiarkan, yaitu,
bitmaps
kosong (baris 23). Dalam hal ini True dikembalikan untuk menunjukkan solusi telah ditemukan.Jika tidak, nama peti dan bitmapnya muncul dari daftar bitmap (baris 26). Meskipun bitmap peti tidak kosong (baris 28), periksa apakah penempatan peti saat ini, diwakili oleh bitmap peti, bertentangan dengan peti yang sebelumnya ditempatkan. Pada baris 29,
not used & crate_bitmap
adalah False jikaused
dancrate_bitmap
keduanya memiliki 1 pada posisi bit yang sama, yang menunjukkan konflik. Jika tidak ada konflik,R()
disebut rekursif (baris 30) untuk mencoba dan menempatkan peti yang tersisa.Jika panggilan rekursif ke
R()
mengembalikan True, itu berarti bahwa solusi telah ditemukan dan penempatan peti saat ini adalah bagian dari solusi itu. Jadi perintah yang sesuai untuk memindahkan peti dicetak dan True diperbanyak ke atas panggilan rekursif (baris 31-32).Ketika dibuat
F()
, setiap bitmap mewakili kotak dek yang akan ditempati oleh peti jika ditempatkan di posisi A1. Menggeser bitmap satu bit ke kanan berhubungan dengan memindahkan peti ke posisi A2. Pergeseran kanan tujuh bit terkait dengan memindahkan krat ke B1, dll. Misalnya, bitmap berikut mewakili krat 'a' di berbagai posisi:Jika kemungkinan penempatan peti tidak berfungsi karena bertentangan dengan peti yang ditempatkan sebelumnya (baris 30) atau karena tidak ada penempatan yang valid dari peti yang tersisa (baris 31). Peti dipindahkan ke posisi yang berbeda dengan menggeser bitmask ke kanan sedikit (baris 35).
Shift
melacak berapa banyak tempat peta bit telah digeser, yang sesuai dengan posisi saat ini dari peti.Jika bitmap kosong (nol), ini menunjukkan bahwa semua kemungkinan penempatan telah dicoba. Salah dikembalikan (baris 37) untuk menunjukkan kegagalan sehingga panggilan ke
R()
rekursi sebelumnya akan mencoba penempatan lain untuk peti tersebut.Untuk memastikan bahwa peti tidak memanjang dari sisi geladak, bit yang sesuai dengan kolom G dan baris 7 ditetapkan
used
untuk panggilan awal keR()
(baris 20).4432676798719
adalah dek kosong yang sesuai dengan0b0000001000000100000010000001000000100000011111111
sumber
Python 2 , 864 byte
Cobalah online!
Penjelasan
Banyak byte yang digunakan untuk mengurai peti dua dimensi yang dimasukkan melalui string tunggal. Peti diwakili sebagai daftar nilai boolean bersarang.
Setelah peti diurai, fungsi mempertimbangkan semua posisi yang mungkin dari semua peti. Untuk melakukannya, itu secara iteratif menyebut dirinya. Ketika menemukan posisi yang mustahil (jika peti akan ditempatkan di luar geladak atau di atas peti lain), ia membunuh cabang pohon rekursi saat ini untuk meningkatkan kinerja.
Ketika melihat bahwa kombinasi penempatan tertentu menghasilkan dek yang benar-benar tertutup, ia mencetak riwayat penempatan peti yang direkam dan keluar secara global dengan mencoba pembagian yang tanpa harapan. Instruksi pengangkutan tercetak bahkan disortir berdasarkan abjad.
Python 2 , 812 byte
Cobalah online!
Penjelasan
String peti diurai dan diubah menjadi sarang boolean yang terdaftar yang mewakili setiap peti.
Fungsi berulang menghasilkan semua daftar panjang yang mungkin sama dengan jumlah krat yang diberikan berisi bilangan bulat
0 <= x < 36
(semua posisi dek kapal yang memungkinkan). Setiap daftar ditafsirkan sebagai instruksi untuk memposisikan semua peti dan diuji. Jika daftar instruksi yang diuji menghasilkan dek tanpa ruang kosong, daftar instruksi harus valid dan dicetak.Menjadi sangat tidak efisien, saya tidak mengujinya pada test case yang disediakan, meskipun pada skenario dengan krat lebih sedikit (lihat tautan TIO). Karena algoritma mencari melalui setiap kemungkinan pengaturan, ia mencoba untuk melihatnya
36**10 = 3.656e15
. Namun secara teori itu masih harus bekerja.sumber
H
/M
keluar dari deklarasi fungsi, karena memiliki mereka dalam deklarasi membuat fungsi tidak dapat digunakan kembali. Bagus, Python.[i]
dengan[b]
, itu bekerja . Algoritma dapat ditingkatkan dengan terlebih dahulu menyortir peti sehingga yang lebih besar diuji sebelum yang kecil.JavaScript, 366
Catatan: fungsi ini dapat mem-parsing input yang lebih kompak, karena tidak peduli dengan spasi 24 chars, dan lubang di peti diperbolehkan.
Saya pikir itu bisa golf sedikit lebih, tapi sekarang pendek dan tidak terlalu lambat, jadi saya suka apa adanya
Kurang golf
Kasus uji banyak dari mereka
sumber