Termín odevzdání | 16.11.2019 23:59 PST |
---|---|
Povinné zadání | 3b |
Volitelné zadání | 2b |
Bonusové zadání | Není |
Počet uploadů | 20 |
Podpůrné soubory | b0b36prp-hw05.zip |
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ávou 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í.
Jedním z cílů tohoto domácího úkolu je procvičení dynamické alokace paměti na základě velikosti vstupu. Proto délka vstupního textu není dopředu známa a je nutné v případě vyčerpání počáteční velikosti (např. 10-100 znaků) dynamicky alokovat prostor větší, např. funkcí realloc
() pro dvojnásobnou délku. V programu používejte pouze množství paměti, které řádově odpovídá zadanému vstupu. Odevzdávací systém kontroluje velikost dynamicky alokované paměti.
Použitá abeceda se skládá pouze z malých a velkých písmen bez diakritiky, tj. znaky v rozsahu [a-zA-Z].
getchar()
nebo scanf(“%c”,…)
tak, abyste si vyzkoušeli dynamickou alokaci paměti podle aktuálně potřeby odpovídající načítanému vstupu.
Každný řádek na vstupu je zakončen znakem '\n'. Na testovacím serveru běží OS Debian, takže se jedná o jeden znak LF 0x0a. (Na Windows se používají dva znaky CR+LF.)
Použití metody dynamického načítání textového řetězce prostřednictvím rozšíření scanf(“%ms”) nebo scanf(“%as”) není z tohoto důvodu povoleno.
-optional
.
Na standardním vstupu očekávejte dvě posloupnosti znaků (texty) na samostatných řádcích. První text je zakódovaná zpráva a druhý text je nespolehlivě odposlechnutý text.
Error: Chybny vstup!
” a skončí s návratovou hodnotou 100
.
stderr
“Error: Chybna delka vstupu!
” a skončí s návratovou hodnotou 101
.
100
a 101
současně, program vypíše pouze chybovou hlášku “Error: Chybny vstup!
” a skončí s návratovou hodnotou 100
.
-prp-optional
”, mohou být délky vstupních textů různé a program tak chybou nekončí.
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
.
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);
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 |
---|---|---|---|
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
Standardní vstup | Očekávaný výstup | Očekávaný chybový výstup | Návratová hodnota |
---|---|---|---|
mnoXYhnJLJ JCudvgtXRi | studentPRP | žádný | 0 |
Standardní vstup | Očekávaný výstup | Očekávaný chybový výstup | Návratová hodnota |
---|---|---|---|
fghQRa-CEC scbdeMKARZ | žádný | Error: Chybny vstup! | 100 |
Standardní vstup | Očekávaný výstup | Očekávaný chybový výstup | Návratová hodnota |
---|---|---|---|
fghQRa scbdeMK | žádný | Error: Chybna delka vstupu! | 101 |
for(int i = 0; i < strlen(text); i++) { ... }
U volitelné části úlohu rozšiřujeme o možnost úplné ztráty písmene nebo naopak odposlechnutí písmene, které nebylo vůbec vysláno. Vstupní texty tak mohou mít různou délku. V tomto případě věrohodný text určíme na základě Levenštejnovy vzdálenosti vypočtené pomocí Wagner-Fisher algoritmu. Program je ve volitelné části spuštěn s argumentem '-prp-optional'. Vstup pro volitolné zadání může obsahovat dva texty různé délky, a proto při spuštění s argumentem “-prp-optional
” nevypisujeme chybu 101
. Použití Levenštejnovy vzdálenosti by fungovalo i pro povinné zadání, ale bylo by výrazně pomalejší, používalo více paměti a odevzdávací systém by ho neakceptoval. Používejte proto prosím Levenštejnovu vzdálenost výhradně pro testovací vstupy z volitelného zadání. Používejte dynamickou alokaci paměti.
Standardní vstup | Očekávaný výstup | Očekávaný chybový výstup | Návratová hodnota |
---|---|---|---|
xUbbemehbT Hellwooorld | Helloworld | žádný | 0 |
Příklad vzdálenostní matice při výpočtu vzdálenosti pomocí Wagner-Fisher algoritmu. Matice je vyplňována postupně po řádcích s využitím předchozích hodnot (dynamické programování).
- | H | e | l | l | o | w | o | o | r | l | d | |
---|---|---|---|---|---|---|---|---|---|---|---|---|
- | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
H | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
e | 2 | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
l | 3 | 2 | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
l | 4 | 3 | 2 | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
o | 5 | 4 | 3 | 2 | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
w | 6 | 5 | 4 | 3 | 2 | 1 | 0 | 1 | 2 | 3 | 4 | 5 |
o | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | 1 | 2 | 3 | 4 |
r | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 1 | 1 | 2 | 3 |
l | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 2 | 2 | 1 | 2 |
d | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 3 | 3 | 2 | 1 |
Levenštejnova vzdálenost je zde rovna jedné, protože stačí pouze jedna operace odebrání písmena.
Veřejné příklady + Makefile: b0b36prp-hw05.zip
Povinné zadání | Volitelné zadání | |
---|---|---|
Název v BRUTE | HW05 | |
Odevzdávané soubory | main.c | |
Argumenty při spuštění | žádné | -prp-optional |
Kompilace pomocí | clang -pedantic -Wall -Werror -std=c99 | |
Očekávaná časová složitost 1) | $\mathcal{O}(n)$ | $\mathcal{O}(n^2)$ |
Očekávaná paměťová složitost | $\mathcal{O}(n)$ | $\mathcal{O}(n^2)$ |
Paměťový limit (stack) [b] | 50 000 | 50 000 |
Paměťový limit (heap) [b] 2) | INPUT * 20 + 20000 | INPUT$^2$ * 10 + 10000 |
Procvičované oblasti | práce s textem, ASCII tabulka, dynamická alokace paměti podle velikosti vstupu | dynamické programování Levenštajnova vzdálenost |