AoC 2023, 10. päev
Ülesanne
Siin: https://adventofcode.com/2023/day/10
Lahendus
Esimene pool
Ülesanne taandub sisuliselt kinnise teekonna pikkuse leidmisele. Kuna küsitakse üht konkreetset punkti, võib julgelt eeldada, et kogu teekonnal on paarisarv punkte (paaritu arv alguspunkti arvesse võtmata).
Omaette probleem on see, kuidas tuvastada, kuhu poole alguspunktist liikuma hakata. Loomulikult võib lähteandmetele peale vaadata ja panna programmi kirja, kuhu poole astuda, aga universaalne lahendus võiks võimalikud liikumissuunad ise lähteandmetest leida.
Teine pool
Teine pool on klassikaline arvutusgeomeetria ülesanne: tuleb tuvastada, kas mingi punkt on kinnise kõvera sees või mitte.
Selleks on üks hea lihtne algoritm: tõmmata sirglõik uuritavast punktist kuhugi, mis on kindlasti väljaspool seda kinnist kõverat ning lugeda ära, mitu korda see lõik kõveraga lõikub. Paarisarvuline lõikumiste arv tähendab, et punkt on väljaspool kõverat, paarituarvuline, et kõvera sees.
Üks probleem, mis on vaja kõigepealt lahendada, on saada aru, millist toru elementi kujutab endast alguspunkt. Selleks kulub hästi ära esimese üleande jaoks kirjutatud alustussuundade tuvastamine.
Edasi tuleb kogu plats ühes suunas, näiteks ridade kaupa, läbi käia ning iga tühja punkti kohta otsustada, kas ta on kinnise toruringi sees või mitte.
Ridade kaupa jalutades on toru ületamine ristisuunas (üle |) lihtne, kuid pikisuunas (kahe põlve vahel) natuke keerulisem. Väike trikk siinjuures on lugeda torupõlvesid suurusena 0,5, osad negatiivsed, osad positiivsed, kuid vastassuunalised samade märkidega. Sel juhul on nii, et kahe vastassuunalise põlve ületamine annab tulemuseks 1,0, ehk et toru on ületatud.
Praalimisminutid:
That's the right answer! You are one gold star closer to restoring snow operations. You got rank 387 on this star's leaderboard. [Continue to Part Two]
That's the right answer! You are one gold star closer to restoring snow operations. You got rank 670 on this star's leaderboard.You have completed Day 10!
Lahenduskäik: https://github.com/fazz/aoc/blob/master/aoc2023/day10.py