Coding Challenge ve Štýrském Hradci: Vítězem se stává..
Na Dni Linuxu ve Štýrském Hradci pořádala společnost grommunio vysoce ceněnou výzvu v kódování. Z 23 účastníků jich 9 mohlo prezentovat úspěšné výsledky. Vítěz hlavní ceny, který byl vybrán losem, si nyní vyzvedl svou cenu v kanceláři společnosti grommunio.
Fabian Ortner ze společnosti grommunio předává šťastnému výherci Andreasovi zbrusu novou konzoli Sony PlayStation 5 v hodnotě téměř 700 eur.
Zní to vlastně docela jednoduše, že?
“Pro splnění tohoto úkolu musíte napsat kód v jazyce C/C++ do souboru \src\main.cpp a vyřešit tak kódovací výzvu na konci tohoto souboru Readme. Používá se MinGW64 s gcc/g++ 15.2, který je automaticky nastaven v místním adresáři a lze jej použít pomocí následujících příkazů. ”
To, co může znít mnoha netechnickým lidem nepochopitelně, se programátorům nezdá složité - alespoň na první pohled. Čtyři úlohy, které grommunio zařadil, byly v zásadě jistě řešitelné, a tak se 23 linuxových expertů jednu dubnovou sobotu ve Štýrském Hradci pustilo do řešení.
Programování pod časovým tlakem
Mnoho účastníků se potýkalo s časovým limitem, ve kterém museli najít správné řešení pomocí kódu, který sami napsali. Původní odhad 20 minut se ukázal jako příliš optimistický; i během závěrečných 40 minut, které byly na řešení vyhrazeny, se podařilo najít správné řešení pouze 9 účastníkům.
Výsledkem bylo, že dva speciálně připravené počítače s Windows ve Štýrském Hradci byly v sobotu téměř nepřetržitě obsazeny a na samotnou soutěž bylo vyčleněno více než sedm hodin.
Nastavení kódovací výzvy
zaměstnanci společnosti grommunio vytvořili na počítačích nové uživatelské účty, nastavili VSCode jako editor a automatizovali různé příkazy prostřednictvím skriptů cmd systému Windows, aby urychlili proces kompilace a odeslání.
Účastník, který úspěšně dokončil výzvu pomocí nástrojů poskytnutých společností grommunio.
“Vytvořili jsme malý koncový bod HTTP, který nám v kombinaci s shellovým skriptem na počítačích s výzvou umožnil generovat personalizované vstupy pro každého účastníka na základě jeho e-mailové adresy a poté reagovat zpětnou vazbou na jeho pokusy o vyřešení problému, ” vysvětluje Fabian Ortner ze společnosti grommunio (na obrázku výše). “Soubor Readme pak poskytoval podrobnější popis toho, co je třeba udělat pro programátorskou úlohu, a tak byl vytvořen poměrně jednoduchý, automatizovaný proces, který měl účast co nejvíce usnadnit. ”
Ale to “co nejjednodušší” netrvalo dlouho. V rámci úkolu měli účastníci opravit nefunkční poštovní server napsáním malého konverzního skriptu. V README začíná první ze čtyř úkolů, které je třeba vyřešit:
“Zdá se, že každý řádek obsahuje celočíselný násobek 8 znaků, zkusme je tedy interpretovat jako jednotlivé bajty. Například:
*010001000101000101001010 0x44 0x51 0x4A 010001000101000001001100 => 0x44 0x50 0x4C 010000100101000101001100 0x42 0x51 0x4C *
Víme, že starý poštovní server používal po exportu e-mailu velmi jednoduchou metodu šifrování:
- Vezměte každý řádek textu, tj. každý bajt
- Pro každý řádek proveďte XOR šifrování s klíčem `grommunio`, znak po znaku
- Jestliže je řádek delší než klíč, použijte klíč znovu, počínaje prvním znakem. ”
Následovaly další požadavky a úkoly, které jim pořádně zamotaly hlavu. Jen málo účastníků dokázalo přijít se správným řešením.
Ale i ti, kteří neuspěli, se měli na co těšit: na konci se mezi všemi účastníky náhodně losovalo, kdo získá slíbený PlayStation. Výherce Andreas byl pozván, aby si jej vyzvedl ve 30. patře DC Tower ve Vídni, v sídle společnosti grommunio.
Řešení? Nebude zde zveřejněno, ale soubor README s úplným zadáním problému je k dispozici pod tímto příspěvkem. Bez serveru, který grommunio postavil pro Graz Linux Days, to však bude chtít trochu představivosti..
Více informací o serveru grommunio na Graz Linux Days se dozvíte v tomto článku.
Návod na kódovací výzvu
Tento úkol vyžaduje, abyste napsali kód v jazyce C/C++ uvnitř souboru .\src\main.cpp a vyřešili tak úkol na konci tohoto readme. Používá MinGW64 s gcc/g++ 15.2, který je automaticky nastaven v místním adresáři a lze jej použít pomocí následujících příkazů.
Pro přiložený skript jsou důležité čtyři příkazy:
1. Registrace e-mailové adresy a spuštění 20minutového časovače:
\glt.cmd start`
2. Chcete-li pouze sestavit svůj kód:
.\glt.cmd build
3. Pro sestavení a spuštění kódu a vypsání jeho výstupu do terminálu:
.\glt.cmd build_and_run
4. Sestavení, spuštění a odeslání vašeho řešení::
.\glt.cmd submit
Příkaz použitý k sestavení vašeho řešení nemá ve výchozím nastavení povoleny žádné optimalizace:
g++.exe -static -O0 -g -std=c++17 src\main.cpp -o build/app.exe
Challenge
Chcete-li spustit výzvu, nejprve vložte svou e-mailovou adresu do souboru user.txt a poté použijte příkaz start pro získání vstupních dat. Použijeme ji pouze k tomu, abychom vás mohli kontaktovat v případě, že vyhrajete losování. Stačí, když ve svém kódu změníte proměnnou výsledek a poté spustíte příkaz submit, abyste zkontrolovali, zda je správný.
WOW. Co se stalo s tím e-mailem během migrace? Během nastavení nového poštovního serveru se nějakým způsobem poškodil jeden z vašich e-mailů. Zdá se, že se skládá pouze z binárních symbolů rozdělených do několika řádků (váš vstup). Zdá se, že v každém řádku je celočíselný násobek 8 symbolů, takže je zkusíme interpretovat jako jednotlivé bajty. Například:
010001000101000101001010 0x44 0x51 0x4A 010001000101000001001100 => 0x44 0x50 0x4C 010000100101000101001100 0x42 0x51 0x4C
Víme, že starý poštovní server používal po exportu E-mailu opravdu jednoduché šifrování:
- Vezměte každý řádek textu, tj. každý bajt
- XOR každého řádku s klíčem grommunio podle znaků
- Pokud je řádek delší než klíč, jednoduše znovu použijte klíč počínaje prvním znakem.
0x44 ^ g = 0x23 0x51 ^ r = 0x23 0x4A ^ o = 0x25 0x44 ^ g = 0x23 0x50 ^ r = 0x22 0x4C ^ o = 0x23 0x42 ^ g = 0x25 0x51 ^ r = 0x23 0x4C ^ o = 0x23
To už vypadá nadějněji, ale stále je tam spousta zpackaných znaků..
Už v dřívějších dobách měl starý mailserver problémy s offsetem u jednotlivých hodnot znaků, přičemž offset závisel na dvou věcech:
- horizontálním kontrolním součtem e-mailové adresy
- indexu znaku v řádku a čísla řádku, ve kterém se nachází
V té době server počítal horizontální kontrolní součet tak, že jednoduše sečetl všechny hodnoty bajtů vaší e-mailové adresy.
max.mustermann@grommunio.com => (m=109) + (a=97) + (x=120) + … = 2888
Poté byl pro každý znak vypočten jeho pozitivní offset pomocí kontrolního součtu modulovaného podle jeho pozice v řádku. Abychom tuto chybu opravili, musíme tedy od každého z bajtů odečíst hodnoty offsetu. Tyto offsety jsou pak navíc po každém řádku posunuty doleva o jeden znak.
0x23 - (2888 % 1) = ’#’ 0x23 - (2888 % 2) = ’#’ 0x25 - (2888 % 3) = ’#’ 0x23 - (2888 % 2) = ’#’ 0x22 - (2888 % 3) = ’ ’ 0x25 - (2888 % 1) = ’#’ 0x23 - (2888 % 3) = ’#’ 0x23 - (2888 % 1) = ’#’ 0x25 - (2888 % 2) = ’#’
Nyní to vypadá jako správná zpráva! Abychom se však ujistili, že máme správný algoritmus, musíme vypočítat elementární součin hodnot posunu krát hodnoty znaků každého použitého klíčového znaku a sečíst je pro každý #-znak ve zprávě. (\n a \r by měly být vyřazeny)
(g=103)\*0 + (r=114)\*0 + (o=111)\*2- (g=103)*0 + (o=111)*0
- (g=103)*2 + (r=114)*0 + (o=111)*0 = 428
Tento součet součinů prvků musíte zapsat do výsledné proměnné, abyste dokončili kódovací úkol!
