Je suis devenu alarmé par la haine croissante des espaces et cette réponse m'a inspiré à m'assurer que le code Morse est à l'abri de cette suppression insidieuse des espaces blancs.

Ainsi, votre tâche sera de créer un programme capable de traduire avec succès le code Morse avec tous les espaces supprimés.

Règles:

1. L'entrée sera une chaîne composée uniquement de tirets et de points (ASCII 2D et 2E). La sortie n'est pas définie pour une entrée contenant d'autres caractères. N'hésitez pas à utiliser n'importe quelle méthode adaptée à la langue de votre choix pour recevoir l'entrée (stdin, fichier texte, utilisateur rapide, peu importe). Vous pouvez supposer que la saisie du code Morse se compose uniquement des lettres AZ, et que les chiffres ou la ponctuation correspondants ne sont pas requis.

2. La sortie doit inclure uniquement les mots contenus dans ce fichier de dictionnaire (encore une fois, n'hésitez pas à utiliser une méthode pratique pour accéder au fichier de dictionnaire). Tous les décodages valides doivent être sortis vers stdout, et tous les points et tirets en entrée doivent être utilisés. Chaque mot correspondant dans la sortie doit être séparé par un espace, et chaque décodage possible doit être séparé par une nouvelle ligne. Vous pouvez utiliser les sorties majuscules, minuscules ou mixtes comme pratique.

3. Toutes les restrictions sur les échappatoires standard s'appliquent à une exception près, comme indiqué ci-dessus, vous pouvez accéder au fichier dictionnaire référencé dans l'exigence 2 via une connexion Internet si vous le souhaitez vraiment. Le raccourcissement d'URL est acceptable, je pense que goo.gl/46I35Z est probablement le plus court.

4. C'est le golf de code, le code le plus court gagne.

Remarque: La publication du fichier de dictionnaire sur Pastebin a modifié toutes les fins de ligne en séquences de style Windows 0A 0E. Votre programme peut supposer des fins de ligne avec 0A uniquement, 0E uniquement ou 0A 0E.

Cas de test:

Contribution:

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

La sortie doit contenir:

Bonjour le monde

Contribution:

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

La sortie doit contenir:

programmation d'énigmes et de golf de code

Contribution:

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

La sortie doit contenir:

le renard brun rapide saute par-dessus le chien paresseux

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

S'il existe une pratique telle que le "sur-golf", je soupçonne que j'ai participé cette fois-ci. Cette solution génère un tableau de tableaux de permutations répétées de tous les mots du dictionnaire , de la longueur 1 jusqu'à la longueur de l'entrée. Étant donné que "a" est le mot le plus court du fichier de dictionnaire et que son code comporte deux caractères, il aurait suffi pour générer des permutations d'une longueur jusqu'à la moitié de la taille de l'entrée, mais l'ajout /2équivaut à de la verbosité dans ce domaine, alors je me suis abstenu.

Une fois que le tableau de permutation a été généré ( NB : il est de longueur 45404 ¹⁰⁴ dans le cas de l'exemple pangrammatique entré), chaque tableau de permutation est concaténé et ses caractères alphabétiques sont remplacés par leurs équivalents en code Morse via la (Regexp, Hash)variante plutôt pratique du #gsubméthode; nous avons trouvé un décodage valide si cette chaîne est égale à l'entrée.

Le dictionnaire est lu (plusieurs fois) à partir d'un fichier nommé "d" et l'entrée ne doit pas contenir de nouvelle ligne.

Exemple d'exécution (avec un dictionnaire qui donnera au programme une chance de se terminer avant la mort par la chaleur de l'univers):

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

Haskell, 296 caractères

• Fichier dictionnaire: doit être un fichier texte nommé "d"
• Entrée: stdin, peut avoir une nouvelle ligne de fin mais pas d'espace blanc interne

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]

Explication des éléments:

• mainlit le dictionnaire, lit stdin, exécute &et formate la sortie de &avec un espace approprié.
• (replicate 97"X"++words".- -... -.-. -.. . ..-. --. .... .. .--- -.- .-.. -- -. --- .--. --.- .-. ... - ..- ...- .-- -..- -.-- --..")!!)(une expression à l'intérieur de la définition de &) est une liste dont les indices sont des codes de caractères (97 est le code de 'a') et les valeurs sont des séquences Morse.
• !(une fonction nommée opérateur infixe) fait correspondre une chaîne à un préfixe; si le préfixe est présent il retourne le reste dans une liste à un élément (succès dans la liste monad), sinon la liste vide (échec dans la liste monad)

• &utilise la liste monad pour une exécution «non déterministe»; il

  1. sélectionne une entrée de d(un mot du dictionnaire),
  2. utilise !pour faire correspondre la forme Morse de ce mot ( w>>=((…)!!).fromEnum, qui est équivalent à concatMap (((…)!!) . fromEnum) w) avec la chaîne d'entrée i,
  3. s'appelle ( d&j) pour correspondre au reste de la chaîne, et
  4. retourne le résultat possible sous la forme d'une liste de mots w:n, dans la liste monad [w:n](qui est l'équivalent concret le plus court return (w:n)).

  Notez que chaque ligne après la ligne 6 fait partie de l' doexpression commencée à la ligne 6; cela prend exactement le même nombre de caractères que l'utilisation de points-virgules sur une seule ligne, mais est plus lisible, bien que vous ne puissiez le faire qu'une seule fois dans un programme.

Ce programme est extrêmement lent. Il peut être rendu plus rapide (et légèrement plus long) facilement en stockant les mots altérés à côté des originaux dans une liste plutôt que de les recalculer à chaque correspondance de modèle. La prochaine chose à faire serait de stocker les mots dans un arbre binaire composé de symboles Morse (un tri à 2 aires ) afin d'éviter d'essayer des branches inutiles.

