2015 vasaros apžvalga

1. Skaitiniai
2. uždavinukai Codeforces, Codeeval
3. Gramatikos "konvertavimas" į regex

Liepos pradžioje teko toliau pasiskaitinėti ko nors apie Perl'ą, ir tai buvo keli skyriai iš knygos: "Perl Best Practices" (Damian Conway), koks vienas skyrius iš "Intermediate Perl", ir pradžia knygos "Higher Order Perl" (M.J.Dominus).

"Perl Best Practices" knygos pradžioje rašo apie kodo parašymo stilių jo skaitomumą. Vėliau apžvelgia įvairias užduotis, su kuriomis susiduriama, ir pasiūlo jiems sprendimą ir parekomenduoja modulių, kuriuos geriausia naudoti. Tad knygos pirmoji pusė - patiko.

Patiko "Higher Order Perl" pradžia. Joje siūlomi standartinių uždavinių sprendimas naudojant rekursiją. O taip pat palaipsniui rekomenduojama išabsrahuoti programą, t.y. padaryti jį kuo labiau "generic".

Taip pat atradau asmeninį M.J.Dominus puslapį, ir iš ten tokį pdf'ą su skaidrėmis apie reguliariųjų išraiškų veikimą. Labai geras pdf'as, gerai aiškinantis veikimo mechanizmą ir backtrackingą. Rekomenduoju.

Neseniai viena programa, kurioje naudojau regex, nustojo teisingai veikti, paleidus ją ant naujesnės Perl versijos (5.20, vietoj 5.18). Paklausinėjus Perl'o išminčių forume, jie išsiaiškino, kad tai bug'as. Jį įkėlė į bugų lentyną. Bug'as tame, kad atsirado klaidingas warningo pranešimas ir pradėjo teisingai nebeveikti konstrukcija "{n}+", kitaip tariant - kvantifikatorius su pliusiuku ( pliusiukas reiškia, kad kvanfitikatorius tampa "possessive", t.y. nebebacktrackinantis). Naujesnėje versijoje, matyt, klaidingai buvo nuspręsta, kad toks užrašas neturi prasmės, kada "n" yra konkretus skaičius. Tačiau iš tiesų jis prasmę turi, pvz. tada, kada kvantifikuojamas dalykas pats turi intervalinį kvantifikatorių, pvz. "(a+){n}+".


2. Prisiregistravau į Codeeval puslapį (parekomendavo draugas), tenai radau tris kategorijas uždavinukų: lengvi, vidutiniai, sunkesni. Pasprendžiau lengvesniųjų. Kiekvienam užtrukdamas 6-30 minucių, išsprendžiau 60. Kelių lengvų neišsprendžiau. Daugumą stengiausi spręsti "funkciškais makaronais", t.y. naudojant map, split, join, grep, eval...

Pvz. uždavinuko 'working experience' sprendimas:

