Saya menjadi waspada dengan kebencian yang semakin besar terhadap ruang dan jawaban ini telah mengilhami saya untuk memastikan kode Morse aman dari penghapusan spasi kosong yang berbahaya ini.
Jadi, tugas Anda adalah membuat program yang berhasil menerjemahkan kode Morse dengan semua ruang dihapus.
Aturan:
Input akan berupa string yang hanya terdiri dari tanda hubung dan titik (ASCII 2D dan 2E). Output tidak ditentukan untuk input yang mengandung karakter lain. Jangan ragu untuk menggunakan metode apa pun yang sesuai dengan bahasa pilihan Anda untuk menerima input (stdin, file teks, pengguna yang cepat, apa pun). Anda dapat mengasumsikan bahwa input kode Morse hanya terdiri dari huruf AZ, dan angka atau tanda baca yang cocok tidak diperlukan.
Keluaran harus mencakup hanya kata-kata yang terkandung dalam file kamus ini (sekali lagi, jangan ragu untuk menggunakan metode yang mudah digunakan untuk mengakses file kamus). Semua dekode yang valid harus berupa output ke stdout, dan semua titik dan garis pada input harus digunakan. Setiap kata yang cocok dalam output harus dipisahkan oleh spasi, dan setiap kemungkinan decoding harus dipisahkan oleh baris baru. Anda dapat menggunakan huruf besar, huruf kecil, atau output huruf campuran sebagai nyaman.
Semua pembatasan pada celah standar berlaku dengan satu pengecualian seperti disebutkan di atas, Anda dapat mengakses file kamus yang dirujuk dalam persyaratan 2 melalui koneksi internet jika Anda benar-benar menginginkannya. Pemendekan URL dapat diterima, saya percaya bahwa goo.gl/46I35Z mungkin yang terpendek.
Ini golf kode, kode terpendek menang.
Catatan: Mem-posting file kamus pada Pastebin mengubah semua akhir baris menjadi urutan gaya Windows 0A 0E. Program Anda dapat mengasumsikan akhir baris dengan 0A saja, 0E saja atau 0A 0E.
Kasus uji:
Memasukkan:
......-...-.. ---. -----.-..-..- ..
Output harus mengandung:
Halo Dunia
Memasukkan:
... ... -. -..-.-. ---- ... -. ---.-....-.
Output harus mengandung:
teka-teki pemrograman dan golf kode
Memasukkan:
-..... -. -..-..-.-.-. - ....-. ---. --- ...-. ----..-.- --.. ---. - .... --- ...-..-.-......-... --- ..-. --- ..-- ---.
Output harus mengandung:
rubah cokelat cepat melompati anjing malas
AN (.- -.)
danEG (. --.)
?Jawaban:
Ruby, 210
Jika ada latihan seperti "over-golfing", saya curiga saya sudah ambil bagian kali ini. Solusi ini menghasilkan array array permutasi berulang dari semua kata kamus , dari panjang 1 hingga panjang input. Mengingat bahwa "a" adalah kata terpendek dalam file kamus dan kodenya adalah dua karakter, itu sudah cukup untuk menghasilkan permutasi dengan panjang hingga setengah ukuran input, tetapi menambahkan
/2
sama dengan verbositas dalam domain ini, jadi saya menahan diri.Setelah array permutasi dihasilkan ( NB : panjangnya 45404 104 dalam kasus input contoh pangrammatik), masing-masing array permutasi disatukan, dan karakter alfabetnya diganti dengan kode Morse mereka yang setara melalui
(Regexp, Hash)
varian yang lebih nyaman dari#gsub
metode; kami telah menemukan decoding yang valid jika string ini sama dengan input.Kamus dibaca (beberapa kali) dari file bernama "d", dan input tidak boleh mengandung baris baru.
Contoh menjalankan (dengan kamus yang akan memberikan program kesempatan bertarung untuk mengakhiri sebelum kematian panas alam semesta):
sumber
Haskell, 296 karakter
Penjelasan elemen:
main
membaca kamus, membaca stdin, mengeksekusi&
, dan memformat output&
dengan spasi yang sesuai.(replicate 97"X"++words".- -... -.-. -.. . ..-. --. .... .. .--- -.- .-.. -- -. --- .--. --.- .-. ... - ..- ...- .-- -..- -.-- --..")!!)
(ekspresi dalam definisi&
) adalah daftar yang indeksnya adalah kode karakter (97 adalah kode dari'a'
) dan nilainya adalah urutan Morse.!
(fungsi bernama sebagai operator infiks) cocok dengan string terhadap awalan; jika awalan hadir ia mengembalikan sisanya dalam daftar satu elemen (sukses di daftar monad), jika tidak daftar kosong (kegagalan dalam daftar monad)&
menggunakan daftar monad untuk eksekusi "nondeterministic"; saya td
(kata kamus),!
untuk mencocokkan bentuk Morse dari kata itu (w>>=((…)!!).fromEnum
, yang setara denganconcatMap (((…)!!) . fromEnum) w
) terhadap string inputi
,d&j
) untuk mencocokkan sisa string, danw:n
, dalam daftar monad[w:n]
(yang merupakan, lebih pendek setara konkret untukreturn (w:n)
).Perhatikan bahwa setiap baris setelah baris 6 adalah bagian dari
do
ekspresi yang dimulai pada baris 6; ini membutuhkan jumlah karakter yang persis sama dengan menggunakan titik koma pada satu baris, tetapi lebih mudah dibaca, meskipun Anda hanya dapat melakukannya sekali dalam suatu program.Program ini sangat lambat. Itu dapat dibuat lebih cepat (dan sedikit lebih lama) dengan mudah dengan menyimpan kata-kata yang telah disebutkan di sebelah aslinya dalam daftar daripada mengkomputasi ulang pada setiap pencocokan pola. Hal berikutnya yang harus dilakukan akan menyimpan kata-kata dalam sebuah pohon biner mengetik dengan simbol Morse (2-ary trie ) sehingga untuk menghindari mencoba cabang yang tidak perlu.
Ini dapat dibuat sedikit lebih pendek jika file kamus tidak mengandung simbol yang tidak digunakan seperti "-", memungkinkan penghapusan
replicate 97"X"++
mendukung.(-97+)
sebelum melakukan!!
.sumber
(+(-97))
dapat ditulis ulang sebagai(-97+)
?|0<1=[]
definisi keduainteract
dan menangkan 12 karakter.interact$unlines.map unwords.(words f&)
concatMap
dengan>>=
Python -
363345Kode:
Penjelasan:
Kamus harus disimpan sebagai file teks biasa bernama "d".
D
,P
,U
DanN
hanya beberapa variabel pembantu untuk definisi yang lebih pendek dari tabel morse lookup.s(i)
adalah fungsi rekursif yang mencetak bagian pesan yang diterjemahkan sebelumnyap
dan setiap terjemahan yang valid dari bagian kode yang tersisai
: Jikai
kosong, kami mencapai akhir kode danb
berisi seluruh terjemahan, dengan demikian kami cukupprint
melakukannya. Kalau tidak, kami memeriksa setiap kataw
dalam kamusd
, menerjemahkannya ke dalam kode morseC
dan, jika kode yang tersisai
dimulaiC
, kami menambahkan kataw
ke awal yang diterjemahkanb
dan memanggil fungsis
secara rekursif pada sisanya.Catatan tentang efisiensi:
Ini adalah versi yang sangat lambat tetapi golf. Terutama memuat kamus dan membangun tabel pencarian morse (
dict(zip(...))
) di setiap iterasi (untuk menghindari lebih banyak variabel) biaya banyak. Dan akan lebih efisien untuk menerjemahkan semua kata dalam file kamus sekali di muka dan tidak dalam setiap rekursi sesuai permintaan. Gagasan ini mengarah ke versi berikut dengan 40 karakter lebih banyak tetapi mempercepat secara signifikan :sumber
.startswith(C)
dengan[:len(C)]==C
.d=sorted(open('d').read().split(),key=len,reverse=1)
Atau, lakukan itu secara eksternal dengan pre-sorting kamus Anda seperti itu.M=eval(open('d').read())
:)Perl (5.10+), 293 karakter
File kamus harus disimpan sebagai "d" (dan harus dalam format unix jika Anda tidak ingin CR di antara kata-kata), masukan morse pada stdin, tanpa baris baru (gunakan
echo -n
).(hanya linebreak untuk pemformatan).
Kode tidak dikunci:
Modus Operandi:
Simbol kode morse disimpan dengan mengubah "." dan "-" ke dalam digit biner 0 dan 1, menambahkan "1" (sehingga titik-titik awal tidak melahap), mengubah angka biner menjadi desimal, dan kemudian menyandikan karakter dengan nilai 61 lebih tinggi (yang membuat saya semua karakter yang dapat dicetak dan tidak ada yang perlu backslashing).
Saya menganggap ini sebagai semacam masalah partisi, dan membangun solusi berdasarkan itu. Untuk setiap kata dalam kamus, itu membangun objek regex yang akan cocok dengan (dan menangkap) representasi morse tanpa spasi di awal string. Kemudian ia memulai pencarian pertama dengan menciptakan keadaan yang tidak cocok dengan kata-kata dan memiliki seluruh input sebagai "input yang tersisa". Kemudian memperluas setiap negara dengan mencari kata-kata yang cocok di awal input yang tersisa, dan membuat negara-negara baru yang menambahkan kata ke kata-kata yang cocok dan menghapus morse dari input yang tersisa. Negara yang tidak memiliki input yang tersisa berhasil dan daftar kata-kata mereka dicetak. Negara yang tidak dapat mencocokkan kata apa pun (termasuk yang berhasil) tidak menghasilkan status anak.
Perhatikan bahwa dalam versi yang tidak diklik, status adalah hash untuk dibaca; dalam versi golf mereka adalah array (untuk kode yang lebih pendek dan lebih sedikit konsumsi memori); slot
[0]
adalah input dan slot yang tersisa[1]
adalah kata-kata yang cocok.Komentar
Ini lambat sekali. Saya bertanya-tanya apakah ada solusi yang tidak. Saya mencoba untuk membangun satu menggunakan Marpa (parser Earley dengan kemampuan untuk memberikan beberapa parsing untuk string input tunggal) tetapi kehabisan memori hanya membangun tata bahasa. Mungkin jika saya menggunakan API tingkat lebih rendah daripada input BNF ...
sumber
chomp()
. Haruskah saya?ord
sebagai gantinyaord$_
. Cukur 1 byte,join$"
bukanjoin" "
Haskell - 418
Masalah decoing ini dapat diselesaikan secara efisien dengan pemrograman dinamis. Saya tahu ini adalah codegolf, tapi saya suka kode cepat.
Katakanlah kita memiliki string input
s
, maka kita membangun sebuah arraydp
,dp[i]
adalah daftar semua hasil penguraian substring yang valids[:i]
. Untuk setiap kataw
dalam kamus, pertama-tama kita menyandikannyamw
, lalu kita dapat menghitung bagiandp[i]
daridp[i - length(mw)]
jikas[i - length(mw):i] == mw
. Kompleksitas waktu bangunandp
adalahO({count of words} {length of s} {max word length})
. Akhirnya,dp[length(s)]
elemen terakhir adalah yang kita butuhkan.Faktanya, kita tidak perlu menyimpan keseluruhan decoding sebagai elemen masing-masing
dp[i]
. Yang kita butuhkan adalah kata yang terakhir diterjemahkan. Ini membuat implementasinya jauh lebih cepat. Harganya kurang dari 2 detik untuk menyelesaikan case "hello world" di laptop i3 saya. Untuk kasus-kasus lain yang diposting dalam pertanyaan, program tidak akan selesai secara pratik karena ada terlalu banyak output.Dengan menggunakan teknik pemrograman dinamis, kita dapat menghitung jumlah dekode yang valid . Anda dapat menemukan kode di sini . Hasil:
Tidak disatukan
Golf
sumber
PHP,
234226 bytefungsi rekursif, mengambil kamus dari file bernama
d
.Gagal untuk setiap kata dalam kamus yang berisi huruf.
Anda dapat menggunakan nama file apa pun jika
define ("d","<filename>");
sebelum memanggil fungsi.Tambahkan 2 atau 3 byte untuk eksekusi lebih cepat:
Hapus
$s?:print"$r\n";
, masukkan$s!=$m?
sebelum0!==
dan:print$r.$w
sebelum;}}
.kerusakan
sumber
Groovy
377337Catatan
Dict harus berupa file bernama
d
. String morse dilewatkan oleh baris perintah. misalnya:Untuk "kompresi kode morse" Saya menggunakan pohon biner
sumber