Il pourrait être légèrement raccourci si le fichier de dictionnaire ne contenait pas de symboles inutilisés tels que "-", permettant la suppression de replicate 97"X"++en faveur de faire .(-97+)avant le !!.

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

Explication:

Le dictionnaire doit être stocké sous forme de fichier texte simple nommé "d".

D, P, UEt ne Nsont que des variables d'aide pour une définition plus courte de la table de consultation de morse.

s(i)est une fonction récursive qui affiche la partie du message précédemment traduite pet chaque traduction valide de la partie de code restante i: si iest vide, nous avons atteint la fin du code et bcontient la traduction entière, donc nous la faisons simplement print. Sinon, nous vérifions chaque mot wdans le dictionnaire d, le traduisons en code morse Cet, si le code restant icommence par C, nous ajoutons le mot wau début traduit bet appelons la fonction srécursivement sur le reste.

Remarque sur l'efficacité:

Ceci est une version assez lente mais golfée. En particulier, le chargement du dictionnaire et la construction de la table de recherche morse ( dict(zip(...))) à chaque itération (pour éviter plus de variables) coûtent cher. Et il serait plus efficace de traduire tous les mots du fichier dictionnaire une fois à l'avance et non à chaque récursivité à la demande. Ces idées conduisent à la version suivante avec 40 caractères supplémentaires mais une accélération significative :

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 caractères

Le fichier du dictionnaire doit être enregistré sous "d" (et doit être au format Unix si vous ne voulez pas de CR entre les mots), entrée morse sur stdin, sans retour à la ligne (utilisation 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}

(sauts de ligne uniquement pour le formatage).

Code non golfé:

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

Mode opératoire:

Les symboles du code Morse sont stockés en changeant "." et "-" en chiffres binaires 0 et 1, en ajoutant un "1" (afin que les points de tête ne soient pas engloutis), en convertissant le nombre binaire en décimal, puis en codant le caractère avec la valeur 61 plus élevée (ce qui me donne tout caractères imprimables et rien qui nécessite une barre oblique inverse).

J'ai pensé à cela comme une sorte de problème de partitionnement et j'ai construit une solution basée sur cela. Pour chaque mot du dictionnaire, il construit un objet regex qui correspondra (et capturera) la représentation morse sans espace de ce mot au début d'une chaîne. Ensuite, il commence une recherche en largeur en créant un état qui ne correspond à aucun mot et dont l'entrée entière est "entrée restante". Ensuite, il développe chaque état en recherchant des mots qui correspondent au début de l'entrée restante et en créant de nouveaux états qui ajoutent le mot aux mots correspondants et suppriment le morse de l'entrée restante. Les États qui n'ont aucune entrée restante réussissent et font imprimer leur liste de mots. Les états qui ne peuvent correspondre à aucun mot (y compris les mots réussis) ne génèrent aucun état enfant.

Notez que dans la version non golfée, les états sont des hachages pour la lisibilité; dans la version golfée, ce sont des tableaux (pour un code plus court et moins de consommation de mémoire); slot [0]est l'entrée restante et slot [1]est les mots correspondants.

Commentaire

C'est incroyablement lent. Je me demande s'il n'y a pas de solution. J'ai essayé d'en construire un en utilisant Marpa (un analyseur Earley avec la possibilité de donner plusieurs analyses pour une seule chaîne d'entrée) mais j'ai manqué de mémoire en construisant simplement la grammaire. Peut-être que si j'utilisais une API de niveau inférieur au lieu de l'entrée BNF ...

Haskell - 418

Ce problème de déco peut être résolu efficacement par une programmation dynamique. Je sais que c'est un codegolf, mais j'adore le code rapide.

Disons que nous avons la chaîne d'entrée s, puis nous construisons un tableau dp, dp[i]est la liste de tous les résultats de décodage valides de la sous-chaîne s[:i]. Pour chaque mot wdans le dictionnaire, d' abord nous encoder à mw, nous pouvons calculer une partie de dp[i]de dp[i - length(mw)]si s[i - length(mw):i] == mw. La complexité temporelle de la construction dpest O({count of words} {length of s} {max word length}). Enfin, dp[length(s)]le dernier élément, c'est ce dont nous avons besoin.

En fait, nous n'avons pas besoin de stocker tout le décodage comme élément de chacun dp[i]. Ce dont nous avons besoin, c'est du dernier mot décodé. Cela rend l'implémentation beaucoup plus rapide. Il a fallu moins de 2 secondes pour terminer la coque "hello world" sur mon ordinateur portable i3. Pour les autres cas affichés dans la question, le programme ne se terminera pas pratiquement car il y en a trop à produire.

En utilisant la technique de programmation dynamique, nous pouvons calculer le nombre de décodages valides . Vous pouvez trouver le code ici . Résultats:

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

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

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

Non golfé

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

PHP, 234 226 octets

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

fonction récursive, prend le dictionnaire d'un fichier nommé d.
Échoue pour chaque mot du dictionnaire contenant une non-lettre.

Vous pouvez utiliser n'importe quel nom de fichier si vous define ("d","<filename>");avant d'appeler la fonction.

Ajoutez 2 ou 3 octets pour une exécution plus rapide:
supprimez $s?:print"$r\n";, insérez $s!=$m?avant 0!==et :print$r.$wavant ;}}.

panne

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

Remarques

Le dict doit être un fichier nommé d. La chaîne morse est passée par ligne de commande. par exemple:

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

Pour la "compression de code morse" j'utilise un arbre binaire