Zaniepokoiła mnie rosnąca nienawiść do przestrzeni, a ta odpowiedź zainspirowała mnie do upewnienia się, że kod Morse'a jest bezpieczny przed tym podstępnym usunięciem białych znaków.

Twoim zadaniem będzie stworzenie programu, który z powodzeniem przetłumaczy kod Morse'a ze wszystkimi spacjami.

Zasady:

1. Wejście będzie ciągiem złożonym wyłącznie z myślników i kropek (ASCII 2D i 2E). Dane wyjściowe są niezdefiniowane dla danych wejściowych zawierających inne znaki. Możesz użyć dowolnej metody dogodnej dla wybranego języka, aby otrzymać dane wejściowe (standardowe, plik tekstowy, monit użytkownika, cokolwiek). Możesz założyć, że wprowadzony kod Morse'a składa się tylko z liter AZ, a pasujące liczby lub znaki interpunkcyjne nie są wymagane.

2. Dane wyjściowe powinny zawierać tylko słowa zawarte w tym pliku słownika (ponownie, skorzystaj z dowolnej dogodnej metody dostępu do pliku słownika). Wszystkie prawidłowe dekodowania powinny być wyprowadzane na standardowe wyjście, a wszystkie kropki i myślniki na wejściu muszą być użyte. Każde dopasowane słowo na wyjściu powinno być oddzielone spacją, a każde możliwe dekodowanie powinno być oddzielone znakiem nowej linii. Jako wygodę możesz używać drukowania wielkich, małych lub mieszanych znaków.

3. Obowiązują wszystkie ograniczenia dotyczące standardowych luk z jednym wyjątkiem, jak wspomniano powyżej, jeśli chcesz, możesz uzyskać dostęp do pliku słownika wymienionego w wymaganiu 2 za pośrednictwem połączenia internetowego. Skracanie adresów URL jest dopuszczalne, uważam, że goo.gl/46I35Z jest prawdopodobnie najkrótszy.

4. To jest golf golf, wygrywa najkrótszy kod.

Uwaga: opublikowanie pliku słownika na Pastebin zmieniło wszystkie zakończenia linii na sekwencje 0A 0E w stylu Windows. Twój program może przyjmować zakończenia linii tylko z 0A, tylko 0E lub 0A 0E.

Przypadki testowe:

Wkład:

......-...-.. ---. -----.-..-..- ..

Dane wyjściowe muszą zawierać:

Witaj świecie

Wkład:

. - ..-. ----- ..-.. ----- ..-. - .. - ... --- .. - ...-.... ... -.-..-.-. ---- ... -. ---.-....-.

Dane wyjściowe muszą zawierać:

programowanie zagadek i golfa kodu

Wkład:

-..... -.-..-..-.-.-. - ....-. ---. --- ...-. ---- ..-.- --.. ---. - .... --- ...-..-.-......-... --- ..-. --- ..-- ---.

Dane wyjściowe muszą zawierać:

szybki brązowy lis przeskakuje nad leniwym psem

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*' '}}

Jeśli istnieje taka praktyka jak „over-golfing”, podejrzewam, że tym razem brałem udział. To rozwiązanie generuje tablicę tablic powtarzających się permutacji wszystkich słów słownika , od długości 1 do długości danych wejściowych. Biorąc pod uwagę, że „a” jest najkrótszym słowem w pliku słownika, a jego kod ma długość dwóch znaków, wystarczyłoby wygenerować permutacje o długości do połowy wielkości danych wejściowych, ale dodawanie /2jest równoznaczne z gadatliwością w tej dziedzinie, więc powstrzymałem się.

Po wygenerowaniu tablicy permutacji ( NB : ma ona długość 45404 ¹⁰⁴ w przypadku przykładowego pangramatycznego przykładu), każda tablica permutacji jest konkatenowana, a jej znaki alfabetyczne są zastępowane odpowiednikami kodu Morse'a za pomocą dość wygodnego (Regexp, Hash)wariantu #gsubmetoda; znaleźliśmy prawidłowe dekodowanie, jeśli ten ciąg znaków jest równy wejściowi.

Słownik jest odczytywany (kilka razy) z pliku o nazwie „d”, a dane wejściowe nie mogą zawierać nowego wiersza.

Przykładowy przebieg (ze słownikiem, który da programowi szansę na zakończenie walki przed śmiercią wszechświata):

