AoC 2020, 13. päev

Ülesanne

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

Sebi mis Sa sebid, algarvud tulevad lõpuks ikka nurgast

Lõpuks ometi ülesanne, mis hingele (loe: võtab kõvasti vanduma, sest tagumikutunne ütleb, et lahendus on siinsamas, aga pea ei jaga ära pühapäeva hommikul). Kass istus ainult vaikselt kõrval ja kuulas hingestatud pobinat kolmes kohalikus keeles.

Esimene osa on suhteliselt lihtne (mis muidugi ei tähenda, et ma poleks suutnud maailma kõige tobedamat programmeerimisviga sisse teha esimese hooga).

Valem konkreetse bussi ooteaja saamiseks on järgmine:

$$ ooteAeg = bussiNr \cdot (\lfloor \frac{saabumisAeg}{bussiNr} \rfloor + 1) - saabumisAeg $$

Nendest ooteaegadest on vaja valida vähim ja arvutada vastus. Hoolikalt tuleb tähele panna, mida vastuseks küsitakse: bussi numbri ja ooteaja korrutist. See on tavaline trikk, millega vaip alt ära tõmmata.

Teine osa on natuke krõbedam, juba ülesandepüstituses on hoiatatud, et arvud lähevad väga suureks. Enamasti tähendab selline hoiatus, et „ära rumaluke kuluta elektrit CPU ringiajamiseks, niikuinii sellest midagi kasu ei ole, leia optimaalne lahendus.“

Esiteks on vaja tähele panna, et kõik bussinumbrid on algarvud ja matemaatiliselt tähendab algarvuliste tsüklite kokkupuutepunktide leidmine nende algarvude mingil viisil omavahel läbikorrutamist. See tuleneb aritmeetika põhiteoreemist¹ – arv, mis jagub täpselt mingite algarvudega on saadav ainult nende läbikorrutamise teel.

Antud juhul komplitseerib ülesannet see, et vajalikud väärtused on nihkega, ehk lihtsalt korrutamisest ei piisa.

Küll on võimalik koostada päris lihtne iteratiivne algoritm (jällegi: väljamõtlemine kell 7:15 hommikul ei olnud lihtne ja lisaks Pythonile oli vaja kolme kohalikku keelt).

1. Võta esimeseks sammuks esimese bussi samm (sest see on see, mis peab lõpuks vastuse andma). Kui optimeerida tahad, võta kõige suurema numbriga bussi samm, aga siis pead vaatama, kuidas lõpus leida esimese bussi saabumise aega.
2. Hakka ajajoont järjest läbi käima.
3. Leides mõne bussi, mis saabub vajaliku nihkega pärast esimest bussi, hakkab kehtima uus reegel: kõik sobivad ajad esimese bussi saabumiseks on esimese bussi numbri ja tolle teise bussi numbri kordsed, ehk samm läheb kohe palju pikemaks. Iga sedasi leitud bussi korral tuleb sammu vastavalt korrutades kasvatada.
4. Goto 2, kuniks korrutis sisaldab kõiki bussinumbreid.

Minu sisendi puhul tuleb lahendus (suurusjärgus $10^{15}$) sedasi 575 sammuga (kaks tsüklit üksteise sees).

Õppetund: joonista arvuridasid rohkem paberi peale välja, see ajab intuitsiooni paremini tööle.

Alternatiivne variant 2. osa lahendamiseks

On olemas ka formaalselt parem viis 2. osa lahendamiseks, ennekõike neile, kes koolis ei maganud. Ma kirjutasin need võrrandisüsteemid isegi välja, aga mingil veidral kujul ja üldse ei saanud aru, et tegu on Hiina jäägiteoreemiga². Häbi, ma olen ju tegelikult kirjutanud tootmissüsteemi koodi, kus on Hiina jäägiteoreem sees.

Ühesõnaga, tekivad võrrandid, kus $z$ on otsitav ajahetk:

$$ z\mod bussiNr_0 \equiv 0 $$ $$ z\mod bussiNr_2 \equiv (bussiNr_2 - 2) $$ $$ z\mod bussiNr_7 \equiv (bussiNr_7 - 7) $$

Jne.

See võrrandisüsteem on puhtal kujul lahendatav Hiina jäägiteoreemi abil, nagu näiteks autori lahkel viidatuna siin: https://hastebin.com/userumorow.apache.

See algoritm on ka optimaalsem, minu sisendi puhul vaid 49 iteratsiooni.

Lahendus

Lahenduskäik siin: https://github.com/fazz/aoc/blob/master/aoc2020/day13.py