(screenshot'as ideones, nes nano ir gedit pasimeta sintaksės spalvinime)

Codeforces rengiamuose kontestuose nelabai sekėsi. Kai kuriuos uždavinius netgi buvau neteisingai išsprendęs. Didesnė dalis tokių klaidų įvyko dėl to, kad iki galo neįsiskaitydavau į sąlygas, ir implementuodavau ne viską, ko prašydavo. Dėl to būdavo sunku patikėti, kai pamatydavau, kad sprendimas "krito". Kitų dalyvių programas irgi nesisekė laužti. Arba nesugalvodavau surasti silpnųjų vietų, arba pradėdavau spręsti ne tą uždavinį, kuriame dauguma klysta, ir kiti kambario "hakeriai" sumedžiodavo klaidingus sprendimus. Visus uždavinius sprendžiu Perlu. Na, bet stengiuosi "elegantiškiau", jeigu tik išeina.

3. Visai neseniai teko skaityti failą, kuriame buvo aprašyta gramatika EBNF forma. Galiausiai šia gramatika buvo aprašytas tam tikros struktūros pranešimas. T.y. turint pranešimą, galima patikrinti, ar jis gramatiškai teisingas (atitinka konkrečią gramatiką). Atsirado mintis, kad galima patikrinti, ar pranešimas atitinka gramatiką, sukonstravus reguliariąją išraišką. Ilgesnį laiką pažiūrėjus į gramatiką, kuri sudaryta iš >15 taisyklių (vienos pvz.: zodis = raide, {raide | pabraukimas}), atėjo dar kita mintis: pamėginti parašyti programą (parserį?), kuri skaitytų gramatikos failą, ir iš jo dalių surinktų reguliariąją išraišką. Tuomet pasikeitus gramatikai ir praleidus šią programą, reguliari išraiška atsinaujintų programiškai, o ne rankomis.

Ant šios užduoties pakibau kelias dienas. Ir susidūriau su tokia vieta, kaip kad sakinys (taisyklė): kabute = '"' | "'". Ir supratau, kad negaliu  pamodifikavęs šią taisyklę, perduoti jos kintamajame į kažkur, kur ji būtų interpoliuojama, nes jeigu stringo, į kurį interpoliuoju taisyklę, delimiteriai yra viena iš kabučių rūšis, tai įvyks sintaksės klaida. O jeigu naudosiu kitokius Perlo delimiterius su operatoriais q ar qq, tai susidursiu su bėda, apdorodamas kitas taisykles, kuriose aprašyti simboliai, tapatūs šiems delimiteriams.

Dar ilgą laiką negalėjau išspręsti vieno warningo ir loginės klaidos, tai - naudojant \Q...\E metacharacter escape sequence, jie nesiinterpoliavo, kaip tikėjausi. O interpoliavosi tiesiog kaip didžiosios raidės. Kada atsisakiau \Q...\E ir pakeičiau į quotemeta, situacija pagerėjo, ir generuojamas regex'as pasidarė gerokai trumpesnis.

Iš tiesų gavosi "žaidybinis" reguliariosios išraiškos generavimas, kur ji generuojama atsižvelgiant į šios gramatikos taisyklių rinkinį, o ne į bet kokią EBNF gramatiką apskritai. Ir dar "žaidybinė" ji todėl, kad iš gramatikos failo, konstruojant regex'ą, išmetami pradžioje komentarai, po to įterpiamos atominės grupės su kvantifikatoriais vietoje EBNF konstrukcijų ( [], {} ), tik po to escapinami metacharacter'iai, ir tik galiausiai apdorojamos specialios išraiškos ? ... ? . O visa, tai, ką išvardinau, neatitinka operatorių veikimo (ir parsinimo) eiliškumo pagal EBNF taisykles. Taigi, programa, kuri generuoja reguliariąją išraišką galbūt ir atitiks aprašytąją gramatiką, tačiau kažkiek gramatiką pakeitus, jau ir nebeatitiks. T.y. programa yra pritempta.
Priedo uždėjau apsiribojimus:
* kad programa apdoroja tik tokią gramatiką, kurioje tarp kabučių yra įrašyti tik po 1 simbolį.
* kad gramatikoje kiekviena taisyklė gali būti aprašyta tik po jos sekančiomis taisyklėmis.

Struktūra tokia:
ebnf - [Skaito gramatikos failą ir ją "parsina", rezultatas į -> generated];
generated - [Gramatikos taisyklės regex kalba, Perl kodu; +generuoja out-re regex'ą];
out-re - [Sugeneruota (su interpoliacija) regex, atitinkanti dominančią taisyklę (konkrečiai - pranešimo taisyklę)];
test - [Perskaito out-re regex'ą ir skaitydama testinius failus (su pranešimais), atsako, ar jie atitinka gramatiką]

Pvz. ebnf:
1) iškerpa gramatiką
2) iškerpa komentarus (aišku gautųsi bugas, jeigu komentaras tarp kabučių, o visgi kabutės yra auktesnio eiliškumo)
 $input =~ s/ \(\* .*? \*\) //gxms;
3) suskaldo į atskirus sakinius-taisykles (skelia per kabliataškį, kuris nėra tarp kabučių)
 my @rules = reverse split /; (?!['"])/x, $input;
4) taisyklėse įkeliami '$' prieš kiekvieną žodį (\w+), šalia kurio nėra skliaustelio, nėra jis \p{} išraišks dalis, ar escapintas metachar'as.
 s/(?<!['"]) (?<!\\) (?<!\\p{) (\b\w+\b) (?!['"])/'$'.$1/xegms;
5, 6) [] ir {}, kurie gali būti nestinti, O(N**2) lėtumu keičiami į atitinkamus kvantifikatorius su possesyvumu, kadangi EBNF nebacktrakina.
 1 while s/ (?<!['"]) \[ (?!\^) ( [^\[\]]* ) \] (?!['"]) /"(?:" . $1 . ")?+"/xegms;
7, 8) escapinami skyrybos ženklai nuo specialaus veikimo
 s/'([^'])'/quotemeta "$1"/xegms;
9) ...dar kreivas žaidimas su klaustukais ? ... ?, ir dar kart "quotemeta" ant dešiniosios  regex'o pusės, ir taisyklę paverčiant į sakinį pavidalu: "my \$1 = {čia quotemet'intas regex'as tik be escap'intų dolerių ir atominėje grupėje};"

