Š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. balandžio 6 d., pirmadienis
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.
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,
}
__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.
2015 m. vasario 9 d., pirmadienis
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
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
2015 m. sausio 14 d., trečiadienis
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.
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.
2014 m. gruodžio 2 d., antradienis
2014 spalis-lapkritis
Dviejų mėnesių bėgyje, tiek kiek leido priežastys, pasiskaitydavau kažko naujo arba seno, ir paspręsdavau uždavinukų.
Skaitymas.
* Wikipedijoje skaitau atskirus straipsnelius programavimo tema, pažindindamasis (dažnai paviršutiniškai) su sąvokomis ir su programų veikimo mechanika. Labiausiai patiko "Optimizing compiler" ir iš jo atsišakojantys įvairių kompiliatoriaus daromų optimizacijų aprašymai. Iš jų labiau suprantami: dead-code elmination, constant folding, loop-invariant motion, strength reduction. Dar skaičiau: Index mapping (trivial hash f-tion), Look-up table (LUT), Minimalism (computing), Segmantation fault, Scripting language, Objective-C, Computer worms... kas papuola and minties.
* Mastering Regular Expressions - pdf'as, pagaliau perskaičiau, iš tiesų perskaičiau 7 iš 9 skyrių, nes >6 skyriai eina atskirai konkrečiãi kalbai, tai 7-ame skyriuje apie Perl'o regex'us. Knyga patiko. Skaityti užtruko ir buvo sunku. Tik galbūt reikėjo paieškot ir skaityt 3rd edition vietoj 2nd.
* Learning Perl - pdf'as, 6th (vėliausias) edition, perskaičiau daugumą skyrių, kelis permečiau akimis. Vienkartinio perskaitymo užteko visiems tiems puslapiams, kur aprašoma jau pažįstama medžiaga. O lėčiau tekdavo paskaityti nežinomus dalykus. Skyriai, į kuriuos mažiau gilinausi, ir/ar kurie man sunkesni, tai viskas apie Encoding'ą, Process management, darbas su failais ir direktorijomis, Perl modules (.pm). O 7, 8, 9 skyriai - greituoju skaitymu, nes apie reguliariasias išraiškas. Uždavinių knygoj neišsprendžiau.
[UPDATE] * Žiūrėjau Youtubėj video (57'), kurį vedė Larry Wall (Perl ir Perl 6 kalbų kūrėjas)). Vidijuje pasakoja jis apie naująją kalbą - Perl 6 (kuri iki šiol oficialiai neišleista), apie jos ideologinius ir konkrečius skirtumus nuo Perl kalbos (kitaip tariant nuo Perl 1..5 kalbos versijų, kurių kiekviena yra suderinama (compatible) su aukštesniąja iš bet kurių tos kalbos versija). Istoriškai gavosi, kad tiek įprastas Perl, tiek Perl 6 vystosi lygiagrečiai, ir nėra taip, kad Perl 6 yra skatintina::naudoti versija => geresnė už paskutiniąsias Perl versijas, t.y. Perl 5.20 su kapeikom. Perl 6 yra net ne atsišakojimas, o perrašyta naujai kalba(?), o jos autorius Larry Wall sako, tai yra ne kalba, o kalbos vienoje.
Man Perl 6 neteko naudotis, tačiau paklausyti šios paskaitos labai labai patiko. Be to buvo smagu paklausyti kalbos, kuria rašinėju, autoriaus kalbą!! Ir džiaugiuosi, kad nemažą dalį supratau apie ką kalbėjo, nes daug to, ką vartojo savo kalboje, perskaičiau Mastering Regular Expressions knygoje. [/U]
Programų rašymas.
* Turnyrėliai, uždavinukai.
Šiek tiek anarchy golf'o.
Kelis kart dalyvavau OpenCup'e. Sekėsi prastokai.
Kelis kart dalyvavau Codeforces. Sekėsi vidutiniškai arba kiek prasčiau.
* Pats sau.
Buvau kadaise nepriklausomai sugalvojęs paprastą klausimą: kaip implementuoti (parašyti) dvimačio fragmento paiešką dvimačiame masyve. Pvz. dvimačiame masyve yra 0- ir 1- ukai. Ar galima jame surasti (ir kiek) "pliusų" sudarytų iš 5 vienetukų. Kitaip tariant, pritempus prie reguliariųjų išraiškų, tai būtų dvimatės reguliarios išraiškos paieška(?).
Vieną dieną prisidėdau ir parašiau primityvią versiją, kurios paieškos greitis nedidelis. O veikimo principas toks: 1) paieškos paveikslėlis yra aprašytas keliomis eilutėmis reguliariųjų išraiškų formatu, tada šios eilutės yra sudedamos į masyvą. 2) duomenyse, kuriuos naršysime, paleidžiame ciklą per eilutes iš viršaus į apačią: 2.1) kiekvienoje toje eilutėje atliekame paprastą paiešką su pirmąja vienmačią reguliaria išraiška iš tų reguliarių išraiškų masyvėlio; 2.1.1) jeigu paieška sėkminga, tada einama laikinai prie sekančios eilutės (stojant į konkrečią jos vietą) ir būtent šioje vietoje atliekama paieška su antrąja masyve esančia reguliaria išraiška. Tam manipuliuoju su eilutės pos() (paieškos starto vieta) ir pririšu paiešką \G inkaru, kad neitų ieškot tolyn į priekį.
Suradus vieną sutapimą, programa veikia toliau ir ieško kitų sutapimų, kuriems leidžiama persidengti (tą suprogramuoti pasirodė kur kas lengviau).
Žemiau:
1) tai, ko ieško programa (4 simboliai, ignoruokim tarpus - jie nėra paieškoje),
2) programos veikimo rezultatas (su parodytomis eilutėmis vėliau naudosimomis reguliariose išraiškose),
3) pavyzdinis programos kodas
3.1) kodo apačioje po užrašo __DATA__ yra duomenų dvimatis laukas, kuriame paieška vykdoma.
1.
#
#
#.
3.
Skaitymas.
* Wikipedijoje skaitau atskirus straipsnelius programavimo tema, pažindindamasis (dažnai paviršutiniškai) su sąvokomis ir su programų veikimo mechanika. Labiausiai patiko "Optimizing compiler" ir iš jo atsišakojantys įvairių kompiliatoriaus daromų optimizacijų aprašymai. Iš jų labiau suprantami: dead-code elmination, constant folding, loop-invariant motion, strength reduction. Dar skaičiau: Index mapping (trivial hash f-tion), Look-up table (LUT), Minimalism (computing), Segmantation fault, Scripting language, Objective-C, Computer worms... kas papuola and minties.
* Mastering Regular Expressions - pdf'as, pagaliau perskaičiau, iš tiesų perskaičiau 7 iš 9 skyrių, nes >6 skyriai eina atskirai konkrečiãi kalbai, tai 7-ame skyriuje apie Perl'o regex'us. Knyga patiko. Skaityti užtruko ir buvo sunku. Tik galbūt reikėjo paieškot ir skaityt 3rd edition vietoj 2nd.
* Learning Perl - pdf'as, 6th (vėliausias) edition, perskaičiau daugumą skyrių, kelis permečiau akimis. Vienkartinio perskaitymo užteko visiems tiems puslapiams, kur aprašoma jau pažįstama medžiaga. O lėčiau tekdavo paskaityti nežinomus dalykus. Skyriai, į kuriuos mažiau gilinausi, ir/ar kurie man sunkesni, tai viskas apie Encoding'ą, Process management, darbas su failais ir direktorijomis, Perl modules (.pm). O 7, 8, 9 skyriai - greituoju skaitymu, nes apie reguliariasias išraiškas. Uždavinių knygoj neišsprendžiau.
[UPDATE] * Žiūrėjau Youtubėj video (57'), kurį vedė Larry Wall (Perl ir Perl 6 kalbų kūrėjas)). Vidijuje pasakoja jis apie naująją kalbą - Perl 6 (kuri iki šiol oficialiai neišleista), apie jos ideologinius ir konkrečius skirtumus nuo Perl kalbos (kitaip tariant nuo Perl 1..5 kalbos versijų, kurių kiekviena yra suderinama (compatible) su aukštesniąja iš bet kurių tos kalbos versija). Istoriškai gavosi, kad tiek įprastas Perl, tiek Perl 6 vystosi lygiagrečiai, ir nėra taip, kad Perl 6 yra skatintina::naudoti versija => geresnė už paskutiniąsias Perl versijas, t.y. Perl 5.20 su kapeikom. Perl 6 yra net ne atsišakojimas, o perrašyta naujai kalba(?), o jos autorius Larry Wall sako, tai yra ne kalba, o kalbos vienoje.
Man Perl 6 neteko naudotis, tačiau paklausyti šios paskaitos labai labai patiko. Be to buvo smagu paklausyti kalbos, kuria rašinėju, autoriaus kalbą!! Ir džiaugiuosi, kad nemažą dalį supratau apie ką kalbėjo, nes daug to, ką vartojo savo kalboje, perskaičiau Mastering Regular Expressions knygoje. [/U]
Programų rašymas.
* Turnyrėliai, uždavinukai.
Šiek tiek anarchy golf'o.
Kelis kart dalyvavau OpenCup'e. Sekėsi prastokai.
Kelis kart dalyvavau Codeforces. Sekėsi vidutiniškai arba kiek prasčiau.
* Pats sau.
Buvau kadaise nepriklausomai sugalvojęs paprastą klausimą: kaip implementuoti (parašyti) dvimačio fragmento paiešką dvimačiame masyve. Pvz. dvimačiame masyve yra 0- ir 1- ukai. Ar galima jame surasti (ir kiek) "pliusų" sudarytų iš 5 vienetukų. Kitaip tariant, pritempus prie reguliariųjų išraiškų, tai būtų dvimatės reguliarios išraiškos paieška(?).
Vieną dieną prisidėdau ir parašiau primityvią versiją, kurios paieškos greitis nedidelis. O veikimo principas toks: 1) paieškos paveikslėlis yra aprašytas keliomis eilutėmis reguliariųjų išraiškų formatu, tada šios eilutės yra sudedamos į masyvą. 2) duomenyse, kuriuos naršysime, paleidžiame ciklą per eilutes iš viršaus į apačią: 2.1) kiekvienoje toje eilutėje atliekame paprastą paiešką su pirmąja vienmačią reguliaria išraiška iš tų reguliarių išraiškų masyvėlio; 2.1.1) jeigu paieška sėkminga, tada einama laikinai prie sekančios eilutės (stojant į konkrečią jos vietą) ir būtent šioje vietoje atliekama paieška su antrąja masyve esančia reguliaria išraiška. Tam manipuliuoju su eilutės pos() (paieškos starto vieta) ir pririšu paiešką \G inkaru, kad neitų ieškot tolyn į priekį.
Suradus vieną sutapimą, programa veikia toliau ir ieško kitų sutapimų, kuriems leidžiama persidengti (tą suprogramuoti pasirodė kur kas lengviau).
Žemiau:
1) tai, ko ieško programa (4 simboliai, ignoruokim tarpus - jie nėra paieškoje),
2) programos veikimo rezultatas (su parodytomis eilutėmis vėliau naudosimomis reguliariose išraiškose),
3) pavyzdinis programos kodas
3.1) kodo apačioje po užrašo __DATA__ yra duomenų dvimatis laukas, kuriame paieška vykdoma.
1.
#
#
#.
2.
(0: .{1}#)
(1: #)
(2: .{2}#\.)
Number of matches: 3;
Upper-left corners match at:
[row: 1|column: 1]
[row: 1|column: 6]
[row: 2|column: 0]
3.
use warnings;
use strict;
sub two_d_search{
my $amount_of_data = shift;
my @data = splice @_, 0, $amount_of_data;
my @pattern = ();
my ($arg, $indentation, $string);
my $i = 0;
while (@_){
$arg = shift;
if ($arg eq "\n"){
$i++;
$arg = shift;
}
$indentation = $arg;
$string = shift;
$pattern[ $i ] .= ".{$indentation}" if $indentation;
$pattern[ $i ] .= $string;
print "($i: $pattern[ $i ])", "\n";
}
my $pos;
my $match = 0;
my @matches = ();
for my $i (0 .. @data - 1){
undef pos $data[ $i ];
OUT_2:
while ($data[ $i ] =~ m/$pattern[0]/g){
($pos) = @-;
# matches can overlap, so 'pos' increases only by +1:
(pos $data[ $i ]) = $pos + 1;
for my $j (1 .. @pattern - 1){
pos ($data[ $i + $j ]) = $pos;
if ($data[ $i + $j ] =~ m/\G$pattern[$j]/){
# do nothing
}
else {
next OUT_2
}
}
$match ++;
push @matches, "[row: $i|column: $pos]";
}
}
$" = "\n"; # set list output separator to "\n"
return "Number of matches: $match;",
"Upper-left corners match at:\n@matches"
}
my @data = <DATA>;
chomp @data;
my @info = &two_d_search(
scalar @data,
@data,
# indentation; string; argument of line separation
1, '#', "\n", # two_d_regex first line
0, '#', "\n", # two_d_regex second line
2, '#\.' # two_d_regex third line
);
print "@info",$/;
__DATA__
#..#.....#.
..#...##...
.#....#..##
#..#....#..
..#...#..#.
.......#.#.
...........
2014 m. spalio 8 d., trečiadienis
Mokslo metų pradžia
Pastaruoju metu:
* skaičiausi en.wikipedia straipsnelių, susijusių su programavimu.
* mėginau pasidomėti Haskell kalba, bet nieko nesupratau.
* dalyvaudavau Codeforces turnyrėliuose ir treniruotėse.
* perskaičiau pusę vienos knygos apie programavimą, vienos iš šių - žemiau pateiktų:
Wikipedijoj susipažįstu su savokom "operator overloading", "arity", "linearithmic (O(n log n)) (complexity)... , permetu akeles per straipsnius pavadinimais "sorting algorithm comparison", "computation complexity", "C++ Standard Library", "Standard Template Library", "ternary operation", "scope", "volatile memory", "random access"... daug straipsnių lieka nesuvirškinti ir per sunkūs, tai apie NFA, DFA ((non-)deterministic finite automata) ir kt.
Codeforces platformoje pastarąjį mėnesį sekėsi gan gerai. Nors išspresdavau nedaug ir pačių lengviausių uždavinių, tačiau gan greitai. Taip pat kartais pavykdavo nulaužti kambariokų programas.Už tai užimdavau neblogas vietas, palyginus, ir kilstelėjo reitingas, kurio adekvatumu galima lengvai paabejoti.
Knygos apie reguliarias išraiškas pirmoje pusėje, kurią įveikiau, radau keletą naujų dalykų, bet daug buvo žinoma ir veikė kaip kartojimas, priminimas. Knygoje daug remiamasi pavyzdžiais, kas man patinka. Ir pavyzdžiai gana praktiški. Pradėjau savo sprendimuose Perl kalba taikyti lookaroundą (lookbehindą ir lookaheadą), ko anksčiau nedariau.
Programose ėmiau naudoti kintamuosius: $/ (input line separator), dažniau teko reguliariosiose išraiškose naudoti modifikatorius "m", reguliariai panaudoju nesenai išmoktuosius Hash'us.
Kartais pagolfinu anarchy golfe.
* skaičiausi en.wikipedia straipsnelių, susijusių su programavimu.
* mėginau pasidomėti Haskell kalba, bet nieko nesupratau.
* dalyvaudavau Codeforces turnyrėliuose ir treniruotėse.
* perskaičiau pusę vienos knygos apie programavimą, vienos iš šių - žemiau pateiktų:
Wikipedijoj susipažįstu su savokom "operator overloading", "arity", "linearithmic (O(n log n)) (complexity)... , permetu akeles per straipsnius pavadinimais "sorting algorithm comparison", "computation complexity", "C++ Standard Library", "Standard Template Library", "ternary operation", "scope", "volatile memory", "random access"... daug straipsnių lieka nesuvirškinti ir per sunkūs, tai apie NFA, DFA ((non-)deterministic finite automata) ir kt.
Codeforces platformoje pastarąjį mėnesį sekėsi gan gerai. Nors išspresdavau nedaug ir pačių lengviausių uždavinių, tačiau gan greitai. Taip pat kartais pavykdavo nulaužti kambariokų programas.Už tai užimdavau neblogas vietas, palyginus, ir kilstelėjo reitingas, kurio adekvatumu galima lengvai paabejoti.
Knygos apie reguliarias išraiškas pirmoje pusėje, kurią įveikiau, radau keletą naujų dalykų, bet daug buvo žinoma ir veikė kaip kartojimas, priminimas. Knygoje daug remiamasi pavyzdžiais, kas man patinka. Ir pavyzdžiai gana praktiški. Pradėjau savo sprendimuose Perl kalba taikyti lookaroundą (lookbehindą ir lookaheadą), ko anksčiau nedariau.
Programose ėmiau naudoti kintamuosius: $/ (input line separator), dažniau teko reguliariosiose išraiškose naudoti modifikatorius "m", reguliariai panaudoju nesenai išmoktuosius Hash'us.
Kartais pagolfinu anarchy golfe.
2014 m. rugsėjo 2 d., antradienis
Apžvalga 2014 rugpjūtis
Šį mėnesį dalelę laiko praleidau skaitinėdamas perldoc.perl.org . Tekstas jame sunkus, ir patys dalykai vietomis sunkiai įkandami, tačiau dalį įsisavinu į atmintį. Kartais mėginu minimaliai pasirašyti - taip geriau įsimena. Pasimokiau hash'ų pradmenis ir išsprendžiau kelis Codeforces uždavinukus su hash'ais. Dar pasiskaičiau apie Perl operatorius (perlop), kintamuosius (perlvar). Dar pamėginau pasirašyti elementarų "dvimatį masyvą", kuris Perl'e gaunamas tik per nuorodų sukūrimą. Taigi - pasimokiau kažko naujo.
Codeforces šį mėnesį sprendėsi prastai. Dariau klaidų, neapgalvojau visų atvejų. Kartą tik trumpam laikui prisijungiau į kontestą, ir kartą - mėginau rašyti mobiliuoju telefonu, kurį pasiskolinau iš draugo: buvo labai sunku rinkti kodo tekstą - daugiausia laiko tai ir užtruko.
Mėginimai crackint'i kitų dalyvių kodus - dažniau nesėkmingi.
Codeforces šį mėnesį sprendėsi prastai. Dariau klaidų, neapgalvojau visų atvejų. Kartą tik trumpam laikui prisijungiau į kontestą, ir kartą - mėginau rašyti mobiliuoju telefonu, kurį pasiskolinau iš draugo: buvo labai sunku rinkti kodo tekstą - daugiausia laiko tai ir užtruko.
Mėginimai crackint'i kitų dalyvių kodus - dažniau nesėkmingi.
Užsisakykite:
Pranešimai (Atom)