Advent of Code 2020

Ametlik: https://adventofcode.com/2020/

Reddit: https://www.reddit.com/r/adventofcode/

Esimene päev: Report Repair

Leia arvude reast 1) paar 2) kolmik, mille summa on 2020.
Tegime koos Iidaga.

Teine päev: Password Philosophy

Leia stringide / paroolide reast need, mis vastavad mustrile.
Õppisin ära ebavajaliku re.split() ja kasuliku *.count() funktsiooni.

Kolmas päev: Toboggan Trajectory

Leia korduvast mustrist üles puud, millega kelk põrkub.

Neljas päev: Passport Processing

Kontrolli passi atribuutide vastavust etteantud reeglitele.

Esimese osaga (kas passil on kõik atribuudid olemas?) sain kergesti maha, aga teisega jäin hätta.
Vale vastus! Liiga suur! S.t. ma lugesin mõne vale passi õigeks.

Programmi loogikat läbi mõeldes viga ei leidnud.
Trükkisin kõik atribuudid välja, lugesin Excelisse, sortisin ära, vaatasin üle - nagu oleks? 
Aastad on lubatud vahemikes, kõik muu ka.
Ainus kahtlane väli oli passi ID number, kus Excel näitas ka seitsme- ja kaheksakohalisi numbreid. 
Miks? -- sest ta sõi algsed nullid ära, ehkki sisendfailis olid need kujul "00345678". 
Lasin programmil endal kõik õigeks loetud PID atribuudid välja trükkida ja oligi viga käes.
"pid" väljale tegin ainult regexp matchi üheksakohalisele arvule, aga pikkuse kontrolli unustasin.
Seega klappis ka iga kümnekohaline (ja pikem) "arv" 0123456789, lisaks ka a0123456789 jne. 
See oligi ainus viga.

Õppisin: tuletasin meelde re.match() regexp süntaksit.

Moraal 1: Excel EI OLE andmete analüüsiks okei vahend - ta interpreteerib ise väärtusi ja teeb trikke. 

Moraal 2: Sisendi kontroll algab alati pikkuse ja formaadi kontrollist. 

Viies päev: Binary Boarding

Stringi (pardakaardi vöötkood) teisendus kümnendsüsteemi.

Väga lihtne ülesanne, tegin ise ja siis koos Aloga uuesti.

Lõpuks tuli kolm rida normaalset kood.

AoC redditis on mingid mega-lahendused, loe ja imesta.

Kuues päev: Custom Customs

Tolli-küsimuste grupeerimine, hulkade koostamine ja intersection(), lihtne.

Seitsmes päev: Handy Haversacks

Üksteise sisse paigutatud värviline pagas.
Tuli tekstist puu ehitada ja seda siis kahte pidi "läbida".

Õppisin: re.match(), collections.defaultdict().

Puu lugemine õnnestus mõlemas pooles esimese korraga õigesti.

Kaheksas päev: Handheld Halting

Mängukonsooli koodi parandamine.
Assembler :) 

Lõpuks :)

Fännid ägisevad masohhistlikult.
Tänu eelmise aasta intcode praktikumile läks tänane väga lihtsalt.

Sõin progemise kõrvale saia ja sõimlesin facebookis ja olin ikkagi global leaderboardil nr 5260.

Edit: hiljem õppisin ära collections.namedtuple() kasutamise. 

Üheksas päev: Encoding Error

"Šiftist" ehk arvude jadast kombinatsioonide leidmine.
Õppisin kasutama itertools.combinations()-it ka * operaarorit, lisaks ja harjutasin (mittevajalik) deque kasutamist. 

Kümnes päev: Adapter Array

Arvude järjestamine ja järjestuste arvu leidmine.
Counter'i kasutus ja walrus operator.

Pidin juba hakkama atsüklilise suunatud graafi topograafiliste sorteerituste arvu leidmist õppima, a õnneks polnud vaja :)

11. päev: Seating System

