Cara unjumble kata-kata dengan python

martinw89

1 Januari 2008, 11. 53 sore

Halo semua,
Saya telah melakukan Tantangan Python (http. // www. pythonchallenge. com), yang merupakan cara luar biasa untuk membiasakan diri dengan Python [/plug]. Saya memutuskan untuk menyiapkan skrip Python cepat untuk memecahkan teka-teki "campur aduk" di koran. Berikut ini adalah kodenya. File kamus yang dirujuk dalam file tersebut berasal dari "12dicts" di http. //Daftar kata. sourceforge. bersih/. Saya tidak mencantumkannya di postingan ini
#. /usr/bin/env python
'''Memecahkan teka-teki Jumble

Menggunakan regex untuk menemukan kemungkinan pengaturan huruf dengan mencocokkannya
sebuah file kamus
Dibuat dengan Vim dan Python 2. 5. '''

impor ulang
impor sistem

def string_to_list(string)
'''Mengambil string dan menambahkan setiap karakter ke daftar. '''
daftar_huruf = []
untuk char_num dalam rentang(len(string))
daftar_surat. tambahkan(string[char_num])
daftar_surat. menyortir()
mengembalikan daftar_surat

def dejumble (kata)
'''Menyelesaikan teka-teki "campur aduk".

"kata" adalah huruf-huruf yang akan "dicampur adukkan. '''
# Ekspresi reguler untuk mencocokkan urutan huruf apa pun dalam kata
regex = kembali. kompilasi("([" + kata + "]{" + repr(len(kata)) + "})")
#Simpan file kamus ke variabel. "
kamus = open("12dicts/5desk. txt", "r"). membaca()
#Temukan semua kecocokan. Tidak cocok dengan SETIAP karakter
possible_match_list = regex. temukan semua (kamus)
kata_huruf = string_to_list(kata)
daftar_pertandingan = []
#Sekarang hanya simpan kecocokan yang karakternya sama dengan aslinya
untuk Word_num dalam range(len(possible_match_list))
match_letters = string_to_list(possible_match_list[word_num])
jika match_letters == kata_huruf
match_list. tambahkan(possible_match_list[word_num])
match_list. menyortir()
#Hapus duplikat
untuk pertandingan di match_list
match_num = match_list. indeks(cocok)
mencoba
while match == match_list[match_num + 1]
del daftar_pertandingan[jumlah_pertandingan + 1]
kecuali IndexError
lulus
#Cetak korek api jika ada
jika len(daftar_pertandingan). = 0
cetak ""
print "*****Kemungkinan cocok. *****"
untuk match_num dalam range(len(match_list))
cetak repr(jumlah_kecocokan + 1) + ". ", daftar_pertandingan[jumlah_pertandingan]
print "******Akhir dari Kemungkinan Kecocokan*****"
cetak ""
kalau tidak
print "Maaf, tidak ditemukan kecocokan. \N"

def utama()
print "Masukkan kata untuk dejumble (ketik 'quit' untuk keluar)"
kata = raw_input("Kata. ")
jika kata. = "keluar"
meruntuhkan (kata)
utama()
kalau tidak
sys. keluar(0)

jika __nama__ == "__main__"
utama()
Jadi, yang saya ingin tahu adalah bagaimana cara membuat kode lebih efisien? . Terima kasih atas sarannya, saya yakin ini akan menarik untuk melihat seberapa efisiennya (tanpa hanya mem-porting ke C. ))

Sunting. Terima kasih atas bantuannya sejauh ini semuanya, inilah mengapa mempelajari Python itu hebat, semua orang baik. Juga, kode terbaru akan ada di setiap posting di mana saya mengubah sesuatu

martinw89

2 Januari 2008, 04. 51 pagi

](*,) SAYA TAHU ada fungsi string-list di Python. Terima kasih. Itu menghemat beberapa baris
Oke, kode baru

#. /usr/bin/env python
'''Memecahkan teka-teki Jumble

Menggunakan regex untuk menemukan kemungkinan pengaturan huruf dengan mencocokkannya
sebuah file kamus
Dibuat dengan Python 2. 5. '''

impor ulang
impor sistem

def dejumble (kata)
'''Menyelesaikan teka-teki "campur aduk".

"kata" adalah huruf-huruf yang akan "dicampur adukkan. '''
# Ekspresi reguler untuk mencocokkan urutan huruf apa pun dalam kata
regex = kembali. kompilasi("([" + kata + "]{" + repr(len(kata)) + "})")
#Simpan file kamus ke variabel. "
kamus = open("12dicts/5desk. txt", "r"). membaca()
#Temukan semua kecocokan. Tidak cocok dengan SETIAP karakter
possible_match_list = regex. temukan semua (kamus)
kata_huruf = daftar(kata)
kata_huruf. menyortir()
daftar_pertandingan = []
#Sekarang hanya simpan kecocokan yang karakternya sama dengan aslinya
untuk Word_num dalam range(len(possible_match_list))
match_letters = daftar(possible_match_list[word_num])
match_letters. menyortir()
jika match_letters == kata_huruf
match_list. tambahkan(possible_match_list[word_num])
match_list. menyortir()
#Hapus duplikat
untuk pertandingan di match_list
match_num = match_list. indeks(cocok)
mencoba
while match == match_list[match_num + 1]
del daftar_pertandingan[jumlah_pertandingan + 1]
kecuali IndexError
lulus
#Cetak korek api jika ada
jika len(daftar_pertandingan). = 0
cetak ""
print "*****Kemungkinan cocok. *****"
untuk match_num dalam range(len(match_list))
cetak repr(jumlah_kecocokan + 1) + ". ", daftar_pertandingan[jumlah_pertandingan]
print "******Akhir dari Kemungkinan Kecocokan*****"
cetak ""
kalau tidak
print "Maaf, tidak ditemukan kecocokan. \N"

