Me alarma el creciente odio a los espacios y esta respuesta me ha inspirado para asegurarme de que el código Morse esté a salvo de esta eliminación insidiosa del espacio en blanco.

Por lo tanto, su tarea será crear un programa que pueda traducir con éxito el código Morse con todos los espacios eliminados.

Reglas:

1. La entrada será una cadena que consta solo de guiones y puntos (ASCII 2D y 2E). La salida no está definida para la entrada que contiene otros caracteres. Siéntase libre de utilizar cualquier método conveniente para el idioma de su elección para recibir la entrada (stdin, archivo de texto, usuario rápido, lo que sea). Puede suponer que la entrada del código Morse solo consta de las letras AZ y que no se requieren números o signos de puntuación coincidentes.

2. La salida debe incluir solo palabras contenidas en este archivo de diccionario (nuevamente, siéntase libre de usar cualquier método conveniente para acceder al archivo de diccionario). Todas las decodificaciones válidas deben enviarse a stdout, y deben usarse todos los puntos y guiones en la entrada. Cada palabra coincidente en la salida debe estar separada por un espacio, y cada posible decodificación debe estar separada por una nueva línea. Puede utilizar mayúsculas, minúsculas o salidas de mayúsculas y minúsculas según convenga.

3. Todas las restricciones sobre las lagunas estándar se aplican con una excepción como se señaló anteriormente, puede acceder al archivo del diccionario al que se hace referencia en el requisito 2 a través de una conexión a Internet si realmente lo desea. El acortamiento de URL es aceptable, creo que goo.gl/46I35Z es probablemente el más corto.

4. Este es el código de golf, el código más corto gana.

Nota: la publicación del archivo de diccionario en Pastebin cambió todas las terminaciones de línea a secuencias de estilo 0A 0E de Windows. Su programa puede asumir terminaciones de línea con solo 0A, solo 0E o 0A 0E.

Casos de prueba:

Entrada:

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

La salida debe contener:

Hola Mundo

Entrada:

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

La salida debe contener:

programación de rompecabezas y código de golf

Entrada:

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

La salida debe contener:

el rápido zorro marrón salta sobre el perro perezoso

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

Si existe una práctica como el "exceso de golf", sospecho que he participado esta vez. Esta solución genera una matriz de matrices de permutaciones repetidas de todas las palabras del diccionario , desde la longitud 1 hasta la longitud de la entrada. Dado que "a" es la palabra más corta en el archivo de diccionario y su código tiene dos caracteres, habría sido suficiente para generar permutaciones de longitud de hasta la mitad del tamaño de la entrada, pero agregar /2es equivalente a la verbosidad en este dominio, así que me abstuve

Una vez que se ha generado la matriz de permutación ( NB : tiene una longitud 45404 ¹⁰⁴ en el caso de la entrada de ejemplo pangramático), cada matriz de permutación se concatena, y sus caracteres alfabéticos se reemplazan con sus equivalentes de código Morse a través de la (Regexp, Hash)variante bastante conveniente de la #gsubmétodo; hemos encontrado una decodificación válida si esta cadena es igual a la entrada.

El diccionario se lee (varias veces) de un archivo llamado "d", y la entrada no debe contener una nueva línea.

Ejemplo de ejecución (con un diccionario que le dará al programa una oportunidad de pelear para terminar antes de la muerte por calor del universo):

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

Haskell, 296 caracteres

• Archivo de diccionario: debe ser un archivo de texto llamado "d"
• Entrada: stdin, puede tener una nueva línea final pero no espacios en blanco internos

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]

Explicación de elementos:

• mainlee el diccionario, lee stdin, ejecuta &y formatea la salida &con espacios en blanco apropiados.
• (replicate 97"X"++words".- -... -.-. -.. . ..-. --. .... .. .--- -.- .-.. -- -. --- .--. --.- .-. ... - ..- ...- .-- -..- -.-- --..")!!)(una expresión dentro de la definición de &) es una lista cuyos índices son códigos de caracteres (97 es el código de 'a') y los valores son secuencias Morse.
• !(una función denominada como operador de infijo) hace coincidir una cadena con un prefijo; si el prefijo está presente, devuelve el resto en una lista de un elemento (éxito en la mónada de la lista), de lo contrario, la lista vacía (falla en la mónada de la lista)

• &usa la lista mónada para la ejecución "no determinista"; eso

  1. selecciona una entrada de d(una palabra del diccionario),
  2. utiliza !para hacer coincidir la forma Morse de esa palabra ( w>>=((…)!!).fromEnumque es equivalente a concatMap (((…)!!) . fromEnum) w) con la cadena de entrada i,
  3. se llama a sí mismo ( d&j) para que coincida con el resto de la cadena y
  4. devuelve el posible resultado como una lista de palabras w:n, en la lista mónada [w:n](que es el equivalente más corto y concreto de return (w:n)).

  Tenga en cuenta que cada línea después de la línea 6 es parte de la doexpresión iniciada en la línea 6; esto toma exactamente la misma cantidad de caracteres que el uso de punto y coma en una sola línea, pero es más legible, aunque solo puede hacerlo una vez en un programa.

Este programa es extremadamente lento. Se puede hacer más rápido (y un poco más) fácilmente almacenando las palabras morsificadas junto a los originales en una lista en lugar de volver a calcularlas en cada coincidencia de patrones. El siguiente paso sería almacenar las palabras en un árbol binario marcado con símbolos Morse (un trie de 2 arios ) para evitar probar ramas innecesarias.

