AoC 2020, 3. päev
Ülesanne
Siin: https://adventofcode.com/2020/day/3
Küll on kena kelguga
Mulle kohe meeldivad sellised ülesanded, mida saab modulo aritmeetikaga lahendada. Ei teagi miks, amatöörkrüptograafi rõõmud vist.
Teisalt on see selline ülesanne, mis on meelega sõnastatud hästi keerulisena ja kunst on ära tabada, milles on tegelikult uba. Brace yourselves, kes esimest aastat ülesandeid lahendavad, see läheb iga päevaga aiva hullemaks – eelmisel aastal oli kaalukeeleks vist 18. päeva ülesanne, kus inimesed jäidki ülesandepüstitusse kinni, selmet vaadata graafi, mille kõrvad sealt tagant välja paistsid. Ülesanne taandus suuresti tavaliseks rändkaupmehe probleemiks.
1. osa
Juba esimeses osas tõmmatakse lahendajal vaip alt ära: the same pattern repeats to the right many times. On nähtud lahendusi, kus kopeeritakse mänguvälja nii mitu korda kui paremale alla mineva diagonaali mahutamiseks vaja on.
Korrektne lahendus on palju lihtsam – mõtle nii, et trajektoor ei lähe mitte järgmisele samakujulisele mänguväljale, vaid „keerdub ümber enda“ ja siseneb väljale uuesti vasakult. Selle väljendamiseks on tuntud matemaaline võte jäägiga arvutamine (või peenemalt „liitmine jäägiklassirühmas“): $$x\leftarrow x + \Delta x\pmod L$$
($\Delta x$ on ülesandes ette nähtud horisontaalne nihe ja $L$ rea pikkus).
Selle valemi töötamiseks on vaja küll kasutada andmestruktuurides nullist algavaid indekseid, aga õnneks on see enamustes programmeerimiskeeltes standardkäitumine.
Näiteks, „üks alla kolm paremale“ näeb illustreeritult välja nii (horisontaalsed positsioonid 0, 3, 6, 9 mod 7 = 2, 5):
O......
...X.#.
..#..#O
..O.#..
....#X.
2. osa
Teine osa on suuresti esimese korduv rakendamine, aga seal üks nurgajuhtum: nimelt on üks võimalikest trajektooridest suunatud allapoole suurema sammuga kui üks rida. See tekitab justkui vajaduse eraldi käsitleda mänguvälja alumisest piirist üleminekut, aga siinkohal tasub hoolikamalt vaadata sisendit: minuteada on kõik võimalikud sisendid paarituarvulise ridade arvuga, mis tähendab, et kahese sammuga astudes lõppeb sõit täpselt alumisel real ja mingit erikäsitlust võrreldes ühese sammuga vaja ei ole ($1 + n\cdot2$ on paaritu).
Aja peale programmeerides ei ole kõige universaalsema lahenduse otsimine üldse oluline. 😇
Lahendus
Lahenduskäik siin: https://github.com/fazz/aoc/blob/master/aoc2020/day03.py