Telegraphy Golf: décoder le code Baudot

31

Contexte

En 1870, Émile Baudot invente le Baudot Code , un codage de caractères de longueur fixe pour la télégraphie. Il a conçu le code pour être entré à partir d'un clavier manuel avec seulement cinq touches; deux opérés de la main gauche et trois de la droite:

Clavier à 5 touches Baudot

L'index droit, le majeur et l'annulaire actionnent respectivement les touches I , II et III , et l'index gauche et le majeur actionnent IV et . (Désormais, j'utiliserai leurs chiffres arabes occidentaux, c'est-à-dire de 1 à 5. ) Les caractères sont entrés sous forme d'accords. Pour saisir la lettre "C", par exemple, l'opérateur appuie sur les touches 1 , 3 et 4touches simultanément, après quoi un bras de brosse rotatif lit chaque touche dans l'ordre et transmet un courant ou, pour les touches non enfoncées, aucun courant. Le résultat est, en termes modernes, un codage binaire à 5 bits le moins significatif en premier, dans lequel notre exemple, "C", est codé comme 10110.

5 bits ??

Vous pensez peut-être que 5 bits, qui peuvent exprimer au plus 32 symboles uniques, ne suffisent pas, même pour toutes les lettres et chiffres anglais, pour ne rien dire de la ponctuation. Baudot avait un truc dans sa manche, cependant: son jeu de caractères est en fait deux jeux distincts: lettres et chiffres , et il a défini deux codes spéciaux pour basculer entre eux. Letter Shift , qui passe en mode Letters, est activé en appuyant uniquement sur la touche 5 ( 00001), et Figure Shift est activé avec la touche 4 ( 00010).

Défi

Votre défi est d'écrire un programme ou une fonction qui décode les transmissions du code Baudot.

Une vraie transmission commencerait par quelques bits d'initialisation, plus un bit de démarrage et d'arrêt avant et après chaque caractère, mais nous allons les ignorer et ne nous soucier que des 5 bits uniques pour chaque caractère. Les formats d'entrée et de sortie sont décrits ci-dessous.

Code de Baudot

Il existe deux versions différentes de Baudot Code: Continental et UK Nous allons utiliser la version UK, qui n'inclut pas de caractères comme "É" du français natif de Baudot. Nous allons également laisser de côté tous les symboles de la version britannique qui ne figurent pas parmi les caractères ASCII imprimables. Vous n'aurez qu'à décoder les caractères du tableau ci-dessous, qui sont tous des caractères ASCII imprimables à l'exception des trois derniers caractères de contrôle qui sont expliqués sous le tableau.

La colonne "Ltr" montre les caractères en mode Lettre et "Fig" montre les caractères en mode Figure:

        Encoding             Encoding
Ltr Fig  12345       Ltr Fig  12345
--- --- --------     --- --- --------
 A   1   10000        P   +   11111
 B   8   00110        Q   /   10111
 C   9   10110        R   -   00111
 D   0   11110        S       00101
 E   2   01000        T       10101
 F       01110        U   4   10100
 G   7   01010        V   '   11101
 H       11010        W   ?   01101
 I       01100        X       01001
 J   6   10010        Y   3   00100
 K   (   10011        Z   :   11001
 L   =   11011        -   .   10001
 M   )   01011        ER  ER  00011
 N       01111        FS  SP  00010
 O   5   11100        SP  LS  00001
 /       11000

Les trois dernières lignes de la colonne de droite sont des caractères de contrôle:

  • ERest l' effacement . Les machines de télégraphie de Baudot imprimeraient un symbole semblable à un astérisque pour ce caractère pour dire au lecteur que le caractère précédent devrait être ignoré, mais nous allons être encore plus gentils avec le lecteur et en fait omettre (ne pas imprimer) le caractère précédent . Il agit de la même façon en mode Lettre et en mode Figure.

  • FSest Figure Shift . Cela fait passer le jeu de caractères des lettres aux chiffres. Si le décodeur est déjà en mode Figure, FS est traité comme un espace (ergo SPdans la colonne "Ltr"). Lorsque le décodeur est en mode Figure, il reste en mode Figure jusqu'à ce qu'un caractère LS soit reçu.

  • LSest Letter Shift . Il fait passer le jeu de caractères des chiffres aux lettres. Si le décodeur est déjà en mode Lettre, LS est traité comme un espace . En mode lettre, le décodeur reste en mode lettre jusqu'à ce qu'un caractère FS soit reçu.

Le décodeur démarre toujours en mode Lettre.

Voici un exemple avec Figure Shift, Letter Shift et Space:

01011 10000 00100 00001 00010 10000 11100 00001 10101 11010
  M     A     Y   LS/SP FS/SP   1     5   LS/SP   T     H

Cela donne le message MAY 15TH. Comme vous pouvez le voir, le premier caractère 00001(Majuscule / Espace) agit comme un espace, car le décodeur est déjà en mode Lettre. Le caractère suivant 00010(Figure Shift / Space) fait passer le décodeur en mode Figure pour imprimer 15. Puis 00001apparaît à nouveau, mais cette fois -ci, il agit comme lettre Shift pour remettre le décodeur en mode Lettre.

Pour votre commodité, voici les caractères dans un format peut-être plus facile à digérer dans un éditeur, triés par code:

A,1,10000|E,2,01000|/,,11000|Y,3,00100|U,4,10100|I,,01100|O,5,11100|FS,SP,00010|J,6,10010|G,7,01010|H,,11010|B,8,00110|C,9,10110|F,,01110|D,0,11110|SP,LS,00001|-,.,10001|X,,01001|Z,:,11001|S,,00101|T,,10101|W,?,01101|V,',11101|ER,ER,00011|K,(,10011|M,),01011|L,=,11011|R,-,00111|Q,/,10111|N,,01111|P,+,11111

Contribution

L'entrée sera une chaîne, un tableau ou une liste de bits dans le premier bit de poids faible. Chaque caractère sera représenté par un quintet de 5 bits. Les bits peuvent être dans n'importe quel format raisonnable, par exemple une chaîne binaire, un tableau de 0s et 1s, une chaîne de caractères "0"et "1", un seul très grand nombre, etc., tant qu'il correspond directement aux bits de la transmission.

Chaque transmission aura au moins un quintet imprimable et au plus 255 quintets (imprimables ou non), soit 5–1,275 bits inclus.

L'entrée ne peut contenir que les bits de la transmission, avec deux exceptions autorisées: n'importe quel nombre de 0bits de début ou de fin et / ou, pour la chaîne, une seule nouvelle ligne de fin peut être ajoutée à la transmission. Les bits ou caractères de début ou de fin ne peuvent pas être ajoutés avant ou après chaque quintet, c'est-à-dire que vous ne pouvez pas garnir chaque quintet à 8 bits (ou prendre chaque quintet comme un nombre unique dans un tableau - à moins que votre langue n'ait un type entier sur 5 bits) ou séparé quintettes avec des bits supplémentaires, par exemple "01111\n11100".

Notes et étuis de bord

  1. La transmission ne contiendra que les caractères des colonnes "Ltr" et "Fig" du tableau ci-dessus. Vous ne recevrez jamais par exemple 01110en mode Figure, car il est absent de la colonne "Fig".

  2. On suppose que le décodeur sera toujours en mode Lettre au début d'une transmission. Cependant, le premier caractère peut être un caractère FS pour passer immédiatement en mode Figure.

  3. Lorsque le décodeur est en mode Lettre, il peut recevoir un caractère LS et lorsqu'il est en mode Figure, il peut recevoir un caractère FS. Dans les deux cas, un caractère Espace doit être imprimé (voir Sortie).

  4. Le caractère ER ne sera jamais le premier caractère d'une transmission, ni ne suivra immédiatement un LS, FS ou un autre ER.

  5. Un personnage FS peut immédiatement suivre un personnage LS et vice versa.

  6. Ni le caractère LS ni le caractère FS ne seront le dernier caractère d'une transmission.

  7. Les caractères /et -peuvent être reçus en mode lettre (codes 11000et 10001, respectivement) ou en mode figure ( 10111 et 00111).

Sortie

La sortie peut être dans n'importe quel format raisonnable, le plus raisonnable étant ASCII (ou UTF-8, pour lequel tous les caractères représentés sont les mêmes que ASCII). Veuillez indiquer dans votre réponse si votre sortie est dans un autre encodage ou format.

Remarques

  • Le caractère espace (voir 3. ci-dessus) doit être un espace ASCII (0x20) ou l'équivalent de votre encodage, c'est-à-dire ce que vous obtenez lorsque vous appuyez sur la barre d'espace.

Gagnant

C'est du . Le code le plus court en octets gagne.

