Scralphabet
Kantung normal ubin Scrabble berisi huruf-huruf berikut ( ?
adalah ubin kosong, yang dapat digunakan untuk huruf lain):
AAAAAAAAABBCCDDDDEEEEEEEEEEEEFFGGGHHIIIIIIIIIJKLLLLMMNNNNNNOOOOOOOOPPQRRRRRRSSSSTTTTTTUUUUVVWWXYYZ??
Surat-surat memiliki nilai berikut:
{"A": 1,"B": 3,"C": 3,"D": 2,"E": 1,"F": 4,"G": 2,"H": 4,"I": 1,"J": 8,"K": 5,"L": 1,"M": 3,"N": 1,"O": 1,"P": 3,"Q": 10,"R": 1,"S": 1,"T": 1,"U": 1,"V": 4,"W": 4,"X": 8,"Y": 4,"Z": 10,"?": 0}
Diberikan kantong normal ubin Scrabble, buat kumpulan kata-kata non-berpotongan dengan skor tertinggi (yaitu, kata-kata individual, bukan pada papan Scrabble) dengan ketentuan sebagai berikut:
- Skor untuk setiap kata adalah
sum(letter_values) * length(word)
. - Anda hanya dapat memasukkan maksimal satu kata yang dimulai dengan setiap huruf alfabet (jadi, maksimal 26 kata).
- Hanya kata-kata Scrabble yang valid (dari kamus ini ) yang dapat dimasukkan. Anda dapat membaca kamus dari suatu file, mengkode-kodenya (ugh), atau mengikisnya dari situs web.
- Anda tidak perlu menggunakan setiap ubin, tetapi semua ubin yang tidak digunakan membentuk satu kata, mencetak dengan cara yang sama, yang mengurangi skor Anda.
Jika diinginkan, kode Anda dapat menerima dua input: isi tas sebagai string, dan nilai huruf dalam beberapa format yang mirip dengan python dict
(seperti di atas); sebagai alternatif, Anda dapat membuat hard-code isi tas dan nilai huruf. Seharusnya menampilkan kata-kata dalam set Anda, skor masing-masing, dan skor total Anda, dalam beberapa format yang masuk akal.
Kumpulan kata dengan skor tertinggi menang, dengan ikatan akan dikirim lebih dulu.
sumber
print"FOO18\nBAR15\nBAZ42\n...\n1523"
?Jawaban:
C, 2765 (optimal)
Edit
Sekarang semua dalam satu file C. Ini hanya menemukan semua solusi optimal. Mereka semua harus memiliki 6 kata 15 huruf dan satu kata 10 huruf yang terdiri dari 8 huruf bernilai 1 dan dua kosong. Untuk itu saya hanya perlu memuat sebagian kecil dari kamus dan saya tidak perlu mencari 15 kata kata dengan kosong. Kode adalah pencarian mendalam-pertama lengkap sederhana.
Pemakaian:
Perhatikan bahwa setiap solusi dicetak dua kali karena ketika menambahkan 15 huruf 'W' kata 2 pesanan dibuat karena ada 2 ubin 'W'.
Solusi pertama yang ditemukan dengan pemecahan titik:
Edit: penjelasan
Apa yang memungkinkan pencarian seluruh ruang? Sambil menambahkan kata baru saya hanya memperhitungkan kata-kata akun yang memiliki huruf sisa paling langka. Surat ini harus dalam beberapa kata (dan kata 15 huruf karena ini akan menjadi surat yang tidak bernilai 1, meskipun saya tidak memeriksanya). Jadi saya mulai dengan kata-kata yang mengandung
J, Q, W, W, X, Z
yang diperhitungkan50, 100, 100, 100, 200, 500
. Pada level yang lebih rendah saya mendapatkan lebih banyak cutoff karena beberapa kata dihilangkan oleh kurangnya huruf. Luasnya pohon pencarian di setiap tingkat:Tentu saja banyak cutoff diperoleh dengan tidak memeriksa solusi yang tidak optimal (kosong dalam 15 kata kata atau kata-kata pendek). Jadi sangat beruntung bahwa 2765 solusi dapat dicapai dengan kamus ini (tapi sudah dekat, hanya 2 kombinasi dari 15 kata kata memberikan sisa yang masuk akal). Di sisi lain, mudah untuk memodifikasi kode untuk menemukan kombinasi skor yang lebih rendah di mana tidak semua 10 huruf sisanya bernilai 1, meskipun akan lebih sulit untuk membuktikan ini akan menjadi solusi yang optimal.
Juga kode menunjukkan kasus klasik optimasi prematur. Versi
matches
fungsi ini membuat kode hanya 30% lebih lambat:Saya bahkan menemukan cara untuk membuat perbandingan paralel bit ajaib lebih pendek daripada di kode asli saya (nibble tertinggi tidak dapat digunakan dalam kasus ini, tetapi ini bukan masalah, karena saya hanya perlu 26 dari 32 nibble):
Tapi itu memberi keuntungan nol.
Edit
Menulis penjelasan di atas, saya menyadari bahwa sebagian besar waktu dihabiskan untuk memindai daftar kata-kata untuk mereka yang mengandung huruf tertentu yang tidak ada dalam
matches
fungsi. Menghitung daftar di muka memberi kecepatan 10x.sumber
Python 2, skor:
18402162Program ini pertama-tama menemukan kata skor terbaik yang tersedia dengan ubin yang diberikan (tanpa menggunakan wildcard), kemudian membuat 10.000 upaya untuk memasukkan kata-kata acak yang memenuhi batasan karakter pertama yang unik dan memiliki ubin yang tersedia. Dengan konstanta saat ini, program ini membutuhkan 27 detik untuk berjalan di mesin saya. Menggunakan konstanta yang lebih besar mungkin akan menemukan kombinasi kata yang lebih tinggi.
UPDATE: Sekarang menggunakan algoritma pemilihan 2 tahap, sehingga ia menemukan yang terbaik dari 50 kata di setiap tahap pilih. Skor penalti sekarang digunakan dalam algoritma evaluasi juga.
Di sini saya sertakan yang terbaik dari beberapa proses:
Perhatikan bahwa saya tidak menggunakan kartu liar dan membayar penalti yang lebih besar (karena panjang kata). Peningkatan di masa mendatang mungkin termasuk penggunaan wildcard.
sumber
Simulated annealing (skor 2246)
Sayangnya ini tidak deterministik. Saya akan mencoba memperbaikinya dan menemukan benih deterministik yang memberikan nilai lebih baik.
sumber
Python, skor
263826752676268926992717Hasil:
Kode:
Penjelasan:
Pencarian mendalam pertama yang mencari seluruh pohon, memilih antara
picks
kata-kata terbaik di setiap tahapSaya mengurutkan seluruh daftar kata satu kali dengan skor di awal. Setelah memilih setiap kata, untuk iterasi berikutnya saya menyaring semua kata yang sekarang tidak mungkin lagi, menjaga urutan, jadi saya tidak perlu mengurutkan daftar pada setiap langkah. Untuk berurusan dengan wildcard, jika ada kemungkinan kartu wild diperlukan, saya memilih 10.000 kandidat teratas, mengganti surat yang hilang dengan wildcard jika diperlukan, dan mengurutkan kembali berdasarkan skor baru (lebih rendah).
Output ini untuk
picks=5
dan8m01s
perlu dijalankan pada mesin 8-core saya.sumber
Java 8, skor
26412681Program dimulai dengan mengambil 40 kata terbaik. Untuk setiap kata, ia menemukan 40 kata terbaik untuk diikuti. Dari 1600 kombinasi, program mengambil 40 terbaik. Untuk setiap kombinasi, 40 kata terbaik ditemukan, dan siklus berulang.
Ketika hanya beberapa ubin yang tersisa, huruf-huruf yang tersisa digabungkan dengan dua kosong untuk kata terakhir.
Memperbarui
Saya meningkatkan ambang batas ke 50 kata terbaik. Juga, setiap kombinasi hanya menambahkan kata-kata yang kurang dari yang sudah ada. Ini mencegah banyak permutasi dari grup yang sama.
Program:
sumber
Perl, skor: 2655
2630Menggunakan:
Penggunaan blanko sebenarnya tidak memberikan banyak sementara secara signifikan memperlambat eksekusi:
Setelah menambahkan beberapa heuristik:
sumber
Python 3, skor 2735
(Skor optimal 2765, "6 kata dari 15 huruf dan satu kata 10 huruf yang terdiri dari 8 huruf bernilai 1 dan dua kosong" telah dicapai oleh nutki .)
Saya menggunakan pendekatan serakah yang mirip dengan yang lain:
Saya mulai dengan daftar satu elemen yang berisi kata-kata dengan skor tertinggi yang berisi Q's.
Di setiap langkah untuk setiap elemen daftar saya membuat
k = 800
daftar baru dengan kata-kata hukum terbaik untuk daftar. Dari daftar daftar agregat, saya menyimpank
daftar penilaian teratas dan mengulangi prosesnya 10 kali.Perhatikan bahwa Anda bisa mendapatkan
k
elemen teratas darin
daftar-panjang di O (n + k * log n) yang O (n) jikak<<n
seperti dalam kasus kami (k = 800, n ~= 250000
) dengan antrian tumpukan. Saya kira metode ini tidak digunakan dalam kiriman lain maka nilai yang lebih kecilk
.Saya menggunakan wildcard sepanjang jalan jika diperlukan untuk kata-kata.
Runtime adalah beberapa menit untuk
k = 800
. Nilai yang lebih besar dan optimasi lainnya belum menghasilkan hasil yang lebih baik.Hasil:
Saya bereksperimen dengan produk Descartes dari kata-kata terbaik yang mengandung Q, J dan X karena surat-surat ini jarang berbagi kata-kata. Skor terbaik saya dengan startegy ini adalah 2723 (
DEMISEMIQUAVERS OXYPHENBUTAZONE INTERSUBJECTIVE FLASHFORWARDING KNOWLEDGABILITY RADIOPROTECTION ANALOGUE EA
).Kode spageti rumit yang tidak perlu (dengan jejak eksperimen dengan metode lain):
sumber