2. uždavinukai Codeforces, OpenCup, kt.
3. Codeforces 7 dienų užduotis: plagijatai.
1. Pastarąjį mėnesį retsykiais paskaitau apie LaTeX'ą, jo elementariuosius pagrindus. Reikėtų jo pagalba susivesti praktikoje rašomą tekstą ir programų kodų iškarpas bei MySQL užklausas į gražų pdf'ą. Tam, matyt, teks panaudoti listings packetą. Neseniai tik pasimėginau rašyti elementaria formules ir matematinius ženklus (patiko ši sunaršyta praktikavimosi svetainė - http://www.codecogs.com/latex/eqneditor.php ). Bet sunkiai įauga tas LaTeX pažinimas.
2. Codeforces platformoje paskutinįsyk sudalyvavau balandžio paskutinę dieną, tačiau tik valandą laiko iš dviejų. Sudalyvavimas buvo nesėkmingas. Nes nutraukiau savo hackinimų seriją - paskutiniai bent 5 raundai buvo tokie, kad hackinimo taškų surinkdavau teigiamą kiekį. Apmaudu tai, kad antrojoje užduotyje nesugalvojau testo, kuriam neatspari netgi mano programa. O su šiuo testu būtų kritusios >3/4 kambario programų.
OpenCup'e pastaruoju metu sėkėsi kiek prasčiau negu vidutiniškai. Kartais, nedalyvavęs realiu laiku, pažiūrėdavau užduotis po turnyro. Turnyro pavasario semestras pasibaigė.
Retsykiais užeinu į anarchy golfą, arba Project Euler. Užvakar ir vakar žiūrėjau užduočių sprendimo meistro Mimino dalį youtube web-transliacijos, kaip jis doroja Project Euler uždavinukus.
Neseniai teko pasiskaityti C++ macros'ų pagrindų. Tai šiandien pamėginau pasirašyt kelias programėlias su macros'ais.
3. Prieš porą savaičių Codeforces paskelbė 7 dienų trukmės užduotį, kurios esmė yra tokia: duoti N folderių, turinčių savyje kiekvienas iki 100 failų, kuriuose yra varžybų dalyvių užduočių sprendimai ir plagijatai, tada reikia parašyti programą, kuri tuos plagijatus suranda, ir išvesti sugrupuotą jų sąrašą. 90% failų - .cpp, likę: .py, .java, .pas, .cs, .c ir kt.
Ties šia užduotim praleidau daug laiko, nes patiko. Pasibaigus užduočiai, surinkau neitin daug taškų. Ją sprendžiau Perl'u. Pirmiausia tai teko pirmą kart pasinaudoti elementariom funkcijom glob ir chdir , tam kad lokaliai nusikeltus failus programa apeitų per visas direktorijas. Norėdamas sulyginti failus (o lyginau poromis), pasirašiau subrutiną, kuri per berods O(max(length(n),length(m))) atsako, ar trumpesnysis failas yra ilgesniojo substring'as (nebūtinai jungusis). Ši subrutina kažkiek plagijatų surasdavo. Dar apsirašiau įvairių kalbų komentarų tryniklius: tiek eilutinių komentarų, tiek blokinių. Ir šiukšlių tryniklius (pvz. dviejų+ iš eilės kabliataškių vertimą į vieną). Tada galvojau, kaip kuo labiau suvienodinti kodus pagal prasmę: 1) subrutina, keičianti eksponentinę skaičiaus išraišką į įprastą, 2) jei pliusas stovi tarp lygybės ženklo ir skaičiaus, tada jį ištrina, 3) parašiau ale konstantų preprocesorių C++ kalbai: programa skaito [#define žodis kita] ir kode keičia visus aptiktus [žodis] į [kita], 4) vėliau parašiau ir "typedef"ui ale preprocesorių, 5) patiko aprašyti subrutiną, kuris Pythono sintaksę (iš off-side rule) konvertuoja į figūrinių skliaustelių ir kabliataškių sintaksę, 6) pasirašiau reguliariųjų išraiškų a) viena trina tarpo simbolius, b) antra keičia visus žodžius išskyrus skaičius į vieną raidę arba į nieką.
Suvienodinus šiais įrankiais kodus, reikėdavo juos palyginti pagal panašumą. Tam apsirašiau dar įvairių subrutinų: 2) paskaičiuoja kiek kokių simbolių kode, ir lygina simbolių kiekių panašumą, 3) paskaičiuoja kiek kokių fragmentų kode yra (pvz. fragmentais sukapojama pagal žodžios ribos vietas (Perl'e - \b)), lygina jų skaitlinį panašumą, 3) sukapoja vieną kodą fragmentais, ir skaičiuoja kiek jų aptinkama antrame kode, 4) paima kelis pirmojo kodo fragmentėlius iš įvairių vietų, sujungia į regex'ą pavidalu [fragmentų masyvas].join'.*' , ir atlieka paiešką antrame kode, 5) eina per pirmą kodą, ima jo gabalėlį ir ieško ar toks gabaliukas yra antrame, ir jeigu suranda, tada pašalina abudu gabaliukus iš abiejų kodų, ir taip toliau, beto - mažinant gabalėlio plotį; jeigu galiausiai vienas iš kodų tampa gana trumpas, subrutina spėja, kad tai plagijatas.
Rimtesni dalyviai be preprocesingo, darė ir kodo parsinimą, ir ieškojo Levenšteino atstumo ir kt., kas pačiam yra (per) sudėtinga.
Įrašo apačioje keli kodo fragmentai:
