AoC 2020, 19. päev

Ülesanne

Siin: https://adventofcode.com/2020/day/19

Kuidas läheb? Ah, tead, regulaarselt…

Ülesandele peale vaadates on kohe selge, et reeglid kujutavad endast lihtsamat sorti regulaarse keele grammatikat (eriti oluline on selle kinnitamiseks fraas there are no loops in the rules). Arvud on mitteterminalid ning tähed terminalid.

Sisendis antud reeglite transleerimine Pythoni $re$ jaoks sobivateks reegliteks on suuresti tagajalgade töö, kuigi esimesel katsel suutsin ma ikka üle mõtelda ja selle liiga keeruliselt lahendada.

Teine osa on huvitavam ja seal tõmmatakse hooletul lugejal vaip alt ära. Pakutud muudatus – reeglite asendamine – on nimelt üsna keeruline viis seda ülesannet lahendada.

Esimene pool polegi niiväga keeruline, selline rekursioon on regulaaravaldisega väljendatav kujul $"(42)+"$, seega jääb keel ikka regulaarseks. Teine pool aga tekitab avaldise $"(42)\{ n \}(32)\{n\}", n \geq 1$, mis ei kirjelda enam regulaarse keele sõna.

Õnneks on aga sisendis olevad sõnad piisavalt lühikesed, nii et väärtusi $n\gt 5$ pole vaja ning selle avaldise saab asendada lihtsalt veidi mölakama regulaaravaldisega.

Trikk on neid asendusi teha mitte originaalsetes reeglites vaid $re$ regexi koostamise algoritmis sobiva koha peal.

Esimene osa valmis 7:37, teine osa 8:01.

Lahendus

Lahendused, kaks tükki, teine 2x lühem kui esimene: https://github.com/fazz/aoc/blob/master/aoc2020/day19.py