Branje podatkov je trivialno.
import numpy as np
grid = np.array([[int(c) for c in v.strip()] for v in open("example.txt")])
h, w = grid.shapeRešitev - no, korak rešitve - tokrat izdajmo v enem zamahu in tokrat bo v funkciji.
def step(grid):
grid += 1
flashed = new = grid > 9
while np.any(new):
for gdx0, gdx1, ndx0, ndx1 in ((0, -1, 1, w), (0, w, 0, w), (1, w, 0, -1)):
for gdy0, gdy1, ndy0, ndy1 in ((0, -1, 1, h), (0, h, 0, h), (1, h, 0, -1)):
grid[gdy0:gdy1, gdx0:gdx1] += new[ndy0:ndy1, ndx0:ndx1]
new = (grid > 9) & ~flashed
flashed |= new
grid[flashed] = 0
return np.sum(flashed)flashed in new bosta bool-ovi
matriki enake velikosti kot grid. flashed bo
povedala, katere hobotnice so se zasvetile v tem koraku,
new pa katere so se zasvetile znotraj koraka, zaradi
sosedov.
V začetku povečamo vse vrednosti za 1 in si zapomnimo,
kaj se je zastevilo, grid > 9.
Dokler se posveti kaj novega, while np.any(new), k
vsakemu polju grid prištejemo 1 za vse sosede,
za katere new pravi, da so se pravkar zasvetili. To bi
lahko napisali z zaporedjem osmih prištevanj v slogu
grid[0:-1, 0:-1] += new[1:h, 1:w]
grid[0:-1] += new[1:h]
grid[0:-1, 1:w] += new[1:h, 0:-1]in tako naprej. Vendar se mi zdi to varneje zapisati z zanko. Stvar
okusa. Glavno je, da povečamo vse elemente grid, ki jih je
potrebno povečati. (Gornja koda poveča števec pri srednji hobotnici, kot
da bi imeli grid += new. To ni čisto prav, vendar ne bo
škodilo; berite naprej.)
Nato pride pomembna logika: na novo so se zasvetila tiste hobotnice,
pri katerih je števec večji od 9 in se niso svetile že od
prej,
new = (grid > 9) & ~flashedTe tudi dodamo med svetleče se hobotnice,
flashed |= newTo torej ponavljamo, dokler se ne zgodi, da se nobena hobotnica ne
zasveti več na novo. Nato nastavimo števec svetlečih se hobotnic na
0,
grid[flashed] = 0(Zato tisti grid += new ne škodi: števec teh hobotnic
bomo tako ali tako nastavili na 0.)
Funkcija na koncu vrne število vseh hobotnic, ki so se v tem koraku zasvetile.
Funkcijo uporabimo za oba dela naloge. Prvi zahteva, povemo, koliko hobotnic se zasveti v 100 korakih.
print(sum(step(grid) for _ in range(100)))1656
V drugem delu nas zanima, po koliko korakih se prvič hkrati zasvetijo
vse hobotnice. Za to naredimo zanko prek funkcije
itertools.count(n), ki šteje od n (privzeta
vrednost je 0) do neskončno. Šteli bomo od 101, saj je prvi korak, ki ga
bomo naredili, že sto prvi.
from itertools import count
for steps in count(101):
if step(grid) == grid.size:
break
print(steps)195