AoC 2023, 12. päev

Ülesanne

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

Lahendus

Esimene pool

Ülesandepüstitus ja pilguheit sisendile ütleb, et esimene pool on lahendatav suhteliselt lihtsa jõumeetodiga, nagu tavaliselt. Ja jällegi on õhus kahtlus, et teine pool viib keerukuse lakke. Seetõttu pole esimest poolt eraldi erilist mõtet analüüsida, vaataks parem, mis teises pooles juhtub.

Oluline on lihtsalt aru saada, et iga mustris esinev küsimärk tähendab üht otsustamata valikut kahe valikuvariandi vahel, seega tuleb $n$ küsimärgiga mustri jõumeetodiga lahendamiseks vaadata läbi $2^n$ varianti. Kuivõrd $n$ väärtused jäävad alla $20$, ei ole sellest erilist probleemi.

Teine pool

Teises pooles arusaadavalt nõnda lihtsalt ei pääse: kõige keerulisem muster minu sisendis nõuaks naiivselt lahendades $2^{94}$ variandi läbivaatamist ja see ei ole mõeldav.

Mida teha? Appi tõttab dünaamiline planeerimine.

Dünaamilise planeerimise aluseks on suuremast probleemist mingi lihtsamini lahendatavate väiksemate probleemide eraldamine, mille lahendusi saab seejärel omavahel kombineerida suurema probleemi lahendamiseks.

Sisendiks on meil muster selle kohta, kus katkised allikad asuda võiks ning katkiste allikate gruppide loetelu.

Üks võimalus on arvutada, kui mitu korda mahub mingi äärmine alamosa gruppidest mingisse mustri sama ääre alamosasse, alates ühest üksikust grupist.

Selline lähenemine annab võimaluse iga grupi puhul läbi vaadatavat mustri ruumi oluliselt piirata: kõige parempoolsema grupi jaoks jääb maksimaalselt selline osa mustrist, mille pikkus on $len(pattern) - sum(groups[:-1]) - len(groups[:-1])$, ehk siis vasakule jääb selline osa mustrist, mis peab ära mahutama kõik ülejäänud grupid ja nendevahelise tühja ruumi. Seda valemit on võimalik veel täpsustada, kuid isegi sedasorti robustne hinnang annab tulemuseks piisavalt kiire algoritmi.

Samal viisil on võimalik hinnata ka vasakpoolse üksiku grupi jaoks sobivat “akent”.

Kõige lihtsam ja selgem lahendus tundubki olevat alustada vasakult ning iga vasakpoolseima grupi võimaliku asetuse jaoks arvutada rekursiivselt välja, kui mitmel viisil ülejäänud grupid ülejäänud mustrisse sobivad. S.t. parempoolse osa töötlemisel koheldakse seda jällegi kui terviklikku sisendit ja hakatakse vasakpoolseima allesjäänud grupi jaoks võimalikke positsioone leidma.

Minu sisendi puhul tuleb sellise meetodi korral teises poole välja arvutada maksimaalselt 500 erinevat mustri ja gruppide kombinatsiooni ühe sisendi rea kohta ja ülesanne ise lahendub umbes 600 millisekundiga (2 poolt kokku).

Kõrvale võib lugeda ka üksjagu teistsuguse lahenduse kohta. Mulle tundub, et see on parem kui minu oma.

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