Inimesed istuvad reeglite järgi, sisuliselt "game of life".
Vajab tähelepanu detailidele, muidu lihtne.
Teises pooles kulutasin palju aega väikeveale - võrdlesin X indeksit Y maksimumiga.
Test-andmed olid 10x10, töötas.
Päris-sisend 94x92, töötas - peaaegu.

 

12. päev - Rain Risk

Laeva liikumine läbi "N4, L4" sisendite.

Õppisin ära vektorite pööramise.

Alguses tegin ilma.

13. päev - Shuttle Search
Tegin jõu-lahenduse, kus sammuks kõige pikema tsükliga buss.

Testisin test-andmete peal ära ja panin käima. Ei lõpetanud :)

Ise võtsin matemaatika ette.

Jõudsin diofantiliste võrranditeni, lugesin natuke ja andsin alla.

Siis tegin veidi algajalikku aritmeetikat, aga ka see ei viinud mind kuhugi.

Arvutasin CRT jaoks jäägid välja ja söötsin https://www.dcode.fr/chinese-remainder sisse.

Kogu modulaararitmeetika on minu jaoks mingi hägu (ja krüptograafia ka, nii piinlik kui see ka pole).

Hiljem tegin Fazzu suurepärase selgituse järgi õige, kiire, mitte-CRT lahenduse.

 

Jube hea ülesanne:

- sai lahendada puhta jõuga (õige keel ja kõva arvuti),

- sai lahendada puhta matemaatikaga - diofantiliste võrrandite või Hiina jäägiteoreemiga,

- sai lahendada puhta loogikaga,

kindlasti kuidagi veel.

Vaatasin Youtubest kaks videot ära, Robert Xiao ja  Jonathan Paulson. RX kulutas ülesande peale 6:40, leidis kettalt oma vana CRT koodi :), JP luges Wikipediat ja juurutas nullist.

AoC Redditis on väga humoorikad kirjeldused selle ülesande jõuga lahendamisest :)

14. päev: Docking Data

Bittide ja stringidega ja regexpidega nikerdamine. Mul pole praktikat ja läks aeglaselt. Nt tekkis selline kaunis rida nagu location = '{:0>36}'.format(str( bin(int(y.group(1))))[2:]). Aga osa 2 sisuline pool läks nagu niuh. Rekursioon ja sum(dict.values()), laksust õige tulemus.

15. päev: mingi arvudega mäng

Tuli arvutada 2020 ja 3000000. liige van Eck'i täisarvude jadast - https://oeis.org/A181391

16. päev: Ticket Translation

Osa-1: eemalda valed piletid (väärtused reeglitest väljas). Hästi lihtne, ainult lugemine võttis aega. Tegin kiiresti koodi, ei testinud ja plaks - õige tulemus.

Osa-2: OOO ÕUDU. Tuli leida, mis väli on piletil mis kohal. Seda saab (vist) lahendada kahel viisil. a) arvutada, mis väljad mis reeglile vastavad. b) arvutada, mis väljale mis reeglid vastavad. Ilmselt saab ka 20x20 tabeli joonistada. Igatahes valisin ma vale viisi, jooksin vastu seina ja nägin hullult aega, et asjast asja saada. Lõpu tegin Excelis, mida sõiman taaskord, tramuse tehisintellekt selline, aga täna aitas ta mind ikkagi hädast välja. Lõpuks tegin puhta Pythoniga ka. Kõige pikem kood seni, 80 rida, lõpuosa on küll täiesti lambikas. 

Lahe ülesanne!!!

Õppisin: 

map() kasutamist -- x = map(int,blah.split(","))

re.match ja üldse regexp'ide kordus  -- sisendi hekseldamine on sellega mõnusalt lihtne

math.prod -- listi korrutis (Python 8+)

set'ist ainsa (või suvalise) elemendi võtmist -- list(setx)[0]

17. päev, Conway Cubes

3D / 4D rakuautomaadid, cellular automata. 

Panin kõik rakud set()'. Selles sisalduvuse kontroll on lihtne, ei pea massiivi ääretingimustega jamama ja maailm on automaatselt lõpmatu. 

