Código Morse para saída padrão

13

Esta questão envolve receber entradas no código Morse como. (ponto final) e - (símbolo de menos), com espaços para separar a entrada. Sua tarefa é converter o código em saída padrão. Você pode assumir que a única entrada contém símbolos de caracteres encontrados no alfabeto Código Morse Internacional, encontrado aqui: http://en.wikipedia.org/wiki/Morse_code#Letters.2C_numbers.2C_punctuation .

Toda saída deve usar letras minúsculas. Um espaço duplo deve ser interpretado como um espaço de palavra.

Entrada de amostra:

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

Resultado:

example. sos

O código mais curto após duas semanas vence.

Peter Taylor
fonte
Você diz que apenas 'símbolos de caracteres' são caracteres e símbolos?
Sinkingpoint
@Quirliom Todos os "símbolos" nesse link são caracteres. Tudo o que você pode colocar em uma String é um caractere (bem, basicamente). No entanto, essa parte da questão está basicamente dizendo que todo pedaço de morse será válido.
Justin
@ Quirliom Sim, todos os 'personagens' de Morse, como .- para 'a' e. para 'e' é válido. Nenhum personagem não-Morse precisa ser tratado.
E o espaço das letras e o espaço das palavras? Um espaço para o primeiro e dois (ou mais) para o último?
Paul R
Slighly (un) relacionados: stackoverflow.com/questions/1352587/code-golf-morse-code
javatarz

Respostas:

8

Mathematica 62

Mathematica nos permite enganar

