Saya tertarik melihat jawaban untuk pertanyaan ini (sekarang sudah tidak ada) , tetapi belum pernah diperbaiki / diperbaiki.
Diberikan satu set dadu Boggle 6-sisi (konfigurasi dicuri dari pertanyaan ini ), tentukan dalam dua menit waktu pemrosesan konfigurasi papan mana yang akan memungkinkan untuk skor setinggi mungkin. (yaitu, dadu mana di lokasi mana dengan sisi atas memungkinkan untuk kumpulan kata skor terbanyak?)
OBJEKTIF
Kode Anda harus berjalan tidak lebih dari 2 menit (120 detik). Pada saat itu, ia harus secara otomatis berhenti berjalan dan mencetak hasilnya.
Skor tantangan final akan menjadi skor Boggle rata-rata 5 kali program.
- Jika terjadi seri, pemenangnya akan algoritma mana saja yang menemukan lebih banyak kata.
- Jika masih ada seri, pemenangnya adalah algoritma mana saja yang lebih panjang (8+) kata.
ATURAN / KENDALA
Ini adalah tantangan kode; panjang kode tidak relevan.
Silakan merujuk ke tautan ini untuk daftar kata (gunakan
ISPELL "english.0"
daftar - daftar SCOWL tidak memiliki beberapa kata yang cukup umum).- Daftar ini dapat dirujuk ke / diimpor / dibaca dalam kode Anda dengan cara apa pun yang Anda inginkan.
- Hanya kata-kata yang cocok dengan regex yang
^([a-pr-z]|qu){3,16}$
akan dihitung. (Hanya huruf kecil, 3-16 karakter, qu harus digunakan sebagai satu unit.)
Kata-kata dibentuk dengan menghubungkan huruf-huruf yang berdekatan (horizontal, vertikal, dan diagonal) untuk mengeja kata-kata dalam urutan yang benar, tanpa menggunakan die tunggal lebih dari sekali dalam satu kata tunggal.
- Kata-kata harus 3 huruf atau lebih; kata yang lebih pendek tidak akan menghasilkan poin.
- Surat duplikat dapat diterima, hanya saja tidak ada dadu.
- Kata-kata yang merentang tepi / silang dari satu sisi papan ke yang lain tidak diperbolehkan.
Skor Boggle akhir ( bukan tantangan ) adalah total nilai poin untuk semua kata yang ditemukan.
- Nilai poin yang ditetapkan untuk setiap kata didasarkan pada panjang kata. (Lihat di bawah)
- Aturan Boggle normal akan mengurangi / mengurangi kata-kata yang ditemukan oleh pemain lain. Asumsikan di sini tidak ada pemain lain yang terlibat dan semua kata yang ditemukan diperhitungkan dalam skor total.
- Namun, kata-kata yang ditemukan lebih dari satu kali di kotak yang sama hanya boleh dihitung satu kali.
Fungsi / program Anda harus MENCARI pengaturan yang optimal; hanya mengkodekan daftar yang telah ditentukan tidak akan berhasil.
Output Anda harus berupa kotak 4x4 dari papan permainan ideal Anda, daftar semua kata yang ditemukan untuk papan itu, dan skor Boggle untuk mencocokkan kata-kata itu.
KONFIGURASI MATI
A A E E G N
E L R T T Y
A O O T T W
A B B J O O
E H R T V W
C I M O T U
D I S T T Y
E I O S S T
D E L R V Y
A C H O P S
H I M N Qu U
E E I N S U
E E G H N W
A F F K P S
H L N N R Z
D E I L R X
MEJA SKOR BOGGLE STANDAR
Word length => Points
<= 2 - 0 pts
3 - 1
4 - 1
5 - 2
6 - 3
7 - 5
>= 8 - 11 pts
*Words using the "Qu" die will count the full 2 letters for their word, not just the 1 die.
CONTOH OUTPUT
A L O J
V U T S
L C H E
G K R X
CUT
THE
LUCK
HEX
....
140 points
Jika diperlukan klarifikasi lebih lanjut, silakan tanyakan!
sumber
4527
(1414
kata-kata total), ditemukan di sini: ai.stanford.edu/ ~ chuongdo^([a-pr-z]|qu){3,16}$
(yang salah akan mengecualikan kata-kata 3 huruf dengan qu, tetapi tidak ada).Jawaban:
C, rata-rata
500+15001750 poinIni adalah peningkatan yang relatif kecil dibandingkan versi 2 (lihat di bawah untuk catatan tentang versi sebelumnya). Ada dua bagian. Pertama: Alih-alih memilih papan secara acak dari kolam, program sekarang beralih ke setiap papan di kolam, menggunakan masing-masing secara bergiliran sebelum kembali ke atas kolam dan mengulangi. (Karena pool sedang dimodifikasi saat iterasi ini terjadi, masih akan ada papan yang dipilih dua kali berturut-turut, atau lebih buruk, tapi ini bukan masalah serius.) Perubahan kedua adalah bahwa program sekarang melacak ketika pool berubah , dan jika program berjalan terlalu lama tanpa memperbaiki konten kumpulan, itu menentukan bahwa pencarian telah "terhenti", mengosongkan kumpulan, dan memulai kembali dengan pencarian baru. Terus melakukan ini sampai dua menit habis.
Awalnya saya berpikir bahwa saya akan menggunakan semacam pencarian heuristik untuk melampaui kisaran 1500 poin. Komentar @ mellamokb tentang board 4527-point membuat saya berasumsi bahwa ada banyak ruang untuk perbaikan. Namun, kami menggunakan daftar kata yang relatif kecil. Papan 4527-point dinilai menggunakan YAWL, yang merupakan daftar kata yang paling inklusif di luar sana - bahkan lebih besar dari daftar kata resmi Scrabble AS. Dengan mengingat hal ini, saya memeriksa kembali papan-papan yang telah ditemukan oleh program saya dan memerhatikan bahwa ada set papan terbatas di atas sekitar 1700 atau lebih. Jadi misalnya, saya memiliki beberapa kali menjalankan yang telah menemukan papan skor 1726, tetapi selalu papan yang sama persis yang ditemukan (mengabaikan rotasi dan refleksi).
Sebagai tes lain, saya menjalankan program saya menggunakan YAWL sebagai kamus, dan ia menemukan papan 4527-point setelah sekitar selusin berjalan. Mengingat ini, saya berhipotesis bahwa program saya sudah berada di batas atas ruang pencarian, dan karena itu penulisan ulang yang saya rencanakan akan memperkenalkan kompleksitas ekstra untuk keuntungan yang sangat sedikit.
Berikut adalah daftar lima papan skor tertinggi yang ditemukan program saya menggunakan
english.0
daftar kata:Keyakinan saya adalah bahwa "papan grep" 1772 (sebagaimana saya sering menyebutnya), dengan 531 kata, adalah papan skor tertinggi yang mungkin dengan daftar kata ini. Lebih dari 50% dari dua menit program saya berakhir dengan board ini. Saya juga membiarkan program saya berjalan semalaman tanpa menemukan sesuatu yang lebih baik. Jadi jika ada papan skor yang lebih tinggi, kemungkinan harus memiliki beberapa aspek yang mengalahkan teknik pencarian program. Papan di mana setiap perubahan kecil yang mungkin pada tata letak menyebabkan penurunan besar dalam skor total, misalnya, mungkin tidak pernah ditemukan oleh program saya. Firasat saya adalah bahwa papan seperti itu sangat tidak mungkin ada.
Catatan untuk versi 2 (9 Juni)
Inilah salah satu cara untuk menggunakan versi awal kode saya sebagai titik awal. Perubahan pada versi ini terdiri dari kurang dari 100 baris, tetapi tiga kali lipat skor game rata-rata.
Dalam versi ini, program memiliki "kumpulan" kandidat, yang terdiri dari N papan skor tertinggi yang telah dihasilkan oleh program sejauh ini. Setiap kali papan baru dibuat, ditambahkan ke kolam dan papan skor terendah di kolam itu dihapus (yang mungkin merupakan papan yang baru saja ditambahkan, jika nilainya lebih rendah dari yang sudah ada). Kelompok ini awalnya diisi dengan papan yang dibuat secara acak, setelah itu ukurannya konstan sepanjang program dijalankan.
Lingkaran utama program terdiri dari memilih papan acak dari kumpulan dan mengubahnya, menentukan skor papan baru ini dan kemudian memasukkannya ke dalam kumpulan (jika skornya cukup baik). Dengan cara ini, program ini terus menyempurnakan papan skor tinggi. Kegiatan utama adalah membuat peningkatan bertahap, bertahap, tetapi ukuran kelompok ini juga memungkinkan program menemukan peningkatan multi-langkah yang sementara membuat skor dewan lebih buruk sebelum dapat membuatnya lebih baik.
Biasanya program ini menemukan maksimum lokal yang baik agak cepat, setelah itu mungkin ada maksimum yang lebih baik terlalu jauh untuk ditemukan. Jadi sekali lagi ada gunanya menjalankan program lebih dari 10 detik. Ini dapat ditingkatkan dengan misalnya membuat program mendeteksi situasi ini dan memulai pencarian baru dengan kumpulan kandidat baru. Namun, ini hanya akan menambah sedikit kenaikan. Teknik pencarian heuristik yang tepat kemungkinan akan menjadi jalan eksplorasi yang lebih baik.
(Catatan: Saya melihat bahwa versi ini menghasilkan sekitar 5k papan / detik. Karena versi pertama biasanya 20k papan / detik, saya awalnya khawatir. Namun setelah membuat profil, saya menemukan bahwa waktu ekstra dihabiskan untuk mengelola daftar kata. Dengan kata lain, itu sepenuhnya karena program menemukan lebih banyak kata per papan. Sehubungan dengan ini, saya mempertimbangkan untuk mengubah kode untuk mengelola daftar kata, tetapi mengingat bahwa program ini hanya menggunakan 10 dari 120 jatah yang dialokasikan, seperti optimasi akan sangat prematur.)
Catatan untuk versi 1 (2 Juni)
Ini adalah solusi yang sangat, sangat sederhana. Semua itu menghasilkan papan acak, dan kemudian setelah 10 detik output yang satu dengan skor tertinggi. (Saya default ke 10 detik karena tambahan 110 detik yang diizinkan oleh spesifikasi masalah biasanya tidak meningkatkan solusi akhir yang cukup layak untuk ditunggu.) Jadi itu sangat bodoh. Namun, ia memiliki semua infrastruktur untuk membuat titik awal yang baik untuk pencarian yang lebih cerdas, dan jika ada yang ingin memanfaatkannya sebelum batas waktu, saya mendorong mereka untuk melakukannya.
Program dimulai dengan membaca kamus ke dalam struktur pohon. (Bentuknya tidak seoptimal mungkin, tetapi lebih dari cukup untuk keperluan ini.) Setelah beberapa inisialisasi dasar lainnya, ia kemudian mulai membuat papan dan mencetaknya. Program memeriksa sekitar 20rb papan per detik pada mesin saya, dan setelah sekitar 200rb papan pendekatan acak mulai berjalan kering.
Karena hanya satu papan yang benar-benar dievaluasi pada waktu tertentu, data penilaian disimpan dalam variabel global. Ini memungkinkan saya untuk meminimalkan jumlah data konstan yang harus dilewati sebagai argumen untuk fungsi rekursif. (Saya yakin ini akan memberi beberapa orang gatal-gatal, dan kepada mereka saya minta maaf.) Daftar kata disimpan sebagai pohon pencarian biner. Setiap kata yang ditemukan harus dicari di daftar kata, sehingga kata-kata duplikat tidak dihitung dua kali. Namun, daftar kata hanya diperlukan selama proses evaulasi, sehingga dihapus setelah skor ditemukan. Dengan demikian, pada akhir program, papan yang dipilih harus dicetak lagi, sehingga daftar kata dapat dicetak.
Fakta menyenangkan: Skor rata-rata untuk papan Boggle yang dibuat secara acak, seperti yang dicetak oleh
english.0
, adalah 61,7 poin.sumber
VBA (rata-rata saat ini berkisar 80-110 poin, belum selesai)
Inilah proses kerja saya, tetapi jauh dari yang terbaik; skor terbaik absolut saya ditemukan di papan mana pun setelah banyak tes berjalan sekitar 120. Masih perlu ada pembersihan umum yang lebih baik dan saya yakin ada lebih banyak efisiensi yang bisa diperoleh di sejumlah tempat.
Ini mungkin terlihat mengerikan bagi sebagian dari Anda, tetapi seperti yang saya katakan, WIP. Saya sangat terbuka terhadap kritik yang membangun ! Maaf untuk tubuh yang sangat panjang ...
Modul Kelas Dadu :
Modul Kelas Pohon :
Modul Kelas TreeNode :
Modul Utama :
sumber
Cepat lihat ukuran ruang pencarian.
Mengurangi untuk mengecualikan pengulangan pada setiap dadu.
@breadbox menyimpan kamus sebagai pemeriksaan Hash Table O (1).
EDIT
Dewan Terbaik (Saya telah menyaksikan sejauh ini)
sumber
Entri saya ada di sini di Dream.In.Code ~ 30ms per pencarian papan (pada mesin 2 inti, harus lebih cepat dengan lebih banyak core)
sumber
:
di dalamnyahttp://
. ;-).NET
untukVBA
tidak terlalu sulit.