Küll oli siis rõõm, kui neljas dimensioon juurde tuli! Üks ring tsüklit juurde, paari kohta üks argument lisaks - x,y,z asemel x,y,z,w - ja oligi valmis. 

Õppisin: hea andmemudel on kõige alus ja teeb elu mõnusaks :)

Edit: lugesin Reddit'i ja häbenen.

- numpy / scipy abil tehakse hämmastavaid lahendusi, tasub õppida

- itertools.product() annab kõik võimalused (-1,-1,-1,-1 ... 1,1,1,1) vahel: set(product([-1,0,1], repeat=4)), vt ka how to avoid nested loops

- programmi töö ajad on millisekundites

A vähemalt sai mul hästi lihtne ja kohe esimesel katsel veavaba lahendus :)

18. päev, Operation Order

Aritmeetiliste avaldiste lugemine ja arvutamine. Ma tean, et selleks on mingid puud ja algoritmid, kuid ei oska neid üldse. Tegin täiesti lollilt. Lugesin avaldise järjest sisse, rekurseerisin sulgudesse ja arvutasin. Teise osa jaoks ümbritsesin + tehted enne sulgudega. Palju indeksite loogikat (sulgude leidmine), aga töötas.

Lahenduste lõimest ei saa ma täna midagi aru - CS taust on puudu. Ühtegi nii rumalat lahendust kui mul ei paista. Inimesed defineerivad & implementeerivad grammatikaid jne. Operaatorite ülelaadimine + eval on muidugi hea trikk :)

19. - 21. jäid vahele, sest kiire nädalavahetus ja olid vist ka rasked ülesanded. Ehk teen järele?

19. päev, Monster Messages, ababbb... sõnumite valideerimine isetehtud grammatikaga

Esimene osa - vaatasin, ei osanud üldse. Ma peaks hakkama grammatikat juurutama? Ei. Siis võtsin netist vihje "build regexp". Esimene osa lahendus sellega suht lihtsalt, natuke rekursiooni ja valmis. 

Teine osa - jätan tegemata. Või siis teen millalgi, kui olen palju targem.

20. päev, Jurassic Jigsaw, pusle kokkupanek kaardi tükkidest

Esimene osa - nurkade leidmine. Läks lihtsalt, lugesin kokku omavahel "klappivad" küljed ja leidsin need ruudud, millel neid oli kõige vähem. 

Teine osa... teen, millalgi, võib-olla :) Tundub jube. Ma saan aru, kuidas seda teha - tuleb hakata kaarti ühest nurgast kokku joonistama. Ja on abiks teada, et pusle tükkide servad klapivad 1:1. Aga hirmus palju tööd on. Redditis on hädaldused "mitusada rida koodi" ja "kümneid tunde progemise aega". 

21. päev, Allergen Assessment 

Retseptide ja allergeenide vastavus. Läks tohutult aega ja sada ülesande läbi lugemist, enne kui aru sain, KUIDAS seda loogilisel tasemel lahendada. (Tuli kõik retseptid, milles sisaldus allergeen X, omavahel ära ristata. Tulemus oligi allergeeni X sisaldav komponent.) 

Progemise mõttes oli 1. osa väga lihtne - Pythoni set, dict ja sisalduvuse kontrollid on imemugavad. Teise osa tegin lihtsalt käsitsi (vaja 8 sõna järjestada).

Redditis sama ülesande jaoks kasutusel: Hopcroft-Karpi algoritm, Z3 solver ja muu hai-tekk.

22. päev: Crab Combat

Kaardimäng. Esimene osa lihtne, teine osa keskmine - tavaline rekursioon. Mida õppida nagu ei ole.

Tegin ära ja läksin Redditit lugema.

Pythoni kood. 15x kiirem kui mul. Loogika ja andmestruktuur (deque) on täpselt samad. Wtf? Hakkasin optimeerima ja:

- debug-printimise kustutamine koos vastavate kontroll-tingimustega andis 1.5 x võitu.

- veel paari if'i tsüklist välja viimine veel 1.5x.

- deque'st stringi vs tuple ehitamine veel 1.5x.

