-
Notifications
You must be signed in to change notification settings - Fork 2
/
life-counter.py
161 lines (118 loc) · 4.61 KB
/
life-counter.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
################################################################################
# new set/dict way
import collections
class Loc(collections.namedtuple('Loc', ['r', 'c'])):
pass
def life_counter(initialGrid, numTicks):
currLifeLocs = set([
Loc(r, c)
for r in range(len(initialGrid))
for c in range(len(initialGrid[r]))
if initialGrid[r][c]])
for tick in range(numTicks):
neighborCounts = collections.Counter()
for liveCellLoc in currLifeLocs:
neighborLocs = [
Loc(liveCellLoc.r + delR, liveCellLoc.c + delC)
for delR in range(-1, 2)
for delC in range(-1, 2)
if delR != 0 or delC != 0]
neighborCounts.update(neighborLocs)
nextLifeLocs = set()
for loc, neighborCount in neighborCounts.items():
if neighborCount == 2 and loc in currLifeLocs or neighborCount == 3:
nextLifeLocs.add(loc)
currLifeLocs = nextLifeLocs
return len(currLifeLocs)
################################################################################
# old grid-based way
import itertools
def life_counter_old(initialGrid, numTicks):
currGrid = [[cell for cell in row] for row in initialGrid]
for tick in range(numTicks):
currGrid = getMinimalGrid(currGrid)
nextGrid = [[None] * len(currGrid[0]) for r in range(len(currGrid))]
for r in range(len(nextGrid)):
for c in range(len(nextGrid[r])):
numLiveNeighbors = getNumLiveNeighbors(currGrid, r, c)
if numLiveNeighbors == 2:
nextGrid[r][c] = getCell(currGrid, r, c)
elif numLiveNeighbors == 3:
nextGrid[r][c] = 1
else:
nextGrid[r][c] = 0
currGrid = nextGrid
numLiveCells = sum(itertools.chain(*currGrid))
return numLiveCells
def getMinimalGrid(lifeGrid):
numR = len(lifeGrid)
numC = len(lifeGrid[0])
minR = None
maxR = None
minC = None
maxC = None
for r in range(numR):
if any(lifeGrid[r]):
minR = r - 1
break
for r in reversed(range(numR)):
if any(lifeGrid[r]):
maxR = r + 1
break
for c, r in itertools.product(range(numC), range(numR)):
if lifeGrid[r][c]:
minC = c - 1
break
for c, r in itertools.product(reversed(range(numC)), range(numR)):
if lifeGrid[r][c]:
maxC = c + 1
break
if minR is None or (minR == 0 and minC == 0 and maxR == len(lifeGrid) - 1
and maxC == len(lifeGrid[0]) - 1):
return lifeGrid
minimalGrid = [
[getCell(lifeGrid, r, c)
for c in range(minC, maxC + 1)]
for r in range(minR, maxR + 1)]
return minimalGrid
def getNumLiveNeighbors(lifeGrid, r, c):
numLiveNeighbors = 0
for r2 in range(r - 1, r + 2):
for c2 in range(c - 1, c + 2):
if getCell(lifeGrid, r2, c2) and (r != r2 or c != c2):
numLiveNeighbors += 1
return numLiveNeighbors
def getCell(lifeGrid, r, c):
if inBounds(lifeGrid, r, c):
return lifeGrid[r][c]
return 0
def inBounds(grid, r, c):
return r >= 0 and c >= 0 and r < len(grid) and c < len(grid[r])
################################################################################
# tests
if __name__ == '__main__':
# These "asserts" using only for self-checking and not necessary for auto-testing
print("in-file asserts begin")
assert life_counter(((0, 1, 0, 0, 0, 0, 0),
(0, 0, 1, 0, 0, 0, 0),
(1, 1, 1, 0, 0, 0, 0),
(0, 0, 0, 0, 0, 1, 1),
(0, 0, 0, 0, 0, 1, 1),
(0, 0, 0, 0, 0, 0, 0),
(1, 1, 1, 0, 0, 0, 0)), 4) == 15, "Example"
assert life_counter(((0, 1, 0, 0, 0, 0, 0),
(0, 0, 1, 0, 0, 0, 0),
(1, 1, 1, 0, 0, 0, 0),
(0, 0, 0, 0, 0, 1, 1),
(0, 0, 0, 0, 0, 1, 1),
(0, 0, 0, 0, 0, 0, 0),
(1, 1, 1, 0, 0, 0, 0)), 15) == 14, "Little later"
assert life_counter(((0, 1, 0),
(0, 0, 1),
(1, 1, 1)), 50) == 5, "Glider"
assert life_counter(((1, 1, 0, 1, 1),
(1, 1, 0, 1, 1),
(0, 0, 0, 0, 0),
(1, 1, 0, 1, 1),
(1, 1, 0, 1, 1)), 100) == 16, "Stones"
print("in-file asserts end")