Izziv: Prehod čez reko

Reševanje te naloge ne zahteva ničesar, česar se še nismo učili. Program bi se moral izvesti v trenutku.

Naloga

Prečkati je potrebno reko, na kateri so na določenih razdaljah postavljeni kamni. Recimo, da so na razdaljah

0 1 2 3 4 7 8 10 11 13

čevljev od brega. Prvi kamen (0) je na enem, drugi (13) pa že na drugem bregu.

Lahko gremo po vseh kamnih, lahko pa tudi kakšnega preskočimo, vendar moremo stopiti največ tri čevlje daleč. Gornje kamne lahko torej prehodimo takole: 0 1 3 4 7 10 11 13, ali takole: 0 3 4 7 10 13 ali 0 2 4 7 8 11 13 ali 0 1 2 3 4 7 8 10 11 13. Ne moremo pa iti 0 1 3 7 10 13, ker je razlika med 3 in 7 večja od 3 in bi čofnili v vodo.

Vprašanje je: na koliko različnih načinov lahko pride do zadnjega kamna, 13?

Pri razmišljanju vam lahko pomaga, če poskusite rešiti nalogo ročno, brez računalnika. V resnici sploh ni težko in ne zahteva velio časa. Vendar ... ne poskušajte dejansko sestavljati in šteti. Trik je v tem, da število poti do nekega kamna izračunamo iz števila poti do nekih drugih, prejšnjih kamnov.

Branje podatkov

Lahko delate z gornjimi podatki, lahko pa jih preberete iz priloženih datotek example.txt (teh je malo več) in input.txt (teh je še veliko več). V datotekah kamni niso urejeni, poleg tega ne vsebujejo začetne 0. Najlažje jih preberete takole:

kamni = [0] + sorted(int(x) for x in open("input.txt"))

Pravilni odgovor za gornji seznam je (najbrž) 35, odgovora za example.txt in input.txt pa sta 19208 in 10578455953408. S pametno idejo pa lahko celo drugega rešite ročno (no, mogoče s kalkulatorjem).

Izvirna naloga

Naloga je z Advent of Code 2020, naloga 10: Adapter Array, kjer je zgodbica sicer nekoliko drugačna. Gre za drugi del naloge; opis dobite, če rešite prvi del (za kar se morate logirati na stran s svojim računom na githubu, googlu, twitterju ali redditu). Rešitev lahko najdete na spletu ... vendar bi bilo to očitno neumno.

Podatki