$ cat d
puzzles
and
code
dummy
golf
programming
$ echo -n .--..-.-----..-..-----..-.--..--...---..--...-.......--.-..-.-.----...--.---.-....-. | ruby morse.rb
programming puzzles and code golf
^C

Haskell, 296 znaków

• Plik słownika: musi być plikiem tekstowym o nazwie „d”
• Dane wejściowe: stdin, może mieć końcowy znak nowej linii, ale nie ma spacji wewnętrznej

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]

Objaśnienie elementów:

• mainodczytuje słownik, odczytuje stdin, wykonuje &i formatuje dane wyjściowe &z odpowiednią białą spacją.
• (replicate 97"X"++words".- -... -.-. -.. . ..-. --. .... .. .--- -.- .-.. -- -. --- .--. --.- .-. ... - ..- ...- .-- -..- -.-- --..")!!)(wyrażenie wewnątrz definicji &) to lista, której indeksy są kodami znaków (97 to kod 'a'), a wartości to sekwencje Morse'a.
• !(funkcja nazwana jako operator infix) dopasowuje ciąg znaków do prefiksu; jeśli prefiks jest obecny, zwraca resztę z listy jednoelementowej (sukces w monadzie listy), w przeciwnym razie pusta lista (błąd w monadzie listy)

• &używa monady listy do wykonania „niedeterministycznego”; to

  1. wybiera wpis d(słowa ze słownika),
  2. służy !do dopasowania formy Morse'a tego słowa ( w>>=((…)!!).fromEnumrównoważnej concatMap (((…)!!) . fromEnum) w) do ciągu wejściowego i,
  3. wywołuje samą ( d&j), aby dopasować resztę ciągu, oraz
  4. zwraca możliwy wynik jako listę słów w:nw monadzie listy [w:n](która jest krótszym, konkretnym odpowiednikiem return (w:n)).

  Zauważ, że każda linia po linii 6 jest częścią dowyrażenia rozpoczętego w linii 6; zajmuje to dokładnie tyle samo znaków, co średników w jednym wierszu, ale jest bardziej czytelny, chociaż można to zrobić tylko raz w programie.

Ten program jest bardzo wolny. Można to zrobić szybciej (i nieco dłużej) łatwo, przechowując zmoryfikowane słowa obok oryginałów na liście, a nie przeliczając je przy każdym dopasowaniu wzoru. Następną rzeczą do zrobienia byłoby przechowywanie słów w drzewie binarnym kluczowanym przez symbole Morse'a (2-arytowe trie ), aby uniknąć próbowania niepotrzebnych gałęzi.

Można go nieco skrócić, jeśli plik słownika nie zawiera nieużywanych symboli, takich jak „-”, umożliwiając usunięcie replicate 97"X"++na korzyść robienia .(-97+)przed !!.

Python - 363 345

Kod:

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

Wyjaśnienie:

Słownik musi być przechowywany jako zwykły plik tekstowy o nazwie „d”.

D, P, UA Nto tylko niektóre zmienne pomocnicze dla krótszej definicji tabeli Morse wyszukiwania.

s(i)to funkcja rekurencyjna, która drukuje poprzednio przetłumaczoną część komunikatu pi każde prawidłowe tłumaczenie pozostałej części kodu i: Jeśli ijest pusta, osiągnęliśmy koniec kodu i bzawiera całe tłumaczenie, a więc po prostu printto. W przeciwnym razie sprawdzamy każde słowo ww słowniku d, tłumaczymy je na kod Morse'a, Ca jeśli pozostały kod izaczyna się od C, dodajemy słowo wdo przetłumaczonego początku bi wywołujemy funkcję srekurencyjnie na pozostałej części.

Uwaga na temat wydajności:

To dość powolna, ale golfowa wersja. Szczególnie ładowanie słownika i konstruowanie tabeli odnośników Morse'a ( dict(zip(...))) w każdej iteracji (aby uniknąć większej liczby zmiennych) kosztuje dużo. Bardziej efektywne byłoby przetłumaczenie wszystkich słów w pliku słownika z wyprzedzeniem, a nie każdej rekurencji na żądanie. Te pomysły prowadzą do następnej wersji z 40 dodatkowymi postaciami, ale znaczącym przyspieszeniem:

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

Perl (5.10+), 293 znaków

Plik słownika powinien być zapisany jako „d” (i powinien być w formacie uniksowym, jeśli nie chcesz CRs między słowami), Morse na stdin, bez końcowego znaku nowej linii (użyj 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}