Se podría hacer un poco más corto si el archivo de diccionario no contiene símbolos utilizados como "-", que permite la eliminación de replicate 97"X"++a favor de hacer .(-97+)antes de que el !!.

Python - 363 345

Código:

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

Explicación:

El diccionario debe almacenarse como un archivo de texto sin formato llamado "d".

D, P, UY Nson sólo algunas de las variables de ayuda para una definición más corta de la tabla de búsqueda morse.

s(i)es una función recursiva que imprime la parte del mensaje traducida previamente py cada traducción válida de la parte del código restante i: si iestá vacío, llegamos al final del código y bcontiene la traducción completa, por lo tanto simplemente la traducimos print. De lo contrario, verificamos cada palabra wen el diccionario d, la traducimos al código morse Cy, si el código restante icomienza con C, agregamos la palabra wal comienzo traducido by llamamos a la función srecursivamente en el resto.

Nota sobre eficiencia:

Esta es una versión bastante lenta pero golfizada. Especialmente cargar el diccionario y construir la tabla de búsqueda morse ( dict(zip(...))) en cada iteración (para evitar más variables) cuesta mucho. Y sería más eficiente traducir todas las palabras en el archivo del diccionario una vez por adelantado y no en cada recursión a pedido. Estas ideas conducen a la siguiente versión con 40 caracteres más pero una aceleración significativa :

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 caracteres

El archivo de diccionario debe guardarse como "d" (y debe estar en formato unix si no desea CRs entre palabras), entrada morse en stdin, sin nueva línea final (uso 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}

(saltos de línea solo para formatear).

Código sin 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;
}

Modus operandi:

Los símbolos del código Morse se almacenan cambiando "." y "-" en dígitos binarios 0 y 1, anteponiendo un "1" (para que los puntos iniciales no se engullen), convirtiendo el número binario en decimal y luego codificando el carácter con el valor 61 más alto (lo que me lleva a todos caracteres imprimibles y nada que necesite barra invertida).

Pensé en esto como un tipo de problema de particionamiento, y construí una solución basada en eso. Para cada palabra en el diccionario, construye un objeto regex que coincidirá (y capturará) la representación morse sin espacio de esa palabra al comienzo de una cadena. Luego comienza una búsqueda de amplitud creando un estado que no coincide con palabras y tiene toda la entrada como "entrada restante". Luego, expande cada estado buscando palabras que coincidan al comienzo de la entrada restante y creando nuevos estados que agregan la palabra a las palabras coincidentes y eliminan el morse de la entrada restante. Los estados que no tienen ninguna entrada restante son exitosos y tienen su lista de palabras impresas. Los estados que no pueden coincidir con ninguna palabra (incluidas las exitosas) no generan estados secundarios.

Tenga en cuenta que en la versión sin golf los estados son hash para facilitar la lectura; en la versión de golf son matrices (para código más corto y menor consumo de memoria); slot [0]es la entrada restante y slot [1]son las palabras coincidentes.

Comentario

Esto es impíamente lento. Me pregunto si hay una solución que no lo es. Traté de construir uno usando Marpa (un analizador Earley con la capacidad de dar múltiples análisis para una sola cadena de entrada) pero me quedé sin memoria simplemente construyendo la gramática. Tal vez si usara una API de nivel inferior en lugar de la entrada BNF ...

Haskell - 418

Este problema de decodificación se puede resolver de manera eficiente mediante programación dinámica. Sé que esto es un codegolf, pero me encanta el código rápido.

Digamos que tenemos la cadena de entrada s, luego construimos una matriz dp, dp[i]es la lista de todos los resultados de decodificación válidos de la subcadena s[:i]. Para cada palabra wen el diccionario, primero tenemos que lo codifica mw, entonces podemos calcular parte dp[i]de dp[i - length(mw)]si s[i - length(mw):i] == mw. La complejidad temporal del edificio dpes O({count of words} {length of s} {max word length}). Finalmente, dp[length(s)]el último elemento es lo que necesitamos.

De hecho, no necesitamos almacenar toda la decodificación como elemento de cada uno dp[i]. Lo que necesitamos es la última palabra decodificada. Esto hace que la implementación sea mucho más rápida. Me costó menos de 2 segundos terminar el estuche "hello world" en mi laptop i3. Para otros casos publicados en la pregunta, el programa no terminará de manera práctica ya que hay demasiados para generar.

Usando la técnica de programación dinámica, podemos calcular el número de decodificaciones válidas . Puedes encontrar el código aquí . Resultados:

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

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

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

Sin 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

Golfed

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

función recursiva, toma el diccionario de un archivo llamado d.
Falla para cada palabra en el diccionario que contiene una no letra.

Puede usar cualquier nombre de archivo si define ("d","<filename>");antes de llamar a la función.

Agregue 2 o 3 bytes para una ejecución más rápida:
elimine $s?:print"$r\n";, inserte $s!=$m?antes 0!==y :print$r.$wantes ;}}.

Descompostura

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

Notas

El dict debe ser un archivo llamado d. La cadena morse se pasa por la línea de comando. p.ej:

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

Para la "compresión de código Morse" estoy usando un árbol binario