Ini adalah permainan kata dari serangkaian kartu aktivitas untuk anak-anak. Di bawah aturan adalah kode untuk menemukan triplet terbaik menggunakan / usr / share / dict / words. Saya pikir itu masalah optimasi yang menarik, dan saya bertanya-tanya apakah orang dapat menemukan perbaikan.
Aturan
- Pilih satu huruf dari masing-masing set di bawah ini.
- Pilih kata menggunakan huruf yang dipilih (dan yang lainnya).
- Skor kata.
- Setiap huruf dari set yang dipilih mendapatkan nomor yang ditunjukkan dengan set (termasuk berulang).
AEIOU
hitung 0- Semua huruf lainnya adalah -2
- Ulangi langkah 1-3 di atas (tanpa menggunakan kembali huruf pada langkah 1) dua kali lebih banyak.
- Skor akhir adalah jumlah dari skor tiga kata.
Set
(atur 1 skor 1 poin, atur 2 skor 2 poin, dll.)
- LTN
- RDS
- GBM
- CHP
- FWV
- YKJ
- QXZ
Kode:
from itertools import permutations
import numpy as np
points = {'LTN' : 1,
'RDS' : 2,
'GBM' : 3,
'CHP' : 4,
'FWV' : 5,
'YKJ' : 6,
'QXZ' : 7}
def tonum(word):
word_array = np.zeros(26, dtype=np.int)
for l in word:
word_array[ord(l) - ord('A')] += 1
return word_array.reshape((26, 1))
def to_score_array(letters):
score_array = np.zeros(26, dtype=np.int) - 2
for v in 'AEIOU':
score_array[ord(v) - ord('A')] = 0
for idx, l in enumerate(letters):
score_array[ord(l) - ord('A')] = idx + 1
return np.matrix(score_array.reshape(1, 26))
def find_best_words():
wlist = [l.strip().upper() for l in open('/usr/share/dict/words') if l[0].lower() == l[0]]
wlist = [l for l in wlist if len(l) > 4]
orig = [l for l in wlist]
for rep in 'AEIOU':
wlist = [l.replace(rep, '') for l in wlist]
wlist = np.hstack([tonum(w) for w in wlist])
best = 0
ct = 0
bestwords = ()
for c1 in ['LTN']:
for c2 in permutations('RDS'):
for c3 in permutations('GBM'):
for c4 in permutations('CHP'):
for c5 in permutations('FWV'):
for c6 in permutations('YJK'):
for c7 in permutations('QZX'):
vals = [to_score_array(''.join(s)) for s in zip(c1, c2, c3, c4, c5, c6, c7)]
ct += 1
print ct, 6**6
scores1 = (vals[0] * wlist).A.flatten()
scores2 = (vals[1] * wlist).A.flatten()
scores3 = (vals[2] * wlist).A.flatten()
m1 = max(scores1)
m2 = max(scores2)
m3 = max(scores3)
if m1 + m2 + m3 > best:
print orig[scores1.argmax()], orig[scores2.argmax()], orig[scores3.argmax()], m1 + m2 + m3
best = m1 + m2 + m3
bestwords = (orig[scores1.argmax()], orig[scores2.argmax()], orig[scores3.argmax()])
return bestwords, best
if __name__ == '__main__':
import timeit
print timeit.timeit('print find_best_words()', 'from __main__ import find_best_words', number=1)
Versi matriks adalah apa yang saya buat setelah menulis satu di python murni (menggunakan kamus dan mencetak setiap kata secara mandiri), dan yang lain di numpy tetapi menggunakan pengindeksan daripada pengalikan matriks.
Optimasi selanjutnya adalah menghapus vokal dari penilaian sepenuhnya (dan menggunakan ord()
fungsi yang dimodifikasi ), tapi saya ingin tahu apakah ada pendekatan yang lebih cepat.
EDIT : menambahkan kode timeit.timeit
EDIT : Saya menambahkan hadiah, yang akan saya berikan untuk perbaikan mana saja yang paling saya sukai (atau mungkin beberapa jawaban, tapi saya harus mendapatkan lebih banyak reputasi jika itu masalahnya).
Jawaban:
Dengan menggunakan ide Keith untuk menghitung skor terbaik untuk setiap kata, saya berhasil mengurangi waktu eksekusi menjadi sekitar 0,7 detik di komputer saya (menggunakan daftar 75.288 kata).
Caranya adalah dengan menelusuri kombinasi kata yang akan dimainkan alih-alih semua kombinasi huruf yang dipilih. Kami dapat mengabaikan semua kecuali beberapa kombinasi kata (203 menggunakan daftar kata saya) karena mereka tidak dapat memperoleh skor yang lebih tinggi dari yang telah kami temukan. Hampir semua waktu eksekusi dihabiskan untuk menghitung skor kata.
Python 2.7:
Ini mengembalikan solusi
['KNICKKNACK', 'RAZZMATAZZ', 'POLYSYLLABLES']
dengan skor 95. Dengan kata-kata dari solusi Keith ditambahkan ke daftar kata saya mendapatkan hasil yang sama dengannya. Dengan menambahkan "xylopyrography" milikmu, aku mendapat['XYLOPYROGRAPHY', 'KNICKKNACKS', 'RAZZMATAZZ']
skor 105.sumber
Ini ide - Anda dapat menghindari memeriksa banyak kata dengan memperhatikan bahwa sebagian besar kata memiliki skor buruk. Katakanlah Anda telah menemukan permainan skor yang cukup bagus yang memberi Anda 50 poin. Maka setiap permainan dengan lebih dari 50 poin harus memiliki kata setidaknya ceil (51/3) = 17 poin. Jadi kata apa pun yang tidak mungkin menghasilkan 17 poin dapat diabaikan.
Berikut beberapa kode yang melakukan hal di atas. Kami menghitung skor terbaik untuk setiap kata dalam kamus, dan menyimpannya dalam array yang diindeks oleh skor. Kemudian kami menggunakan array itu untuk memeriksa hanya kata-kata yang memiliki skor minimum yang diperlukan.
Skor minimum naik dengan cepat hingga 100, yang berarti kita hanya perlu mempertimbangkan 33+ kata-kata poin, yang merupakan fraksi yang sangat kecil dari total keseluruhan (saya
/usr/share/dict/words
memiliki 208662 kata yang valid, hanya 1723 di antaranya 33+ poin = 0,8%). Berjalan sekitar setengah jam di mesin saya dan menghasilkan:sumber