Tais laikais, kai namuose stovėjo IBM 486, o windows’ams parsinešti užtekdavo 36 flopikų, dabar populiari gamification (čia procesas kai kažkokį veiksmą paverti žaidimu) sąvoka manau neegzistavo, arba ją žinojo labai mažai žmonių. Tačiau būtent tą metodiką gerai išmanė mano informatikos mokytojas ir šio žaidimo „levelius“ bandau pereiti jau 15 metų. Šypsena sulaužius sunkiai spręstą uždavinį dar labiau užkabindavo stengtis ir kuo greičiau gauti naują užduotį – pereiti į sekantį lygį.

Kuriant taikomąsias programas taip pat kyla įvairių problemų (technologija, paternai, UX), bet trumpi sukti uždaviniai, kur reikia rasti algoritmą – vieta kur akys sublizga taip pat, kaip prieš tuos 15 metų. Todėl kai pernai netyčia radau http://adventofcode.com/2015 – pasijaučiau taip, kaip geimeris jaučiasi gavęs naują mylimo žaidimo versiją. Idėja paprasta – kasdien nuo gruodžio 1 dienos iki 25 duodama po 2 uždavinius. Antras uždavinys būna sudėtingesnė pirmo uždavinio versija. Pernai kalėdų seneliui reikėjo padėti įžiebti lemputes ant eglutės, o šiais metais problema rimtesnė – reikia padėti surasti jo laikrodžio osciliatorių, kurį pavogė Velykų triušis.

Užduotys pradžioje nesunkios, bet vėliau gerokai priverčia pasukti galvas, keletą kartų ir iki paryčių užsisėdėjau debugindamas savo algoritmą, „kuris turėtų veikt“. Smagu palaužyti galvas, o buvo ir situacijų, kurios davė pamokų ir kasdieniam darbui, pvz uždavinį su tekstais, kurį mano PC vargo spręsdamas turbūt pusdienį, pavyko suoptimizuoti iki pusės minutės, tiesiog pakeitus string į StringBuilder. Tokios pamokos turbūt iš galvos jau niekada neišsimuš.

Viršuje pernykštė eglė, deja skolos už paskutines 5 dienas po švenčių taip ir neatidaviau, kitos veiklos atsirado. Kam įdomu sprendimai guli git’e

https://github.com/sauliusc/AdventOfCode2015

O čia šių metų dar liūdnas žemėlapis iki Kalėdų senio paslėptos įrangos. Kad nebūtų taip paprasta, šiais metais nutariau pasunkinti sau užduotį ir visus sprendimus rašyti su Node.js. Su javascript paskutinius 5 metus beveik neturėjau reikalų, tad metas prisiminti ir išmėginti tą super greitą serverį. Kas gausis taip pat mėginsiu talpinti Git’e

https://github.com/sauliusc/AdventOfCode2016

Tai kas su manim kartu?

http://adventofcode.com/2016

Progresas, arba pamokos kurių neužmirši

3 Diena 1 dalis

JavaScript šįkart pakiaulino 🙁 Kas galėjo pagalvot, kad skaičių masyvas standartiškai vis vien rikiuojamas pagal abėcėle. Ši atrodo logiška išraiška visiškai neteisinga

var sides = element.match(/\S+/g).map(Number).sort();

Tikroji tiesa:

var sides = element.match(/\S+/g).map(Number).sort((a, b) => { return a - b });

Išsprendus užduotis forume https://www.reddit.com/r/adventofcode/ galima pasižiūrėti kaip kiti žmonės išsprendė tą patį uždavinį įvairiomis kalbomis. Ten galima rasti tiek minimalistinius sprendimus, pvz.:

document.body.innerText.split`\n`.map(x=>x.split` `).filter(t=>t.every((x,i)=>t.reduce((s,y,j)=>i==j?s:+y+s,0)>+x)).length

tiek sprendimus parašytus egzotinėmis kalbomis arba pvz excel’io formulėmis.

3 Diena 2 dalis

Įveikta dalis po ilgų kančių skaitant užduotį. Tradicinis programuotojo fail’as, kai kliento tiesa visiškai nesutampa su tuo, ką įsivaizdavo programuotojas

5 Diena

Jau visai pripratau prie JavaScript sintaksės. Ir pirmą karta JavaScript duoda į kaulus c#. Du kartus.

Viena iš užduoties dalių – užkoduoti tekstą šešioliktainiu MD5 kodu. Palyginimui šįkart algoritmą realizavau tiek c#, tiek JavaScript.

MD5 hex kodavimo kodas c#

MD5 md5Hash = MD5.Create();
var bytes = md5Hash.ComputeHash(Encoding.UTF8.GetBytes(newValue));
var s = new StringBuilder();
 foreach (byte b in bytes)
{
     s.Append(b.ToString("x2"));
}
hash = s.ToString();

Javascript

hash = crypto.createHash('md5').update(newValue).digest("hex");

Viso algoritmo vykdymo laikas ir 27649592 MD5 derinių perrinkimas:

C# – 348s

JavaScript – 176s

9 diena

String’ų montavimas! Jei pirma daugiau primena „Blonskio laborus“ su surandam-pakeičiam algoritmu ir tinkamų duomenų iškrapštymu, tai antra dalis buvo smagumėlis – viso labo prasukti ta patį pirmoje dalyje esantį algoritmą n kartų. Įspėjimas paprastas:

Unfortunately, the computer you brought probably doesn’t have enough memory to actually decompress the file; you’ll have to come up with another way to get its decompressed length.

Ir jis visiškai teisingas – po trečios iteracijos gaunu out of memory klaidą, tad sveikos rekursijos, jau galvojau nepasimatysim 🙂 Privertė jos paprakaituoti netik galvą, bet ir procesorių pasisukti 50% pajėgumu 329s. Sudaryto stringo ilgis – 10943094568

10 diena

Na ir užsuko klausimėlį, turbūt kokį pusvalandį vis pasižiūrėdavau į pavyzdį su paaiškinimais ir uždarydavau 🙂 Tušinukas ir lapas popieriaus padėjo suprasti kas ten vyksta ir kad šįkart pateikti duomenys nėra apdorojami ta pačia tvarka kaip yra išvardinti faile. Po šio nušvitimo algoritmas jau greitai susidėliojo – vėl ačiū rekursijoms 🙂

11 diena

Užskaitau šitą uždavinį kaip techninę skolą 🙁 Labai daug skaitymo, užduotis vizualiai kaip ir aiški, bet algoritmas galvoje nesidėlioja. Na ir tegul – kažkada vis vien susivirškins 🙂

13 diena

Grįžo vaiduoklis iš praeities 🙂 Puikiai pamenu paskutinį uždavinį, kurio mokykloje taip ir neišsprendžiau. 

Užduotis: vabaliukas turi pereiti į kitą lentos galą nepastebėtas. O nepastebėtas jis bus tuomet, jei eis tik savo spalvos langeliais. Koks trumpiausias kelias pereiti lentą. Nežinau ką dabar moko mokyklose, bet tada aš tikrai nieko nebuvau girdėjęs grafus, o trumpiausio kelio radimo algoritmas taip ir liko užkritęs tarp pamokų/egzaminų 13 metų. Šios dienos užduotis buvo iš dviejų dalių:

1. Žemėlapio sudarymo pagal tam tikrą formulę – easy
2. Trumpiausio kelio radimas – čia proga rasti/prisiminti tokius algoritmus kaip Breadth First Search, Depth First Search, Best First Search, Dijkstra’s Method, A*. Visgi patingėjau kažkurį iš algoritmų aprašinėti pats ir tiesiog pasinaudojau vienu iš Node modulių pathfinding kuris visą darbą padarė už mane.

14 diena

Atrodo kūrėjams šiais metais patinka MD5 kodavimas 🙂 Užduotis trumpai: sukti MD5 generavimo ciklą (abc1 => MD5, abc2 =>MD5), kode rasti 3 iš eilės pasikartojančius simbolius, ir patikrinti ar tie patys simboliai pasikartoja 5 kartus iš eilės sekančiame 1000 derinių. Ir tokių kodų reikia surasti 64.

Pirmoje dalyje reikėjo užkoduoti ir išanalizuoti ~23k derinių kad gauti atsakymą (Node lengvai suvalgė užduotį, 303ms).

Antroje dalyje viskas tas pats, tik kiekvieną gautą MD5 kodą reikia prasukti dar 2016 kartų 🙂 Viso ~42M derinių iki teisingo atsakymo (čia jau sunkiau, 169s, bet vistiek pakenčiama).

Gerai kad pirmą dalį realizuodamas nesiėmiau bruteforce ir pakartotinai negeneravau tų pačių 1000 sekančių reikšmių, o tiesiog į sąrašą dėjausi kodus su 3 simboliais ir radus 5 pasikartojančius simbolius tikrindavau ar nėra prieš tai įrašų laukiančio šių pasikartojimų. Bruteforce turbūt būtų ir nakčiai reikėję palikt. Žodžiu uždavinį užskaitau, smagiai algoritmas dėliojosi  🙂

15 diena

Tiesiog poilsis 😀 Daug prirašyta, o sprendimas paprastas – surasti skaičių, kurį panaudojus su tam tikrais duomenimis, viskas pasidalintų be liekanos 🙂 Galvojau antroje dalyje bus kažkas paruošta sudėtingo – pasirodo ne, tereikėjo pridėti dar vieną eilutę užduotyje. Node JS šitą uždavinį kaip siemkes išlukšteno:

1 dalis: 400589 deriniai per 5 ms