Les restrictions

  • Les failles standard sont interdites.

  • Les espaces de fin et / ou une seule nouvelle ligne de fin sont autorisés. Les espaces de tête ou d'autres caractères (qui ne font pas partie de la transmission) sont interdits.

  • Vous ne pouvez pas utiliser de fonctions intégrées ou de bibliothèque qui décodent le code Baudot (ou l'un de ses descendants, par exemple Murray Code, ITA-1, etc.).

Cas de test

Input: 001101000010100111101110010101
Output: BAUDOT
Input: 11010010001001100011110111101111100
Output: HELLO
Input: 01011100000010000001000101000011100000011010111010
Output: MAY 15TH
Input: 0001000100010000001000001011101110011100101010010110101010001111100101
Output: 32 FOOTSTEPS
Input: 10110000110101011100111100001111011010000001101110
Output: GOLF
Input: 000100011000001111100000100010110111001100010110010000111111
Output: 8D =( :P
Input: 0000100001000010000100010001111011111011000011100010001
Output (4 leading spaces):     -/=/-
Jordan
la source
1
Remarque: j'ai encodé les cas de test à la main; si vous voyez quelque chose qui ne va pas, veuillez en parler.
Jordan
1
Dans la table de codes et le résumé qui l'accompagne, le code 00010est répertorié comme SPen mode lettre et FSen mode figure. Selon la description, si nous sommes en mode lettre et que nous recevons du code 00010, nous devrions passer en mode figure, mais les valeurs dans le tableau semblent être l'inverse. Aussi, vice versa pour 00001.
Sok
3
Cet homme était sacrément intelligent, je ne connaissais pas la compression utilisée en télégraphie. Merci pour la leçon d'histoire.
Magic Octopus Urn
4
@carusocomputing Right ?? Baudot n'avait pas d'éducation formelle au-delà de l'école primaire, mais non seulement il a inventé le code Baudot, il a inventé un système de multiplexage qui permettait à quatre opérateurs d'utiliser une seule ligne télégraphique simultanément. J'ai trouvé cette brochure de 1919 qui décrit ses inventions en détail très intéressante: samhallas.co.uk/repository/telegraph/b6_baudot_multiplex.pdf
Jordan

Réponses:

6

Pyth, 98 97 95 93 90 83 80 octets

Le code contient des caractères non imprimables, voici donc un xxdhexdump réversible :

00000000: 753f 7133 4a69 4832 5047 2b47 3f3c 334a  u?q3JiH2PG+G?<3J
00000010: 4040 6332 2e22 275a 75ae 5751 fb4e 3cd7  @@c2."'Zu.WQ.N<.
00000020: 02ce 8719 aac1 e0e0 fe1f 09e5 85bc a767  ...............g
00000030: 8e0c 1f47 508a cad1 1acb b26f 951e e5d6  ...GP......o....
00000040: 225a 4a2a 5c20 715a 3d5a 744a 637a 356b  "ZJ*\ qZ=ZtJcz5k

Essayez-le en ligne. Suite de tests.

Assez longue, mais la table de consultation ne prenne plus la moitié de l'espace.

Pour 117 octets, voici la même chose sans imprimables (nécessite cependant ISO-8859-1):

u?q3JiH2PG+G?<3J@@c2."'Zu®WQûN<×\x02Î\x87\x19ªÁààþ\x1f\tå\x85¼§g\x8e\x0c\x1fGP\x8aÊÑ\x1a˲o\x95\x1eåÖ"ZJ*\ qZ=ZtJcz5k

Ou, pour 93 octets, sans compression sur la table de recherche:

u?q3JiH2PG+G?<3J@@c2"OVDPYSBREXGMIWFNA-JKUTCQ/ZHL5'0+3;8-2;7);?;;1.6(4;9/;:;="ZJ*\ qZ=ZtJcz5k
PurkkaKoodari
la source
5

JavaScript (ES6), 160 158 153 octets

let f =
    
s=>s.replace(/.{5}/g,s=>(n='0b'+s-1)<2?m-n?(m^=1,''):' ':"? !YSBREXGMIWFNA-JKUTCQ/ZHLOVDP? ?!3 8-2 7) ?  1.6(4 9/ : =5'0+"[n+m*32],m=0).replace(/.!/g,'')

console.log(f("001101000010100111101110010101"));
console.log(f("11010010001001100011110111101111100"));
console.log(f("01011100000010000001000101000011100000011010111010"));
console.log(f("0001000100010000001000001011101110011100101010010110101010001111100101"));
console.log(f("10110000110101011100111100001111011010000001101110"));
console.log(f("000100011000001111100000100010110111001100010110010000111111"));
console.log(f("0000100001000010000100010001111011111011000011100010001"));

Arnauld
la source
5

Lot, 306 304 octets

@echo off
set/pc=
set r=
set d=! !!YSBREXGMIWFNA-JKUTCQ/ZHLOVDP!! !3!8-2!7)!?!!1.6(4!9/!:!=5'0+
set s=2
:l
set/an=(s^&32)+0%c:~,2%%%6*8+0x%c:~2,3%%%14
set c=%c:~5%
if %n%==%s% set/as^^=35&goto l
call set r=%%r%%%%d:~%n%,1%%
if %r:~-1%==! set r=%r:~,-2%&goto l
if not "%c%"=="" goto l
echo %r%

Prend entrée sur STDIN. Étant donné que Batch n'a pas de conversion binaire, je dois le simuler en utilisant une conversion octale et hexadécimale.

  • Les deux premiers chiffres sont convertis en octal (je ne peux pas utiliser de décimal car le premier chiffre pourrait l'être 0). Les valeurs possibles sont 00, 01, 10et 11. Les deux derniers ont de la valeur 8et 9mais je veux 2ou 3alors je prends le reste modulo 6.
  • Les trois derniers chiffres sont convertis en hexadécimal. Les chiffres sont soit 14ou 252fois leur valeur souhaitée, pour prendre le reste modulo 14( 252=14*18).
  • c est la chaîne codée
  • r est le résultat jusqu'à présent
  • d est le tableau de décodage
  • s est l'indice (en tenant compte de l'état de décalage) du caractère qui change d'état de décalage
  • nest le décodage binaire plus le bit 5 s, qui est soit égal à l'état de décalage, auquel cas l'état de décalage est basculé, soit indexé dans le tableau de décodage pour trouver le caractère suivant (ou! pour effacer)
Neil
la source
3

PHP, 206 octets

foreach(str_split($argv[1],5)as$s)($k="# f*YSBREXGMIWFNA-JKUTCQ/ZHLOVDP#l *3#8-2#7)#?##1.6(4#9/#:#=5'0+"[32*$f+bindec($s)])=="*"?array_pop($a):($k=="f"?$f=1:($k=="l"?$f=0:($k=="#"?:$a[]=$k)));echo join($a);
Jörg Hülsermann
la source
2

Puce , 1069 octets

C'est un big'n, mais c'était assez amusant à écrire.

Prend l'entrée comme une chaîne de "1"«et "0"». (Bien qu'il ne regarde vraiment que le bit faible.)

 AZZZZ,-o.AZZZZ  AZZZZ,o-.AZZZZ
*\\\\\]oo[\/\\\**//\\\]oo[/\\\\*
*\\\\/]oo[\/\\/**//\\/]oo[/\\\/*
*\\\//]oo[\/\//**//\//]oo[/\\//*
*\\\/\]oo[\/\/\**//\/\]oo[/\\/\*
*\\//\]oo[\///\**////\]oo[/\//\*
*\\///]oo[\////**/////]oo[/\///*
*\\/\/]oo[\//\/**///\/]oo[/\/\/*
*\\/\\]oo[\//\\**///\\]oo[/\/\\*
=
        o--------K-----o
      ,oo.   z---+~S  ,oo.
     ,LooR. !ZZZZ'   ,LooR.
    ,LLooRR.        ,LLooRR.
   ,LLLooRRR.      ,LLLooRRR.
  ,LLLLooRRRR.    ,LLLLooRRRR.
 ,LLLLLooRRRRR.  ,LLLLLooRRRRR. ,~Z
,LLLLLLooRRRRRR.,LLLLLLooRRRRRR.>m'
|||||||oo||||||||||||||oo||||||)/Rz.
xxxxxxxxxxxxxxx)xxxxxxxxxxxxxxxx\^-^S
x)x))))))))))))xx)))))))))))))xx\g
xx)xxxxxxxxxxxxxxxxxxxxxxxxxxx))\f
xxxxxx))xxxxxxxxxxxxx)))))))))xx\e
xx)x))x)xxxxx))x)))))xxxxxxx)))x\d
xx))x))xxx)))xxxxx)))xxxx)))xx)x\c
xx)xx)xx))x))x)xx)xx)xx))x))x)xx\b
x)))))))x)xx)xxxx)x)xx)x)xx)xx)x\a
x)x)x))))))x)x))x)))x)))xx))x))x/f
x)x)x))))))x)x)xxx)xxxxxxxx)x)xx/e
xxxxxxxx))xxxxxx))))x)))xxx)x))x/d
xxxxx))xxxxx)x)xxx)xxx))xx))xx)x/c
xxx)xxx)xxxx)x)xxxxxx))xxx))x))x/b
x)xxx)x)x)xx)xxxxx))x)))xx))xxxx/a

Essayez-le en ligne!

Remarque: L'effacement utilise le caractère de retour arrière ASCII ( \x08), ce qui signifie qu'ils auront l'air drôle dans TIO, mais ils ont l'air bien dans, disons, xterm.

Structure basique

En haut, au-dessus de la =ligne, se trouve le décodeur d'entrée. Il transforme l'entrée en l'un des 32 signaux distincts. Celles-ci sont envoyées du ohaut au dessus du =bas.

Les montagnes triangulaires de L'et R' font simplement pivoter le motif de rangées distinctes en colonnes. La grille ci-dessous qui traduit chaque colonne en son caractère de sortie. Pour les signaux inconnus, NUL ( \x00) est produit. Pour les décalages spéciaux, au lieu d'imprimer un caractère, la petite goutte à droite change de mode.

La chose semblable à un téléphérique entre les deux montagnes supprime toute impression entre chaque quintette, sinon, cela tenterait de décoder également tous les quintets qui se chevauchent. Essayez de remplacer le !par un espace pour voir par vous-même. (L'exécution en mode verbeux -vpeut également être intéressante ici.)

Je ne sais pas comment réduire cela pour le moment; il est déjà assez dense pour sa taille.

Phlarx
la source
0

GNU sed, 334 + 1 = 335 octets

+1 octet pour le -rdrapeau. Prend entrée sur STDIN.

En examinant les anciens défis, j'ai réalisé que celui-ci serait assez facile avec sed et bon pour la pratique. Je n'ai pas tenté de compression, donc la table de recherche représente plus de la moitié du code.

s|.*|#@&;01000E211000/%00100Y310100U401100I%11100O500010f 10010J601010G711010H%00110B810110C901110F%00001 l10001-.01001X%11001Z:00101S%10101T%01101W?11101V'00011<<10011K(01011M)11011L=00111R-10111Q/01111N%11111P+10000A111110D0|
:
s/@([01]{5})(.*;.*\1)(..)/\3@\2\3/
t
s/@;.*//
s/#f /@/
s/@ l/#/
s/#(.)./\1#/
s/@.(.)/\1@/
t
s/.<|[#@]//g

Essayez-le en ligne!

Explication

Le code fonctionne en deux phases: tout d'abord, il remplace chaque série de 5 chiffres binaires par les deux caractères correspondants (lettre et chiffre) d'une table de recherche. La table de recherche est au format 𝟎𝟎𝟎𝟎𝟎𝐋𝐅𝟎𝟎𝟎𝟎𝟎𝐋𝐅… où 𝟎 est un chiffre binaire et 𝐋 et 𝐅 sont respectivement la lettre et le chiffre correspondants. %remplace les caractères manquants (il peut s'agir de n'importe quel caractère autre que la nouvelle ligne). FS/SPest représenté par f<space>et SP/LSest <space>l. ERest représenté par <<.

Il parcourt ensuite chaque paire avec un "curseur" correspondant au mode actuel - #pour le mode lettre, @pour le mode figure. Le #curseur supprime le deuxième caractère de la paire, puis passe à la paire suivante, et le @supprime le premier et avance. En d'autres termes, #A1B8devient A#B8et alors AB#, et @A1B8devient 1@B8et alors 18@. Lorsque le #curseur rencontre, f<space>il le supprime et se remplace par le @curseur, et vice versa lors des @rencontres <space>l.

Lorsqu'il ne reste aucune paire, le curseur final est supprimé avec tous les caractères suivis de <.

# Setup: Append a lookup table to the line.
# Also prepends "#" and "@" which we'll use as "cursors" later.
s|.*|#@&;01000E211000/%00100Y310100U401100I%11100O500010f 10010J601010G711010H%00110B810110C901110F%00001 l10001-.01001X%11001Z:00101S%10101T%01101W?11101V'00011<<10011K(01011M)11011L=00111R-10111Q/01111N%11111P+10000A111110D0|

# Phase 1
:
  # Using "@" as a "cursor", substitute for each run of 5 binary digits the
  # two corresponding characters from the lookup table.
  s/@([01]{5})(.*;.*\1)(..)/\3@\2\3/
  t   # Loop (branch to `:`) as long as substitutions are made.

s/@;.*//       # Delete the "@" and lookup table

# Phase 2
s/#f /@/       # FS (f ) in letter mode (#); delete and switch to figure mode (@ cursor).
s/@ l/#/       # LS ( l) in figure mode (@); delete and switch to letter mode (# cursor).
s/#(.)./\1#/   # Letter mode; replace pair with first of pair; advance cursor.
s/@.(.)/\1@/   # Figure mode; replace pair with second of pair; advance cursor.
t              # If any substitutions were made, branch (loop) to `:`.

# Teardown
s/.<|[#@]//g   # Delete characters followed by < (ER) and cursor.
Jordan
la source