def utama()
print "Masukkan kata untuk dejumble (ketik 'quit' untuk keluar)"
kata = raw_input("Kata. ")
jika kata. = "keluar"
meruntuhkan (kata)
utama()
kalau tidak
sys. keluar(0)

jika __nama__ == "__main__"
utama()

martinw89

2 Januari 2008, 05. 35 pagi

Itu poin yang bagus, setelah membaca beberapa artikel pengoptimalan, saya mengerti bahwa lebih cepat menggunakan nomor indeks untuk memanipulasi daftar daripada item (yang masuk akal). Namun dalam hal ini saya tidak melakukan sesuatu yang besar dan daftarnya sangat kecil, jadi keterbacaannya sepadan. Kode terbaru
#. /usr/bin/env python
'''Memecahkan teka-teki Jumble

Menggunakan regex untuk menemukan kemungkinan pengaturan huruf dengan mencocokkannya
sebuah file kamus
Dibuat dengan Vim dan Python 2. 5. '''

impor ulang
impor sistem

def dejumble (kata)
'''Menyelesaikan teka-teki "campur aduk".

"kata" adalah huruf-huruf yang akan "dicampur adukkan. '''
# Ekspresi reguler untuk mencocokkan urutan huruf apa pun dalam kata
regex = kembali. kompilasi("([" + kata + "]{" + repr(len(kata)) + "})")
#Simpan file kamus ke variabel. "
kamus = open("12dicts/5desk. txt", "r"). membaca()
#Temukan semua kecocokan. Tidak cocok dengan SETIAP karakter
possible_match_list = regex. temukan semua (kamus)
kata_huruf = daftar(kata)
kata_huruf. menyortir()
daftar_pertandingan = []
#Sekarang hanya simpan kecocokan yang karakternya sama dengan aslinya
untuk kecocokan dalam daftar_pertandingan_mungkin
match_letters = daftar(cocok)
match_letters. menyortir()
jika match_letters == kata_huruf
match_list. tambahkan (cocokkan)
match_list. menyortir()
#Hapus duplikat
untuk pertandingan di match_list
match_num = match_list. indeks(cocok)
mencoba
while match == match_list[match_num + 1]
del daftar_pertandingan[jumlah_pertandingan + 1]
kecuali IndexError
lulus
#Cetak korek api jika ada
jika len(daftar_pertandingan). = 0
cetak ""
print "*****Kemungkinan cocok. *****"
untuk match_num dalam range(len(match_list))
cetak repr(jumlah_kecocokan + 1) + ". ", daftar_pertandingan[jumlah_pertandingan]
print "******Akhir dari Kemungkinan Kecocokan*****"
cetak ""
kalau tidak
print "Maaf, tidak ditemukan kecocokan. \N"

def utama()
print "Masukkan kata untuk dejumble (ketik 'quit' untuk keluar)"
kata = raw_input("Kata. ")
jika kata. = "keluar"
meruntuhkan (kata)
utama()
kalau tidak
sys. keluar(0)

jika __nama__ == "__main__"
utama()

evymetal

3 Januari 2008, 04. 21 malam

* Menggunakan C tidak akan mempercepat ini, saya menganggap sebagian besar waktu dihabiskan dalam ekspresi reguler, dan setelah dikompilasi Anda tidak akan mendapatkannya lebih cepat tidak peduli bahasa apa yang Anda gunakan untuk memanggilnya. Ini adalah contoh sempurna mengapa sering kali tidak ada gunanya menulis sesuatu dalam C

* jika Anda melakukan ini dengan banyak kata campur aduk per eksekusi program maka akan jauh lebih cepat untuk memuat kamus ke dalam RAM sebelumnya (di loop utama) dan hanya meneruskannya ke fungsi (data dikirim melalui referensi jadi hampir tidak

* BTW, saya akan menyelesaikan masalah ini dengan membuat indeks terbalik pada unigram dalam satu kata (mirip dengan yang disarankan popch)

e. g
"makan" akan menjadi
[1,0,0,0,1,. ]
(1 "a", 1 "e" dst.)

Kemudian simpan ini sebagai kunci untuk "dict" atau serupa (mungkin pohon tertulis [dengan cerdik?] untuk menghemat memori), yang akan memiliki daftar kata sebagai datanya

Setelah ini selesai, fungsi hanya perlu melihat ke bawah 26 level untuk setiap kata yang campur aduk, dan mengembalikan daftar yang ditemukannya

(seharusnya mungkin untuk mengoptimalkan saran di atas untuk mengambil rata-rata kurang dari 26 level dengan menggunakan struktur seperti pohon yang lebih baik - tapi saya tidak yakin apakah lebih cepat menggunakan python dict, mereka dioptimalkan dengan baik secara internal - setidaknya

inisialisasi akan memakan waktu lebih lama. (Saya biasanya melakukan hal-hal berbasis server jadi saya tidak terlalu peduli dengan inisialisasi)

Bagaimana Anda memperbaiki kata-kata campur aduk dengan Python?

Bagaimana Anda mengatur kata-kata campur aduk?

Apa itu kata Unjumble?