2015 balandis

1. LaTeX
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:

Grafai (Dijkstra)

Šiandien atsiverčiau sąsiuvinį ir mėginau iš atminties prisiminti Dijkstra algoritmą. Pasipaišiau vieną jungųjį grafą su keliais ciklais, be pasikartojančių briaunų ir briaunų, jungiančių tą pačią viršūnę. Nuskaitomas grafas kaip eilučių iš trijų duomenų laukų rinkinys: [viršūnė], [viršūnė], [briaunos svoris (kaina)]. Pradžioj iki galo nesupratau, kaip turėtų elgtis algoritmas ir ėmiau rašyti kažką panašaus į paiešką į plotį (bfs). Vėliau pamačiau, kad, reikia pirmenybę skirti mažiausią kainą turinčiai viršūnei, kuri gali būti paėjusi nuo pradinės viršūnės tolėliau, tai tą ilgokai rašiausi.
Apskritai Dijkstros algoritmas yra algoritmas, kurio rezultatas tai yra pigiausi (nebūtinai trumpiausi) keliai tarp vienos pasirinktos grafo viršūnės ir visų kitų viršūnių. Jis pradeda veikti nuo pasirinktos viršūnės ir plečiasi briaunomis link kitų viršūnių ir jose saugo einamąjį minimalųjį svorį (kainą), o plėtimosi frontas - visada ties pigiausiai pasiekiama viršūne, kuri jau buvo aplankyta.
Galiausiai parašiau kažką panašaus į minimą algoritmą, tik algoritminis sudėtingumas atrodo nesutvarkytas iki galo, ir programa turėtų veikti lėtai prie didesnių duomenų. Pirmoj įvesties eilutėj - dvi viršūnės: iš kurios į kurią nueit. Išveda -1, jeigu pasiekti neįmanoma, o jei įmanoma - išveda maršrutą. Viršūnės pažymėtos numeriais, nors gali būti ir raidės/žodžiai.

use warnings;
use strict;

while(<DATA>){
    my ($n, $m) = (split);
    my %h = ();
    my $maxw = 1e7;
    for (<DATA>){
        my ($v, $d, $w) = split;
         $h{ $v }{neib} //= [];
         $h{ $d }{neib} //= [];
         $h{ $v }{ $d } = $w ;
         $h{ $d }{ $v } = $w ;
         $h{ $v }{weight} = $maxw;      
         $h{ $d }{weight} = $maxw;
        push @{ $h{ $v }{neib} }, $d;
        push @{ $h{ $d }{neib} }, $v;
    }

    $h{ $n }{weight} = 0;
    $h{ $n }{from} = -1;
    my @arr = ($n);

    while (@arr){
        my $min = $maxw;
        my $min_node;
            $min > $h{ $_ }{weight} and
            ($min = $h{ $_ }{weight}, $min_node = $_)
        for @arr;
        my $node = $min_node;
        @arr = grep $_ != $min_node, @arr;
        push @arr, grep $h{ $_ }{weight} == $maxw,
            @{ $h{ $node }{neib} };
        for my $neib ( @{ $h{ $node }{neib} } ){
            $neib == $h{ $node }{from} and next;
            if ($h{ $neib }{weight} >
                $h{ $node }{weight} + $h{ $neib }{ $node }
                )
            {
                $h{ $neib }{weight} =
                $h{ $node }{weight} + $h{ $neib }{ $node };
              
                $h{ $neib }{from} = $node;
            }
        }
    }
  
    my @ans = ($m);
    $h{ $m }{from} // (@ans = (-1));
    while ( $ans[0] != -1 and $h{ $m }{from} > -1 ){
        push @ans, $m = $h{ $m }{from};
    }
    @ans = reverse @ans;
    print "@ans";
}
__DATA__
11 2
1 2 88
4 1 10
4 3 10
5 4 10
1 7 45
8 7 10
9 8 15
10 8 10
8 11 50
9 4 5
11 7 10

