Golf Decode Morse

24

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.

Kode morse

Aturan:

  1. 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.

  2. 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.

  3. 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.

  4. 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

Komintern
sumber
3
Bagaimana Anda bisa tahu antara AN (.- -.)dan EG (. --.)?
seequ
2
@ Sieg - Output kemudian harus menyertakan kedua decode yang valid.
Comintern
1
@ Dennis - Ahhh ... Saya berani bertaruh Pastebin atau browser saya yang melakukannya. File sumber saya tidak memilikinya. Anda dapat mengubah pembatas garis ke sistem yang sesuai, tidak ada perubahan lain. Saya akan mengedit pertanyaan ketika saya tidak ada di ponsel saya.
Comintern
2
@ Talko itu perilaku yang benar. Perhatikan bahwa masalahnya mengatakan output Anda harus menyertakan "hello world", bukan hanya sebatas itu. Seharusnya mencetak semua dekode yang valid.
hobbs
2
(Hampir puitis, sungguh)
hobbs

Jawaban:

5

Ruby, 210

(1..(g=gets).size).map{|x|puts IO.read(?d).split.repeated_permutation(x).select{|p|p.join.gsub(/./,Hash[(?a..?z).zip"(;=/%513':07*)29@-+&,4.<>?".bytes.map{|b|('%b'%(b-35))[1,7].tr'01','.-'}])==g}.map{|r|r*' '}}

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 /2sama 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 #gsubmetode; 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):

$ cat d
puzzles
and
code
dummy
golf
programming
$ echo -n .--..-.-----..-..-----..-.--..--...---..--...-.......--.-..-.-.----...--.---.-....-. | ruby morse.rb
programming puzzles and code golf
^C
Three If By Whiskey
sumber
5

Haskell, 296 karakter

  • File kamus: harus berupa file teks bernama "d"
  • Input: stdin, mungkin memiliki baris baru tambahan tetapi tidak ada spasi internal
main=do f<-readFile"d";getLine>>=mapM(putStrLn.unwords).(words f&)
i!""=[i]
(i:j)!(p:q)|i==p=j!q
_!_=[]
_&""=[[]]
d&i=do
w<-d
j<-i!(w>>=((replicate 97"X"++words".- -... -.-. -.. . ..-. --. .... .. .--- -.- .-.. -- -. --- .--. --.- .-. ... - ..- ...- .-- -..- -.-- --..")!!).fromEnum)
n<-d&j
[w:n]

Penjelasan elemen:

  • mainmembaca 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 t

    1. mengambil entri d (kata kamus),
    2. menggunakan !untuk mencocokkan bentuk Morse dari kata itu ( w>>=((…)!!).fromEnum, yang setara denganconcatMap (((…)!!) . fromEnum) w ) terhadap string input i,
    3. menyebut dirinya sendiri (d&j ) untuk mencocokkan sisa string, dan
    4. mengembalikan hasil yang mungkin sebagai daftar kata w: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 doekspresi 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 !!.

Kevin Reid
sumber
Sialan, itu pintar. Memberi +1 kepada Anda.
Alexander Craggs
1
Tahukah Anda bahwa (+(-97))dapat ditulis ulang sebagai (-97+)?
haskeller bangga
Anda harus menghapus definisi ketiga h dan bukannya menambah |0<1=[]definisi kedua
bangga haskeller
2
Gunakan interactdan menangkan 12 karakter.interact$unlines.map unwords.(words f&)
gxtaillon
1
Anda harus dapat mengganti concatMapdengan>>=
haskeller bangga
3

Python - 363 345

Kode:

D,P='-.';U,N='-.-','.-.'
def s(b,i):
 if i=='':print b
 for w in open('d').read().split():
  C=''.join([dict(zip('abcdefghijklmnopqrstuvwxyz-\'23',[P+D,D+3*P,U+P,'-..',P,D+N,'--.',4*P,2*P,P+3*D,U,N+P,2*D,D+P,D*3,'.--.',D+U,N,P*3,D,'..-',3*P+D,'.--','-..-',U+D,'--..']+['']*4))[c]for c in w]);L=len(C)
  if i[:L]==C:s(b+' '+w,i[L:])
s('',input())

Penjelasan:

Kamus harus disimpan sebagai file teks biasa bernama "d".

D, P, UDanN hanya beberapa variabel pembantu untuk definisi yang lebih pendek dari tabel morse lookup.

s(i)adalah fungsi rekursif yang mencetak bagian pesan yang diterjemahkan sebelumnya pdan setiap terjemahan yang valid dari bagian kode yang tersisa i: Jika ikosong, kami mencapai akhir kode dan bberisi seluruh terjemahan, dengan demikian kami cukup printmelakukannya. Kalau tidak, kami memeriksa setiap kata wdalam kamus d, menerjemahkannya ke dalam kode morse Cdan, jika kode yang tersisa idimulai C, kami menambahkan kata wke awal yang diterjemahkan bdan 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 :

