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 flpo
from itertools import product
from math import hypot
def can_pass(matrix, start, end):
reachable = set([start])
cells = product(range(len(matrix)), range(len(matrix[0])))
valid_cells = {(x, y) for x, y in cells if matrix[x][y] == matrix[start[0]][start[1]]}
while True:
neighbours = set((x, y) for x, y in valid_cells if any(hypot(x-a, y-b) == 1 for a, b in reachable))
if end in neighbours:
return True
if not neighbours:
return False
reachable |= neighbours
valid_cells -= reachable
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'
April 16, 2017
