Dewesoft izziv 🚀

Opis izziva

Kot znanstvenik znane vesoljske agencije si zadolžen za razvoj novega načina prenašanja informaciji po vesolju. Algoritem, ki ga boš razvil mora najprej zakodirati niz byte-ov, ki se bodo poslali na oddaljeno vesoljsko postajo. Med prenosom se bo zaradi kozmičnih žarkov po vseh pričakovanjih nekaj bitov v sporočilu pokvarilo, tako da mora kodirani niz vsebovati mehanizme redundance, da bo lahko na vesoljski postaji sestrski algoritem takšen niz pravilno odkodiral. Kodiranje mora tako delovati robustno, učinkovito ter z mero redundance.

Zahteve

• Izdelaj dva programa, enega za kodiranje niza in drugega, ki bo kodiran niz pretvoril v prvotno obliko.

• Program za kodiranje mora pretvoriti kakršenkoli niz byte-ov v kodiran niz byte-ov.

• Kodiran niz mora biti najmanjši, kot je lahko. Prav tako mora biti redundančno sestavljen.

• Program za dekodiranje naj bo zmožen sprejeti kodiran niz. Kodiran niz je lahko “pokvarjen” (naključni biti so lahko negirani).

• Algoritem naj poskusi popraviti in dekodirati prejeti kodiran niz.

• Oba programa naj svoji rešitvi izpišeta na standarden izhod.

• Algoritem naj deluje hitro, za omogočanje čim hitrejše komunikacije.

Evalvacijski kriterij

• Dolžina kodiranega niza → Manjše je boljše.

• Redundanca sporočila → Več odpravljenih napak med prenosom je boljše.

• Hitrost kodiranja in dekodiranja → Hitrejše je boljše.

Dodeljevanje točk

• Da se podani rešitvi štejejo točke, mora ta najprej pravilno prestati sprejemne teste. To so preprosti primeri kodiranja in dekodiranja, ki ne testirajo redundance.

• Celotna ocena je sestavljena iz seštevkov ocen hitrosti, redundance, ter učinkovitosti. Posamezna ocena lahko prinese največ 1 točko, največja celotna ocena znaša 3 točke.

• Vse posamezne ocene se normirajo glede na najboljšo doseženo oceno vseh oddanih rešitev.

Oddaja

• Svoje rešitve oddaj v poljubnem programskem jeziku.

• Uporaba knjižnic je omejena zgolj na standardne, ki so nameščene skupaj s poljubnim programskim jezikom.

• Poleg oddanih rešitev dodaj tudi kratko razlago, kako delujeta kodiranje in dekodiranje. Označi tudi kateri program je namenjen za kodiranje in kateri za dekodiranje ter kako se ju zažene.

Opis vhoda v program za kodiranje

• N: celo število 1 - 10^6

• Niz N-tih byte-ov

Opis vhoda v program za dekodiranje

• N: celo število

• Niz N-tih byte-ov

Primer poteka izvajanja

$ python3 ./encode < original_data.txt > encoded_data.txt

$ ./corrupt < encoded_data.txt > encoded_corrupted_data.txt

$ python3 ./decode < encoded_corrupted_data.txt > decoded_data.txt

 Primer vhoda in izhoda pri izvajanju

original_data.txt: “5\n abcde”

encoded_data.txt: “xyzw”

encoded_corrupted_data.txt: “4\n x1zw”

decoded_data.txt: “abcde”