Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Creative category for Can You Pass? by tokyoamado
import collections
def can_pass(matrix, first, second):
network = matrix_to_network(matrix)
adj_list = make_adj_list(network)
return second in find_all_relations(adj_list, first)
def matrix_to_network(matrix):
coordinates = [[(row, col) for col in range(len(matrix[0]))] for row in range(len(matrix))]
mat_with_coord = [list(zip(*t)) for t in list(zip(coordinates, matrix))]
edges_in_row = find_edges_in_row(mat_with_coord)
edges_in_column = find_edges_in_row(zip(*mat_with_coord))
return [edge for edges in edges_in_row + edges_in_column for edge in edges]
def find_edges_in_row(mat_with_coord):
edges = [
[(pair[0][0], pair[1][0]) for pair in zip(row, row[1:]) if pair[0][1] == pair[1][1]]
for row in map(list, mat_with_coord)
]
return edges
# function from O'REILLY: How to find friends
def make_adj_list(adjpairs):
adjlist = collections.defaultdict(set)
for (left, right) in adjpairs:
if left == right:
continue
else:
adjlist[left].add(right)
adjlist[right].add(left)
return adjlist
def find_all_relations(adjlist, node):
relations = []
jobs = [node]
while(jobs):
here = jobs.pop(0) # pop(0): breadth first / pop(): depth first
neighbors = adjlist.pop(here, set())
for neighbor in neighbors:
adjlist[neighbor].remove(here)
relations += list(neighbors)
jobs += list(neighbors)
return relations
Oct. 18, 2017
Comments:
