Johnny mencoba membuat teka-teki silang, tetapi ia kesulitan membuat kata-kata yang cocok satu sama lain.
Dia telah datang dengan beberapa kata persegi panjang sederhana: yaitu, kelompok kata-kata yang membentuk persegi panjang di mana semua jalur horizontal dan vertikal membentuk sebuah kata.
//2x2
PA
AM
//2x3
GOB
ORE
//3x3
BAG
AGO
RED
//3x4
MACE
AGES
WEES
Namun, untuk membuat teka-teki yang baik, ia membutuhkan beberapa kata persegi panjang yang agak lebih besar dari 3x4. Alih-alih menderita karena pengaturan surat selama berjam-jam, Johnny lebih memilih untuk memiliki program yang melakukan ini untuknya - dan dalam karakter sesedikit mungkin, karena blok kode yang panjang sangat menakutkan bagi programmer biasa seperti Johnny.
Diberikan
- sebuah file teks kamus mana kata-kata dipisahkan oleh baris baru dalam urutan abjad,
- input menentukan jumlah baris dan kolom dalam kata-kata persegi panjang (yang dapat disediakan namun paling nyaman dalam bahasa pemrograman pilihan Anda)
menghasilkan setidaknya satu kata persegi panjang. Jika tidak mungkin untuk menghasilkan kata persegi panjang dengan leksikon dan dimensi yang diberikan, program tidak perlu memiliki perilaku yang ditentukan. Tidak perlu bagi program untuk dapat menghasilkan persegi panjang yang berisi lebih dari 64 huruf atau memiliki dimensi yang melebihi 8 di kedua arah. Program harus dapat menyelesaikan dalam jumlah waktu yang wajar, katakanlah, dalam tiga puluh menit atau kurang.
EDIT: Jika Anda melakukan NxN persegi panjang, Anda diizinkan untuk menggunakan file kamus yang lebih kecil yang hanya berisi kata-kata yang memiliki panjang N huruf.
Jawaban:
Haskell, 586 karakter
Diminta dengan memberikan 3 argumen: jumlah baris, jumlah kolom, jumlah solusi; dan daftar kata diterima pada
stdin
:Seperti yang Anda lihat 7x7 berjalan relatif cepat. Waktu masih 8 × 8 dan 7 × 6 ....
Akan lebih pendek 9 karakter untuk menghapus jumlah argumen solusi dan hanya menghasilkan semua solusi, tetapi kemudian menjadi tidak mungkin waktu.
Map String a
lebih lambat daripada pohon buatan tanganMap Char a
...Vector
jauh lebih cepat daripada menggunakan yang sederhanaMap
. Kenapa melakukan ini? Karena saya pikir solusi yang lebih dekat ke tujuan 8x8 di bawah ½ jam lebih disukai daripada solusi yang lebih pendek.sumber
--make
setelah ghc) dengan daftar kata yang diposting dalam pertanyaan, saya mendapatkan kata-kata yang tidak ada dalam daftar, seperti "zymesz" dan "muda".Python, 232 karakter
Ini hanya dapat menangani hingga 6x6 dalam batas 1/2 jam.
sumber
3,3
tetapi kata3x4
+2
menjadi+1
s.\r
dariw
, dan di Linux saya telah mengkonversi file ke format Unix, sehingga keduanya tidak berfungsi.Java (1065 byte)
Jauh dari menjadi yang terpendek, tapi saya pikir itu yang paling dekat dengan memenuhi batasan waktu. Saya menyimpan 14 byte dengan mengasumsikan bahwa file input telah disaring dengan kata-kata dengan panjang yang tepat; di netbook saya, jika Anda memberi makan keseluruhan
words.txt
maka ia menghabiskan menit pertama preprocessing itu, membuang sebagian besar apa yang dihasilkannya, dan kemudian hanya membutuhkan sekitar 20 detik untuk menyelesaikan 7x7. Di desktop saya itu melakukan semuanya dalam waktu kurang dari 15 detik, memberikan:Saya telah membiarkannya berjalan selama lebih dari 50 jam tanpa menemukan solusi 8x7 atau 8x8. Kata 8 huruf sepertinya menjadi batas kritis untuk masalah ini - hanya sekitar setengah penuh tanpa membuat banyak kemajuan.
Pendekatan yang digunakan adalah pivot penuh dan heuristik berdasarkan jumlah kemungkinan penyelesaian horizontal dikalikan jumlah kemungkinan penyelesaian vertikal. Misal jika kita memiliki kisi perantara
lalu kita beri sudut kiri atas nilai heuristik
count(aean*)count(aa***) + count(bean*)count(ba***) + ... + count(zean*)count(za***)
. Dari semua sel, kita memilih sel dengan nilai heuristik terkecil (yaitu yang paling sulit untuk dipenuhi), dan kemudian bekerja dengan huruf-huruf dalam urutan jumlah yang mereka berikan pada nilai heuristik sel tersebut (yaitu mulai dengan yang paling mungkin berhasil) ).sumber
F #
Solusi mundur, tapi saya akan mengoptimalkan ruang pencarian nanti.
sumber
awk, 283
(mungkin perlu menambahkan 14 untuk flag input parameter)
Panggil dengan misalnya
awk -v x=2 -v y=2
...Temukan kecocokan pertama dan cetak (283 karakter):
Temukan jumlah kecocokan (245 karakter, jauh lebih lambat):
Untuk kedua program (tentu saja lebih untuk solusi dihitung), waktu berjalan jauh melebihi 30 menit untuk beberapa nilai x dan y.
Yang menarik, berikut adalah jumlah kata untuk setiap panjang kata:
sumber