AoC 2023, 13. päev

Ülesanne

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

Lahendus

Esimene pool

Esimese poole lahendamiseks tasub appi võtta kaks lihtsat kuid tõhusat tööriista: Hammingi distants ning maatriksi transponeerimine.

Hammingi distants on ühepikkuste stringide erinevuse mõõt, mis ütleb, kui mitut positsiooni tuleks emmas-kummas stringis muuta, et stringid ühesuguseks muuta.

Lisaks tasub tähele panna, et küsitakse peegeldusjoonest üles ning peegeldusjoonest paremale jäävate ridade-veergude koguseid. Kui me kohtleme iga üksikut sisendit kui maatriksit, saab selle probleemi sõnastada kui maatriksis $A$ peegeldusjoonest ülespoole jäävate ridade arvu ja vastavas transponeeritud maatriksis $A^T$ peegeldusjoonest ülespoole jäävate ridade arvu. See võimaldab kasutada ülesande kahe alamosa lahendamiseks sama algoritmi, muutes vaid sisendit.

Algoritm:

• Teisenda maatriks vektoriks, mille iga element on kahe kõrvutise maatriksi rea vaheline Hammingi distants.
• Iga $0$-väärtuse kohta uuri, kas vastavest ridade paarist üleval ja all sama kaugel olevate ridade vahel on paarikaupa Hammingi distants $0$. Kui jah, siis ongi tegu otsitava peegeldusega.

Sisendandmed on sellised, et iga sisendi elemendi (maatriksi) ja tema transponeeritud maatriksi kohta on täpselt üks selline peegeldus, kuigi kõrvutiolevad samasuguseid ridu võib olla veel.

Teine pool

Teise poole jaoks saab esimese poole algoritmi laiendada, seejuures nii, et mõlemad pooled saab lahendada korraga. Kui aga vaadata algoritmi eraldi, siis:

• Jätka esimeses poole leitud vektoriga, ignoreerides juba leitud peegeldust.
• Leia selline peegeldus, mille puhul välistab esimese poole lahendiks olemise ainult üks Hammingi distants väärtusega $1$.
• Seejuures on vaja käsitleda erijuhtu, et peegelduspind ei ole tuvastatud mitte distantsi $0$ vaid hoopiski $1$ järgi, st. veaparandust vajav rida on vahetult peegelduspinna kõrval.

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