Prehod čez reko

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. Zadnji kamen je ž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.

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

Nalogo lahko rešite na različne manj učinkovite načine. Na enega kar počasnega, vendar potencialno delujočega, namiguje spodnja koda:

>>> from itertools import combinations
>>>
>>> kamni = [1, 2, 3, 4, 7, 8, 10, 11, 13]
>>>
>>> list(combinations(kamni, 7))
[(1, 2, 3, 4, 7, 8, 10), (1, 2, 3, 4, 7, 8, 11), (1, 2, 3, 4, 7, 8, 13), (1, 2, 3, 4, 7, 10, 11),
(1, 2, 3, 4, 7, 10, 13), (1, 2, 3, 4, 7, 11, 13), (1, 2, 3, 4, 8, 10, 11), (1, 2, 3, 4, 8, 10, 13),
(1, 2, 3, 4, 8, 11, 13), (1, 2, 3, 4, 10, 11, 13), (1, 2, 3, 7, 8, 10, 11), (1, 2, 3, 7, 8, 10, 13),
(1, 2, 3, 7, 8, 11, 13), (1, 2, 3, 7, 10, 11, 13), (1, 2, 3, 8, 10, 11, 13), (1, 2, 4, 7, 8, 10, 11),
(1, 2, 4, 7, 8, 10, 13), (1, 2, 4, 7, 8, 11, 13), (1, 2, 4, 7, 10, 11, 13), (1, 2, 4, 8, 10, 11, 13),
(1, 2, 7, 8, 10, 11, 13), (1, 3, 4, 7, 8, 10, 11), (1, 3, 4, 7, 8, 10, 13), (1, 3, 4, 7, 8, 11, 13),
(1, 3, 4, 7, 10, 11, 13), (1, 3, 4, 8, 10, 11, 13), (1, 3, 7, 8, 10, 11, 13), (1, 4, 7, 8, 10, 11, 13),
(2, 3, 4, 7, 8, 10, 11), (2, 3, 4, 7, 8, 10, 13), (2, 3, 4, 7, 8, 11, 13), (2, 3, 4, 7, 10, 11, 13),
(2, 3, 4, 8, 10, 11, 13), (2, 3, 7, 8, 10, 11, 13), (2, 4, 7, 8, 10, 11, 13), (3, 4, 7, 8, 10, 11, 13)]
>>>
>>> list(combinations(kamni, 8))
[(1, 2, 3, 4, 7, 8, 10, 11), (1, 2, 3, 4, 7, 8, 10, 13), (1, 2, 3, 4, 7, 8, 11, 13), (1, 2, 3, 4, 7, 10, 11, 13),
(1, 2, 3, 4, 8, 10, 11, 13), (1, 2, 3, 7, 8, 10, 11, 13), (1, 2, 4, 7, 8, 10, 11, 13), (1, 3, 4, 7, 8, 10, 11, 13),
(2, 3, 4, 7, 8, 10, 11, 13)]

... in tako naprej in nazaj. Ne samo za 7 in 8, temveč od 1 do len(kamni).

Enega nič prida hitrejšega, ampak prav tako delujočega, nakazuje tole:

>>> from itertools import combinations_with_replacement
>>>
>>> list(combinations_with_replacement([True, False], 4))
[(True, True, True, True), (True, True, True, False),
 (True, True, False, False), (True, False, False, False),
 (False, False, False, False)]

Namesto 4 bi imeli len(kamni). Pa razmislite, kaj bi s toliko True-ji in False-i, kolikor je kamnov.

Na tak ali drugačen način lahko sestavite vse možne poti in preverite, koliko je legalnih.

Očitno boljši način je, da poskusite sestaviti vse možne poti.

Pri razmišljanju vam lahko pomaga, če poskusite rešiti nalogo ročno, brez računalnika. V resnici sploh ni težko. Vendar ... ne poskušajte dejansko sestavljati in šteti. Trik je v tem, da število poti do nekega kamna izračunaš 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č).

Pravilni odgovor za gornji seznam je (najbrž) 35, (gotovo pravilna) odgovora za example.txt in input.txt pa sta 19208 in 10578455953408. Z naivnimi rešitvami bo možno rešiti gornji primer, drugega najbrž ne, tretjega pa gotovo ne. 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