Fiquei alarmado com o crescente ódio aos espaços e essa resposta me inspirou a garantir que o código Morse esteja a salvo dessa remoção insidiosa do espaço em branco.
Portanto, sua tarefa será criar um programa que possa traduzir com êxito o código Morse com todos os espaços removidos.
Regras:
A entrada será uma sequência que consiste apenas de traços e pontos (ASCII 2D e 2E). A saída é indefinida para a entrada que contém outros caracteres. Sinta-se à vontade para usar qualquer método conveniente ao seu idioma de escolha para receber a entrada (stdin, arquivo de texto, usuário imediato, qualquer que seja). Você pode supor que a entrada do código Morse consiste apenas nas letras AZ e que números ou pontuação correspondentes não são necessários.
A saída deve incluir apenas as palavras contidas nesse arquivo de dicionário (novamente, sinta-se à vontade para usar qualquer método conveniente para acessar o arquivo de dicionário). Todas as decodificações válidas devem ser enviadas para stdout e todos os pontos e traços na entrada devem ser usados. Cada palavra correspondente na saída deve ser separada por um espaço e cada possível decodificação deve ser separada por uma nova linha. Você pode usar letras maiúsculas, minúsculas ou letras maiúsculas como conveniente.
Todas as restrições sobre brechas padrão se aplicam com uma exceção, conforme mencionado acima; você pode acessar o arquivo de dicionário mencionado no requisito 2 por meio de uma conexão à Internet, se realmente desejar. O encurtamento de URL é aceitável, acredito que o goo.gl/46I35Z é provavelmente o mais curto.
Este é o código de golfe, o código mais curto vence.
Nota: A publicação do arquivo de dicionário no Pastebin alterou todas as terminações de linha para sequências 0A 0E do estilo Windows. Seu programa pode assumir terminações de linha apenas com 0A, apenas 0E ou 0A 0E.
Casos de teste:
Entrada:
......-...-.. ---. -----.-..-..- ..
A saída deve conter:
Olá Mundo
Entrada:
- ..-. ----- ..-.. ----- ..-. - .. - ... --- .. - ...-.... ... -.-..-.-. ---- ... -. ---.-....-.
A saída deve conter:
quebra-cabeças de programação e código de golfe
Entrada:
-..... -.-..-..-.-.-. - ....-. ---. --- ...-. ---- ..-.- ---- ---. - .... --- ...-..-.-......-... --- ..-. --- ..-- ---.
A saída deve conter:
a rápida raposa marrom pula sobre o cachorro preguiçoso
AN (.- -.)
eEG (. --.)
?Respostas:
Ruby, 210
Se existe uma prática como "excesso de golfe", suspeito que tenha participado desta vez. Esta solução gera uma matriz de matrizes de permutações repetidas de todas as palavras do dicionário , do comprimento 1 até o comprimento da entrada. Dado que "a" é a palavra mais curta no arquivo de dicionário e seu código tem dois caracteres, seria suficiente gerar permutações de comprimento até a metade do tamanho da entrada, mas adicionar
/2
é equivalente à verbosidade neste domínio, então eu me abstive.Depois que a matriz de permutação é gerada ( NB : é de comprimento 45404 104 no caso da entrada de exemplo pangramática), cada matriz de permutação é concatenada e seus caracteres alfabéticos são substituídos por seus equivalentes de código Morse por meio da
(Regexp, Hash)
variante bastante conveniente do#gsub
método; encontramos uma decodificação válida se essa sequência for igual à entrada.O dicionário é lido (várias vezes) em um arquivo chamado "d" e a entrada não deve conter uma nova linha.
Exemplo de execução (com um dicionário que dará ao programa a chance de terminar antes da morte pelo calor do universo):
fonte
Haskell, 296 caracteres
Explicação dos elementos:
main
lê o dicionário, lê stdin, executa&
e formata a saída&
com espaço em branco apropriado.(replicate 97"X"++words".- -... -.-. -.. . ..-. --. .... .. .--- -.- .-.. -- -. --- .--. --.- .-. ... - ..- ...- .-- -..- -.-- --..")!!)
(uma expressão dentro da definição de&
) é uma lista cujos índices são códigos de caracteres (97 é o código de'a'
) e valores são sequências Morse.!
(uma função nomeada como operador de infixo) corresponde a uma sequência contra um prefixo; se o prefixo estiver presente, ele retornará o restante em uma lista de um elemento (êxito na mônada da lista); caso contrário, na lista vazia (falha na mônada da lista)&
usa a mônada da lista para execução "não determinística"; istod
(uma palavra do dicionário),!
para combinar a forma Morse dessa palavra (w>>=((…)!!).fromEnum
que é equivalente aconcatMap (((…)!!) . fromEnum) w
) à string de entradai
,d&j
) para corresponder ao restante da string ew:n
, na mônada da lista[w:n]
(que é o equivalente mais curto e concreto areturn (w:n)
).Observe que todas as linhas após a linha 6 fazem parte da
do
expressão iniciada na linha 6; isso leva exatamente o mesmo número de caracteres que o ponto e vírgula em uma única linha, mas é mais legível, embora você possa fazer isso apenas uma vez em um programa.Este programa é extremamente lento. Isso pode ser mais rápido (e um pouco mais longo) facilmente, armazenando as palavras modificadas ao lado dos originais em uma lista, em vez de recalculá-las em cada correspondência de padrão. A próxima coisa a fazer seria para armazenar as palavras em uma árvore binária introduzidos por símbolos Morse (a 2 ary Trie ) de modo a evitar a tentar ramos desnecessários.
Pode ser feito um pouco mais curto, se o arquivo de dicionário não contém símbolos não utilizados tais como "-", permitindo a remoção
replicate 97"X"++
da favor de fazer.(-97+)
antes da!!
.fonte
(+(-97))
pode ser reescrito(-97+)
?|0<1=[]
à segunda definiçãointeract
e ganhe 12 caracteres.interact$unlines.map unwords.(words f&)
concatMap
por>>=
Python -
363345Código:
Explicação:
O dicionário deve ser armazenado como um arquivo de texto sem formatação chamado "d".
D
,P
,U
EN
são apenas algumas variáveis auxiliares para uma definição mais curta da tabela de pesquisa morse.s(i)
é uma função recursiva que imprime a parte da mensagem traduzida anteriormentep
e cada tradução válida da parte restante do códigoi
: Sei
estiver vazia, chegamos ao final do código eb
contém a tradução inteira, portanto, simplesmenteprint
. Caso contrário, verificamos cada palavraw
no dicionáriod
, traduzimos para código morseC
e, se o código restantei
começarC
, adicionamos a palavraw
ao início traduzidob
e chamamos a funçãos
recursivamente no restante.Nota sobre eficiência:
Esta é uma versão bastante lenta, mas golfada. Especialmente carregar o dicionário e construir a tabela de pesquisa morse (
dict(zip(...))
) em cada iteração (para evitar mais variáveis) custa muito. E seria mais eficiente traduzir todas as palavras no arquivo do dicionário uma vez com antecedência e não em cada recursão sob demanda. Essas idéias levam à seguinte versão, com mais 40 caracteres, mas aceleração significativa :fonte
.startswith(C)
por[:len(C)]==C
.d=sorted(open('d').read().split(),key=len,reverse=1)
Ou faça isso externamente, classificando seu dicionário dessa maneira.M=eval(open('d').read())
:)Perl (5.10+), 293 caracteres
O arquivo do dicionário deve ser salvo como "d" (e deve estar no formato unix, se você não quiser CRs entre as palavras), entrada morse no stdin, sem nova linha final (uso
echo -n
).(quebras de linha apenas para formatação).
Código não destruído:
Modo de operação:
Os símbolos do código Morse são armazenados alterando "." e "-" nos dígitos binários 0 e 1, acrescentando um "1" (para que os pontos iniciais não sejam engolidos), convertendo o número binário em decimal e depois codificando o caractere com o valor 61 mais alto (o que me leva a tudo caracteres imprimíveis e nada que precise de barra invertida).
Pensei nisso como um tipo de problema de particionamento e construí uma solução com base nisso. Para cada palavra no dicionário, ele constrói um objeto regex que corresponderá (e capturará) a representação morse sem espaço dessa palavra no início de uma sequência. Em seguida, inicia uma pesquisa abrangente criando um estado que não corresponde a nenhuma palavra e que tem toda a entrada como "entrada restante". Em seguida, ele expande cada estado procurando por palavras que correspondam no início da entrada restante e criando novos estados que adicionam a palavra às palavras correspondentes e removem o morse da entrada restante. Os estados que não têm entrada restante são bem-sucedidos e têm sua lista de palavras impressa. Os estados que não podem corresponder a nenhuma palavra (incluindo as bem-sucedidas) não geram estados filhos.
Observe que na versão não-gasta os estados são hashes para facilitar a leitura; na versão golfed, são matrizes (para código mais curto e menor consumo de memória); slot
[0]
é a entrada restante e slot[1]
são as palavras correspondentes.Comentário
Isso é incrivelmente lento. Gostaria de saber se existe uma solução que não existe. Tentei criar um usando Marpa (um analisador Earley com a capacidade de fornecer várias análises para uma única sequência de entrada), mas fiquei sem memória apenas construindo a gramática. Talvez se eu usasse uma API de nível inferior em vez da entrada BNF ...
fonte
chomp()
. Eu devo?ord
vez deord$_
. Shave 1 byte dizendojoin$"
em vez dejoin" "
Haskell - 418
Esse problema de remoção de estilo pode ser resolvido com eficiência por meio de programação dinâmica. Eu sei que isso é um codegolf, mas eu amo código rápido.
Digamos que temos a sequência de entrada e
s
, em seguida, construímos uma matrizdp
,dp[i]
é a lista de todos os resultados válidos de decodificação de substrings[:i]
. Para cada palavraw
no dicionário, primeiro codificando-amw
, então podemos calcular partedp[i]
dodp[i - length(mw)]
ses[i - length(mw):i] == mw
. A complexidade temporal do edifíciodp
éO({count of words} {length of s} {max word length})
. Finalmente,dp[length(s)]
o último elemento, é o que precisamos.De fato, não precisamos armazenar toda a decodificação como o elemento de cada
dp[i]
. O que precisamos é a última palavra decodificada. Isso torna a implementação muito mais rápida. Custou menos de 2 segundos para finalizar o estojo "olá mundo" no meu laptop i3. Para outros casos postados na pergunta, o programa não será concluído na prática, pois há muitos para produzir.Usando a técnica de programação dinâmica, podemos calcular o número de decodificações válidas . Você pode encontrar o código aqui . Resultados:
Ungolfed
Golfe
fonte
PHP,
234226 bytesfunção recursiva, pega dicionário de um arquivo chamado
d
.Não corresponde a todas as palavras do dicionário que não sejam letras.
Você pode usar qualquer nome de arquivo se
define ("d","<filename>");
antes de chamar a função.Adicione 2 ou 3 bytes para uma execução mais rápida:
remova
$s?:print"$r\n";
, insira$s!=$m?
antes0!==
e:print$r.$w
antes;}}
.demolir
fonte
Groovy
377337Notas
O ditado deve ser um arquivo chamado
d
. A sequência morse é passada pela linha de comando. por exemplo:Para "compactação de código morse", estou usando uma árvore binária
fonte