Tujuan dari tantangan ini adalah untuk menulis sebuah program yang dapat menebak kata dalam jumlah upaya sekecil mungkin. Ini didasarkan pada konsep acara TV Lingo ( http://en.wikipedia.org/wiki/Lingo_(US_game_show) ).
Aturan
Mengingat panjang kata yang dilewati sebagai argumen pertama pada baris perintahnya, program pemain melakukan lima upaya untuk menebak kata dengan menulis tebakan pada output standarnya diikuti oleh satu \n
karakter.
Setelah tebakan dibuat, program menerima string pada input standarnya, juga diikuti oleh satu \n
karakter.
String memiliki panjang yang sama dengan kata untuk menebak dan terdiri dari urutan karakter berikut:
X
: yang berarti bahwa huruf yang diberikan tidak ada dalam kata untuk menebak?
: yang berarti bahwa huruf yang diberikan hadir dalam kata untuk menebak, tetapi di lokasi lainO
: yang berarti bahwa surat di lokasi ini telah ditebak dengan benar
Misalnya, jika kata untuk menebak adalah dents
, dan program mengirimkan kata dozes
, itu akan menerima OXX?O
karena d
dan s
benar, e
salah tempat, dan o
dan z
tidak ada.
Berhati-hatilah bahwa jika sebuah huruf muncul lebih sering dalam upaya menebak daripada dalam kata untuk menebak, itu tidak akan ditandai sebagai ?
dan O
lebih dari jumlah kemunculan huruf dalam kata untuk menebak. Misalnya, jika kata untuk menebak adalah cozies
dan program mengirim tosses
, ia akan menerimaXOXXOO
karena hanya ada satu s
untuk menemukan.
Kata-kata dipilih dari daftar kata bahasa Inggris. Jika kata yang dikirim oleh program bukan kata yang valid dengan panjang yang benar, upaya dianggap sebagai kegagalan otomatis dan hanya X
kata yang dikembalikan.
Program pemain harus mengasumsikan bahwa file bernama wordlist.txt
dan mengandung satu kata per baris ada di direktori kerja saat ini, dan dapat dibaca seperlunya.
Tebakan seharusnya hanya terdiri dari huruf kecil alfabet ( [a-z]
).
Tidak ada operasi jaringan atau file lain yang diizinkan untuk program ini.
Permainan berakhir ketika string yang hanya terdiri dari O
dikembalikan atau setelah program melakukan 5 upaya dan tidak dapat menebak kata.
Mencetak gol
Skor permainan diberikan oleh rumus yang diberikan:
score = 100 * (6 - number_of_attempts)
Jadi, jika kata tersebut ditebak dengan benar pada percobaan pertama, diberikan 500 poin. Percobaan terakhir bernilai 100 poin.
Gagal menebak kata memberikan poin nol.
Lubang
Program pemain akan dievaluasi dengan mencoba membuat mereka menebak 100 kata acak untuk setiap panjang kata antara 4 dan 13 karakter secara inklusif.
Pemilihan kata acak akan dilakukan terlebih dahulu sehingga semua entri harus menebak kata yang sama.
Program yang menang, dan jawaban yang diterima, akan menjadi orang yang mencapai skor tertinggi.
Program akan dijalankan di mesin virtual Ubuntu, menggunakan kode di https://github.com/noirotm/lingo . Implementasi dalam bahasa apa pun diterima selama instruksi yang masuk akal untuk mengkompilasi dan / atau menjalankannya disediakan.
Saya menyediakan beberapa implementasi tes di ruby di repositori git, jangan ragu untuk mengambil inspirasi dari mereka.
Pertanyaan ini akan diperbarui secara berkala dengan peringkat untuk jawaban yang dipublikasikan sehingga penantang dapat meningkatkan entri mereka.
Evaluasi akhir resmi akan berlangsung pada tanggal 1 Juli .
Memperbarui
Entri sekarang dapat mengasumsikan keberadaan wordlistN.txt
file untuk mempercepat membaca daftar kata untuk panjang kata saat ini untuk N antara 4 dan 13 secara inklusif.
Misalnya, ada wordlist4.txt
file yang berisi keempat kata huruf, dan wordlist10.txt
berisi semua sepuluh kata huruf, dan sebagainya.
Hasil babak pertama
Pada tanggal 2014-07-01-01, tiga entri telah dikirimkan, dengan hasil sebagai berikut:
4 5 6 7 8 9 10 11 12 13 Total
./chinese-perl-goth.pl 8100 12400 15700 19100 22100 25800 27900 30600 31300 33600 226600
java Lingo 10600 14600 19500 22200 25500 28100 29000 31600 32700 33500 247300
./edc65 10900 15800 22300 24300 27200 29600 31300 33900 33400 33900 262600
** Rankings **
1: ./edc65 (262600)
2: java Lingo (247300)
3: ./chinese-perl-goth.pl (226600)
Semua entri dilakukan secara konsisten, dengan pemenang yang jelas, menjadi entri C ++ dari @ edc65.
Semua kontestan sangat mengagumkan. Sejauh ini saya belum bisa mengalahkan @ chinese-perl-goth.
Jika lebih banyak entri dikirimkan, evaluasi lain akan dilakukan. Entri saat ini juga dapat ditingkatkan jika Anda merasa dapat melakukan yang lebih baik.
sumber
Jawaban:
C ++ 267700 Poin
Porting dari mesin MasterMind lama.
Perbedaan dari MasterMind:
Ide dasarnya adalah memilih kata yang meminimalkan ruang solusi. Algoritma ini sangat lambat untuk tebakan pertama (maksud saya 'hari'), tetapi tebakan pertama yang terbaik hanya bergantung pada kata len, jadi hardcoded pada sumbernya. Tebakan-tebakan lainnya dilakukan dalam hitungan detik.
Kode
(Kompilasi dengan g ++ -O3)
Skor saya
Evaluasi dengan istilah, 100 putaran:
Total 265'100
Skor yang dievaluasi sendiri
Inilah poin rata-rata saya, yang dicetak di seluruh daftar kata. Tidak sepenuhnya dapat diandalkan karena beberapa detail algoritma telah berubah selama pengujian.
Menurut angka-angka ini, skor rata-rata saya harus dekat 257'800
PIT SCORE
Akhirnya saya menginstal Ruby, jadi sekarang saya memiliki skor 'resmi':
sumber
Java, 249700 poin (mengalahkan Perl Goth Cina dalam tes saya)
Daftar peringkat yang diperbarui:
Berikut adalah daftar peringkat lama menggunakan
pit.rb
:Dibandingkan dengan @chineseperlgoth, saya kalah dalam kata-kata yang lebih pendek (<6 karakter) tetapi saya menang dalam kata-kata yang lebih panjang (> = 6 karakter).Idenya mirip dengan @chineseperlgoth, hanya saja ide utama saya adalah tentang menemukan tebakan (bisa berupa kata dengan panjang yang sama, belum tentu salah satu dari kemungkinan yang tersisa) yang memberikan informasi paling banyak untuk tebakan berikutnya.
Saat ini saya masih bermain dengan formula, tetapi untuk papan skor di atas, saya memilih kata yang akan menghasilkan minimum untuk:Versi terbaru menggunakan skor berbeda untuk menemukan tebakan terbaik berikutnya, yang memaksimalkan jumlah "satu kemungkinan" setelah tebakan saat ini. Ini dilakukan dengan mencoba semua kata dalam daftar kata yang telah dipangkas (untuk menghemat waktu) pada semua kandidat yang mungkin, dan melihat tebakan mana yang lebih memungkinkan untuk menghasilkan "kemungkinan tunggal" (yaitu, setelah tebakan ini hanya akan ada satu kemungkinan jawaban) untuk tebakan selanjutnya.
Jadi misalnya menjalankan ini:
Dari tiga tebakan pertama, kita sudah mendapatkan "* oo * s" dengan "n" di suatu tempat dan kita masih perlu mencari satu surat lagi. Sekarang keindahan dari algoritma ini adalah bahwa alih-alih menebak kata-kata yang mirip dengan bentuk itu, alih-alih menebak kata yang tidak ada hubungannya dengan tebakan sebelumnya sama sekali, mencoba memberikan lebih banyak huruf, semoga mengungkapkan huruf yang hilang. Dalam hal ini kebetulan juga mendapatkan posisi untuk "b" yang hilang dengan benar, dan diakhiri dengan tebakan akhir yang tepat "boons".
Ini kodenya:
sumber
Perl
Masih ada beberapa ruang untuk perbaikan tetapi setidaknya itu mengalahkan contoh pemain yang disertakan :)
Mengasumsikan akses tulis ke direktori saat ini untuk menyimpan daftar kata (untuk membuatnya berjalan sedikit lebih cepat); akan membuat
wordlist.lenN.stor
file menggunakanStorable
. Jika ini merupakan masalah, hapusread_cached_wordlist
dan ubah kode hanya untuk digunakanread_wordlist
.Penjelasan
Pertama, saya membuat histogram frekuensi huruf di semua kata dalam daftar kata saat ini (
build_histogram
). Maka saya perlu memilih tebakan saya berikutnya - yang dilakukan olehfind_best_word
. Algoritma penilaian hanya menambahkan nilai histogram bersamaan, melompati huruf yang sudah terlihat. Ini memberi saya kata yang berisi surat paling sering di daftar kata. Jika ada lebih dari satu kata dengan skor yang diberikan, saya memilih satu secara acak. Setelah menemukan sebuah kata, saya mengirimkannya ke mesin permainan, membaca jawabannya lalu mencoba dan melakukan sesuatu yang berguna dengannya :)Saya memelihara serangkaian kondisi, yaitu, huruf yang dapat terjadi pada posisi tertentu dalam sebuah kata. Pada awalnya, ini hanya sederhana
(['a'..'z'] x $len)
, tetapi diperbarui berdasarkan petunjuk yang diberikan dalam balasan (lihatupdate_conds
). Saya membangun regex dari kondisi itu dan memfilter daftar kata melalui itu.Selama pengujian saya menemukan bahwa penyaringan tersebut tidak menangani
?
dengan baik, maka filter kedua (filter_wordlist_by_reply
). Ini mengambil keuntungan dari fakta bahwa huruf yang ditandai?
terjadi pada kata pada posisi yang berbeda, dan menyaring daftar kata yang sesuai.Langkah-langkah ini diulang untuk setiap iterasi dari loop utama, kecuali jika solusinya ditemukan (atau tidak mungkin membaca dari stdin lagi, yang berarti kegagalan).
Kode
sumber