2dalis: 3045959 deriniai per 38ms

16 diena

Tiesiog nuostabus uždavinys priverčiantis susimąstyti apie kokybiškus algoritmus kodą! Pirma dalis paprasta – Turim pradinius duomenis pvz 10001, šiuos duomenis dvigubinam pridėdami pabaigoje atvirkštinę reikšmę iki tam tikro ilgio, pasiekus ilgį skaičiuojam checksum – iš dviejų šalimais esančių simbolių darom 1 arba 0 priklausomai nuo to ar jie sutampa tol, kol bendras ilgis nepasidaro nelyginis. Easy ane?

1 dalis – sugeneruoti eilutę iš 272 simbolių. Nėr ką aiškinti, tiesiog du ciklais ir elementarus darbas su stringais.

2 dalis – sugeneruoti eilutę iš 35651584 simbolių 😀 Kaip manot, ką padarė mano algoritmas gavęs tokią užduotį? Žinoma, išspjovė gražų OutOfMemory exception 🙂 Jau aišku kad tokio dydžio eilutę formuoti iš esmės ydinga, bet visgi įdomu paskaityti ką gali JavaScript. Įdomi dalis, jog jokių string buferių naudoti neverta, JS pats puikiai moka su kuriamais string susitvarkyt, ne taip kaip .net. Taigi dar vienas bandymas, pirmą eilutės konstravimo dalį pataisiau kad vietoj dviejų kintamųjų naudotų vieną. Rezultatas – TaskManager’yje mano procesas naudoja ~30% procesoriaus, atmintis šokinėja nuo 150MB iki 700MB, bet atsakymo deja nesugeba išstenėt 🙂 Max buvo išgauta 4M ilgio eilutė kažkur per pusantros valandos. Na ką padarysi, darom vadinasi normaliai, konvertuojam pradinę eilutę į skaičių masyvą ir dirbam su juo. Rezultatas gražus – atsakymas gautas per 8s. Šaunuolis Node JS!

Pasidaviau smalsumui ir viską perrašiau ir su C#

StringBuilder och kas plušėjo ir atsakymą sugebėjo išspausti per: vis dar sukasi…

Panaudojus List<byte> rezultatas nustebino – 2,6s.  Tad nereikia stumti ant .net, kad jis kartais būna lėtas – tiesiog reikia panaudoti tinkamas priemones, na ir žinoma pirštukus kartais tiesiog patiesinti…

17 diena

Skola vabaliukui galutinai atiduota 😀 Teko parašyti „maze solve“ algoritmą dinamiškai kintančiam labirintui, tad šįkart su Node JS moduliais nepavyko išsisukti. Iš esmės nieko baisaus, 3D masyvas aplankytam keliui saugoti ir rekursija su išvardintais if’ais 🙂 Baisu būna tik tol, kol nepradedi rašyt 🙂

18 diena

Nuobodoka. Tradicinis scenarijus: darbas su stringais, pirma dalis su mažai operacijų (pradinė įvestis 38), antra – su gerokai daugiau (pradinė įvestis 40000). Tik kad antrą dalį Node JS sukramtė per nepilnas 10s, tad optimizuot yra ką, bet šįkart jau gaila laiko, ir taip aišku ką reikia daryt 🙂

20 diena

Na patingėjo šįkart elfai kažką sudėtingo paruošt 🙂 Tereikėjo surast nepersidengiančius intervalus.

1. Rikiuojam intervalus nuo mažiausio iki didžiausio, suvalgydami persidengiančius
2. Prabėgam per sąrašą ir surandam tarpų intervalus

Tikrų tikriausias universiteto uždavinukas. Tik ataskaitos su „Blonskiagramom“ nereikia rašyt 🙂

21 diena

2 savaičių šventinė pertrauka, bet metas grįžti ir pabaigti tai kas pradėta 🙂 Skaitau sąlygą – kažkur ji man matyta, atsidarau projektą – ogi iš tikrųjų viskas suprogramuota, bet deja neveikia 🙂 Vėl darbas su stringais – 6 skirtingų komandų vykdymas slankiojant ir kaitaliojant raides. Puikus uždavinys tikrint pastabumui ir prisiminti kaip iš tikrųjų reikia debug’inti, kadangi po praėjusio testinio scenarijaus išlindo gal kokie 3 bugai. Visa laimė, kad jie buvo pradžioje ir nereikėjo rankomis perskaičiuoti kokias 30 eilučių 🙂

Antra dalis paprasta bet įdomi – revertinti užkoduotą eilutę, pagal duotas taisykles, taigi visas operacijas teko sugalvoti kaip įvykdyti atvirkščiai.

P.S. Ir vėl viena klaida buvo dėl javascript tipų neapibrėžtumų, su skaičiumi prie vienos situacijos pasielgė kaip su stringu tyliai tyliai. Zaraza…

Komentarai

Komentarai