Diberikan daftar string, temukan matriks kuadrat terkecil yang berisi masing-masing string awal. String dapat muncul secara horizontal, vertikal atau diagonal dan maju atau mundur seperti dalam pertanyaan ini Puzzle Pencarian Kata .
Kata-kata harus ditempatkan di kotak, dengan setidaknya satu kata di setiap arah (horizontal, vertikal dan diagonal). Kata-kata akan muncul hanya satu kali.
Jadi, inputnya hanyalah daftar kata-kata. Sebagai contoh: CAT, TRAIN, CUBE, BICYCLE
. Salah satu solusi yang mungkin adalah:
B N * * * * *
* I * * C A T
* A C * * * *
* R * Y * * C
* T * * C * U
* * * * * L B
* * * * * * E
Saya mengganti mengisi surat dengan tanda bintang hanya untuk kejelasan. Keluaran yang diinginkan harus mencakup surat pengisian acak.
AC
di contoh Anda akan membuat yang lainCAT
jika ituT
.A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
tidak memiliki solusi.Jawaban:
JavaScript (ES6), 595
628 680Sunting Beberapa pembersihan dan penggabungan:
- fungsi P digabung di dalam fungsi R
- calc x dan z dalam .map yang sama
- ketika solusi ditemukan, atur x ke 0 untuk keluar dari loop luar
- definisi gabungan dan panggilan W
Edit2 lebih banyak bermain golf, isi acak disingkat, loop luar direvisi ... lihat riwayat untuk sesuatu yang lebih mudah dibaca
Berbeda dengan jawaban yang diterima,ini harus bekerja untuk sebagian besar input. Hanya hindari kata-kata satu huruf. Jika sebuah output ditemukan, itu optimal dan menggunakan semua 3 arah.Kendala untuk menghindari pengulangan kata sangat sulit. Saya harus mencari kata berulang di setiap langkah menambahkan kata ke grid, dan pada setiap karakter isian acak.
Subfungsi utama:
P (w) benar jika kata palindrome. Kata palindrom akan ditemukan dua kali ketika memeriksa kata-kata yang diulang.
R (s) periksa kata yang berulang pada kisi s
Q (s) mengisi kisi-kisi dengan karakter acak - itu rekursif dan mundur jika kata berulang - dan bisa gagal.
W () rekursif, cobalah untuk mengisi kotak ukuran yang diberikan, jika memungkinkan.
Fungsi utama menggunakan W () untuk menemukan kisi keluaran, mencoba dari ukuran kata terpanjang dalam input hingga jumlah panjang semua kata.
Tidak digabungkan dan dijelaskan (tidak lengkap, maaf guys ini banyak pekerjaan)
Uji di Firefox / konsol FireBug
F (['TRAIN', 'CUBE', 'BOX', 'BICYCLE'])
tidak diisi
F (['TRAIN', 'ARTS', 'RAT', 'CUBE', 'BOX', 'BICYCLE', 'STORM', 'BRAIN', 'DEPTH', 'MOUTH', 'MOUTH', 'SLAB'])
F (['AA', 'AB', 'AC', 'AD', 'AE', 'AF', 'AG'])
F (['AA', 'AB', 'AC', 'AD', 'AE', 'AF'])
output tidak terisi - @nathan: sekarang Anda tidak dapat menambahkan A x lainnya tanpa pengulangan. Anda akan membutuhkan kisi yang lebih besar.
sumber
C #
Berikut ini adalah implementasi sederhana dengan pekerjaan yang masih harus dilakukan. Ada sangat banyak kombinasi untuk mendapatkan ukuran terkecil. Jadi hanya menggunakan algoritma paling sederhana yang bisa dipikirkan.
Uji
sumber
at least one word in each direction (horizontal, vertical and diagonal)
. Menjalankan program pengujian, tanpa kata horisontal (3 vertikal, 1 diag)