Der wachsende Hass auf Leerzeichen hat mich beunruhigt , und diese Antwort hat mich dazu inspiriert, sicherzustellen, dass Morse-Code vor dieser heimtückischen Entfernung von Leerzeichen sicher ist.

Ihre Aufgabe wird es also sein, ein Programm zu erstellen, das erfolgreich Morse-Code übersetzt, wobei alle Leerzeichen entfernt werden.

Regeln:

1. Die Eingabe ist eine Zeichenfolge, die nur aus Strichen und Punkten besteht (ASCII 2D und 2E). Die Ausgabe ist für Eingaben, die andere Zeichen enthalten, undefiniert. Sie können eine beliebige Methode verwenden, die für die Sprache Ihrer Wahl geeignet ist, um die Eingaben zu erhalten (stdin, Textdatei, Benutzeraufforderung usw.). Sie können davon ausgehen, dass die Eingabe des Morsecodes nur aus den Buchstaben AZ besteht und keine übereinstimmenden Zahlen oder Satzzeichen erforderlich sind.

2. Die Ausgabe sollte nur Wörter enthalten, die in dieser Wörterbuchdatei enthalten sind (Sie können auch hier eine beliebige Methode verwenden, um auf die Wörterbuchdatei zuzugreifen). Alle gültigen Dekodierungen sollten auf stdout ausgegeben werden, und alle Punkte und Striche in der Eingabe müssen verwendet werden. Jedes übereinstimmende Wort in der Ausgabe sollte durch ein Leerzeichen getrennt sein, und jede mögliche Dekodierung sollte durch eine neue Zeile getrennt sein. Sie können die Ausgabe in Groß- und Kleinschreibung oder in gemischten Groß- und Kleinschreibung verwenden.

3. Alle Beschränkungen für Standardlücken gelten mit einer Ausnahme wie oben angegeben. Sie können auf die in Anforderung 2 genannte Wörterbuchdatei über eine Internetverbindung zugreifen, wenn Sie dies wirklich möchten. URL-Kürzung ist akzeptabel, ich glaube, dass goo.gl/46I35Z wahrscheinlich die kürzeste ist.

4. Dies ist Code Golf, der kürzeste Code gewinnt.

Hinweis: Durch das Posten der Wörterbuchdatei in Pastebin wurden alle Zeilenenden in Sequenzen im Windows-Stil 0A 0E geändert. Ihr Programm kann Zeilenenden mit nur 0A, nur 0E oder 0A 0E annehmen.

Testfälle:

Eingang:

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

Die Ausgabe muss enthalten:

Hallo Welt

Eingang:

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

Die Ausgabe muss enthalten:

Programmieren von Rätseln und Code-Golf

Eingang:

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

Die Ausgabe muss enthalten:

der schnelle braune Fuchs springt über den faulen Hund

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

Wenn es so etwas wie "Übergolf" gibt, habe ich vermutlich dieses Mal daran teilgenommen. Diese Lösung generiert ein Array von Arrays wiederholter Permutationen aller Wörterbuchwörter von Länge 1 bis zur Länge der Eingabe. Da "a" das kürzeste Wort in der Wörterbuchdatei und sein Code zwei Zeichen lang ist, wäre es ausreichend gewesen, Permutationen mit einer Länge von bis zu der halben Größe der Eingabe zu generieren, aber das Hinzufügen entspricht /2der Ausführlichkeit in diesem Bereich. also habe ich verzichtet.

Sobald die Permutation Array erzeugt worden ist ( NB : es ist mit einer Länge von 45404 ¹⁰⁴ in dem Fall der pangrammatic Beispiel Eingabe), wird jede Permutation Array verkettet, und seine alphabetischen Zeichen sind mit ihrem Morsealphabet Äquivalenten über die eher bequem ersetzt (Regexp, Hash)Variante der #gsubMethode; Wir haben eine gültige Dekodierung gefunden, wenn diese Zeichenfolge der Eingabe entspricht.

Das Wörterbuch wird (mehrmals) aus einer Datei mit dem Namen "d" gelesen, und die Eingabe darf keinen Zeilenumbruch enthalten.

Beispiellauf (mit einem Wörterbuch, das dem Programm die Chance gibt, vor dem Hitzetod des Universums zu enden):

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

Haskell, 296 Zeichen

• Wörterbuchdatei: muss eine Textdatei mit dem Namen "d" sein
• Eingabe: stdin, hat möglicherweise eine nachgestellte Newline, aber kein internes Whitespace

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]

Erklärung der Elemente:

• mainLiest das Wörterbuch, liest stdin, führt aus &und formatiert die Ausgabe &mit geeigneten Leerzeichen.
• (replicate 97"X"++words".- -... -.-. -.. . ..-. --. .... .. .--- -.- .-.. -- -. --- .--. --.- .-. ... - ..- ...- .-- -..- -.-- --..")!!)(Ein Ausdruck innerhalb der Definition von &) ist eine Liste, deren Indizes Zeichencodes (97 ist der Code von 'a') und deren Werte Morsefolgen sind.
• !(eine Funktion, die als Infix-Operator bezeichnet wird) vergleicht eine Zeichenfolge mit einem Präfix. Wenn das Präfix vorhanden ist, gibt es den Rest in einer Liste mit einem Element zurück (Erfolg in der Listenmonade), andernfalls die leere Liste (Fehler in der Listenmonade).

• &verwendet die Listenmonade für die „nicht deterministische“ Ausführung; es

  1. wählt einen Eintrag von d(ein Wörterbuchwort),
  2. verwendet !, um die Morseform dieses Wortes ( w>>=((…)!!).fromEnumwas äquivalent zu ist concatMap (((…)!!) . fromEnum) w) mit der Eingabezeichenfolge abzugleichen i,
  3. ruft sich selbst ( d&j) auf, um mit dem Rest der Zeichenfolge übereinzustimmen, und
  4. Gibt das mögliche Ergebnis als eine Liste von Wörtern w:nin der Listenmonade zurück [w:n](die das kürzere, konkrete Äquivalent zu ist return (w:n)).

  Beachten Sie, dass jede Zeile nach Zeile 6 Teil des doin Zeile 6 gestarteten Ausdrucks ist. Dies erfordert genau die gleiche Anzahl von Zeichen wie die Verwendung von Semikolons in einer einzelnen Zeile, ist jedoch besser lesbar, obwohl Sie dies in einem Programm nur einmal tun können.

Dieses Programm ist extrem langsam. Es kann schneller (und etwas länger) gemacht werden, indem die morsifizierten Wörter neben den Originalen in einer Liste gespeichert werden, anstatt sie bei jeder Musterübereinstimmung neu zu berechnen. Das nächste, was zu tun wäre, wäre, die Wörter in einem Binärbaum zu speichern, der mit Morse-Symbolen (einem 2-stelligen Trie ) versehen ist, um unnötige Verzweigungen zu vermeiden.

Es könnte etwas kürzer gemacht werden, wenn die Wörterbuchdatei keine unbenutzten Symbole wie "-" enthielte, was das Entfernen von replicate 97"X"++zugunsten von .(-97+)vor dem erlaubt !!.

Python - 363 345

Code:

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

Erläuterung:

Das Wörterbuch muss als reine Textdatei mit dem Namen "d" gespeichert werden.

D, P, UUnd Nsind nur einige Helfer Variablen für eine kürzere Definition der morse Lookup - Tabelle.

s(i)ist eine rekursive Funktion, die den zuvor übersetzten Nachrichtenteil pund jede gültige Übersetzung des restlichen Codeteils ausgibt i: Wenn ileer, haben wir das Ende des Codes erreicht und benthalten die gesamte Übersetzung, also haben wir es einfach print. Andernfalls überprüfen wir jedes Wort wim Wörterbuch d, übersetzen es in Morsecode, Cund wenn der verbleibende Code mit ibeginnt C, fügen wir das Wort wzum übersetzten Anfang hinzu bund rufen die Funktion srekursiv für den Rest auf.

Hinweis zur Effizienz:

Dies ist eine ziemlich langsame, aber golfene Version. Insbesondere das Laden des Wörterbuchs und das Erstellen der Morse-Nachschlagetabelle ( dict(zip(...))) in jeder Iteration (um mehr Variablen zu vermeiden) kostet viel. Und es wäre effizienter, alle Wörter in der Wörterbuchdatei einmal im Voraus und nicht bei jeder Rekursion nach Bedarf zu übersetzen. Diese Ideen führen zu der folgenden Version mit 40 weiteren Zeichen, die sich jedoch erheblich beschleunigt:

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 Zeichen

Die Wörterbuchdatei sollte als "d" gespeichert werden (und sollte im Unix-Format sein, wenn Sie keine CRs zwischen Wörtern wünschen), Morseeingabe auf stdin, ohne abschließende Newline (Verwendung 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}

(Zeilenumbrüche nur zur Formatierung).

Ungolfed-Code:

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

