Code Morse vers sortie standard

13

Cette question implique de prendre des entrées en code Morse comme. (point) et - (symbole moins), avec des espaces pour séparer l'entrée. Votre tâche consiste à convertir le code en sortie standard. Vous pouvez supposer que la seule entrée contient des symboles de caractères trouvés dans l'alphabet International Morse Code, ici: http://en.wikipedia.org/wiki/Morse_code#Letters.2C_numbers.2C_punctuation .

Toutes les sorties doivent utiliser des lettres minuscules. Un double espace doit être interprété comme un espace de mots.

Exemple d'entrée:

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

Production:

example. sos

Le code le plus court après deux semaines gagne.

Peter Taylor
la source
Vous dites que seuls les «symboles de caractères» sont des caractères et des symboles?
Sinkingpoint
@Quirliom Tous les "symboles" de ce lien sont des caractères. Tout ce que vous pouvez mettre dans une chaîne est un caractère (enfin, fondamentalement). Cependant, cette partie de la question dit essentiellement que chaque morceau de morse sera valide.
Justin
@Quirliom Oui, chaque «personnage» Morse, comme .- pour «a» et. pour «e» est valide. Aucun personnage non morse n'a besoin d'être manipulé.
Qu'en est-il de l'espace des lettres et de l'espace des mots? Un espace pour les premiers et deux (ou plus) pour les seconds?
Paul R

Réponses:

8

Mathematica 62

Mathematica nous permet de tricher

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

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

e

exemple.

avez-vous hué aujourd'hui?

Les deux premiers symboles .et .-sont nécessaires pour interpréter correctement les petits codes.

