AoC 2023, 6. päev

Ülesanne

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

Lahendus

Ülesande esimene pool lahendub lihtsa jõuvõttega: tuleb itereerida üle võimalike saavutatavate teepikkuste ning panna kirja, kui mitu neist kvalifitseerub. Jõuvõte on lihtsasti programmeeritav, ei tohi ju unustada, et võistlus käib ka aja peale.

Ka teine pool on sama jõuvõttega lahendatav, ma olen isegi natuke üllatunud, et on, sest siin oleks olnud võimalus lihtsad lahendused välistada.

Aga igal juhul võtab teise poole jõuvõte nii kaua aega, et korraliku programmeerija au ei luba sellise lahendusega leppida.

Kuidas saab kiiremini?

• Lihtne on leida, et peab kehtima tingimus: $rekord \lt vajutuseAeg*(aeg-vajutuseAeg)$ või et siis $-vajutuseAeg^2 + vajutuseAeg*aeg - rekord > 0$.
• Sellest on võimalik tuletada, et ruutvõrrandi $-vajutuseAeg^2 + vajutuseAeg*aeg - rekord = 0$ lahendid võiks anda mingi aimduse sellest, millises vahemikus võiks olla nupuvajutuse ajad, et paadi poolt läbitud teepikkus ületaks kehtiva rekordi.
• Juhul, kui lahendid oleks kõik murdarvulised, oleks võitvate variantide arvu leidmine lihtne: $\lfloor suurem \rfloor - \lfloor väiksem \rfloor$ – see annaks, mitu võitvat sõitu on viimasest mittevõitvast sõidust viimase võitva sõiduni (vajutuse aja järgi lugedes).
• Paraku on osad lahendid täisarvulised ning nende vahe on ühe võrra suurem, kui võitvate sõitude arv, seda peab arvesse võtma.

Samas võib aga võtta ka SymPy või muu sarnase vahendi ning lihtsalt esialgse võrratuse lahendada.

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