Telegraphy Golf: dekodowanie kodu Baudot

31

tło

W 1870 r. Émile Baudot wynalazł kod Baudota , kodowanie znaków o stałej długości dla telegrafii. Zaprojektował kod, który należy wprowadzać z klawiatury ręcznej za pomocą zaledwie pięciu klawiszy; dwa obsługiwane lewą ręką, a trzy prawą:

5-klawiszowa klawiatura Baudot

Prawy palec wskazujący, środkowy i serdeczny obsługują odpowiednio klawisze I , II i III , a lewy palec wskazujący i środkowy obsługują IV i . (Odtąd będę używać ich cyfr zachodnioafrykańskich, tj. Od 1 do 5. ) Znaki są wprowadzane jako akordy. Aby wprowadzić na przykład literę „C”, operator naciska 1 , 3 i 4klawisze jednocześnie, po czym obracające się ramię szczotki odczytuje kolejno każdy klawisz i przekazuje prąd lub, w przypadku klawiszy nie wciśniętych, brak prądu. Rezultatem jest, we współczesnych terminach, 5-bitowe kodowanie binarne jako najmniej znaczące jako pierwsze, w którym nasz przykład „C” jest zakodowany jako 10110.

5 bitów?

Być może myślisz, że 5 bitów, które mogą wyrazić co najwyżej 32 unikalne symbole, nie wystarczy nawet dla wszystkich angielskich liter i cyfr, nie mówiąc już o interpunkcji. Baudot miał jednak sztuczkę: jego zestaw znaków to tak naprawdę dwa odrębne zestawy: litery i cyfry , i zdefiniował dwa specjalne kody, aby przełączać się między nimi. Przesunięcie liter , które przełącza się w tryb liter, jest aktywowane przez naciśnięcie samego klawisza 5 ( 00001), a przesuwanie rysunków jest aktywowane za pomocą klawisza 4 ( 00010).

Wyzwanie

Twoim wyzwaniem jest napisanie programu lub funkcji, która dekoduje transmisje kodu Baudot.

Prawdziwa transmisja zaczynałaby się od niektórych bitów inicjalizacyjnych oraz bitów startu i stopu przed i po każdej postaci, ale pomijamy je i martwimy się tylko o 5 unikatowych bitów dla każdej postaci. Formaty wejściowe i wyjściowe omówiono poniżej.

Kod Baudota

Istnieją dwie różne wersje kodu Baudot: kontynentalny i brytyjski. Użyjemy wersji brytyjskiej, która nie zawiera znaków takich jak „É” z francuskiego języka Baudot. Pominiemy również wszystkie symbole w wersji brytyjskiej, które nie należą do drukowanych znaków ASCII. Będziesz musiał jedynie zdekodować znaki z poniższej tabeli, z których wszystkie są drukowalnymi znakami ASCII, z wyjątkiem trzech ostatnich znaków kontrolnych, które są wyjaśnione poniżej tabeli.

Kolumna „Ltr” pokazuje znaki w trybie Letter, a „Fig” pokazuje znaki w trybie 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

Ostatnie trzy wiersze w prawej kolumnie to znaki kontrolne:

  • ERto Kasowanie . Maszyny telegraficzne Baudota wydrukowałyby gwiazdkowy symbol dla tej postaci, aby powiedzieć czytelnikowi, że poprzedni znak powinien zostać zignorowany, ale będziemy jeszcze przyjemniejsi dla czytelnika i faktycznie pominiemy (nie drukujemy) poprzedniego znaku . Działa tak samo w trybie literowym i cyfrowym.

  • FSjest Przesunięcie Figury . To przełącza zestaw znaków z liter na cyfry. Jeśli dekoder jest już w trybie cyfrowym, FS jest traktowany jako spacja (ergo SPw kolumnie „Ltr”). Gdy dekoder znajduje się w trybie cyfrowym, pozostaje w trybie cyfrowym do momentu otrzymania znaku LS.

  • LSto Przesunięcie liter . Przełącza zestaw znaków z cyfr na litery. Jeśli dekoder jest już w trybie Letter, LS jest traktowany jako spacja . W trybie Letter dekoder pozostaje w trybie Letter, dopóki nie zostanie odebrany znak FS.

Dekoder zawsze uruchamia się w trybie Letter.

Oto przykład z przesunięciem cyfr, przesunięciem liter i spacją:

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

To daje komunikat MAY 15TH. Jak widać, pierwszy 00001znak (Shift / Spacja) działa jak spacja, ponieważ dekoder jest już w trybie Letter. Następny znak 00010(Przesunięcie figury / spacja) przełącza dekoder w tryb rysowania, aby wydrukować 15. Następnie 00001pojawia się ponownie, ale tym razem działa jak Przesunięcie litery, aby ponownie ustawić dekoder w trybie Letter.

Dla Twojej wygody, oto znaki w formacie, który być może łatwiej jest przetrawić w edytorze, posortowane według kodu:

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

Wkład

Dane wejściowe będą ciągiem, tablicą lub listą bitów w kolejności od najmniej znaczącego bitu do pierwszej. Każda postać będzie reprezentowana przez kwintet 5 bitów. Bity mogą być w dowolnym rozsądnym formacie, np. Ciąg binarny, tablica 0s i 1s, ciąg "0"i "1" znaków, pojedyncza bardzo duża liczba itp., Pod warunkiem, że mapuje bezpośrednio na bity transmisji.

Każda transmisja będzie miała co najmniej jeden kwintet do wydruku i co najwyżej 255 kwintetów (do wydruku lub w inny sposób), tj. 5–1 275 bitów włącznie.

Dane wejściowe mogą zawierać tylko bity transmisji, z dwoma dopuszczalnymi wyjątkami: Dowolna liczba 0bitów wiodących lub końcowych i / lub, w przypadku danych wejściowych, do transmisji może zostać dodany pojedynczy znak nowej linii. Wiodących lub końcowych bitów lub znaków nie można dodawać przed każdym kwintetem ani po nim, tzn. Nie można uzupełnić każdego kwintetu do 8 bitów (lub wziąć każdy kwintet jako pojedynczą liczbę w tablicy - chyba że w Twoim języku jest 5-bitowa liczba całkowita) lub osobno kwintety z dowolnymi dodatkowymi bitami, np "01111\n11100".

Notatki i etui na brzeg

  1. Transmisja będzie zawierać tylko znaki w kolumnach „Ltr” i „Fig” w powyższej tabeli. Nigdy nie otrzymasz np. 01110W trybie rysowania, ponieważ nie ma go w kolumnie „Rys.”.

  2. Zakłada się, że dekoder zawsze będzie w trybie Letter na początku transmisji. Jednak pierwszym znakiem może być znak FS, który natychmiast przełącza się w tryb figurki.

  3. Gdy dekoder jest w trybie Letter, może otrzymać znak LS, a gdy jest w trybie Figure, może otrzymać znak FS. W obu przypadkach należy wydrukować znak spacji (patrz Wyjście).

  4. Postać ER nigdy nie będzie pierwszą postacią w transmisji, ani nie będzie natychmiast następować po LS, FS lub innym ER.

  5. Postać FS może natychmiast następować po znaku LS i odwrotnie.

  6. Ani znak LS, ani FS nie będzie ostatnim znakiem w żadnej transmisji.

  7. /I -postacie mogą być otrzymane zarówno w trybie tekstowym (kody 11000i 10001, odpowiednio) lub w trybie rysunku ( 10111 a 00111).

Wydajność

Dane wyjściowe mogą mieć dowolny rozsądny format, przy czym najbardziej rozsądnym jest ASCII (lub UTF-8, dla którego wszystkie reprezentowane znaki są takie same jak ASCII). Proszę wskazać w swojej odpowiedzi, czy dane wyjściowe są w innym kodowaniu lub formacie.

Notatki

  • Znak spacji (patrz 3. powyżej) powinien być spacją ASCII (0x20) lub ekwiwalentem twojego kodowania, tzn. Tym, co otrzymasz po naciśnięciu spacji.

Zwycięski

To jest . Najkrótszy kod w bajtach wygrywa.

Ograniczenia

  • Standardowe luki są zabronione.

  • Dozwolone są końcowe spacje i / lub pojedyncza nowa linia. Wiodące spacje lub inne postacie (które nie są częścią transmisji) są niedozwolone.

  • Nie możesz używać żadnych wbudowanych funkcji bibliotecznych, które dekodują kod Baudot (lub któregokolwiek z jego potomków, np. Kod Murraya, ITA-1 itp.).

Przypadki testowe

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):     -/=/-
Jordania
źródło
1
Uwaga: ręcznie zakodowałem przypadki testowe; jeśli zobaczysz coś, co wygląda źle, proszę głośno.
Jordan
1
W tabeli kodów i towarzyszącym skrócie kod 00010jest wymieniony tak jak SPw trybie literowym i FStrybie cyfrowym. Zgodnie z opisem, jeśli jesteśmy w trybie literowym i otrzymujemy kod 00010, powinniśmy przejść do trybu liczbowego, ale wartości w tabeli wydają się być odwrotnie. I odwrotnie dla 00001.
Sok
3
Ten człowiek był cholernie bystry, nigdy nie wiedziałem o kompresji stosowanej w telegrafii. Dzięki za lekcję historii, stary.
Magic Octopus Urn
4
@carusocomputing Right ?? Baudot nie miał formalnego wykształcenia poza szkołą podstawową, ale nie tylko wynalazł kod Baudot, ale także wynalazł system multipleksowania, który umożliwił czterech operatorom jednoczesne korzystanie z jednej linii telegraficznej. Znalazłem tę broszurę z 1919 r., Która
Jordan

Odpowiedzi:

6

Pyth, 98 97 95 93 90 83 80 bajtów

Kod zawiera znaki niedrukowalne, więc oto odwracalny xxdzrzut heksowy:

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

Wypróbuj online. Zestaw testowy.

Dość długi, ale tabela odnośników zajmuje większość miejsca.

Dla 117 bajtów jest to ta sama rzecz bez drukowalnych (wymaga jednak 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

Lub, dla 93 bajtów, bez kompresji w tabeli odnośników:

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

JavaScript (ES6), 160 158 153 bajtów

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
źródło
5

Partia, 306 304 bajtów

@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%

Pobiera dane wejściowe na STDIN. Ponieważ Batch nie ma konwersji binarnej, muszę go sfałszować za pomocą konwersji ósemkowej i szesnastkowej.

  • Pierwsze dwie cyfry są konwertowane z ósemkowej (nie mogę użyć dziesiętnej, ponieważ pierwsza cyfra może być 0). Możliwe są następujące wartości 00, 01, 10i 11. Te dwie ostatnie mają wartość 8i 9ale chcę 2albo 3więc biorę modulo pozostałą 6.
  • Ostatnie trzy cyfry są konwertowane z wartości szesnastkowych. Cyfry są albo 14czy 252czasy ich pożądanej wartości, aby zabrać modulo pozostałą 14( 252=14*18).
  • c jest zakodowanym łańcuchem
  • r jest jak dotąd wynikiem
  • d jest tablicą dekodującą
  • s jest indeksem (uwzględniającym stan przesunięcia) znaku, który przełącza stan przesunięcia
  • njest dekodowaniem binarnym plus bit 5 s, który albo jest równy stanowi przesunięcia, w którym to przypadku stan przesunięcia jest przełączany, albo indeksuje się do tablicy dekodującej, aby znaleźć następny znak (lub! aby usunąć)
Neil
źródło
3

PHP, 206 bajtów

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
źródło
2

Chip , 1069 bajtów

Wielkie, ale fajnie było pisać.

Pobiera dane wejściowe jako ciąg "1"„s "0"” i „s”. (Chociaż tak naprawdę wygląda tylko na niski bit.)

 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

Wypróbuj online!

Uwaga: Erasure używa znaku cofnięcia ASCII ( \x08), co oznacza, że ​​będą wyglądać śmiesznie w TIO, ale dobrze wyglądają, powiedzmy, w xterm.

Podstawowa struktura

Na górze, powyżej =linii, znajduje się dekoder wejściowy. Przekształca sygnał wejściowy w jeden z 32 oddzielnych sygnałów. Są one wysyłane z opowyższych powyżej =do poniższych.

Trójkątne góry Li Rtylko obracają wzór z oddzielnych rzędów do kolumn. Poniższa siatka tłumaczy każdą kolumnę na znak wyjściowy. Dla nieznanych sygnałów \x00generowana jest NUL ( ). W przypadku specjalnych przesunięć zamiast drukowania znaku mała kropelka po prawej stronie zmienia tryb.

Podobne do wagonika między dwoma górami tłumi wszelkie nadruki między każdym kwintetem, w przeciwnym razie próbowałoby to również dekodować wszystkie nakładające się kwintety. Spróbuj zamienić na !spację, aby zobaczyć to na własne oczy. (Uruchomienie w trybie pełnym -vmoże również być tutaj interesujące).

W tej chwili nie jestem pewien, jak to zmniejszyć; jest już dość gęsty jak na swój rozmiar.

Phlarx
źródło
0

GNU sed, 334 + 1 = 335 bajtów

+1 bajt dla -rflagi. Pobiera dane wejściowe na STDIN.

Patrząc na stare wyzwania, zdałem sobie sprawę, że z sedem będzie to całkiem łatwe i dobre do ćwiczeń. Nie próbowałem żadnej kompresji, więc tabela odnośników zawiera ponad połowę kodu.

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

Wypróbuj online!

Wyjaśnienie

Kod działa w dwóch fazach: po pierwsze, zastępuje każdy ciąg 5 cyfr binarnych odpowiednimi dwoma znakami (literą i cyfrą) z tabeli odnośników. Tabela przeglądowa ma format 𝟎𝟎𝟎𝟎𝟎𝐋𝐅𝟎𝟎𝟎𝟎𝟎𝐋𝐅… gdzie 𝟎 jest cyfrą binarną, a 𝐋 i 𝐅 są odpowiednio literą i cyfrą. %oznacza brakujące znaki (może to być dowolny znak inny niż nowa linia). FS/SPjest reprezentowany przez f<space>i SP/LSjest <space>l. ERjest reprezentowany przez <<.

Następnie przechodzi przez każdą parę za pomocą „kursora” odpowiadającego bieżącemu #trybowi - w trybie literowym, @w trybie cyfrowym. #Kursor usuwa drugą postać pary, a następnie przejście do następnej pary i @usuwanie pierwszego i postęp. Innymi słowy, #A1B8staje się A#B8i wtedy AB#, i @A1B8staje się 1@B8i wtedy 18@. Kiedy #kursor napotka f<space>, usuwa go i zastępuje się @kursorem, i na odwrót, gdy @napotyka <space>l.

Gdy nie ma już par, ostatni kursor jest usuwany wraz ze znakami, po których następuje <.

# 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.
Jordania
źródło