HW 05 - Caesarova šifra

Termín odevzdání 15.11.2019 23:59 CET
Povinné zadání 5b
Bonusové zadání není
Počet uploadů 15

Zadání

Naším úkolem je rozluštit zprávu zakódovanou Caesarovou šifrou, která funguje na principu záměny písmene z abecedy za písmeno posunuté o pevně určený počet míst. V našem případě máme k dispozici nejen zašifrovaný text, ale také nespolehlivě odposlechnuté originální znění zprávy, tj. některé znaky originální zprávy jsou chybně zapsány. Řešení tak můžeme založit na testování všech možností kódování Caesarovou šifrou a porovnání s odposlechnutým textem. Posun s největší shodou dekódovaného textu s odposlechnutou zprávu budeme považovat za správný a takto dekódovaný text je náš požadovaný výstup. Obecně nemusí tento postup vést na unikátní správné řešení, nicméně v testovaných případech vždy existuje unikátní řešení.

Tato úloha slouží k procvičení práce s polem pevné délky. Proto je ve vstupním souboru uvedena délka zprávy.
Použitá abeceda se skládá pouze z malých a velkých písmen bez diakritiky, tj. znaky v rozsahu [a-zA-Z].

Vstup

Na standardním vstupu očekávejte číslo, které reprezentuje délku zprávy, a dvě posloupnosti znaků (texty) na samostatných řádcích. První text je zakódovaná zpráva a druhý text je nespolehlivě odposlechnutý text.

  • Pokud na prvním řádku není číslo nebo vstupní text neodpovídá abecedě [a-zA-Z] vypíše program na standardní chybový výstup “Error: Chybny vstup!” a skončí s návratovou hodnotou 100.
  • Pokud je některý ze vstupních textů kratší, než uvádí číslo na prvním řádku souboru, program vypíše na stderrError: Chybna delka vstupu!” a skončí s návratovou hodnotou 101.
  • Chyby jsou vyhodnocovány postupně, v pořadí výskytu (tj. první nalezená chyba ukončuje běh programu s příslušnou chybovou hodnotou). Současný výskyt obou chyb není testován.
  • Informace o chybě vypsaná na standardní chybový výstup není ukončena znakem konce řádku.

Výstup

Na standardní výstup vypište dekódovanou zprávu jako posloupnost znaků zakončenou znakem konce řádku. Program končí s návratovou hodnotou 0.

Implementance

Program vhodně dekomponujte na jednotlivé funkce, např. funkce pro dekódování textu o definovaný posun a výpočet vzdálenosti dvou textových řetězců:

void shift(const char *src, char *dst, int offset);
 
int compare(const char *str1, const char *str2);

Dále může být vhodné napsat funkci pro šifrování jednoho písmene, která bude respektovat zadanou abecedu [a-zA-Z]. Například:

char rotate(char original, int offset);

Příklad 1 - pub01

V prvním příkladu je zašifrován text “Helloworld”. Posun je zde o 42 písmen. (16 míst je mezi 'h' a 'x'; 26 pak mezi malými a velkými písmeny). Zašifrovaný text je tedy “xUbbemehbT”.

Odposlechnutý text může být například “??lloworld”, kde písmena na místě otazníku špatně odposlechneme a dostaneme jiné náhodné písmeno, například “XYlloworld”.

Standardní vstup Očekávaný výstup Očekávaný chybový výstup Návratová hodnota
10
xUbbemehbT
XYlloworld
Helloworld
žádný 0

Příklad vyhodnocení. Největší počet shodných písmen (8/10) má posun o 10, proto jej vyhodnotíme jako správný výsledek.

00: xUbbemehbT ~ XYlloworld > 0 correct letters
01: yVccfnficU ~ XYlloworld > 0 correct letters
02: zWddgogjdV ~ XYlloworld > 1 correct letters
03: AXeehphkeW ~ XYlloworld > 0 correct letters
04: BYffiqilfX ~ XYlloworld > 1 correct letters
05: CZggjrjmgY ~ XYlloworld > 0 correct letters
06: DahhksknhZ ~ XYlloworld > 0 correct letters
07: Ebiiltloia ~ XYlloworld > 1 correct letters
08: Fcjjmumpjb ~ XYlloworld > 0 correct letters
09: Gdkknvnqkc ~ XYlloworld > 0 correct letters
10: Helloworld ~ XYlloworld > 8 correct letters -- result
11: Ifmmpxpsme ~ XYlloworld > 0 correct letters
12: Jgnnqyqtnf ~ XYlloworld > 0 correct letters
...
50: vSZZckcfZR ~ XYlloworld > 0 correct letters
51: wTaadldgaS ~ XYlloworld > 0 correct letters
52: xUbbemehbT ~ XYlloworld > 0 correct letters

Příklad 2 - pub02

Standardní vstup Očekávaný výstup Očekávaný chybový výstup Návratová hodnota
10
mnoXYhnJLJ
JCudvgtXRi
studentPRP
žádný 0

Příklad 3 - pub03

Standardní vstup Očekávaný výstup Očekávaný chybový výstup Návratová hodnota
10
fghQRa-CEC
scbdeMKARZ
žádný
Error: Chybny vstup!
100

Příklad 4 - pub04

Standardní vstup Očekávaný výstup Očekávaný chybový výstup Návratová hodnota
10
fghQRa
scbdeMK
žádný
Error: Chybna delka vstupu!
101

Varianty

Veřejné příklady + Makefile: hw05.zip

Povinné zadání
Název v BRUTE HW05
Odevzdávané soubory main.c
Kompilace pomocí clang -pedantic -Wall -Werror -std=c99
Předpokládaná složitost program by měl být schopen zvládnout zpracovat 100 tisic hodnot do 5 sekund.
Odevzdávací systém má nastaven timeout na 10s.
courses/b0b99prpa/hw/hw05.txt · Last modified: 2019/11/13 15:10 by viteks