Nüüd on mul näivalt täpselt sama kood mis tundmatul sõbral, aga 4x aeglasem (1.5 vs 6 sekundit).

Ja trikk või süüdlane on... parampampaa... nested tuples.

Kopeerin iseenda kommentaari:

Ja siis on paar sissekannet allpool puhas loogiline... mõttekäik, mis kiirendab programmi tööd veel KAKSSADA korda. Oh jah. 

23. päev, Crab Cups

Topside liigutamise mäng. Nagu kõik, tegin esimese osa lollakate listidega. Teise (miljon topsi, 10 miljonit ringi) dictionary peale ehitatud ühesuunalise listiga. Tegelikult piisas ka ka teise osa jaoks lihtsast listist ja oli 25% kiirem kui dict.
Redditis on näha, et enamik mõtlesid üle ja uurisid kõigepealt mingeid ring_buffer ja deque sorti struktuure. 

24. päev, Lobby Layout, kuusnurkne plaadistik ja "game of life". 

Ooo needust.

Kõigepealt lugesin läbi kogu https://www.redblobgames.com/grids/hexagons/. Tundus jube segane. Siis joonistasin kõik paberi peale üles - sai päris lihtne. Esimene osa saigi kärmelt valmis ja õige. Ka teine osa tundus lihtne. Kirjutasin valmis ja...

.. ei tööta. Annab test-andmete peal vale tulemuse.

Wtf.

Kulutasin tunde debugimise peale. Lõpuks tegeles suurem osa koodist kuusnurkse struktuuri eri viisil väljatrükkimisega. 

Lõin käega, tegin pausi, seejärel kirjutasin esimese osa nullist uuesti. 
Ja see lahendas probleemi. Mul oli juurutusviga - kaks rida omavahel vahetuses. 1. osa tulemus tuli sellega õige, aga 2. osa sisend vale. Kui see sai korda, läks ka 2. osa kood laksust käima ja oligi õige.

Õppisin: palju kuusnurkade kohta. Aga eeskätt seda, et uusi asju on raske õppida. Kõik 3D ja kompleksarvudega lahendused - ma ei saa neist aru. :(((( Ja ei saagi. 

25. päev, Combo Break ehk Diffie-Hellman murdmine

Veidi moodul-aritmeetikat. Ma ei saa sellest eriti aru, aga see lahendus puhta jõuga. Kuid nagu ikka, tehakse Redditis tõelist keemiat, vabandust, matemaatikat :) 

Üldine moraal

- Kontrolli alati, kas sisendi viimane rida loeti sisse ja läks ka korrektselt arvesse.

- Kui on täielik ummik, siis kirjuta programm nullist uuesti.

- Pythoni andmestruktuurid ja muud võimalused on täielik mõnu. 

Lugemist

"Kuidas nad nii kiired on???" -- Redditi lõim kiirest progemisest. Kaheksanda päeva ülesanne oli "loo virtuaalarvuti" ja esimene leaderboardi kirje tekkis 90 sekundiga. Pika jutu kirjutab xiaowuc1 ise - 8. päeva võitja ja praegune edetabeli esimene. 

betaveros, tänavune võtja, kirjutab programmeerimisest.

"Going fast in Advent of Code" - https://kevinyap.ca/2019/12/going-fast-in-advent-of-code/

AoC 2020 põhjalike selgitustega: 

https://github.com/mebeim/aoc/blob/master/2020/README.md

Ülesannete lahendamise suhteline raskus / aeg, edetabeli täiumise aja alusel. Selle aasta ülesanded on võrdlemisi lihtsad. Eelmise aasta keskel oli leaderboard'i täitumise aeg (100 inimest on mõlemad osad ära lahendanud) umbes 45 minutit. Sel aastal on 15.

Mul on hetkel tehtud kõik ülesanded peale päevade 19, 20, 21. Ühe ülesande (busside ajagraafikute teine osa) jaoks kasutasin Mart Oruaasalt pärit selgitust. Muud on olnud aga tehtavad ja üsnagi lihtsad. 

Fazz selgitab (jube hästi): https://fazz.github.io/tags/aoc2020/