Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
DFS from alive nodes for unique groups solution in Clear category for New Cities by JamesArruda
def all_visible_nodes(curr, grid, off, viz):
for g in grid:
if len(g) == 1:
viz.add(curr)
continue
a, b = g
if a == curr and b not in off:
if b not in viz:
viz.add(b)
all_visible_nodes(b, grid, off, viz)
if b == curr and a not in off:
if a not in viz:
viz.add(a)
all_visible_nodes(a, grid, off, viz)
def subnetworks(net, crushes):
# reduce the network to only alive nodes
new_net = []
up_nodes = set()
for a, b in net:
use = []
if a not in crushes:
use.append(a)
up_nodes.add(a)
if b not in crushes:
use.append(b)
up_nodes.add(b)
if use:
new_net.append(use)
# for each node, get what is visible
all_viz = set()
for n in up_nodes:
viz = set()
all_visible_nodes(n, new_net, [], viz)
all_viz.add(tuple(sorted(viz)))
return len(all_viz)
if __name__ == '__main__':
#These "asserts" using only for self-checking and not necessary for auto-testing
assert subnetworks([
['A', 'B'],
['B', 'C'],
['C', 'D']
], ['B']) == 2, "First"
assert subnetworks([
['A', 'B'],
['A', 'C'],
['A', 'D'],
['D', 'F']
], ['A']) == 3, "Second"
assert subnetworks([
['A', 'B'],
['B', 'C'],
['C', 'D']
], ['C', 'D']) == 1, "Third"
print('Done! Check button is waiting for you!')
Sept. 14, 2018
Comments:
