Kot skoraj vsako leto tudi letos ena naloga v slogu Conwayeje igre življenja.
Tokrat imamo stole (L
) vmes pa so prazni prostori.
L.LL.LL.LL
LLLLLLL.LL
L.L.L..L..
LLLL.LL.LL
L.LL.LL.LL
L.LLLLL.LL
..L.L.....
LLLLLLLLLL
L.LLLLLL.L L.LLLLL.LL
V prvem delu se ljudje posedajo po stolih tako, da
V drugem delu se pravila spremenijo tako, da ne opazujejo osmih polj okrog sebe, temveč pogledajo v vseh osem smeri in preštejo, v koliko smereh je prvi stol, ki ga vidijo, zaseden.
"Igra" teče tako, da v vsakem koraku naredimo "statistiko" za vse stole in jih izpraznimo ali napolnimo ali pustimo. Po določenem številu korakov pridemo v situacijo, ko se nič več ne spremeni. Naloga je ugotoviti, koliko stolov je takrat zasedenih.
Reševanje naloge bo imelo tri dele:
Naloga ni posebej težka, zato se bomo ob njej predvsem učili lepo programirati. :)
Podatke bomo shranili v seznamu seznamov, poleg tega pa si bomo
shranili še širino in višino polja, w
in
h
.
= [list(x.strip()) for x in open("example.txt")]
seats = len(seats[0]), len(seats)
w, h
seats
Da preverimo vseh osem sosedov polja (x, y)
, bomo
potrebovali dve zanki, takole
for x0 in (x - 1, x, x + 1)
for y0 in (y - 1, y, y + 1)
if (x0, y0) != (x, y) and 0 <= x0 < w and 0 <= y0 < h
S pogojem izločimo srednje polje, ki seveda na šteje, poleg tega pa se moramo znebiti koordinat izven pravokotnika.
Za vsako takšno koordinato moramo preveriti, ali velja
seats[y0][x0] == "#"
. To je True
ali
False
, se pravi 1
ali 0
.
Pa smo končali.
def count_occupied(state, x, y):
return sum(state[y0][x0] == "#"
for x0 in (x - 1, x, x + 1)
for y0 in (y - 1, y, y + 1)
if (x0, y0) != (x, y) and 0 <= x0 < w and 0 <= y0 < h)
Za drugi del je potrebno napisati zanki, ki določita smeri. Potem se pomikamo v tej smeri, dokler ne pridemo do stola ali do roba.
Napisati takšno funkcijo ni posebna umetnost, umetnost pa jo je
napisati tako, da je kratka in se koda na ponavlja. Kakorkoli obračam,
se izkaže, da je še najbolj praktična različica while True
,
v zanki pa break
, kadar pridemo do stola ali roba.
def count_occupied_line(state, x, y):
= 0
occupied for dx in (-1, 0, 1):
for dy in (-1, 0, 1):
if dx == dy == 0:
continue
= x, y
x0, y0 while True:
+= dx
x0 += dy
y0 if 0 <= x0 < w and 0 <= y0 < h:
if state[y0][x0] != ".":
+= state[y0][x0] == "#"
occupied break
else:
break
return occupied
Najprej napišimo funkcijo, ki za vsak stol (ali prazno mesto)
izračuna njegovo naslednje stanje. Funkcija kot argument dobi trenutno
stanje, koordinate, funkcijo za izračun števila sosedov
(count_occupied
ali count_occupied_line
) in
število sosedov, ob katerem sedeči zapusti svoj stol.
Funkcija je precej očitna.
def next_state(state, x, y, occ_counter, occ_limit):
= state[y][x]
curr if curr != ".":
= occ_counter(state, x, y)
f if f == 0:
return "#"
if f >= occ_limit:
return "L"
return curr
Zdaj, ko je vse tako lepo pripravljeno, pa gremo z zanko čez oba dela
naloge: enkrat štejemo z count_occupied
in zapustimo sedež
pri 4
sosedih, enkrat z count_occupied_line
in
5
sosedi.
= [list(x.strip()) for x in open("input.txt")]
seats = len(seats[0]), len(seats)
w, h
for func, limit in ((count_occupied, 4), (count_occupied_line, 5)):
= None, seats
prev, state while state != prev:
= state
prev = [[next_state(state, x, y, func, limit)
state for x in range(w)] for y in range(h)]
print(sum(sum(c == "#" for c in v) for v in state))
2448
2234
Notranja zanka primerja trenutno in prejšnje stanje. Dokler nista enaka, si trenutno stanje zapomni kot prejšnje, novo pa sestavi tako, da izračuna naslednje stanje za vse koordinate stolov.
Program ni najhitrejši. Pythonove zanke pač niso najhitrejša stvar na
svetu, kakih dobrih bližnjic, s katerimi bi se jih izognili, pa ni. Z
numpy
-jem se da še kar lepo in hitro poskrbeti za prvi del,
z drugim pa se mi ni dalo hecati.