Anda diminta untuk menulis pemecah Hangman. Pengujian terhadap daftar kata bahasa Inggris ini [1] , pemecah yang memecahkan jumlah kata terbanyak akan menang, dengan jumlah total tebakan yang salah menjadi tie-breaker. Semua kata dalam daftar kata akan diuji secara acak.
[1]: Daftar kata ini diambil dari sini , kemudian angkanya dihapus, lalu kata-kata dengan panjang 1 atau dengan karakter non-abjad dihapus, maka 4096 kata unik paling sering dipilih sebagai daftar kata ini.
Rinciannya:
Program Anda akan berinteraksi dengan program permainan, yang akan memberi Anda melalui stdin garis bawah dan surat-surat yang ditebak dengan benar. Program Anda akan memberikan untuk menerka tebakan Anda, dan itu harus disimpulkan dari input apakah tebakan sebelumnya benar atau salah. Setelah salah 6 kali, program Anda hilang. Program Anda harus siap untuk pertandingan berikutnya setelah setiap pertandingan berakhir (setelah menang atau kalah).
Panjang kode Anda harus benar-benar kurang dari 2048 byte, dan program Anda tidak boleh menggunakan sumber daya eksternal apa pun (termasuk tetapi tidak terbatas pada mengakses daftar kata pada penyimpanan lokal atau dari Internet).
Contoh : (Input didahului di >sini hanya untuk klarifikasi - sebenarnya tidak ada dalam input)
>_______ // 7 underscores
a // Now you wait for input again
>_a___a_
e
>_a___a_ // Implies that your guess is wrong
>_____ // new round, this will be given ONLY IF you already have 6 losses
Misalkan Anda salah untuk 6 kali, Anda akan menerima input akhir yang menyiratkan dugaan Anda salah, dan program Anda harus siap untuk memulai babak baru (yaitu mengambil input lain).
Jika kamu menang,
>_angman
h
>hangman
>_____ // new round
Setelah mengetahui bahwa Anda telah menang (karena input tidak memiliki garis bawah), Anda harus siap untuk menerima babak selanjutnya.
Program Anda harus berhenti ketika menerima input END.
Jika program Anda tidak deterministik (tergantung pada keacakan, pseudorandomness, waktu sistem, suhu sekitar, suasana hati saya, dll.), Anda harus secara eksplisit menyatakan bahwa dalam kiriman Anda, dan skor Anda akan diambil 10 kali (oleh saya, kecuali diinstruksikan lain) dan dirata-rata.
Catatan : jika Anda menggunakan bahasa seperti python, harap secara otomatis menghapus stdout Anda setelah setiap pernyataan cetak.
Program game adalah sebagai berikut (kredit ke nneonneo ):
import sys, random, subprocess
proc = subprocess.Popen(sys.argv[1:], stdin=subprocess.PIPE, stdout=subprocess.PIPE)
def p(x):
proc.stdin.write(x+'\n')
proc.stdin.flush()
wordlist=[]
f=open('wordlist.txt', 'r')
for i in f:
wordlist.append(i[:-1] if i[-1]=='\n' else i)
# wordlist=[i[:-1] for i in f]
random.shuffle(wordlist)
score=0
totalerr=0
for s in wordlist:
s2=[]
for i in s:
s2.append('_')
err=0
p(''.join(s2))
while err<6 and '_' in s2:
c=proc.stdout.readline().strip()
nomatch=True
for i in range(0, len(s)):
if s[i]==c:
s2[i]=c
nomatch=False
if nomatch:
err+=1
totalerr+=1
p(''.join(s2))
if err<6:
score+=1
p('END')
sys.stderr.write('score is '+str(score)+', totalerr is '+str(totalerr)+'\n')Pemakaian: python ./game.py [yoursolverprogram]
Contoh: python ./game.py ruby ./solver.rb
Ini harus bekerja seperti program penilaian lama, tetapi tidak tergantung pada pipa bernama, sehingga dapat bekerja pada platform lain. Rujuk ke riwayat revisi jika Anda tertarik pada yang lama.
sumber
subprocessfifo eksternal untuk menjalankan game? Dengan cara ini kode akan berfungsi untuk OS lain (misalnya, Cygwin di Windows). Berikut inigame.pydimodifikasi untuk digunakansubprocessuntuk memulai program bernama pada command-line: gist.github.com/nneonneo/d173f8888e1ea0c6fe37 . Gunakan sebagaipython game.py <program> [args], mispython game.py python hangman.py.Jawaban:
Python 2, skor = 2111
Jalankan dengan
python -u. (Untuk pengujian dengan pengontrol yang diberikanpython ./game.py python -u ./solver.py,.) Ini adalah 2044 kode byte + 1 untuk-u= 2045 byte.Hasil
Bagaimana itu bekerja
Program ini menggantikan semua
_s dengan1s dalam kondisi saat ini, memperlakukan hasilnya sebagai bilangan bulat-36, dan membawanya modulo 1879, memberikan kita fungsi hash mentah. Ia memilih huruf untuk ditebak dengan mengindeks nilai hash ini ke dalam string panjang huruf. Jika sudah menebak huruf itu sebelumnya, itu mengurangi modulus oleh 6 (jadi selalu relatif prima ke 36) dan mengambil huruf yang berbeda, mengulang sampai menemukan huruf yang belum ditebak.Saya merancang strategi ini untuk memiliki banyak variabel tweakable (huruf individu dari string panjang), yang sebagian besar akan secara mandiri mempengaruhi skor akhir dengan jumlah kecil. Itu membuatnya sangat cocok untuk optimasi gaya mendaki bukit — saya menggunakan Diversified Late Acceptance Search .
Python 2, skor = 2854
Dengan penggunaan byte bebas yang tidak dapat dicetak dan kompresi bawaan, kami dapat memeras lebih banyak informasi.
Dekode dengan
xxd -r, dan jalankan denganpython -u. (Untuk pengujian dengan pengontrol yang diberikanpython ./game.py python -u ./solver.py,.) Ini adalah 2047 kode byte + 1 untuk-u= 2048 byte.Hasil
sumber
Python: 2006 byte, skor = 1501
1885 byte, skor = 13371961 byte, skor = 1207Ini kiriman saya:
Skor hasil:
Program ini sepenuhnya deterministik. Gumpalan raksasa (yang merupakan
zlibdata terkompresi basis-64-disandikan ) adalah daftar pohon keputusan (satu pohon per kata panjang). Setiap pohon keputusan menyandikan pohon biner lengkap dengan kedalaman antara 2 dan 5. Setiap simpul internal adalah karakter tunggal, dan keputusan dihasilkan berdasarkan pada apakah karakter tersebut ada atau tidak dalam kata hangman.Setiap simpul daun pohon biner berisi tabel frekuensi yang dioptimalkan khusus untuk cabang pencarian pohon. Tabel ini secara khusus dioptimalkan untuk mendukung penyelesaian kata-kata tertentu, sementara sepenuhnya mengabaikan kata-kata lain (yang tidak dapat dijangkau karena anggaran "kegagalan" terbatas). Tabel tidak dioptimalkan untuk meminimalkan kesalahan, dan dengan demikian jumlah total program ini tinggi meskipun skornya (relatif) bagus.
Pengoptimal, yang tidak ditampilkan, menggunakan pengoptimal linier nondeterministik yang memanfaatkan strategi penurunan gradien acak untuk menghasilkan tabel frekuensi.
sumber
range(4)bisa diganti dengan[1]*4ketentuan bahwa Anda sebenarnya tidak perlu menggunakan nilaii.decode('zip')alih-alihdecode('zlib')Rubi
Pengajuan bersama dari pengguna PragTob dan saya sendiri.
Hasil:
Ini memiliki 1672 karakter dan belum di-golf, jadi kami memiliki ruang yang cukup untuk peningkatan algoritmik.
Pertama kita menyimpan hash frekuensi karakter (dihitung dari daftar kata) yang dikelompokkan berdasarkan panjang kata.
Kemudian di setiap babak kita cukup mengurutkan semua karakter berdasarkan frekuensi untuk panjang saat ini dan mencobanya dari yang paling umum ke yang paling umum. Dengan menggunakan pendekatan ini kami jelas gagal setiap kata yang bahkan hanya memiliki karakter umum menengah.
sumber
score is 625, totalerr is 23196masih terkini dengan algoritma Anda yang diperbarui? Saya mencoba yang serupa dan saya hanya mendapat maksimum 300.Pembaruan Menggunakan metode yang mirip dengan @nneonneo, saya tiba pada kode ini, tepatnya 2.047 karakter .
Skor:
Kode:
Entri lama
Hasil:
Ini bukan rata-rata karena algoritma ini bersifat deterministik, yaitu selalu memberikan skor yang sama untuk daftar kata yang diacak.
Inilah entri saya di Python 2.7; golf (717 karakter)
Ini menggunakan ide yang sama dengan @ m.buettner, menyimpan daftar surat yang diurut berikut yang akan dibuat tebakannya. Tapi, ini tidak menggunakan data frekuensi secara langsung, melainkan hanya mencoba hampir setiap permutasi huruf yang mungkin dan mensimulasikan permainan, dan akhirnya mengambil permutasi yang memberikan skor terbaik.
Versi ini dioptimalkan menggunakan top-9 huruf, jadi untuk kata-kata 2-huruf dan 3-huruf, permutasi sudah yang optimal, di kelas algoritma di mana informasi dari input sebelumnya diabaikan. Saat ini saya masih menjalankan kode untuk 10 huruf teratas, mengoptimalkan kata-kata 4 huruf (dan juga menemukan solusi yang lebih baik untuk kata-kata yang lebih panjang).
Entri tidak valid
Untuk pembandingan saya, berikut adalah kode yang menggunakan pohon keputusan penuh, 11092 karakter.
Skor:
Kode:
sumber
Perl, 1461 byte, skor = 1412, totalerr = 21050
(Catatan, ini 1461 bytes setelah menghapus sedikit spasi opsional. Seperti yang dicetak, ini sekitar seratus lebih berat, tetapi masih jauh di bawah 2000.)
Saya mencoba lebih banyak pendekatan "halus", tetapi yang satu ini akhirnya mengalahkan mereka semua. Dua string data hanyalah daftar peringkat karakter yang paling mungkin mengikuti setiap karakter, dan karakter yang paling mungkin mendahului setiap karakter (dengan digraf yang tidak muncul dalam daftar kata tidak terwakili sama sekali).
<dan>digunakan untuk mewakili awal dan akhir kata. Sebagai contoh,"w[aiehonrlsdtkfy]"berarti "wa" lebih umum daripada "wi" lebih umum daripada "kita" dll.%d, Pemetaan ke depan, termasuk peringkat global, disimpan sebagai$d{''}. Ini digunakan untuk tempat-tempat di mana ada dua yang tidak diketahui secara berurutan, atau di mana semua digraf di daftar kata habis (jadi kita harus berurusan dengan kata yang bukan daftar kata).Untuk setiap posisi yang tidak diketahui dalam kata, itu terlihat pada karakter sebelumnya, memberikan masing-masing karakter berikut kemungkinan skor, mulai dari 180 untuk peringkat teratas, dan menurun menjadi 80 pada akhir daftar; maka hal yang sama dilakukan untuk karakter berikut. Semua skor untuk semua karakter ditambahkan, dan skor dengan skor tertinggi dipilih.
Setelah surat ditebak, dihapus langsung dari tabel peringkat, sehingga tidak dapat ditebak lagi (sampai kita mulai kata baru dan menginisialisasi ulang tabel).
Pembaruan: memperoleh banyak poin dengan memperbaiki bug (kami tidak menghapus surat dari tabel terbalik) dan mengubah cara poin turun saat kami turun daftar.
sumber
Python: 2046 bytes, skor = 1365
skor 1365, totalerr adalah 21343
Banyak kode meminjam dari penyerahan python nneonneo (tanpanya saya tidak akan mendapatkan ini di bawah batas 2048 byte). Awalnya saya pikir ini seharusnya skor sekitar 200 lebih, tetapi saya menemukan kesalahan pada alat pembuatan string data saya. Sekarang sudah diperbaiki, skor saya jauh lebih masuk akal 1365.
Daripada membuat pohon biner berdasarkan panjang, saya membuat pohon biner tunggal untuk menampung informasi frekuensi. Pohon itu tidak memiliki kedalaman yang seragam, karena tidak ada gunanya menyimpan informasi frekuensi untuk apa pun yang lebih dalam dari enam tebakan yang salah (tetapi tebakan yang benar secara teori bisa menjadi dua belas dalam untuk "jauh" dan "tidak nyaman"). Pohon berbentuk canggung ini dinavigasi oleh kode faktorial (sebenarnya menggunakan fungsi kombinasi ). Untuk membuat data string lebih dapat dikompresi, saya mengisi semua indeks yang tidak digunakan dengan 's'.
Saya menggunakan skrip untuk menghitung string yang baik untuk disimpan sebagai d, dan jika seseorang dapat bermain golf beberapa karakter dari sisa skrip, maka berikut adalah beberapa penggantian yang akan menghasilkan skor yang lebih baik. Baris atas adalah string yang disandikan dalam program di atas.
Skrip yang saya gunakan untuk menghasilkan string data ada di sini , kalau-kalau berguna bagi siapa saja!
sumber
distinct, output program Anda adalah, secara berurutaneitanogsuc, yang artinya entah bagaimana berhenti memberikan output walaupun hanya menebak dengan salah 5 kali.The D bahasa pemrograman adalah alat saya pilihan untuk tantangan ini.
Hanya sedikit dari batas 2.048 byte, meskipun sedikit di-golf di beberapa bagian untuk menurunkan jumlah byte, semua pengangkatan yang berat tetap dapat dibaca dengan sempurna. Pemecah ini tidak terlalu baik dalam pekerjaannya, dan saya berharap itu akan dikalahkan dengan mudah, tetapi ini hanya untuk membuat bola bergulir. Kick off, jadi untuk berbicara.
EDIT # 1 :
Seperti yang telah ditunjukkan, kode asli cenderung mati sekarat ketika menghabiskan semua vokal. Karena tidak berfungsi dengan baik, saya menggantinya dengan pendekatan yang agak lebih brutal untuk menebak secara acak.EDIT # 2 : Kode asli telah diperbaiki dan sekarang berdiri.
Skor :
25.7; totalerr: 24,529.9 (average of 10 tests).Bagaimana itu bekerja
Pemecah ini benar-benar acak. Bahkan keacakannya adalah waktu yang acak dan menyenangkan!
Ketika program menerima input, ia akan menebak satu karakter acak yang belum ditebak dan mengirimkannya ke STDOUT.
Algoritma menebak berfungsi sebagai berikut:
sumber
./test.d(44): Error: cannot implicitly convert expression (uniform(0, Letters.length, rng)) of type ulong to int. Saya berhasil memperbaikinya dengancast(int). Setelah 10 berjalan, skor rata-rata Anda adalah 22,4 kata dengan 24529.1 tebakan yang salah. Saya akan menguji ulang jika Anda memperbaiki versi yang lebih canggih :) Selamat bersenangSolusi JAVASCRIPT + HTML
sumber