Ini adalah teka-teki kata.
Program Anda harus menerima dua kata pada input standar.
Kata pertama adalah kata awal. Kata dua adalah kata akhir.
Dari kata awal Anda harus mencapai kata akhir yang mengubah / menambah / menghapus satu huruf sekaligus. Setelah setiap modifikasi itu harus membentuk kata yang valid baru. Surat yang ditambahkan ditambahkan ke awal atau akhir. Anda dapat menghapus huruf dari lokasi mana pun (tetapi panjangnya kata tidak boleh lebih dari tiga huruf). Catatan: Anda tidak dapat mengatur ulang huruf untuk membentuk kata.
Output dari program ini adalah urutan kata-kata yang akan didapat dari kata awal hingga kata akhir.
Contoh:
Input:
Post Shot
Output:
Post
cost
coat
goat
got
hot
shot
Pemenang:
- Program harus berjalan dalam waktu yang wajar (kurang dari 10 detik).
- Program yang dapat menghasilkan urutan output terpendek ke kata-kata hadiah.
- Zink -> Silikon
- Jika lebih dari satu program mendapat urutan terpendek maka program terpendek dalam karakter (mengabaikan ruang putih).
- Jika kita masih memiliki lebih dari satu tanggal / waktu pengiriman program akan digunakan.
Catatan:
- Kapitalisasi tidak relevan.
- Kode untuk membangun kamus tidak diperhitungkan dalam biaya kode.
- Kata Hadiah dan urutan akan dihasilkan dari:
http://dl.packetstormsecurity.net/Crackers/wordlists/dictionaries/websters-dictionary.gz
- Kata Hadiah dan urutan akan dihasilkan dari:
code-golf
word-puzzle
Martin York
sumber
sumber
Jawaban:
Python, 288 karakter
(tidak termasuk baris pembacaan kamus)
untuk tantangan
zink
untuksilicon
:Ada beberapa kata aneh di kamus itu ...
sumber
guester overturn
(membutuhkan waktu) atauregatta gyrally
(tidak kembali) ;-)traceroute - 10 karakter
detail
Router sudah dikonfigurasikan sebelumnya dengan OSPF diaktifkan dan diatur dengan cara ini.
Dan ya, saya membutuhkan 23.314 router untuk sepenuhnya mendukung semua kata. :-)
sumber
zink->pink->pank->pani->panic->pinic->sinic->sinico->silico->silicon
saya benar-benar mencoba dengan algoritma Dijkstra (yang digunakan dalam OSPF) dan dapat menemukan jalur sekitar 1s, saya akan posting di pos terpisah nanti, setelah saya bermain golf.PHP -
886689644612Memuat kamus:
Kode aktual (hanya untuk keduanya):
pemakaian:
Hasil:
Ini harus berjalan dalam waktu kurang dari 0,5 detik untuk 'Zink Silicon', dan kurang dari 1 detik untuk sebagian besar kasus (kadang-kadang lebih lama ketika tidak ada solusi, tetapi masih kembali).
Ini menggunakan algoritma A * dengan levenshtein distance untuk memperkirakan batas jarak yang lebih rendah.
Beberapa tes simpang:
vas arm
->vas bas bar barm arm
(dengan kata yang lebih panjang dari awal dan akhir)oxy pom
->oxy poxy poy pom
regatta gyrally
-> (tidak ada, tetapi skrip berakhir dengan benar)aal presolution
-> +8 karakterlenticulated aal
-> -9 karakteracarology lowness
-> 46 hopcaniniform lowness
-> 51 hopcauliform lowness
-> 52 hopoverfoul lowness
-> 54 hopdance facia
-> beberapa kata di jalur memiliki 4 karakter lebih banyak daripada keduanya mulai / berakhirsumber
PHP Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 71 bytes)
php -dmemory_limit=256M
.had->hand
bukan langkah yang valid, Anda hanya dapat menambahkan surat ke awal atau akhir. Sama untukvest->verst
:-)Python
Karena saya tidak bisa memasukkan kode golf untuk dikompres ke beberapa ratus byte, ini adalah versi saya yang tidak diklik.
Tes
Menambahkan Tes user300
Lebih lagi
sumber
3 <= len(x) <= max(map(len, [nodea, nodeb]))
apakah dijamin bahwa jalan setapak tidak akan pernah melewati kata yang lebih lama dari kata awal dan akhir?oxy pom
; jalur terpendek adalahoxy->poxy->poy->pom
. Juga tampaknya Anda mengizinkan permutasi dan penyisipan di mana saja, yang tidak diizinkan :-)