skip to content W3C SVG

AoC 2022, 24. päev

Publish date: Dec 24, 2022
Tags:

Ülesanne

Siin: https://adventofcode.com/2022/day/24

Päkapikud on jobud ja kaotavad oma küpsised ära

Ülesanne, mis näeb esmapilgul karvasem välja kui tundub.

Paar viisi, kuidas sellest ülesandest mõtelda, et asi lihtsam oleks:

  • tuulte võimalike asendite arv tasapinnal on lõplik, nimelt võrdne mänguplatsi mõõtmete vähima ühiskordsega;
  • ruum, kus tuleb liikuda, ei ole mitte kahemõõtmeline plats, vaid kolmemõõtmeline ruum, mille üheks dimensiooniks on aeg.

Kõige lihtsam lahendus esimesele osale on teostada laiuti otsing (BFS) mööda vabu punkte ruumis, jättes pidevalt sammude arvu meelde ning ning esimene samm lõpp-positsioonile ongi võimalik lühim tee.

Tuulte kõikvõimalikud asendid on seejuures võimalik räsitabelisse ette arvutada, ning liikumisel saab seetõttu odavalt järgi vaadata, kas konkreetne punkt on antud ajahetkel tuultest vaba või mitte.

Teise osa lahendamisel tuleb sedasama protseduuri lihtsalt kaks täiendavat korda läbi teha, vahetades vahepeal algus- ja lõpp-punktid omavahel.

Küll aga on selline lahendus suhteliselt aeglane, Python 3 realisatsioon töötab kahe osa peale kokku umbes viis sekundit.

Ideid, kuidas lahendust kiirendada.

  • Mulle eraldatud sisendandmed olid küllalt eripärased, nimelt sellised, mille puhul mõõtmete vähim ühiskordne on suhteliselt suur ($100 = 2^2 * 5^2, 35 = 5 * 7, lcm = 2^2 * 5^2 * 7 = 700$). Foorumitest on lugeda selliste sisendandmete kohta, mille puhul on vähim ühiskordne märksa väiksem. Küll aga saab ka sel puhul optimeerida ettearvutatavate platside kogust (ja seega vabade punktide järgivaatamise kiirust): horisontaalsuunas ning vertikaalsuunas liikuvate tuulte positsioone tuleb vaadata eraldi, siis on võimalik $700$ ettearvutatud platsi asemel piirduda $100 + 35 = 135$ platsiga. Kuna minu sisendandmete puhul oli teise osa tulemuseks $720$ sekundit, oli kõigi täielike platside ettearvutamine vähese kasuteguriga trikk.
  • Lihtsa laiuti otsingu asemel kasutada algoritmi A* kohandatud varianti, mille puhul kasutatakse heuristilise mõõduna parasjagu uuritava punkti Manhattani distantsi lõpp-punktist. See võimaldab esimeses järjekorras tegeleda selliste punktidega, mis asuvad sihtkohale lähemal, vähendades läbivaadatavate variantide hulka oluliselt.

Selliste trikkidega in võimalik viia lahenduse mõlema poole tööaeg kokku umbes 800ms kanti. Vähe? Palju? Ei tea. Kompileeritavates keeltes on bitinikerdamisega palju kiiremaid lahendusi saavutatud, aga kas see ka Pythonis võimalik on, arvutusliku keerukuse arvelt, ei tea.

Lahendus

Lahendus: https://github.com/fazz/aoc/blob/master/aoc2022/day24.py