d=open('d').read().split()
D,P='-.';U,N='-.-','.-.'
M=dict(zip('abcdefghijklmnopqrstuvwxyz-\'23',[P+D,D+3*P,U+P,'-..',P,D+N,'--.',4*P,2*P,P+3*D,U,N+P,2*D,D+P,D*3,'.--.',D+U,N,P*3,D,'..-',3*P+D,'.--','-..-',U+D,'--..']+['']*4))
T=[''.join([M[c]for c in w])for w in d]
def s(b,i):
 if i=='':print b
 for j,w in enumerate(d):
  C=T[j];L=len(C)
  if i[:L]==C:s(b+' '+w,i[L:])
s('',input())
Falko
sumber
Anda dapat menyimpan 2 karakter dengan mengganti .startswith(C)dengan [:len(C)]==C.
Greg Hewgill
Wow terima kasih! Semakin aneh, karena memuat seluruh kamus di setiap rekursi menyimpan karakter - dan memperlambat algoritme sekali lagi.
Falko
@GregHewgill: Ya, itulah yang saya lakukan pada awalnya. Saya baru saja mengedit jawaban saya untuk mengatasi kedua versi.
Falko
1
Anda dapat menghasilkan hasil yang lebih menarik (kata-kata yang lebih panjang) lebih cepat dengan mengurutkan kamus dengan menurunkan panjang kata. d=sorted(open('d').read().split(),key=len,reverse=1)Atau, lakukan itu secara eksternal dengan pre-sorting kamus Anda seperti itu.
Greg Hewgill
Heck, jika Anda dapat memformat ulang file kamus, formatlah itu sebagai kamus Python yang sudah dihitung sebelumnya dan M=eval(open('d').read()):)
Greg Hewgill
3

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).

