Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Can You Pass? by BrianMcleod
from itertools import product
def can_pass(matrix, first, second):
"""
Check if a path exists between first and second.
"""
# create a set that contains all the cells with the same value as first
valid = {(x,y) for x,y in product(range(len(matrix)), range(len(matrix[0])))
if matrix[x][y] == matrix[first[0]][first[1]]}
current = {first}
# if current is empty, path is dead. If second in current, path is found
while current and second not in current:
valid -= current # remove current cells to prevent bac tracking
# find all cells in valid that are neighbors of any current cells
# test for neighbor is abs(pt[0]-c_pt[0]) + abs(pt[1]-c_pt[1]) == 1
current = {pt for pt in valid for c_pt in current
if sum((abs(a-b) for a,b in zip(pt, c_pt))) == 1}
return bool(current)
if __name__ == '__main__':
assert can_pass(((0, 0, 0, 0, 0, 0),
(0, 2, 2, 2, 3, 2),
(0, 2, 0, 0, 0, 2),
(0, 2, 0, 2, 0, 2),
(0, 2, 2, 2, 0, 2),
(0, 0, 0, 0, 0, 2),
(2, 2, 2, 2, 2, 2),),
(3, 2), (0, 5)) == True, 'First example'
assert can_pass(((0, 0, 0, 0, 0, 0),
(0, 2, 2, 2, 3, 2),
(0, 2, 0, 0, 0, 2),
(0, 2, 0, 2, 0, 2),
(0, 2, 2, 2, 0, 2),
(0, 0, 0, 0, 0, 2),
(2, 2, 2, 2, 2, 2),),
(3, 3), (6, 0)) == False, 'First example'
Sept. 30, 2018
Comments:
