AoC 2023, 8. päev

Ülesanne

Siin: https://adventofcode.com/2023/day/8

Lahendus

Esimene pool

Ülesande esimene pool on küllalt lihtne tee läbisammumise ülesanne, tuleb ainult jälgida seda, et sisendi esimesel real antud valikujuhised moodustavad lõpmatu ringi, st. lõppu jõudes tuleb sujuvalt algusest jätkata.

Teine pool

Ülesande teine pool on justkui tavaline vähima ühiskordse leidmine, sest võib ometi eeldada, et kõigi kummituste läbi käidud teed moodustavad mingi kindla pikkusega tsükli ning ülesande vastuseks on selliste tsüklite pikkuste vähim ühiskordne.

Küll aga tekib ülesandepüstitust vaadates paar ebamugavad küsimust:

• Kas võib olla nii, et kummitus, mis alustab positsioonilt 11A, lõpetab positsioonil 22Z?
• Kas võib olla nii, et kummitus, mis alustab positsioonilt 11A, lõpetab küll positsioonil 11A, kuid läbib seda positsiooni veel ühe kuni mitu korda, enne kui jõuab oma täistsükliga lõpuni?
• Lisaks on võimalikud veel mõned variatsioonid eeloleval teemal…

Vastus esimesele küsimusele on jaatav, sest eksisteerib AAA, aga mitte AAZ (vähemalt minu sisendandmetes).

Vastus teisele küsimusele on eitav, aga seda peab lihtsalt eksperimentaalselt kontrollima.

Tulemusena tähendab see, et ülesanne on märksa lihtsam kui ta mingis absoluutvariandis olla võiks.

Lahendamiseks on vaja jälgida iga kummitust tema teekonnal, kuniks on teada kõigi kummituste läbitud kinniste teekondade pikkused. Teekond on lõppenud, kui kummitus saabub mingisse paika, mille nimi lõppeb Z-tähega.

Seejärel on vaja mõne käepärase meetodiga, näiteks algarvudeks tegurdamise abil, leida nende teepikkuste vähim ühiskordaja.

Ja nagu AoC-s tihti kombeks, võib pärast teise osaga tutvumist avastada, et esimene ja teine osa lahenduvad üsna sarnasel viisil, vahe on ainult mõnes üksikus parameetris. Selles ülesandes on erinevuseks see, kuidas tuvastada esimene positsioon (AAA vs xxA).

Lahenduskäik: https://github.com/fazz/aoc/blob/master/aoc2023/day08.py