Morsecodesymbole werden durch Ändern von "." Gespeichert. und "-" in die Binärziffern 0 und 1, wobei eine "1" vorangestellt wird (damit die führenden Punkte nicht verschlungen werden), die Binärzahl in eine Dezimalzahl umgewandelt wird und dann das Zeichen mit dem höheren Wert 61 codiert wird (wodurch ich alle bekomme) druckbare Zeichen und nichts, was Backslashing benötigt).

Ich stellte mir das als eine Art Partitionierungsproblem vor und baute darauf eine Lösung auf. Für jedes Wort im Wörterbuch wird ein reguläres Objekt erstellt, das mit der raumlosen Morse-Darstellung des Wortes am Anfang einer Zeichenfolge übereinstimmt (und diese erfasst). Dann beginnt eine Breitensuche, indem ein Zustand erzeugt wird, der keinen Wörtern entspricht und die gesamte Eingabe als "verbleibende Eingabe" enthält. Anschließend wird jeder Zustand erweitert, indem nach Wörtern gesucht wird, die am Anfang der verbleibenden Eingabe übereinstimmen, und neue Zustände erstellt werden, die das Wort zu den übereinstimmenden Wörtern hinzufügen und die Morse aus der verbleibenden Eingabe entfernen. Zustände ohne verbleibende Eingabe sind erfolgreich und ihre Wortliste wird gedruckt. Zustände, die keinem Wort entsprechen (einschließlich erfolgreicher), erzeugen keine untergeordneten Zustände.

Beachten Sie, dass die Zustände in der ungolfed-Version Hashes für die Lesbarkeit sind. in der Golf-Version sind sie Arrays (für kürzeren Code und weniger Speicherverbrauch); slot [0]ist die verbleibende Eingabe und slot [1]die übereinstimmenden Wörter.

Kommentar

Das ist gottlos langsam. Ich frage mich, ob es eine Lösung gibt, die es nicht gibt. Ich habe versucht, einen mit Marpa (einem Earley-Parser mit der Möglichkeit, mehrere Parser für eine einzelne Eingabezeichenfolge zu erstellen) zu erstellen, aber es fehlte mir der Speicher, nur um die Grammatik zu konstruieren. Vielleicht, wenn ich eine niedrigere API anstelle der BNF-Eingabe verwendet ...

Haskell - 418

Dieses Enthüllungsproblem kann durch dynamische Programmierung effizient gelöst werden. Ich weiß, dass dies ein Codegolf ist, aber ich liebe schnellen Code.

Angenommen, wir haben die Eingabezeichenfolge s, dann erstellen wir ein Array dp, dp[i]das die Liste aller gültigen Dekodierungsergebnisse der Teilzeichenfolge enthält s[:i]. Für jedes Wort wim Wörterbuch codieren wir es zuerst nach mw, dann können wir einen Teil dp[i]von dp[i - length(mw)]if berechnen s[i - length(mw):i] == mw. Die zeitliche Komplexität des Bauens dpist O({count of words} {length of s} {max word length}). Schließlich ist dp[length(s)]das letzte Element, was wir brauchen.

Tatsächlich müssen wir nicht die gesamte Dekodierung als das Element von jedem speichern dp[i]. Was wir brauchen, ist das letzte entschlüsselte Wort. Dies beschleunigt die Implementierung erheblich. Es kostete weniger als 2 Sekunden, um das "Hallo Welt" -Fall auf meinem i3-Laptop zu beenden. In anderen in der Frage genannten Fällen wird das Programm nicht automatisch beendet, da zu viele ausgegeben werden können.

Mit der dynamischen Programmiertechnik können wir die Anzahl der gültigen Decodierungen berechnen . Den Code finden Sie hier . Ergebnisse:

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

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

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

Ungolfed

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 gespielt

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 Bytes

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

rekursive Funktion, nimmt das Wörterbuch aus einer Datei mit dem Namen d.
Schlägt für jedes Wort im Wörterbuch fehl, das einen Nichtbuchstaben enthält.

Sie können einen beliebigen Dateinamen verwenden, define ("d","<filename>");bevor Sie die Funktion aufrufen.

Fügen Sie 2 oder 3 Bytes für eine schnellere Ausführung hinzu:
Entfernen $s?:print"$r\n";, Einfügen $s!=$m?vor 0!==und :print$r.$wvor ;}}.

Nervenzusammenbruch

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

Anmerkungen

Das Diktat muss eine Datei mit dem Namen sein d. Die Morsezeichenfolge wird über die Befehlszeile übergeben. z.B:

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

Für "Morse-Code-Komprimierung" verwende ich einen Binärbaum