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.
Komentarų nėra:
Rašyti komentarą