CheckioPuzzles/can-pass.py at master · jmegner/CheckioPuzzles · GitHub

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
'''
author: Jacob Egner
date: unknown
island: unknown

for latest versions of my solutions, see my checkio solution github repo:
https://github.com/jmegner/CheckioPuzzles

'''


import collections


class Loc(collections.namedtuple('Loc', ['r', 'c'])):

    def inBounds(self, grid):
        return ( self.r >= 0 and self.c >= 0
            and self.r < len(grid)
            and self.c < len(grid[self.r]) )


def can_pass(matrix, startRc, endRc):
    locStack = [Loc(*startRc)]
    visitedLocs = set()

    while locStack:
        loc = locStack.pop()

        if loc == endRc:
            return True

        visitedLocs.add(loc)

        rcDels = [ [0, -1], [0, +1], [-1, 0], [+1, 0], ]

        for rDel, cDel in rcDels:
            nextLoc = Loc(loc.r + rDel, loc.c + cDel)

            if ( nextLoc.inBounds(matrix) and nextLoc not in visitedLocs
                    and matrix[loc.r][loc.c] == matrix[nextLoc.r][nextLoc.c] ):
                locStack.append(nextLoc)

    return False


if __name__ == '__main__':
    assert can_pass( ((0, 0), (0, 0)), (0, 0), (1, 1) ) == True, "very small"
    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'