AoC 2020, 8. päev

Ülesanne

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

AI parandab Su programmi ise ära ja teeb veel pai ka ja puhub peale

Väikeste virtuaalmasinate kirjutamine ei ole kuigi huvitav, kui seda juba paar korda teinud oled, aga ma siiralt loodan, et mõne noore inimese kehutab selline asi assembleris programmeerima. Obskuursed ja salapärased oskused tulevad elus kasuks.

Esimene osa on lihtne tsüklituvastus - hoia aiva läbitud $pc$-d meeles ja looda, et mälu otsa ei saa (ei ta saa).

Teise osa kiire ja töötav lahendus on lihtne brute force üle kõigi nende instruktsioonide, mis esimese osa jooksul läbi käidi – mitte üle kõigi instruktsioonide, nagu seninähtud lahendused on olnud.

Küll aga pakuvad sellised ülesanded pärastiseks nuputamist teemal „Kuidas Chuck Norrise automaatne programmianalüsaator seda teeks“.

Osa 2, alternatiivne lahenduskäik

Kui kujutada ette sellise programmi täitmisgraafi, siis jaguneb see jämedalt kolmeks:

• Positsioonid, kust saab nõutud lõpp-positsiooni – $A$
• Positsioonid, kuhu saab 0-positsioonist (esimeses pooles täidetav osa) – $B$
• Ülejäänud positsioonid, mis pole kuigi huvitavad.

On oluline, et algse programmi korral kehtib $A\cap B = \emptyset$.

Lisaks on veel üks huvitav hulk: need positsioonid, kuhu saab $B$-sse kuuluvate instruktsioonide modifitseerimisel – $C$. Selle hulga saab programmi algsel sisselugemisel lihtsa vaeva arvutada.

$A$ on leitav lõpp-positsioonist tagurpidi otsinguga.

Ülesande püstitus ütleb, et $|C\cap A|$ on täpselt $1$ ja see ongi see üks koht programmis, mida on vaja muuta – on ainult vaja teha natuke tagajalgade tööd, et kätte saada, milline see positsioon täpselt oli, mille juurde see üks hüpe kuulus.

Lahendus

Lahenduskäik siin (mõlemad variandid 2. osast): https://github.com/fazz/aoc/blob/master/aoc2020/day08.py