Spet ena lepa naloga, predvsem drugi del. Lepa je, ker ni potrebno programirati, temveč razmišljati. Programiranje je potem trivialno.
Spet bomo izpustili zgodbico: imamo seznam pozitivnih celih števil, ki jim dodamo še 0 in še število, ki je za 3 večje od največjega. Števila so sicer v naključnem vrstnem redu, a če bi opazovali, katera števila so v seznamu, katera ne, bi odkrili, da nikoli ne manjka le eno; luknje med njimi so vedno dolge dve števili. V bistvu nas zanima, koliko je zaporednih števil in koliko lukenj, v katerih manjkata dve števili. To dvoje moramo zmnožiti. (Ta opis ni preveč dober. Če se ne spomnite naloge in ga ne razumete, poglejte originalni opiz, ki pa je precej dolg.)
Očitno bo potrebno števila urediti, zato jih preberimo kar v sorted
, dodamo pa še 0 in številko, ki je za 3 večja od največje; tako hoče naloga. Potem z zip
sestavimo razlike, jih preštejemo in zmnožimo, kar moramo.
from collections import Counter
s = sorted(int(x) for x in open("input.txt"))
s = [0] + s + [s[-1] + 3]
jumps = Counter((y - x for x, y in zip(s, s[1:])))
print(jumps[1] * jumps[3])
1904
Ta je pa zanimiv. Števila moramo zložiti v zaporedje od 0 do največjega, pri čemer smemo kakšno število tudi izpustiti, vendar razlika med zaporednima številoma nikoli ne sme biti večja od 3. Koliko takšnih zaporedij obstaja?
Poglejmo zaporedje
0, 1, 2, 3, 4, 7, 8, 9, 10, 11, 14, 17, 18, 19, 20,
Na kratko: do 11 pridemo tako, da k vsem možnim potem do 8 do 9 in do 10 pripišemo 11. Poti do 11 je torej toliko, kot poti do 8, 9 in 10 skupaj. Takšno velja za vsa števila, od 0 do konca. Razen, seveda, za tista, ki manjkajo.
In tako naprej.
Zdaj, ko smo to razmislili, je programiranje trivialno.
from collections import defaultdict
ways = defaultdict(int)
ways[0] += 1
for jolt in s:
for i in range(1, 4):
ways[jolt + i] += ways[jolt]
print(ways[s[-1]])
10578455953408
Do števila n
lahko pridemo na toliko načinov, na kolikor lahko pridemo do n - 1
, n - 2
in n - 3
. Do števila 0 pa pridemo na 1 način. To nam da naslednjo preprosto funkcijo.
def ways(n):
return n == 0 or sum(ways(x) for x in range(n - 3, n) if n in s)
ki pa je ne bomo pognali, ker bi tekla v nedogled, saj bi zelo pogosto spraševala za eno in isto število. Da se temu izognemo, bomo dodali dekorator @lru_cache(3)
, s katerim bomo dosegli, da si bo funkcija zapomnila zadnja dva rezultata in jih ne računala vedno znova. (Seveda bi lahko vzeli več kot dva, vendar to že zadošča!)
Mimogrede ugotovimo, da ni nobene potrebe, da bi bil seznam s
urejen. Iz estetskih razlogov pa je lepo, če je množica, saj bo napogostejša operacija, ki jo bomo potrebovali, in
. (V resnici pa je število števil tako majhno, da je čisto vseeno, ali so shranjena v množici ali seznamu.)
from functools import lru_cache
s = {0} | {int(x) for x in open("input.txt")}
@lru_cache(2)
def ways(n):
return n == 0 or sum(ways(x) for x in range(n - 3, n) if x in s)
ways(max(s))
10578455953408