(podziały wierszy tylko w przypadku formatowania).

Nieskluczony kod:

# 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:

Symbole kodu Morse'a są przechowywane przez zmianę „.” i „-” na cyfry binarne 0 i 1, poprzedzając „1” (aby kropki nie były pochłaniane), konwertując liczbę binarną na dziesiętną, a następnie kodując znak o wartości 61 wyższej (co daje mi wszystko znaki do druku i nic, co wymaga ukośnika odwrotnego).

Myślałem o tym jako o problemie z partycjonowaniem i na tej podstawie zbudowałem rozwiązanie. Dla każdego słowa w słowniku konstruuje obiekt wyrażenia regularnego, który będzie pasował (i przechwytywał) bezprzestrzenną reprezentację Morse'a tego słowa na początku łańcucha. Następnie rozpoczyna się wyszukiwanie od początku do końca, tworząc stan, który nie pasuje do żadnych słów i zawiera całe dane wejściowe jako „pozostałe dane wejściowe”. Następnie rozszerza każdy stan, szukając słów pasujących na początku pozostałych danych wejściowych i tworząc nowe stany, które dodają słowo do dopasowanych słów i usuwają Morse'a z pozostałych danych wejściowych. Stany, które nie mają żadnych pozostałych danych wejściowych, są udane i wydrukowano ich listę słów. Stany, które nie mogą dopasować żadnych słów (w tym te zakończone sukcesem), nie generują stanów potomnych.

Zauważ, że w wersji bez golfa stany są skrótami dla czytelności; w wersji golfowej są to tablice (dla krótszego kodu i mniejszego zużycia pamięci); szczelina [0]to pozostałe wejście, a szczelina [1]to dopasowane słowa.

Komentarz

To jest bezbożnie wolne. Zastanawiam się, czy istnieje rozwiązanie, które nie jest. Próbowałem zbudować jeden przy użyciu Marpy (parsera Earleya z możliwością dawania wielu parsów dla jednego ciągu wejściowego), ale zabrakło mi pamięci po prostu konstruując gramatykę. Może gdybym użył interfejsu API niższego poziomu zamiast wejścia BNF ...

Haskell - 418

Ten problem dekompresyjny można skutecznie rozwiązać za pomocą programowania dynamicznego. Wiem, że to kodegolf, ale uwielbiam szybki kod.

Załóżmy, że mamy ciąg wejściowy s, a następnie budujemy tablicę dp, dp[i]jest to lista wszystkich prawidłowych wyników dekodowania podłańcucha s[:i]. Dla każdego słowa ww słowniku najpierw go kodujemy mw, a następnie możemy obliczyć część dp[i]z dp[i - length(mw)]if s[i - length(mw):i] == mw. Złożoność czasowa budowy dpjest O({count of words} {length of s} {max word length}). Wreszcie dp[length(s)]ostatni element jest tym, czego potrzebujemy.

W rzeczywistości nie musimy przechowywać całego dekodowania jako elementu każdego z nich dp[i]. Potrzebujemy ostatniego zdekodowanego słowa. Dzięki temu wdrożenie jest znacznie szybsze. Ukończenie „hello world” na moim laptopie i3 kosztowało mniej niż 2 sekundy. W innych przypadkach zamieszczonych w pytaniu program nie zakończy się w sposób praktyczny, ponieważ jest zbyt wiele danych wyjściowych.

Za pomocą techniki programowania dynamicznego możemy obliczyć liczbę prawidłowych dekodowań . Możesz znaleźć kod tutaj . Wyniki:

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

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

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

Bez golfa

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

Grał w golfa

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

PHP, 234 226 bajtów

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)." ");}}

funkcja rekurencyjna, pobiera słownik z pliku o nazwie d.
Nie powiedzie się za każde słowo w słowniku zawierające nieliterową literę.

Możesz użyć dowolnej nazwy pliku, jeśli define ("d","<filename>");przed wywołaniem funkcji.

Dodaj 2 lub 3 bajty, aby przyspieszyć wykonanie:
Usuń $s?:print"$r\n";, wstaw $s!=$m?przed 0!==i :print$r.$wprzed ;}}.

awaria

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
            )
        ;
    }
}

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

Notatki

Dict musi być plikiem o nazwie d. Ciąg Morse'a jest przekazywany z wiersza poleceń. na przykład:

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

Do „kompresji kodu Morse'a” używam drzewa binarnego