2015 m. pradžios apžvalga

1. Mokslai
2. Pasimokymai
3. "Sportinis" programavimas

1. Nuo sausio mėn. turiu įdomų užsiėmimą moksluose - prisidėjimą prie duombazės kuravimo. Duombazėje yra įvairūs tekstiniai duomenų failai, turintys atitikti tam tikras formatavimo taisykles, stardartus, bei duomenys juose turi būti neprieštaringi. Mano užduotys gali būti įvairios: 1) papildyti failus trūkstama informacija iš kitur, 2) papildyti failus kuria nors informacija, apskaičiuojant ją, remiantis jau esama faile informacija, 3) taisyti gramatines, sintaksės klaidas, 4) nestandartiškai atvaizduotą duomenį pakeisti standartu, 5+) ir kt.; >>> Veiklą vykdau iš kompiuterio, kuriame suinstaliuoti Ubuntu. Unix terpėje tekdavo būti retai, dėl to sausio pradžioje reikėjo labai greitai apsimokyti paprasčiausių terminalo programų. Ir jau nutuokiu, bei dažnai naudoju šias: ls, la, cp, rm, mv, touch, echo, ln, mkdir, rmdir, cat, head, tail, history, date, xargs, sort, uniq, jobs, fg, fuser, du... Rečiau panaudoju, ir ne tiek nutuokiu: find, diff, comm, alias, kill, sponge. Labai dažnai naudoju failų skaityklę less, ji paprasta ir joje patogi paieška. >>> Be terminalo (tty) išmanymo, reikėjo išmanyti ir naudojimąsi MySql duomenų baze, nes įvairūs duomenys ir įrašai saugomi duomenų bazės laukuose, ir juos reikėdavo pasiekti. Todėl teko prisiminti ir patobulinti savo select užklausos mokėjimą. Dažniausiai tenka naudoti gramatikos žodžius ir funkcijas tokias: select, count, from, where, group, order, limit, like. Su like ieškau laukų pagal teksto fragmentą. Rečiau ir nesavarankiškai (su pagalba) tenka duomenis į DB ir įkelti. >>> Įvairiai tekstinei paieškai atlikti - failams ar eilutėms atrinkti - tenka naudoti grep, awk, o jei neišmanau, kaip pasinaudoti šiais paprastesniais įrankiais, imu labiau pažįstamą ir universalesnį įrankį - perl'ą. Failams redaguoti įjungiu opciją perl -i (inplace). >>> Norėdamas paredaguoti iškart keliuose failuose tapačias paprastas klaidas, dažniausiai parašau regexp'ą, o jam paduodu per konvejerį (pipeline) atrinktų failų ar eilučių sąrašą. Pvz. būna tokio tipo konvejeris: [ kreipinys į DB ] | [ kelių į failus sukūrimas, pagal rastus failų identifikatorius ] | [ failų redagavimas ]. >>> Duombazės failai yra versionuojami. Versijų kontrolės sistema - Subversion (svn). Taip pat ir ja teko apsimokyt veikt. Anksčiau teko ją mokytis paskaitų metu, bet sunkiai suprasdavau ir nedaug ką mokėdavau. Dabar moku šiek tiek daugiau, pavyzdžiui, revert'int failą, peržiūrėti tik dalį paskutiniųjų log'ų. Dažniau naudoju ir svn diff. >>> Duombazei kuruoti yra parašyta kitų žmonių įrankių, įvairiomis kalbomis. Man kartais tenka skaityti tas programas, kurių didesnė dalis parašyta perl'u. Kadangi programos yra ilgos, tai skaityti užtrunka laiko, o dar blogiau - kada programoje naudojami moduliai - tada reikia dar aiškintis, ką daro būtnt jie. Programose naudojamos sudėtingesnės duomenų struktūros, t.y. duomenys kartais laikomi netgi kokiuose tai hashų hashų array hashuose, kol visą tokį susidedi į galvos tūrį, praeina laiko, sunku.

