Codeerwedstrijd in Graz: En de winnaar is..
Tijdens de Graz Linux Days organiseerde grommunio een veelgeprezen codeerwedstrijd. Van de 23 deelnemers konden er 9 succesvolle resultaten voorleggen. De hoofdprijswinnaar, geselecteerd via loting, heeft zijn prijs inmiddels opgehaald op het kantoor van grommunio.
codeerwedstrijd - winnaar](/img/posts/26-05-15_Coding-Challenge_winner.webp)
Fabian Ortner van grommunio overhandigt een gloednieuwe Sony PlayStation 5 ter waarde van bijna 700 euro aan de gelukkige winnaar Andreas.
Het klinkt eigenlijk best eenvoudig, nietwaar?
“Voor deze opdracht moet je C/C++ code schrijven in het bestand \src\main.cpp om de Coding Challenge aan het einde van dit leesmij-bestand op te lossen. MinGW64 met gcc/g++ 15.2 wordt gebruikt, dat automatisch wordt ingesteld in een lokale map en kan worden gebruikt met de volgende commando’s.”
Wat voor veel niet-technische mensen misschien onbegrijpelijk klinkt, lijkt voor programmeurs niet moeilijk - tenminste niet op het eerste gezicht. In principe waren de vier opdrachten van grommunio zeker op te lossen en dus gingen 23 Linux-experts de uitdaging aan op een zaterdag in april in Graz.
Programmeren onder tijdsdruk
Veel deelnemers worstelden met de tijdslimiet waarbinnen ze de juiste oplossing moesten vinden met behulp van zelfgeschreven code. De aanvankelijke schatting van 20 minuten bleek veel te optimistisch; zelfs binnen de laatste 40 minuten waren slechts 9 deelnemers in staat om de juiste oplossing te vinden.
Als gevolg hiervan waren de twee speciaal geprepareerde Windows-machines in Graz bijna continu bezet op zaterdag, met meer dan zeven uur toegewezen aan de uitdaging zelf.
De opzet van de codeerwedstrijd
grommunio-medewerkers hadden nieuwe gebruikersaccounts aangemaakt op de computers, VSCode ingesteld als editor en verschillende opdrachten geautomatiseerd via Windows cmd-scripts om het compilatie- en indieningsproces te versnellen.
code-uitdaging - code](/img/posts/26-05-15_Coding-Challenge_code.webp)
Een deelnemer die de uitdaging met succes voltooit met de hulpmiddelen van grommunio.
“We hebben een klein HTTP-eindpunt opgezet waarmee we, in combinatie met een shellscript op de computers van de uitdaging, voor elke deelnemer gepersonaliseerde invoer konden genereren op basis van hun e-mailadres en vervolgens konden reageren met feedback over hun pogingen om het probleem op te lossen,” legt Fabian Ortner van grommunio uit (op de foto hierboven). “Een Readme-bestand gaf vervolgens een gedetailleerdere beschrijving van wat er gedaan moest worden voor de programmeertaak, en zo werd een vrij eenvoudig, geautomatiseerd proces gecreëerd om deelname zo gemakkelijk mogelijk te maken.”
Maar dat “zo eenvoudig mogelijk” duurde niet lang. Voor de uitdaging moesten deelnemers een slecht werkende mailserver repareren door een klein conversiescript te schrijven. In de README begint de eerste van vier op te lossen taken met:
“Het lijkt erop dat elke regel een geheel veelvoud van 8 karakters bevat, dus laten we proberen deze te interpreteren als individuele bytes. Bijvoorbeeld:
*010001000101000101001010 0x44 0x51 0x4A 010001000101000001001100 => 0x44 0x50 0x4C 010000100101000101001100 0x42 0x51 0x4C *
We weten dat de oude mailserver een zeer eenvoudige versleutelingsmethode gebruikte na het exporteren van de e-mail:
- Neem elke regel tekst, dus elke byte
- Voor elke regel voert u een XOR-versleuteling uit met de sleutel
grommunio, teken voor teken - Als een regel langer is dan de sleutel, pas dan gewoon de sleutel opnieuw toe*, beginnend bij het eerste teken.”*
Er volgden nog meer eisen en taken die hun hoofd echt op hol brachten. Slechts een paar deelnemers konden de juiste oplossingen bedenken.
Maar zelfs degenen die niet slaagden, hadden iets om naar uit te kijken: uiteindelijk bepaalde een willekeurige trekking onder alle deelnemers wie de beloofde PlayStation zou ontvangen. De winnaar, Andreas, mocht de PlayStation komen ophalen op de 30e verdieping van de DC Tower in Wenen, in het hoofdkantoor van grommunio.
De oplossing? Die wordt hier niet gepost, maar het README-bestand met de volledige probleemstelling is beschikbaar onder dit bericht. Zonder de server die grommunio bouwde voor de Graz Linux Days, zal het echter een beetje verbeelding vergen..
Leer meer over grommunio op de Graz Linux Days in dit artikel.
Codeerwedstrijd Instructies
Deze uitdaging vereist dat je wat C/C++ code schrijft in .rcmain.cpp om de uitdaging aan het einde van deze leesmij op te lossen. Het gebruikt MinGW64 met gcc/g++ 15.2 dat automatisch wordt ingesteld in een lokale map en kan worden gebruikt met de volgende commando’s.
Er zijn vier belangrijke commando’s voor het meegeleverde script:
1. Om je e-mailadres te registreren en de timer van 20 minuten te starten:
.\glt.cmd start
2. Om alleen je code te bouwen:
.\glt.cmd build
3. Om je code te bouwen en uit te voeren en de uitvoer naar de terminal af te drukken:
.\glt.cmd build_and_run
4. Om je oplossing te bouwen, uit te voeren en in te sturen:
.\glt.cmd submit
Het commando dat wordt gebruikt om je oplossing te bouwen heeft standaard geen optimalisaties ingeschakeld:
g++.exe -static -O0 -g -std=c++17 srcmain.cpp -o build/app.exe
Uitdaging
Om de uitdaging te starten moet je eerst je E-Mail adres in het user.txt bestand zetten en dan het start commando gebruiken om je input te krijgen. We gebruiken het alleen om contact met je op te nemen als je de trekking wint. Je hoeft alleen de result variabele in je code te veranderen en dan het submit commando uit te voeren om te controleren of het correct is.
WOW. Wat is er met die e-mail gebeurd tijdens de migratie? Op de een of andere manier is een van je e-mails beschadigd geraakt tijdens de installatie van je nieuwe mailserver. Het lijkt alleen te bestaan uit binaire symbolen opgesplitst in een paar regels (je invoer). Er lijkt een geheel veelvoud van 8 symbolen per regel te zijn, dus laten we proberen ze te interpreteren als individuele bytes. Bijvoorbeeld:
010001000101000101001010 0x44 0x51 0x4A 010001000101000001001100 => 0x44 0x50 0x4C 010000100101000101001100 0x42 0x51 0x4C
We weten dat de oude mailserver een heel eenvoudige versleuteling gebruikte na het exporteren van de e-mail:
- Neem elke regel tekst, d.w.z. elke byte
- XOR elke regel met de sleutel grommunio karaktergewijs
- Als een regel langer is dan de sleutel, hergebruik dan gewoon de sleutel vanaf het eerste teken.
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
Dat ziet er al veelbelovender uit, maar er zijn nog steeds veel verknoeide tekens..
Vroeger had de oude mailserver al problemen met offsets op individuele karakterwaarden, waarbij de offset afhing van twee dingen:
- Een horizontale checksum van je E-Mail adres
- de index van het teken in een regel en het regelnummer waarin het staat
Destijds berekende de server een horizontale controlesom door simpelweg alle bytewaarden van je e-mailadres bij elkaar op te tellen.
max.mustermann@grommunio.com => (m=109) + (a=97) + (x=120) + … = 2888
Vervolgens werd voor elk teken de positieve offset berekend door de checksum modulo de positie in de regel te nemen. Om deze fout te corrigeren moeten we dus de offsetwaarden aftrekken van elk van de bytes. Bovendien worden deze offsets na elke regel één karakter naar links verschoven.
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) = ’#’
Nu lijkt dit een correcte boodschap! Maar om er zeker van te zijn dat we een correct algoritme hebben, moeten we het element-wise product berekenen van de offset-waarden maal de tekenwaarden van elk gebruikt sleutelteken en deze optellen voor elk #-teken in het bericht. (De letters n en r moeten worden weggegooid)
(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
Je moet deze som van elementaire producten naar de resultaatvariabele schrijven om de codeeruitdaging te voltooien!