ybeltukov
la source
Il manque la conversion en minuscules.
Peter Taylor
@PeterTaylor Il peut être facilement modifié f=ToLowerCase@StringDrop[WolframAlpha[". .- "<>#,"Result"],2]&pour les minuscules.
ybeltukov le
L'utilisation de l'API Wolfram Alpha ne nécessite-t-elle pas un identifiant d'application? Si oui, cela ne devrait-il pas ajouter au nombre de caractères? Solution néanmoins très intelligente.
Björn Lindqvist
@ BjörnLindqvist Évaluez simplement exactement cette commande dans Mathematica , ça va très bien.
ybeltukov
23

Drat, j'espérais arriver ici avant l'arrivée des GolfScripters :-(

Anyhoo ...

C: 228 caractères:

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

J'ai pensé ajouter une explication sur la façon dont cela fonctionne.

Les données d'entrée sont analysées en fonction des données d'arborescence dans *c, qui peuvent être développées comme suit (en utilisant ·pour représenter un nœud vacant):

                     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
····$·······?_····"··.····@···'··-········;!·)·····,····:·······

En commençant en haut de l'arbre, descendez en vous déplaçant vers la gauche pour un point et vers la droite pour un tiret. Ensuite, affichez le caractère auquel vous vous trouvez à la fin de la chaîne d'entrée (c'est-à-dire lorsqu'un caractère d'espacement est rencontré). Ainsi, par exemple, trois points et un tiret vous amèneront à vvia e, iet s. Au lieu de vérifier explicitement les points (ASCII \x2e) et les tirets (ASCII \x2d), nous avons seulement besoin de vérifier le dernier bit ( m[n]&1), qui est 0 pour .et 1 pour -.

Six lignes suffisent pour tout coder sauf $, qui a 7 points / tirets:, ...-..-mais comme les données d'entrée sont garanties pour être valides, cela peut facilement être corrigé en tronquant l'entrée à 6 caractères ( m[6]=0) et en interprétant ...-..comme à la $place. Nous pouvons également supprimer les 7 derniers octets des données de l'arborescence, car ils sont tous vides et ne sont pas nécessaires si l'entrée est valide.

r3mainer
la source
1
Belle astuce pour supprimer le dernier caractère des codes à 6 caractères et raccourcir la table de recherche.
Peter Taylor
2
Je vote autant pour la clarté de la discussion que pour la qualité de l'algorithme. Bon travail.
Michael Stern
Voyez si vous pouvez raser quelques caractères en traitant caractère par caractère au lieu de lire une chaîne entière. cPourrait être aligné. Vous pourriez peut-être utiliser le modulo et un décalage pour essayer d’écraser ensemble les valeurs les plus élevées; c'est ce que je fais dans ma solution. Bref, beau travail!
FireFly
8

GolfScript ( 116 113 97 caractères)

Cela inclut les caractères non imprimables utilisés dans une table de recherche, donc je le donne en sortie 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

Cela décode en un programme équivalent à

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+

qui est essentiellement

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

Cela utilise un hachage parfait (non minimal) basé sur l'idée de base d' un algorithme optimal pour générer des fonctions de hachage parfaites minimales; Tchèque, Havas et Majewski; 1992 . Leur idée de base est que vous utilisez deux fonctions de hachage, f1et f2, avec une table de recherche g, et le hachage parfait est (g[f1(str)] + g[f2(str)]) % m(où mest le nombre de chaînes que nous souhaitons distinguer); la partie intelligente est la façon dont ils construisent g. Considérez toutes les valeurs f1(str)et les f2(str)chaînes strd'intérêt en tant que nœuds dans un graphique non orienté, et ajoutez un bord entre f1(str)etf2(str)pour chaque chaîne. Ils exigent non seulement que chaque arête soit distincte, mais que le graphe soit acyclique; alors c'est juste un DFS pour assigner des poids aux nœuds (c'est-à-dire pour remplir la table de recherche g) de telle sorte que chaque bord ait la somme requise.

Czech et al génèrent des fonctions aléatoires f1et f2qui sont exprimées via des tables de recherche, mais ce n'est clairement pas bon: j'ai cherché un hachage approprié en utilisant des conversions de base simples avec deux bases distinctes de -10 à 9. J'ai également assoupli l'exigence acyclique. Je ne voulais pas assigner les chaînes à des valeurs de 0 à 54, mais aux codes ASCII correspondants, donc plutôt que d'en prendre (g[f1(str)] + g[f2(str)]) % mje voulais (g[f1(str)] + g[f2(str)]) % Npour certains N > 'z'. Mais cela donne la liberté d'essayer divers Net de voir si l'un d'eux autorise une table de recherche valideg , qu'il y ait des cycles ou non. Contrairement à Czech et al, je me fiche que la recherche de la fonction de hachage parfaite soit O (n ^ 4).

Le graphique généré par -4baseet 5basemod 59est:

Graphique rendu par point avec quelques ajustements mineurs

ce qui est assez sympa à part le plus gros composant connecté, qui a trois cycles de longueur 1. Il faut remonter N=233avant de pouvoir trouver celui gqui est cohérent.

Peter Taylor
la source
Autres encodages possibles pour la table de recherche: l'encodage différentiel ne va pas aider, car il n'y a pas de structure. Il pourrait être possible d'exploiter la non-répétition des valeurs en codant comme une permutation, mais soit les écarts doivent être traités séparément (54 caractères de sortie => 30 octets d'entropie, plus le décodage; les exécutions nécessitent au moins 15 octets si elles sont codées en tant que conversion de base directe; il serait peut-être possible d'améliorer le total actuel de 92 octets) ou nous permutons 138 éléments (plus de 98 octets d'entropie, plus le décodage).
Peter Taylor
Comme il s'agit d'un code sans préfixe, nous ne pouvons pas facilement essayer de passer le dur travail à une implémentation zlib.
Peter Taylor
4

C, 169 caractères

Je n'ai pas pu trouver une meilleure fonction de hachage ..

(J'ai posté le code non réduit, mais je l'ai compté réduit; pour réduire, faites simplement :%s/ //g | %j!dans vim, puis remettez l'espace dans la chaîne littérale.)

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

Essai

( morse.inest juste l'alphabet entier en morse sur des lignes séparées):

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

Explication

Celui-ci est assez simple. c < 33trouve un espacement / séparateur ( , \n, EOF, ...). c % 2traduit un point ou un tiret en un peu. L'idée est de créer un nombre unique pour chaque caractère simplement en l'interprétant comme un nombre binaire (après l'avoir préfixé avec 1 pour traiter la longueur variable) (cette interprétation est la v*2 + c%2partie). J'obtiens ensuite une LUT de 137 caractères, que j'ai compactée en hachant la valeur résultante ( v < 64? v : v % 51 + 33, constantes trouvées par essais et erreurs et en regardant la distribution et en essayant de trouver un énorme écart). Malheureusement, cette fonction de hachage a une seule collision, c'est pourquoi je dois cas particulier le 40 → '&'mappage.

Luciole
la source
4

R , 145 octets

Traduit un point en 2, un tiret en 1 et interprète le nombre en ternaire et prend le mod 89, ce qui donne un nombre unique que nous pouvons utiliser dans une table de hachage. La présence d'un 13 (111 base-3) signifie ajouter 1 car ASCII 13 ne fonctionne pas dans TIO.

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

Essayez-le en ligne!

R , 236 octets (non concurrent)

Cela ne va pas être compétitif, mais cela nous permet de montrer quelque chose d'intéressant dans R: stocker l'arborescence du code Morse dans une structure de langage citée met la récupérer du code de points et de tirets très simplement en utilisant le fait qui [[peut être appliqué récursivement à listes. Par exemple, m[[c(2,2,3,2)]]récupère le point, le point, le tiret, le point 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]])))

Essayez-le en ligne!

J.Doe
la source
1

Powershell, 193 octets

$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 test moins golfé:

$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"
}

Production:

True: example. sos
True: 0123456789abcdefghijklmnopqrstuvwxyz
True: hello world
mazzy
la source
0

JavaScript (165 octets, implémentant uniquement quatre plans.)

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)

L'entrée doit être affectée à n, exécutez le code suivant pour obtenir la sortie:

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
la source
Non seulement cela semble être une implémentation incomplète, mais cela ne fonctionne même pas. Fiddle + Chrome donne une erreur Cannot read property '42' of undefined, et IdeOne signale également une erreur (bien que sans message utile).
Peter Taylor
Essayez de le réparer :)
Timtech
@PeterTaylor Il est indiqué qu'il ne prend en charge que quatre plans, c'est-à-dire jusqu'à 4 caractères morse de long, il n'acceptera donc pas . -..- .- -- .--. .-.. . .-.-.-en entrée, car le dernier code a une longueur de 6 caractères. Dans l'exemple de script, je l'omet et je continue . -..- .- -- .--. .-.., qui alerte ( example).
aularon
Voici un violon avec le deuxième code de bloc: jsfiddle.net/aularon/AHY4e/1
aularon