f=ToLowerCase@StringDrop[WolframAlpha[". .- "<>#,"Result"],2]&

f@"."
f@". -..- .- -- .--. .-.. . .-.-.-"
f@".... .- ...- .  -.-- --- ..-  -- --- --- . -..  - --- -.. .- -.-- ..--.."

e

exemplo.

você se queixou hoje?

Os dois primeiros símbolos .e .-são necessários para interpretar códigos pequenos corretamente.

ybeltukov
fonte
Falta a conversão para minúscula.
Peter Taylor
@PeterTaylor Pode ser facilmente modificado f=ToLowerCase@StringDrop[WolframAlpha[". .- "<>#,"Result"],2]&para letras minúsculas.
precisa saber é o seguinte
O uso da api do Wolfram Alpha não requer um ID de aplicativo? Nesse caso, isso não deveria aumentar a contagem de caracteres? No entanto, solução muito inteligente.
Björn Lindqvist
@ BjörnLindqvist Basta avaliar exatamente esse comando no Mathematica , ele é muito bom.
precisa saber é o seguinte
23

Drat, eu esperava chegar aqui antes da chegada dos GolfScripters :-(

Anyhoo ...

C: 228 caracteres:

char n,t,m[9],*c=" etianmsurwdkgohvf l pjbxcyzq  54 3   2& +    16=/   ( 7   8 90    $       ?_    \"  .    @   '  -        ;! )     ,    :";
main(){while(scanf("%s",m)>0){for(t=m[6]=n=0;m[n];n++)t+=t+1+(m[n]&1);putchar(c[t]);}}

Eu pensei em adicionar uma explicação de como isso funciona.

Os dados de entrada são analisados ​​de acordo com os dados da árvore *c, que podem ser expandidos da seguinte forma (usando ·para representar um nó vago):

                     dot <-- (start) --> dash
                e                               t
        i               a               n               m
    s       u       r       w       d       k       g       o
  h   v   f   ·   l   ·   p   j   b   x   c   y   z   q   ·   ·
 5 4 · 3 · · · 2 & · + · · · · 1 6 = / · · · ( · 7 · · · 8 · 9 0
····$·······?_····"··.····@···'··-········;!·)·····,····:·······

Começando no topo da árvore, desça enquanto se move para a esquerda para um ponto e para a direita para um traço. Em seguida, imprima o caractere em que você estiver quando a sequência de entrada terminar (ou seja, quando um caractere de espaço em branco for encontrado). Por exemplo, três pontos e um traço levará você a vvia e, ie s. Em vez de procurar explicitamente por pontos (ASCII \x2e) e traços (ASCII \x2d), precisamos apenas verificar o último bit ( m[n]&1), que é 0 .e 1 para -.

Seis linhas são suficientes para codificar tudo $, exceto 7 pontos / traços: ...-..-mas, como os dados de entrada são válidos, isso pode ser facilmente corrigido truncando a entrada em 6 caracteres ( m[6]=0) e interpretando ...-..como $alternativa. Também podemos cortar os últimos 7 bytes dos dados da árvore, pois todos estão vazios e não são necessários se a entrada for válida.

r3mainer
fonte
1
Bom truque para descartar o último caractere dos códigos de 6 caracteres e diminuir a tabela de pesquisa.
Peter Taylor
2
Estou votando tanto pela clareza da discussão quanto pela qualidade do algoritmo. Bom trabalho.
Michael Stern
Veja se você pode cortar alguns caracteres processando caractere por caractere, em vez de ler uma sequência inteira em c. Talvez você possa usar módulo e deslocamento para tentar juntar os valores mais altos; é isso que faço na minha solução. Enfim, bom trabalho!
FireFly
8

GolfScript ( 116 113 97 caracteres)

Isso inclui caracteres não imprimíveis usados ​​em uma tabela de pesquisa, por isso estou fornecendo-o como saída xxd:

0000000: 6e2d 2720 272f 7b60 7b5c 6261 7365 2035
0000010: 3925 2210 a9cd 238d 57aa 8c17 d25c d31b
0000020: 432d 783e 277a 3823 e146 e833 6423 23ac
0000030: e72a 39d5 021c 4e33 3b30 3138 dc51 2044
0000040: 3aa7 d001 df4b 2032 333f 36ae 51c3 223d
0000050: 7d2b 5b35 2d34 5d2f 2b32 3333 257d 256e
0000060: 2b

Isso decodifica para um programa equivalente a

n-' '/{`{\base 59%"\x10\xA9\xCD#\x8DW\xAA\x8C\x17\xD2\\\xD3\eC-x>'z8#\xE1F\xE83d##\xAC\xE7*9\xD5\x02\x1CN3;018\xDCQ D:\xA7\xD0\x01\xDFK 23?6\xAEQ\xC3"=}+[5-4]/+233%}%n+

que é essencialmente

n-' '/{`{\base 59%"MAGIC STRING"=}+[5-4]/+233%}%n+

Isso usa um hash perfeito (não mínimo) com base na idéia central de Um algoritmo ideal para gerar funções de hash perfeitas mínimas; Tcheco, Havas e Majewski; 1992 . A idéia básica deles é que você use duas funções de hash f1e f2, junto com uma tabela de pesquisa g, e o hash perfeito seja (g[f1(str)] + g[f2(str)]) % m(onde mestá o número de strings que desejamos distinguir); a parte inteligente é a maneira como eles constroem g. Considere todos os valores f1(str)e f2(str)cadeias strde interesse como nós em um gráfico não direcionado e adicione uma aresta entre f1(str)ef2(str)para cada sequência. Eles exigem não apenas que cada aresta seja distinta, mas que o gráfico seja acíclico; então é apenas um DFS atribuir pesos aos nós (ou seja, para preencher a tabela de pesquisa g), de modo que cada borda tenha a soma necessária.

Czech et al. Geram funções aleatórias f1e f2são expressas por meio de tabelas de pesquisa, mas isso claramente não é bom: procurei um hash adequado usando conversões básicas simples com duas bases distintas de -10 a 9. Também relaxei o requisito acíclico. Eu não queria atribuir as strings a valores de 0 a 54, mas aos códigos ASCII correspondentes, então, ao invés de pegar o que (g[f1(str)] + g[f2(str)]) % meu queria (g[f1(str)] + g[f2(str)]) % Npara alguns N > 'z'. Mas isso permite liberdade para tentar várias Ne ver se alguma delas permite uma tabela de pesquisa válida g, independentemente de haver ciclos. Ao contrário de Czech et al, não me importo se a busca pela função hash perfeita for O (n ^ 4).

O gráfico gerado por -4basee 5basemod 59é:

Gráfico processado por ponto com alguns pequenos ajustes

o que é bastante bom, exceto pelo maior componente conectado, que tem três ciclos de comprimento 1. Temos que ir até N=233que possamos encontrar um gque seja consistente.

Peter Taylor
fonte
Outras codificações possíveis para a tabela de pesquisa: a codificação de diferença não vai ajudar, porque não existe a estrutura. Pode ser possível explorar a não repetição de valores codificando como uma permutação, mas as lacunas precisam ser tratadas separadamente (54 caracteres de saída => 30 bytes de entropia, mais decodificação; as execuções precisam de pelo menos 15 bytes se codificadas como uma conversão de base direta; talvez seja possível melhorar o total atual de 92 bytes) ou estamos permutando 138 itens (mais de 98 bytes de entropia, mais decodificação).
Peter Taylor
Como é um código sem prefixo, não podemos facilmente tentar reduzir o trabalho árduo para uma implementação zlib.
Peter Taylor
4

C, 169 caracteres

Não consegui encontrar uma função de hash melhor ..

(Publiquei o código não minificado, mas contei como minificado; para minificar basta fazer :%s/ //g | %j!no vim e, em seguida, colocar o espaço na cadeia literal de volta.)

c, v = 1;

main() {
  while (c = getchar(), ~c)
    v = c < 33? putchar(
      "& etianmsurwdkgohvf.l.pjbxcyzq..54.3.;!2).+...,16=/:..(.7.?_8.9o\"...$...@...'..-"[v < 64? (v != 40)*v : v % 51 + 33]
    ), 1 : v * 2 + c % 2;
}

Execução de teste

( morse.iné apenas o alfabeto inteiro em letras maiúsculas e minúsculas):

% clang morse.c && ./a.out </tmp/morse.in
abcdefghijklmnopqrstuvwxyzO123456789.,?'!/()&:;=+-_"$@
% ./a.out <<<'. -..- .- -- .--. .-.. . .-.-.-  ... --- ...'
example. sos

Explicação

Este é bastante direto. c < 33encontra um espaço em branco / separador ( , \n, EOF, ...). c % 2traduz um ponto ou traço em um pouco. A idéia é criar um número único para cada caractere simplesmente interpretando-o como um número binário (depois de prefixá-lo com 1 para lidar com o comprimento da variável) (essa interpretação é a v*2 + c%2parte). Em seguida, recebo um LUT de 137 caracteres, que compactou com hash do valor resultante ( v < 64? v : v % 51 + 33constantes encontradas por tentativa e erro e olhando a distribuição e tentando encontrar uma lacuna enorme). Infelizmente, essa função hash tem uma única colisão, e é por isso que eu preciso especial-caso o 40 → '&'mapeamento.

FireFly
fonte
4

R , 145 bytes

Traduziu um ponto para um 2, um traço para um 1 e interpreta o número no ternário e pega o mod 89, que fornece um número único que podemos usar em uma tabela de hash. A presença de um 13 (111 base-3) significa adicionar 1 porque o ASCII 13 não funciona no TIO.

cat(c(letters,0:9,".")[match(strtoi(chartr(".-","12",scan(,"",t=scan(,""))),3)%%89+1,utf8ToInt('DG,)62	5N*EHMAI.%"!4=@'))],sep='')

Experimente online!

R , 236 bytes (não concorrente)

Isso não será competitivo, mas nos permitirá mostrar algo interessante em R: armazenar a árvore de código Morse dentro de uma estrutura de linguagem citada me recuperá-la do código de pontos e traços de maneira muito simples, usando o fato de que [[pode ser aplicado recursivamente a listas. Por exemplo, m[[c(2,2,3,2)]]recupera ponto, ponto, traço, ponto ou "f".

m=quote(.(e(i(s(h(5,4),v(,3)),u(f,M(,2))),a(r(l,.(.(,.),)),w(p,j(,1)))),t(n(d(b(6),x),k(c,y)),m(g(z(7),q),o(D(8),S(9,0))))))
for(w in scan(,"",t=scan(,"")))
cat(chartr("MDS","-. ","if"(is.symbol(z<-m[[(utf8ToInt(w)==45)+2]]),z,z[[1]])))

Experimente online!

J.Doe
fonte
1

Powershell, 193 bytes

$n=1
-join("$args "|% t*y|%{if($_-32){$n=$n*2+($_-ne'.')}else{("  etianmsurwdkgohvf l pjbxcyzq  54 3   2& +~16=/   ( 7   8 90~~~?~ `"  .~@   '  -~~;! )~ ,~:~~~~$"-replace'~','    ')[$n]
$n=1}})

Script de teste com menos golfe:

$f = {

$n=1
-join(
    "$args "|% t*y|%{
        if($_-32){
            $n=$n*2+($_-ne'.')
        }else{
            ("  etianmsurwdkgohvf l pjbxcyzq  54 3   2& +~16=/   ( 7   8 90~~~?~ `"  .~@   '  -~~;! )~ ,~:~~~~$"-replace'~','    ')[$n]
            $n=1
        }
    }
)

}

@(
    ,("example. sos",". -..- .- -- .--. .-.. . .-.-.-  ... --- ...")
    ,("0123456789abcdefghijklmnopqrstuvwxyz","----- .---- ..--- ...-- ....- ..... -.... --... ---.. ----. .- -... -.-. -.. . ..-. --. .... .. .--- -.- .-.. -- -. --- .--. --.- .-. ... - ..- ...- .-- -..- -.-- --..")
    ,("hello world", ".... . .-.. .-.. ---  .-- --- .-. .-.. -..")
) | % {
    $expected,$s = $_
    $result = &$f $s
    "$($result-eq$expected): $result"
}

Resultado:

True: example. sos
True: 0123456789abcdefghijklmnopqrstuvwxyz
True: hello world
confuso
fonte
0

JavaScript (165 bytes, implementando apenas quatro planos).

n=''.replace(/\./g,1).replace(/-/g,0).split(' ')
l='|te|mnai|ogkdwrus|cöqzycxbjpälüfvh'.split('|')
r=''
for(i in n){r+=l[n[i].length][parseInt(n[i],2)]}
alert(r)

A entrada deve ser atribuída a n, execute o seguinte código para obter a saída:

n='. -..- .- -- .--. .-.. .'.replace(/\./g,1).replace(/-/g,0).split(' ')
l='|te|mnai|ogkdwrus|cöqzycxbjpälüfvh'.split('|')
r=''
for(i in n) {r+=l[n[i].length][parseInt(n[i],2)]}
alert(r)
aularon
fonte
Isso não apenas parece ser uma implementação incompleta, mas nem funciona. O Fiddle + Chrome apresenta um erro Cannot read property '42' of undefinede o IdeOne também relata um erro (embora sem uma mensagem útil).
Peter Taylor
Tente corrigi-lo :)
Timtech
@PeterTaylor Afirma-se que ele suporta apenas quatro planos, ou seja, códigos morse longos com até 4 caracteres, portanto não será aceito . -..- .- -- .--. .-.. . .-.-.-como entrada, pois o último código tem 6 caracteres. No script de exemplo, eu o omito e continuo com . -..- .- -- .--. .-..quais alertas ( example).
aularon
Aqui está um violino com o segundo código de bloco: jsfiddle.net/aularon/AHY4e/1
aularon