-
Notifications
You must be signed in to change notification settings - Fork 1
/
data.py
440 lines (356 loc) · 13.3 KB
/
data.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
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
import random
import curses
from collections import deque
WEST = 1
NORTH_WEST = 2
NORTH_EAST = 4
EAST = 8
SOUTH_EAST = 16
SOUTH_WEST = 32
ALL = (WEST | NORTH_WEST | NORTH_EAST | EAST | SOUTH_EAST | SOUTH_WEST)
# TODO: there is a rule that disallows the creation of
# bottlenecks of N>2 nodes
# this can probably be a rule that can be generalized
# as disallowing deletion of nodes if the surrounding
# nodes neighbors would form this kind of bottleneck
# TODO: i would also wager there is a multi-waypoint rule
# that guarantees at least two distinct paths to the
# core (to stop gauntlets)
class Node(object):
def __init__(self, row: int, column: int):
self.row = row
self.column = column
self.is_visited = False
self.is_exposed = False
self.block_count = 0
self.input = 0
self.num_neighbors = 0
self.__token = None
@property
def is_blocked(self):
return self.block_count > 0
def on_exposed(self):
pass
def on_attacked(self):
pass
@property
def token(self):
return self.__token
@token.setter
def token(self, x):
if self.__token is not None:
self.__token.node = None
self.__token = x
if self.__token is not None:
self.__token.node = self
class BfsNode(object):
def __init__(self, node, parent, depth):
self.node = node
self.parent = parent
self.depth = depth
class System(object):
def __init__(self, seed=None):
self.width = 8
self.height = 8
self.nodes = []
self.selected_node = None
self.core = None
self.exposed_count = 0
self.virus = Virus(self)
self.create_nodes(seed)
def bfs_iterator(self, node):
if node is None:
raise ValueError
queue = deque()
queue.append(BfsNode(node, None, 0))
visited = {node}
while len(queue) > 0:
cursor = queue.pop()
yield cursor
for neighbor in self.get_neighbors(cursor.node):
if neighbor in visited:
continue
visited.add(neighbor)
queue.insert(0, BfsNode(neighbor, cursor, cursor.depth + 1))
def prune_disjoint(self, node):
nodes = set([x.node for x in self.bfs_iterator(node)])
for row in range(self.height):
for col in range(self.width):
node = self.nodes[row][col]
if node not in nodes:
self.nodes[row][col] = None
def create_nodes(self, seed):
# Initialize the random number generator with a seed, if provided
if seed is not None:
random.seed(seed)
# Iterate over all the node spots and create a new node.
for row_index in range(self.height):
row = [None] * self.width
self.nodes.append(row)
for column_index in range(self.width):
self.nodes[row_index][column_index] = Node(row_index, column_index)
# TODO: randomly select a bunch of corner bits and turn them off?
starting_node = self.get_starting_node()
self.visit_node(starting_node, force=True)
node_at_jumps = self.get_nodes_at_jumps(starting_node, 5)
waypoint = random.choice(node_at_jumps)
core_node_candidates = []
for row in range(self.height):
for col in range(self.width):
node = self.nodes[row][col]
sp = self.get_path(starting_node, node)
if sp is None or len(sp) < 8:
continue
core_node_candidates.append(self.nodes[row][col])
# Place down the core token
core_node = random.choice(core_node_candidates)
self.core = Core(self)
core_node.token = self.core
# Lock down a path to the core
p = self.get_path(starting_node, waypoint)
q = self.get_path(waypoint, self.core.node)
locked_nodes = set(p + q)
locked_nodes.add(starting_node)
population = []
for row in range(self.height):
for col in range(self.width):
node = self.nodes[row][col]
if node in locked_nodes:
continue
population.append(node)
# Start deleting nodes at random from the remaining popoulation
# there should probably be rules for this (can't have two adjacent nodes <= 2 neighbors)
area = self.width * self.height
k = area // 4
nodes_to_delete = random.choices(population, k=k)
for node in nodes_to_delete:
self.nodes[node.row][node.column] = None
# Prune disjointed trees
self.prune_disjoint(starting_node)
# Candidate nodes for firewalls
population = []
for row in range(self.height):
for col in range(self.width):
node = self.nodes[row][col]
if node is None or node == starting_node:
continue
if self.get_num_neighbors(node) < 6 or self.get_path(node, self.core.node) == 1:
population.append(node)
firewall_nodes = random.choices(population, k=6)
for node in firewall_nodes:
node.token = Firewall(self)
def remove_node(self, node):
for neighbor in self.get_neighbors(node):
neighbor.num_neighbors -= 1
self.nodes[node.row][node.column] = None
def is_valid_index(self, row, col):
return row >= 0 and row < self.height and col >= 0 and col < self.width
def can_visit_node(self, node):
# is_visited -> has been visited once
if node is None:
return False
if (node.is_visited and node.token is None) or node.is_blocked:
return False
return node.is_exposed
def visit_node(self, node, force=False):
if not force and not self.can_visit_node(node):
return
if node is None:
raise RuntimeError('cannot visit a null node!')
if not node.is_visited:
# Node has not been visited before
node.is_visited = True
# Expose surrounding nodes
node.is_exposed = True
for neighbor in self.get_neighbors(node):
if not neighbor.is_exposed:
neighbor.is_exposed = True
# If a token exists, expose it
if node.token is not None:
node.token.on_exposed()
else:
if node.token is not None:
node.token.on_attacked(self.virus)
self.selected_node = node
def get_starting_node(self):
m = 100
starting_nodes = []
for row in range(self.height):
for column in range(self.width):
node = self.nodes[row][column]
if node is None:
continue
num_neighbors = self.get_num_neighbors(node)
if num_neighbors < m:
m = num_neighbors
starting_nodes = [node]
elif num_neighbors == m:
starting_nodes.append(node)
return random.choice(starting_nodes)
def get_nodes_at_jumps(self, node, jumps):
# bfs, keep track of
queue = deque()
queue.append(BfsNode(node, None, 0))
nodes = []
visited = {node}
while len(queue) > 0:
cursor = queue.pop()
neighbors = self.get_neighbors(cursor.node)
for neighbor in neighbors:
if neighbor in visited:
continue
visited.add(neighbor)
if cursor.depth >= jumps:
nodes.append(neighbor)
break
new = BfsNode(neighbor, cursor, cursor.depth + 1)
queue.insert(0, new)
return nodes
def get_neighbor(self, node, direction):
if node is None:
raise RuntimeError()
row, column = node.row, node.column
if direction == WEST:
if column <= 0:
return None
return self.nodes[row][column - 1]
elif direction == EAST:
if column >= self.width - 1:
return None
return self.nodes[row][column + 1]
if row % 2 == 0: # even row
# top-left
if direction == NORTH_WEST and row > 0 and column > 0:
return self.nodes[row - 1][column - 1]
# above-right
elif direction == NORTH_EAST and row > 0:
return self.nodes[row - 1][column]
# below-left
elif direction == SOUTH_WEST and row < self.height - 1 and column > 0:
return self.nodes[row + 1][column - 1]
# below-right
elif direction == SOUTH_EAST and row < self.height - 1:
return self.nodes[row + 1][column]
else: # odd row
if direction == NORTH_WEST and row > 0:
return self.nodes[row - 1][column]
elif direction == NORTH_EAST and row > 0 and column < self.width - 1:
return self.nodes[row - 1][column + 1]
elif direction == SOUTH_WEST and row < self.height - 1:
return self.nodes[row + 1][column]
elif direction == SOUTH_EAST and row < self.height - 1 and column < self.width - 1:
return self.nodes[row + 1][column + 1]
return None
def get_neighbors(self, node):
if node is None:
return []
neighbors = []
for direction in map(lambda x: 1 << x, range(6)):
neighbor = self.get_neighbor(node, direction)
if neighbor is not None:
neighbors.append(neighbor)
return neighbors
def get_num_neighbors(self, node):
return sum(1 for _ in self.get_neighbors(node))
# breadth-first search
def get_path(self, start: Node, destination: Node):
if start == destination:
return []
queue = deque()
queue.append(BfsNode(start, None, 0))
path = []
visited = set() # set of visited nodes
while len(queue) > 0:
cursor = queue.pop()
visited.add(cursor.node)
if cursor.node == destination:
# traverse up parent hierarchy, reverse, and return
while cursor.parent is not None:
path.insert(0, cursor.node)
cursor = cursor.parent
return path
neighbors = self.get_neighbors(cursor.node)
for neighbor in neighbors:
if neighbor not in visited:
child = BfsNode(neighbor, cursor, cursor.depth)
queue.insert(0, child)
visited.add(neighbor)
return None
def node_at(self, row, col):
return self.nodes[row][col]
def get_node_for_input(self, char):
char = char - 97
for row in range(self.height):
for column in range(self.width):
node = self.nodes[row][column]
if node is not None and not node.is_visited and node.is_exposed and node.input == char:
return node
return None
# TODO: virus is kind of like a node!
# has coherence, has health? component?? kind of overkill
# TODO nodes can have a token on them! makes it a bit easier and allows clean abstraction
# to allow the virus itself to be a token
class Token(object):
def __init__(self, system, node=None):
self.node = node
self.system = system
self.coherence = 0
self.strength = 0
# TODO: let the system logic handle this??
def on_attacked(self, attacker):
self.take_damage(attacker.strength)
if not self.is_dead:
# If the token survives the attack, hit the attacker back!
attacker.take_damage(self.strength)
def take_damage(self, coherence):
self.coherence = max(0, self.coherence - coherence)
if self.is_dead:
self.on_destroyed()
@property
def is_dead(self):
return self.coherence <= 0
def on_exposed(self):
pass
def on_destroyed(self):
if self.node is not None:
self.node.token = None
class Virus(Token):
def __init__(self, system, node=None):
super().__init__(system, node)
self.coherence = 80
self.strength = 20
def on_destroyed(self):
# if it's
pass
class Core(Token):
def __init__(self, system):
super().__init__(system)
self.coherence = 70
self.strength = 10
def on_destroyed(self):
pass
class Firewall(Token):
def __init__(self, system):
super().__init__(system)
self.coherence = 80
self.strength = 10
@property
def can_be_attacked(self):
return True
def on_exposed(self):
super().on_exposed()
for neighbor in self.system.get_neighbors(self.node):
neighbor.block_count += 1
def on_destroyed(self):
for neighbor in self.system.get_neighbors(self.node):
neighbor.block_count -= 1
super().on_destroyed()
# needs to be activated...can they be deactivated once activated?
class Utility(Token):
def __init__(self, system):
super().__init__(system)
def activate(self):
pass
class Repair(Utility):
def __init__(self):
pass