open D,d;chomp(@w=<D>);@m{a..z}=map{substr(sprintf("%b",-61+ord),1)=~y/01/.-/r}
'BUWI?OKMATJQDCLSZGE@FNHVXY'=~/./g;%w=map{$_,qr#^\Q@{[s/./$m{$&}/reg]}#}@w;
@a=[$i=<>];while(@a){say join$",@{$$_[1]}for grep!$$_[0],@a;
@a=map{$x=$_;map{$$x[0]=~$w{$_}?[substr($$x[0],$+[0]),[@{$$x[1]},$_]]:()}@w}@a}

(hanya linebreak untuk pemformatan).

Kode tidak dikunci:

# Read the word list
open my $dictionary, '<', 'd';
chomp(my @words = <$dictionary>);

# Define morse characters
my %morse;
@morse{'a' .. 'z'} = map {
  $n = ord($_) - 61;
  $bits = sprintf "%b", $n;
  $bits =~ tr/01/.-/;
  substr $bits, 1;
} split //, 'BUWI?OKMATJQDCLSZGE@FNHVXY';

# Make a hash of words to regexes that match their morse representation
my %morse_words = map {
  my $morse_word = s/./$morse{$_}/reg;
  ($_ => qr/^\Q$morse_word/)
} @words;

# Read the input
my $input = <>;

# Initialize the state
my @candidates = ({ remaining => $input, words => [] });

while (@candidates) {
  # Print matches
  for my $solution (grep { $_->{remaining} eq '' } @candidates) {
    say join " ", @{ $solution->{words} }; 
  } 
  # Generate new solutions
  @candidates = map {
    my $candidate = $_;
    map {
      $candidate->{remaining} =~ $morse_words{$_}
        ? {
          remaining => substr( $candidate->{remaining}, $+[0] ),
          words => [ @{ $candidate->{words} }, $_ ],
        }
        : ()
    } @words
  } @candidates;
}

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 ...

hobbs
sumber
Jika saya menambahkan persyaratan yang sama dengan Kevin Reid (tidak ada baris baru di input) saya dapat menyimpan 7 karakter dengan menghapus chomp(). Haruskah saya?
hobbs
"Jangan ragu untuk menggunakan metode apa pun yang nyaman".
Comintern
Cukur 2 byte dengan ordsebagai gantinya ord$_. Cukur 1 byte, join$"bukanjoin" "
Zaid
2

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 array dp, dp[i]adalah daftar semua hasil penguraian substring yang valid s[:i]. Untuk setiap kata wdalam kamus, pertama-tama kita menyandikannya mw, lalu kita dapat menghitung bagian dp[i]dari dp[i - length(mw)]jika s[i - length(mw):i] == mw. Kompleksitas waktu bangunan dpadalah O({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:

input: ......-...-..---.-----.-..-..-..
count: 403856

input: .--..-.-----..-..-----..-.--..--...---..--...-.......--.-..-.-.----...--.---.-....-.
count: 2889424682038128

input: -.....--.-..-..-.-.-.--....-.---.---...-.----..-.---..---.--....---...-..-.-......-...---..-.---..-----.
count: 4986181473975221635

Tidak disatukan

import Control.Monad

morseTable :: [(Char, String)]
morseTable = zip ['a'..'z'] $ words ".- -... -.-. -.. . ..-. --. .... .. .--- -.- .-.. -- -. --- .--. --.- .-. ... - ..- ...- .-- -..- -.-- --.."

wordToMorse :: String -> Maybe String
wordToMorse xs = return . concat =<< mapM (`lookup` morseTable) xs

slice :: (Int, Int) -> [a] -> [a]
slice (start, end) = take (end - start) . drop start

decode :: String -> String -> IO ()
decode dict s = trace (length s) [] where
  dict' = [(w, maybe "x" id . wordToMorse $ w) | w <- lines dict]
  dp = flip map [0..length s] $ \i -> [(j, w) |
        (w, mw) <- dict', let j = i - length mw, j >= 0 && mw == slice (j, i) s]

  trace :: Int -> [String] -> IO ()
  trace 0 prefix = putStrLn . unwords $ prefix
  trace i prefix = sequence_ [trace j (w:prefix) | (j, w) <- dp !! i]

main :: IO ()
main = do
  ws <- readFile "wordlist.txt"
  decode ws =<< getLine

Golf

import Control.Monad
l=length
t=zip['a'..]$words".- -... -.-. -.. . ..-. --. .... .. .--- -.- .-.. -- -. --- .--. --.- .-. ... - ..- ...- .-- -..- -.-- --.."
h s=return.concat=<<mapM(`lookup`t)s
f d s=g(l s)[]where g 0 p=putStrLn.unwords$p;g i p=sequence_[g j(w:p)|(j,w)<-map(\i->[(j,w)|(w,m)<-[(w,maybe"x"id.h$w)|w<-lines d],let j=i-l m,j>=0&&m==(take(i-j).drop j$s)])[0..l s]!!i]
main=do d<-readFile"d";f d=<<getLine
sinar
sumber
Senang melihat solusi yang cukup efisien. Sekarang saya hanya harus memahaminya :)
hobbs
2

PHP, 234 226 byte

function f($s,$r=""){$s?:print"$r
";foreach(file(d)as$w){for($i=+$m="";$p=@strpos(__etianmsurwdkgohvf_l_pjbxcyzq,$w[$i++]);)$m.=strtr(substr(decbin($p),1),10,"-.");0!==strpos($s,$m)?:g(substr($s,strlen($m)),$r.trim($w)." ");}}

fungsi 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?sebelum 0!==dan :print$r.$wsebelum ;}}.

kerusakan

function f($s,$r="")
{
    $s?:print"$r\n";            // if input is empty, print result
    foreach(file(d)as$w)        // loop through words
    {
        // translate to morse:
        for($i=+$m="";              // init morse to empty string, $i to 0
                                        // loop while character is in the string
            $p=@strpos(__etianmsurwdkgohvf_l_pjbxcyzq,$w[$i++])
        ;)
            $m.=                        // 4. append to word morse code
                strtr(
                    substr(
                        decbin($p)      // 1: convert position to base 2
                    ,1)                 // 2: substr: remove leading `1`
                ,10,"-.")               // 3. strtr: dot for 0, dash for 1
            ;
        0!==strpos($s,$m)           // if $s starts with $m
            ?:f(                        // recurse
                substr($s,strlen($m)),  // with rest of $s as input
                $r.trim($w)." "         // and $r + word + space as result
            )
        ;
    }
}
Titus
sumber
1

Groovy 377 337

r=[:];t={x='',p=''->r[s[0]]=p+x;s=s.substring(1);if(p.size()<3){t('.',p+x);t('-',p+x)}};s='-eishvuf-arl-wpjtndbxkcymgzqo--';t()
m=('d'as File).readLines().groupBy{it.collect{r.get(it,0)}.join()}
f={it,h=[]->it.size().times{i->k=it[0..i]
if(k in m){m[k].each{j->f(it.substring(i+1),h+[j])}}}
if(it.empty){println h.join(' ')}}
f(args[0])

Catatan

Dict harus berupa file bernama d. String morse dilewatkan oleh baris perintah. misalnya:

% groovy morse.groovy ......-...-..---.-----.-..-..-.. | grep 'hello world'
hello world

Untuk "kompresi kode morse" Saya menggunakan pohon biner

cfrick
sumber