2. Pastaruoju metu mažai ko papildomai mokiausi, aiškinausi. Tačiau nuo labai senai reikėjo suprasti 1) sudėtingesnes duomenų struktūras, 2) kaip vaikščioti ir išgauti duomenis iš grafų, 3+) ir kt. Neseniai pradėjau savo programose retsykiais kurti tas sudėtingesnes duomenų struktūras, tikiuosi palaipsniui įprasiu. O pavaikščioti grafu pamėginau vakar - kovo 1-ąją. Nusipiešiau nedidelį medį, ir užsidaviau klausimu: kaip galiu jį visą pereiti, jeigu duotos jo viršūnes jungiančios briaunos? Ogi pabandžiau pasirinkęs bet kurią viršūnę, eiti nuo jos į šalis iki visų kaimyninių. Susidėdavau kaimyninių viršūnių sąrašą, ir tada iš visų jų paejėdavau irgi vienu žingsniu į priekį. Ir taip toliau. Gavosi, matyt, kažkas panašaus į taip vadinamą BFS (breadth-first search). Per vakarą pavyko padaryti du dalykus: 1. nupiešus ne medį, o grafą su ciklu, padaryti taip, kad mano paieška praneštų ar grafe yra ciklas, 2. pasirinkus dvi viršūnes, sužinoti koks jas jungia trumpiausias atstumas (intuityviai atrodo, kad veikia teisingai visais atvejais).
Tai va, liko dar daug ko pasimokyt ir pasiaiškint.

3. Pastarosiom savaitėm gan dažnai dalyvauju Opencup'e ir Codeforces. Lygis daugmaž stabilus, nei krenta, nei labai kyla. Įsimintina vakar diena: Opencup'e vieną iš užduočių pavyko išspręsti pirmam iš viso Div. 2. Tai, iš tiesų, buvo viena iš svajonių, tokių didelių, kaip kažkada Codeforces sistemoje buvo - ką nors nulaužti. Ta užduotis buvo "gana eilutinė". Tai gal davė man pranašumo, nes perl'o įrankiais greitai galiu jas apdoroti. Užskaitė ją man 47-ąją turnyrėlio minutę. Tačiau prieš tai dar buvo viena visiškai elementari (irgi eilutinė), kurią išsprendžiau per 4 min. (bet buvo pora aplenkusiųjų). Sudėtingesnioji užduotis vadinosi K. Barcode.

Sąlyga tokia: yra 5 eilučių pločio, tam tikro ilgio nuskaitytas barkodas. Jeigu nuskaitymo metu atpažinta balta spalva, tai pavaizduota Tašku, jeigu juoda - Iksu, o jeigu spalva neatpažinta - Klaustuku. Barkode dvi bet kurios spalvos iš eilės einančios vienodos spalvos juostelės reiškia vienetuką, o viena - nuliuką. Turint nuskaitymo duomenis, reikia parašyti gautus vienetukus ir nuliukus, arba išvesti -1, jeigu vienareikšmiškai nustatyti neįmanoma.

Sprendimas (gražiau perrašytas po konkursėlio) atrodo taip:

<DATA>;
map { chomp; $i = 0; $verticals[ $i ++ ] .= $_ for split // } <DATA>;

$line = join '', map {
    y/?//d;
    y///cs;
    /^.$/ ? $_ : q(?)   
    } @verticals;

    $_ = $line;
   
nO_Operation while 0
|| s/\.\?(?=\.)/.X/g
|| s/X\?(?=X)/X./g
|| s/\Q?XX\E/.XX/g
|| s/\QXX?\E/XX./g
|| s/\Q?..\E/X../g
|| s/\Q..?\E/..X/g
;

if (/[?]/){print -1}
else{
s/(.)\1/1/g,
s/[^1]/0/g,   
print
}

__DATA__
4
.X??
.??.
??.?
?X.?
.X?.

( Ideone su komentarais )

Pastaraisiais metais OpenCup antrojo diviziono dalyvių kiek apmažėję, tai dėl to, konkurencija mažesnė, ir būti vienos užduoties atžvilgiu pirmam gali pasisekti lengviau.

Codeforces svetainėje sekasi vidutiniškai, tačiau galėčiau išskirti, kad programuoti sekasi kiek sunkiau, o ieškoti klaidų varžovų koduose, jas aptikti, sukurti tinkamą testą ir nulaužti - sekasi kiek geriau, ir be to į tai daug pastangų įmetu. Neseniai vienų varžytuvių metu net 9 kambario dalyvių kodus nulaužiau. Tačiau buvo kartu ir gaila, nes jeigu būčiau išsprendęs lengvają B užduotį, dar ir ten galėčiau daug laužti (jei greit sugalvočiau kaip), nes krito virš 3/4 kambario programų ant sisteminių testų.

Išspręstoji buvo labai įdomi užduotis. Matematinė, eilutinė.

Sąlyga: yra duota skaitmenų eilutė, reikia sukurti didžiausią įmanomą skaičių, tokį, kad to skaičiaus skaitmenų ir duotos eilutės skaitmenų faktorialų sumos būtų lygios.

Funkcinis programavimas?

Kol kas tik palengva įsisavimu funkcinio programavimo sąvoką.
Kiek suprantu, tai programavimas 1) be priskyrimo operatorių, 2) su visokiom anoniminėm f-cijom, lambdom, 3) rekursijom?
Jei reikėtų iš tešlos padaryti didelio raganosio formos sausainį, turint pradžioje tešlos gumulą, tai funkciškai programuojant, tas tešlos gumulas visaip tampomas (visas, ar tik jo dalis), bet visada lieka monolitinis, o programuojant struktūriškai tas gumulas plėšomas, iš jo formuojamos būsimo raganosio dalys, kurios kažkada - suklijuojamos.
Į funkcinį programavimą man panašu: 
* užklausos duomenų bazei;
* komandinės eilutės konvejeriai;

Patinka Ruby kalboje kad galima duomenį (ar jų paketą) keisti paeiliui iš kairės į dešinę parašytomis funkcijomis, primena konvejerio struktūrą. Pvz. gets().chomp.scan().gsub().... Patogu tai, kad duomuo po funkcijos panaudojimo dažniausiai nekeičiamas (nebent yra galimybė po funkcijos vardo prirašyti šauktuką), ko nėra Perl'e. Perl'e yra naujas regex'ų modifikatorius "r" - kaip tik nedestruktyvus - patogus keitimams, nekuriant nereikalingų kintamųjų.

Šiandien kažkiek valandų praleidau Project Euler svetainėje, mėgindamas spręsti matematinius uždavinius, o atsakymus išgauti Perl'u. Tai kai kurie uždavinių sprendimo priėjimas atrodo tinkamas spręsti funkciškai. Pvz. 42-ą užduotį sprendžiau taip:

$a{ $i += $_ } //= 1 for 1 .. 50;
print eval join '+', map { 0 + exists $a{ eval join '+', map /\w/ && -64+ ord $&, split/\B/ } } split /,/, <>

Čia buvau pasidaręs reikšmių hash'ą. O tada, visus nuskaitytus duomenis apdoroju funkcijomis paeiliui, nekurdamas kintamųjų, ir apdorojęs išvedu atsakymą. Neapsieičiau čia be "eval" funkcijos.

Panašiai uždavinys 30:

