2017 m. birželio 21 d., trečiadienis

Rekurencijos grafikai (matricos) arba 2016 spalio - 2017 gegužės apžvalga

Per minimą laikotarpį kartais atsirasdavo priežasčių, daugiau ar mažiau, ko įdomesnio paskaityt ar pasimokyt. Kartais atvirkščiai.

Vienas iš tų dalykų, universitete, kuriame dar leista pratęsti studijas, nagrinėtas ir paviršutiniškai pažintas dalykas buvo rekurencijos (panašumų) grafikai (angl. recurrence plot, RP, wiki, [1]).

Pačiam sau teko pasirašyti minimalaus paprastumo programų, kurios iš duomenų sudaro RP (CRP, JRP), vėliau atlikti su jom (o tai yra {1, 0} matricos) nesudėtingus veiksmus.

Tiek rudenį, tiek pavasarį, dar tekdavo laisvalaikiu sudalyvauti Codeforces ir opencup.ru turnyrėliuose, labai tradiciškai. Be ypatingų rezultatų.

***

Plačiau apie rekurencijos grafiką

Tai juodų-baltų taškų matricą gaunama, lyginant vieną laiko eilutę su kita (jei su savimi pačia, tai matrica vadinama autorekurencijos m.). Teko susidurt tik su diskrečiom laiko (arba gylių) eilutėm. Lyginant dvi eilutes, kuriose duomenys: 1...N ir 1...M, gaunama NxM matrica. Autorekurencijos atveju - kvadratinė - NxN.
Šioje matricoje jos elementas A[i][j] įgis binarinę reikšmę: 1 arba 0, kitaip - juodą arba baltą spalvą. Kurią iš reikšmių įgaus, priklauso nuo pasirinkto skirtumo slenksčio (ϵ, epsilon) - reikšmės, per kurią gali skirtis vienos eilutės [i] reikšmė nuo kitos eilutės [j] reikšmės. Aritmetinis reikšmių skirtumas - paprasčiausias pavyzdys. Tačiau gali būti ir sudėtingesni reikšmių palyginimo variantai.

Autorekurencijos matrica, visai logiška, kad turės vienetais užpildytą įstrižainę  - tapatumo įstržainę (angl. line of identity, LOI).

Pavyzdžiui, žemiau pateikta kaip atrodo autorekurencijos matrica, gauta lyginant funkciją f(x) = |sin(x)| intervale [0; 6π]. Juodi taškai - didesnio panašumo reikšmės (remiantis paprastu euklidiniu atstumu). Grafikas sudarytas ne pasirenkant slenkstinį epsilon, o užsakius programos, kad sugeneruotų 30% labiausiai rekuruojančių taškų.

Žiūrint į RP, patyrusia akim galima nustatyt kai kurias savybes, kurias turi reikšmių eilutė; labiausiai - ar reikšmės cikliškai atsikartoja, ar užsistovi, ar yra chaotinės vs stochastinės.
Be savybių nužvelgimo akimis, galima kurti ir naudoti įvairias skaitines statistikas.

2016 m. spalio 12 d., trečiadienis

2016 liepa-spalis

* Bendrai
* Uždavinukai Codeforces ir pnš.
* Savo užduotys

BENDRAI

Šiuo laikotarpiu mažai programavau, dar mažiau - gilinausi ar skaičiau literatūros/tutorialų. Dalyvavau Codeforces platformos renginiuose. Rudens pradžioj poroj OpenCup'o kontestų. Tebesprendžiu viską Perl kalba. Rezultatai vidutiniški, nesama lygio pakylėjimo. Netgi pablogėjimas lyginant šių metų su praeitų metų Codeforces reitingu. Vieną dieną ėmiau ir suprogramavau "žodžių kryžiuoklį" - skirtą kryžiažodžiams sudaryt.

UŽDAVINUKAI

Codeforces patikdavo eilutiniai uždaviniai. Ir patiko vienas dvimačio masyvo uždavinys: Stačiakampėje matricoje (iki 50x50) taškai tai - vanduo, grotelės - žemyno dalis. Reikia užpilti tiek ežerų, kad liktų tik K, ir sunaudoti kuo mažiau žemių.
Sprendžiau nuoseklia paieška ir bfs'u. Nuoseklia paieška randu tašką (vandens telkinio dalį), ir sukuriu masyvą šiam vandens telkiniui, į masyvą push'inu keturių gretimų langelių koordinates. Ir tęsiu su šio masyvo elementais tą patį. Jeigu koordinatė išeina iš stačiakampio ribų - reiškia susiliejimą su vandenynu = ne ežeras. Vėl nuoseklia paieška ieškau taško. Visus surastus ežerus surikiuoju pagal plotą, ir užpilu mažiausius.

Rinktinės reguliariosios išraiškos iš įvairių Codeforces uždavinių:

Uždavinyje, kur visus masyvo elementus 
reikėjo suporuot į vienodas sumas:
0 while s/\b(\d+)((?: \d+)*) ((??{ $each - $1 }))\b/ (push @pairs, "$1 $3"), $2 /e;