print eval join '+', map { $_ * ($_ == eval join '+', map $_ ** 5 , split // ) } 1 .. 1e6

Perl. Su laiku prisijaukinama naujų įrankių.

Begyvenant, vis paskaitant dokumentacijas ir vadovėlius apie Perl'ą, tenka susipažint su naujomis funkcijomis ir galimybėmis, (<+ pasibandyt +>), po to pritaikyt, ir galiausiai - prisijaukint ir naudoti kai papuola proga.

Išsivardinsiu tų funkcijų ir jų pažinties etapų apytikslias pradžias.

Prieš tai paminėsiu, kad kai ką pradėjau naudoti praktiškai iškart, po pirmųjų pažinčių su Perlu:
while/for, if (retai unless), valdantieji (and or && ||), <>, print, tr///, s///ig, $1..., \s\d\w, ^.*$, cho(m)p, sort, rand, length, push, pop, unshift, shift, join'', split//, open, close, ord, vėliau s|||igmse, vėliau (last next redo exit), reverse...

sub -- 2012 -- 2012? -- 2012?
references -- 2012, 2013, 2014 -- no -- no
2D array -- 2012?, 2014 rugpj -- 2014 rugpj -- 2014 ruduo
%hash -- 2012?, 2014 rugpj -- 2014-08-12 -- 2014 rugpj

, -- 2013 -- 2013 -- 2013
one-line for/while -- 2013? -- 2013? -- 2013?
scalar -- 2012 -- 2012 -- rarely
undef, defined -- 2014? -- 2014? -- yes
local -- 2014? -- 2014 -- rarely
our -- undef -- undef -- no
? : -- 2012? -- 2012 -- 2012
map -- 2014 lap -- 2014 gru -- undef
grep -- 2014 lap -- undef -- no
splice -- 2012? -- 2013? -- no
each -- 2012?, 2014 ruduo -- 2014-08-12 -- no
eval -- 2013? -- 2013? - rarely
pos -- 2014? -- 2014 ruduo -- 2014 ruduo
substr -- 2012 -- 2012 -- 2013?

$0, $! -- 2012? -- 2013? -- 2013?
$, -- undef -- 2013 -- 2014
$", $/, $\ -- undef -- 2014 ruduo? -- 2014 ruduo
@-, @+ -- 2014? -- 2014? -- 2014 ruduo
$&, $`, $' -- 2012 -- undef -- 2013

<=>/cmp -- 2013? -- 2014? -- 2014 ruduo?
\b, \B -- 2012 -- 2013? -- 2013?
\K -- 2014 spa -- 2015-01-09 -- no
\G -- 2013? -- 2014-12-16 -- no
{n}, {n,m} -- 2012 -- 2012? -- 2013?
/x -- 2012, 2014 rug -- 2014 lap -- 2014 lap
/e -- 2012 -- 2012? -- 2012?
/r -- 2013 gruo -- 2013 gruo -- 2013 gruo
(??{}), (?{}) -- 2014 spa -- 2014 spa -- no
lookaround -- 2014 rugs -- 2014 rugs -- 2014 rugs
possessive and lazy quantifiers -- 2012? -- 2013? -- 2013?

qr -- 2012?, 2014 spa -- 2014 lap -- 2014 lap
q, qq -- undef -- 2014 lap -- 2014 lap
qw -- undef -- 2013? -- 2014

pack -- undef -- undef -- no
unpack -- undef -- undef -- no
split " " -- 2012, 2014 lap -- 2014-12-01 -- undef
split " ", $_, N -- 2014 lap -- 2015-01-13 -- no
rindex -- 2012 -- 2014-12-16 -- undef
cho(m)p -- 2012 -- 2012 -- 2012
study -- 2014 spa -- undef -- no
printf -- 2012? -- 2013? -- 2013
sprintf -- 2013? -- 2013? -- 2013
<<heredoc -- 2014 -- 2014 ruduo -- rarely
__DATA__ -- 2014 ruduo -- 2014 ruduo -- 2014 ruduo
do {} while -- 2012? -- 2015-01-04 -- no
do {}; -- undef -- undef -- no
die, warn -- 2013? -- 2013? -- rarely
defined-or // -- undef -- undef -- 2014?
xor -- undef -- 2014 ruduo -- 2014 ruduo
a..z -- undef -- 2013? - 2013?
( )= -- 2013? -- 2013? -- 2014
scalar .. (flip-flop) -- 2014 lap -- 2014 lap -- no
shift: << >> -- 2013 -- 2013 -- 2013
binary (~, ^, &, |) -- undef -- undef -- no
uc, lc, ucfirst -- 2012? -- 2012? -- 2012?
LABEL -- 2012? -- undef -- 2014?
use POSIX (ceil, floor) -- undef -- undef -- rarely
use integer, bigint, bignum, bigrat -- undef -- undef -- yes

Nenaudoju naujųjų: smartmatch ~~, given-when.