Uždavinys - ar tai veidrodinis palindromas? (sprendimas rekursinis):
$F = 1;
$F &&= f( <> );

print ! $F ? "NIE" : "TAK";

sub f {
 my ($A) = shift;
 $A =~ s/\B.*\B// &&$&&& ( $F &&= f($&) );
 $F &&= 
 $A =~ /bd|db|pq|qp|^([ovwxAHIMOT-Y])\1?$/;
 }
 

Uždavinys apie masyvo kairiųjų elementų naikinimą, priklausomai nuo c:
s/.*(\b\d+) (\d+\b)(??{ $2 - $1 <= $c })//;
(nepraėjo: TLE#55; o su non-greedy '.*?' - 
gavosi Perl bug'as (Can't COERCE unknown...), 
pranešiau, bet yra žinomas)


Uždavinys - vietoje klaustukų įrašyti raides taip (jei įmanoma), 
kad eilutėje būtų 26-ių raidžių nuoseklus substringas, 
turintis savyje visas abėcėlės raides.
$c = $_ = <>;
 
while( /(?=(.{26}))/g ){
 next if ($L = $1) =~ /(\w).*\1/;
 $L =~ s/\?/$_/ for grep $L !~ /$_/, 'A'..'Z';
 
 substr $c, pos, 26, $L;
 $c =~ y/?/X/;
 
 $f = 1;
 last;
 }
 
print $f ? $c : -1
 
Uždavinys. Ar tų pačių metų iš eilės einančių dviejų mėnesių 
pirmosios dienos gali būti duotomis dvejomis 
savaitės dienomis (nekeliamuosiuose metuose)?
 
($f, $s) = map s/..\K.*//sr, <>;

print qw(NO YES)[ ("motuwethfrsasu" x 2) =~ /$f((..){2,3})?(?<=$s)/ && 1 ] 



OpenCup'e GP_of_SPb patiko uždavinys apie laikmatį. Yra juosta, sujungta ratu, ant kurios kas 12 langelių nupaišytos padalos. Viso 12 x 60 = 720 padalų = 60 minučių. Ties kas penkta padala yra nupaišytas minučių skaičius: ..., 5, 0, 55, 50, ..., 10, 5, 0, 55, ... . Stebėtojas gauna tik laikmačio langelio vaizdą, kuris yra 60 x 12 matmenų (tik užapvalinti kampai užtemdyti). Tikslus laikas yra ties langelio viduriu. Iš langelio vaizdo reikia pasakyti tikslų laiką (laikmačio tikslumu, t.y. 5 sek).

Pvz. įėjimo duomenys:

-------X..........XX..........XX..........XX.........-------
----..XX..........XX..........XX..........XX..........XX----
-..........................................................-
X..................................................XXXXXXX..
XX.................................................XX.......
XX.................................................XXXXXX...
XX......................................................XX..
XX......................................................XX..
XX.................................................XX...XX..
-...................................................XXXXX..-
----....................................................----
-------..............................................-------


(paveikslėlyje matosi 10-uko fragmentas ir pilnas penketukas)
Atsakymas: 07:05 (t.y. 7 min, 5 s)

Programos pagrindinis fragmentas:

#!/usr/bin/perl

use warnings;
use strict;

my $i;
my @A;
while(<DATA>){
    chomp;
    /\d/ ? $i = $& : push @{ $A[$i] }, $_;
}

chomp( @_ = <> );

my $regex = join ".{721}", map { s/\./\\./gr =~ y/-/./r } @_[0..9];

my @L;
push @L, ('.' x 5 . ( 'X' x 2 . '.' x 10 ) x 64 . 'X' x 2 . '.' x 5) x 2;
push @L, '.' x length $L[0];

for my $i ( 'a26', 0, 'a48', (map { (split //, $_ * 5), 'a44' } reverse 2 .. 11), 'a4', 5, 'a52', 0, 'a26' ){
    for my $j (0 .. 6){
        $L[$j + 3] .= $i =~ /a(\d+)/ ? '.' x $1 : $A[$i][$j]
    }
}

my $L = join "\n", @L;

$L =~ s/$regex.*//s or print "NOOOOO!\n";

my $sec5 = (720 - length $L) % 720;

printf "%02d:%02d\n", (int $sec5 / 12), 5 * ($sec5 % 12);


__DATA__
0
.XXXXX..
XX..XXX.
XX.XXXX.
XXXX.XX.
XXX..XX.
XXX..XX.
.XXXXX..
........

<...>

(http://ideone.com/4MDCaC


SAVO UŽDUOTYS

Sudariau žodžių kryžiuoklį. Jis veikia lėtai, nes atlieką daug perrinkimo. Veikimo laikas berods didėja ^2.5, didėjant kryžiuojamų žodžių skaičiui.
Normaliai veikia su iki ~20 žodžių.
Įsimena žodžius. Tada ilgiausią deda horizontaliai. Vėliau perrenka visus kitus žodžius, bandydamas sukryžiuoti, gaunant kuo daugiau susikirtimų, ir kuo mažesnį naują kryžiažodžio plotą (apimantįjį stačiakampį).

Pvz. išvestis:

          V                                  V                                                               
          *                   V              *                                                 V             
H    *    *    *    *    *    *    *    *    *                             V                   *             
          *                   *              *         H    *    *    *    *    *    *    *    *    *        
          *    H    *    *    *    *    *    *    *    *    *    *    *    *    *              *             
          *                   *              *    H    *    *    *    *    *    *              *             
          *         H    *    *    *    *    *    *    *    *    *    *    *    *              *             
                                             *    H    *    *    *    *    *    *    *         *             
                                             *                             *                   *             
                                   H    *    *    *    *    *    *    *    *                   *             
               H    *    *    *    *    *    *                                                               

                                                                                                   
[lietuvos upė]
[saugos prietaisas]
[gėlė]
[riešutas]
[spalva]
[naminis žinduolis]
[mėnuo]
[rusijos miestas]
[transporto priemonė]
[savaitės diena]
[vasaros šventė]
[medis]
[plėšri žuvis]


2016 m. birželio 21 d., antradienis

2015/2016 m.m. ir veiklos apžvalga

Universitete mokiausi abudu semestrus. Programavau pagrinde Perl'u. Pirmąjį - turėjau keletą dalykų, kuriuos reikėdavo daug programuoti. Antrąjį - praktikavausi projekte.
Tarp kitko paspręsdavau Codeforces ir OpenCup kontestus.

Be to nuo praeitos iki šios vasaros pagrinde sėdžiu namuose ant Linux'ų. Įsirašęs Linux Mintus. Lievi, bet kažkaip pakenčiu.

Pirmąjį semestrą teko pasipraktikuoti su Perl'u redaguotis/tvarkytis duomenis. Dar teko programuoti įvairius algoritmus. Intergravimas, Bezier kreivės - šitus rašiau C kalba.
Viename iš dalykų, reikėjo programas rašyti kruopščiai skaitomas ir kruopščiai išvedančias išvestį. Taigi, teko išsiugdyti daugiau disciplinos skaitomume. Dalyko metu parašiau: labirinto perėjimą į plotį ir į gylį, Hanojaus bokštą rekursyviai ir iteratyviai, viena kitos nepuolančių šachmatų valdovių uždavinį, BC ir FC (backward ir forward chaining'us). Tarp kitko sau pasirašiau ir Sudoku žaidimo sprendiklį. Taigi semestro metu, nemažai draugystės su "backtracking'u". Apskritai, rekursija, backtraking'as ir chaining'ai - labai įdomios loginės temos.

Vieno dalyko metu teko atlikti grupinį darbą - projektuoti sistemą, bet jos neprogramuoti. Turėjo gautis visoks tekstas ir lentelės bei schemos, o kadangi dirbdavome ne vien susirinkę biblėj, bet ir iš namų, tai draugai pamokė naudotis GitHub'u ir naudojomės juo.
Kai susipažinau, praėjau jį naudoti ir visiems kitiems dalykams, kaip versijavimo sistemą. Netgi savo spręstus uždavinius iš CodeEval sistemos, persikėliau į GitHub'ą.

Pavasarį, kažką veikiau projekte. Turėjau gan įdomią temą: reikėjo skenuotuose tekstuose išskirti pastraipų, paveikslėlių, ir kitų loginių atskirų blokų, koordinates. Pavyko parašyti programą, kuri užlieja tarpus tarp gretimų pikselių, jeigu jis neviršija N. Apdoroja po eilutę. Taigi, norint užlieti ir horizontaliai ir vertikaliai, tekdavo paversti paveikslėlį ant šono.
Tam reikalui pasimokiau Netpbm paketo programų.
Vėliau užlietus blokus reikėdavo surasti. Taigi paeilučiui eidavau iš viršaus žemyn ir prijungdavau besiliečiančias pikselių eilutes prie jau esančių (kaip prie blokų), kartais apsijungiant fragmentams į vieną, arba susikuriant naujam.
Dar aprašiau opciją - apjungti tokius fragmentus, jeigu juos apimantieji minimalieji stačiakampiai persikloja.

Tiek Codeforces, tiek OpenCup'e pastaraisisi metais sunkiau gaudavosi spręsti.

Apskritai programuoti pasidarė sunku, blogesnis įsiminimas, dažnas nuovargis, ir kitos mintys. Dėl ko apatijos ir pnš. įtakoje krenta imlumas, galimybės. Univere prisidirbau skolų. Tačiau patenkintas, kad kažkiek visgi programuoju, ir kažkiek pavyksta.

2015 m. rugpjūčio 23 d., sekmadienis

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 m. gegužės 2 d., šeštadienis

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:


























2015 m. balandžio 6 d., pirmadienis

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. kovo 2 d., pirmadienis

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.