Skip to content

pydsa.grid

Grid

Bases: list

A list of rows that also takes a (row, col) pair as an index.

Source code in pydsa/grid.py 
194
195
196
197
198
199
200
201
202
203
204
205
206
class Grid(list):
    """A list of rows that also takes a (row, col) pair as an index."""

    def __getitem__(self, k):
        if type(k) is tuple:
            return list.__getitem__(self, k[0])[k[1]]
        return list.__getitem__(self, k)

    def __setitem__(self, k, v):
        if type(k) is tuple:
            list.__getitem__(self, k[0])[k[1]] = v
        else:
            list.__setitem__(self, k, v)

cells 

cells(
    grid: Sequence[Sequence[Any]],
    start: int = 0,
    val: Any = None,
    eq: Any = None,
    lt: Any = None,
    lte: Any = None,
    gt: Any = None,
    gte: Any = None,
) -> Iterator[Cell]

Every (i, j) of grid with i >= start and j >= start, in row-major order. With eq, lt, lte, gt or gte, only the cells whose value passes them all (see _holds). val is the old name for eq.

Source code in pydsa/grid.py 
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
def cells(
    grid: Sequence[Sequence[Any]],
    start: int = 0,
    val: Any = None,
    eq: Any = None,
    lt: Any = None,
    lte: Any = None,
    gt: Any = None,
    gte: Any = None,
) -> Iterator[Cell]:
    """Every (i, j) of grid with i >= start and j >= start, in row-major order.
    With eq, lt, lte, gt or gte, only the cells whose value passes them all
    (see _holds). val is the old name for eq."""
    eq = val if eq is None else eq
    for i in range(start, len(grid)):
        for j in range(start, len(grid[0])):
            if _holds(grid[i][j], eq, lt, lte, gt, gte):
                yield i, j

nbrs 

nbrs(
    grid: Sequence[Sequence[Any]],
    r: Any,
    c: Optional[int] = None,
    dirs: Sequence[Cell] = CARDINALS,
    val: Any = None,
    eq: Any = None,
    lt: Any = None,
    lte: Any = None,
    gt: Any = None,
    gte: Any = None,
) -> Iterator[Cell]

The cells (r + dr, c + dc) for (dr, dc) in dirs that lie on grid. nbrs(grid, p) takes the cell as one pair. With eq, lt, lte, gt or gte, only the cells whose value passes them all (see _holds). val is the old name for eq.

Source code in pydsa/grid.py 
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
def nbrs(
    grid: Sequence[Sequence[Any]],
    r: Any,
    c: Optional[int] = None,
    dirs: Sequence[Cell] = CARDINALS,
    val: Any = None,
    eq: Any = None,
    lt: Any = None,
    lte: Any = None,
    gt: Any = None,
    gte: Any = None,
) -> Iterator[Cell]:
    """The cells (r + dr, c + dc) for (dr, dc) in dirs that lie on grid.
    nbrs(grid, p) takes the cell as one pair. With eq, lt, lte, gt or gte,
    only the cells whose value passes them all (see _holds). val is the
    old name for eq."""
    if c is None:
        r, c = r
    eq = val if eq is None else eq
    for dr, dc in dirs:
        nr, nc = r + dr, c + dc
        if in_bounds(grid, nr, nc):
            if _holds(grid[nr][nc], eq, lt, lte, gt, gte):
                yield nr, nc

in_bounds 

in_bounds(
    grid: Sequence[Sequence[Any]],
    r: Any,
    c: Optional[int] = None,
) -> bool

True if (r, c) is a cell of grid. in_bounds(grid, p) takes the cell as one pair.

Source code in pydsa/grid.py 
83
84
85
86
87
88
def in_bounds(grid: Sequence[Sequence[Any]], r: Any, c: Optional[int] = None) -> bool:
    """True if (r, c) is a cell of grid. in_bounds(grid, p) takes the cell as
    one pair."""
    if c is None:
        r, c = r
    return 0 <= r < len(grid) and 0 <= c < len(grid[0])

is_edge 

is_edge(
    grid: Sequence[Sequence[Any]], r: int, c: int
) -> bool

True if (r, c) lies on the first or last row or column of grid.

Source code in pydsa/grid.py 
91
92
93
def is_edge(grid: Sequence[Sequence[Any]], r: int, c: int) -> bool:
    """True if (r, c) lies on the first or last row or column of grid."""
    return r == 0 or c == 0 or r == len(grid) - 1 or c == len(grid[0]) - 1

edges 

edges(grid: Sequence[Sequence[Any]]) -> Iterator[Cell]

Every (i, j) on the border of grid, each once, in row-major order.

Source code in pydsa/grid.py 
 96
 97
 98
 99
100
def edges(grid: Sequence[Sequence[Any]]) -> Iterator[Cell]:
    """Every (i, j) on the border of grid, each once, in row-major order."""
    for i, j in cells(grid):
        if is_edge(grid, i, j):
            yield i, j

table 

table(*dims: int, fill: Any = 0) -> List[Any]

A new table of the given dimensions, every cell set to fill.

table(n) is a list of n cells; table(m, n) is m rows of n cells, the rows distinct lists; table(l, m, n) nests one level deeper.

Source code in pydsa/grid.py 
103
104
105
106
107
108
109
110
def table(*dims: int, fill: Any = 0) -> List[Any]:
    """A new table of the given dimensions, every cell set to fill.

    table(n) is a list of n cells; table(m, n) is m rows of n cells, the
    rows distinct lists; table(l, m, n) nests one level deeper."""
    if len(dims) == 1:
        return [fill] * dims[0]
    return [table(*dims[1:], fill=fill) for _ in range(dims[0])]

like 

like(
    grid: Sequence[Sequence[Any]], fill: Any = 0
) -> List[List[Any]]

A new table with the shape of grid, every cell set to fill.

Source code in pydsa/grid.py 
113
114
115
def like(grid: Sequence[Sequence[Any]], fill: Any = 0) -> List[List[Any]]:
    """A new table with the shape of grid, every cell set to fill."""
    return table(len(grid), len(grid[0]), fill=fill)

shape 

shape(
    *seqs: Any, last_index: bool = False
) -> Tuple[int, ...]

The sizes of a nested list, or of several sequences side by side.

shape(grid) follows grid[0] down while it is a list: (rows, cols, ...). shape(a, b) is (len(a), len(b)). With last_index, every size less one: the index of the last cell.

Source code in pydsa/grid.py 
118
119
120
121
122
123
124
125
126
127
128
129
130
131
def shape(*seqs: Any, last_index: bool = False) -> Tuple[int, ...]:
    """The sizes of a nested list, or of several sequences side by side.

    shape(grid) follows grid[0] down while it is a list: (rows, cols, ...).
    shape(a, b) is (len(a), len(b)). With last_index, every size less one:
    the index of the last cell."""
    if len(seqs) == 1:
        dims, x = [len(seqs[0])], seqs[0]
        while dims[-1] and isinstance(x[0], list):
            x = x[0]
            dims.append(len(x))
    else:
        dims = [len(s) for s in seqs]
    return tuple(d - 1 for d in dims) if last_index else tuple(dims)

put 

put(
    grid: List[List[Any]], at: Iterable[Cell], v: Any
) -> None

Set grid[i][j] = v for every (i, j) in at.

v is one value, or an iterable read once per cell in the order of at: put(dp, cells(dp), accumulate(...)).

Source code in pydsa/grid.py 
141
142
143
144
145
146
147
def put(grid: List[List[Any]], at: Iterable[Cell], v: Any) -> None:
    """Set `grid[i][j] = v` for every (i, j) in at.

    v is one value, or an iterable read once per cell in the order of at:
    put(dp, cells(dp), accumulate(...))."""
    for (i, j), x in zip(at, _spread(v)):
        grid[i][j] = x

row 

row(grid: Sequence[Sequence[Any]], i: int) -> List[Any]

A copy of row i.

Source code in pydsa/grid.py 
150
151
152
def row(grid: Sequence[Sequence[Any]], i: int) -> List[Any]:
    """A copy of row i."""
    return list(grid[i])

col 

col(grid: Sequence[Sequence[Any]], j: int) -> List[Any]

A copy of column j, top to bottom.

Source code in pydsa/grid.py 
155
156
157
def col(grid: Sequence[Sequence[Any]], j: int) -> List[Any]:
    """A copy of column j, top to bottom."""
    return [r[j] for r in grid]

set_row 

set_row(grid: List[List[Any]], i: int, v: Any) -> None

Set every cell of row i to v, one value or an iterable read left to right.

Source code in pydsa/grid.py 
160
161
162
def set_row(grid: List[List[Any]], i: int, v: Any) -> None:
    """Set every cell of row i to v, one value or an iterable read left to right."""
    put(grid, ((i, j) for j in range(len(grid[i]))), v)

set_col 

set_col(grid: List[List[Any]], j: int, v: Any) -> None

Set every cell of column j to v, one value or an iterable read top to bottom.

Source code in pydsa/grid.py 
165
166
167
def set_col(grid: List[List[Any]], j: int, v: Any) -> None:
    """Set every cell of column j to v, one value or an iterable read top to bottom."""
    put(grid, ((i, j) for i in range(len(grid))), v)

grid_bfs 

grid_bfs(
    grid: Sequence[Sequence[Any]],
    sources: Sequence[Cell],
    ok: Callable[[Any], bool] = lambda v: True,
    dirs: Sequence[Cell] = CARDINALS,
) -> List[List[int]]

Steps from the nearest source to every cell; -1 where none reaches.

A cell is entered only if ok(grid[cell]) holds. Sources are entered unconditionally at distance 0.

Source code in pydsa/grid.py 
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
def grid_bfs(
    grid: Sequence[Sequence[Any]],
    sources: Sequence[Cell],
    ok: Callable[[Any], bool] = lambda v: True,
    dirs: Sequence[Cell] = CARDINALS,
) -> List[List[int]]:
    """Steps from the nearest source to every cell; -1 where none reaches.

    A cell is entered only if ok(grid[cell]) holds. Sources are entered
    unconditionally at distance 0.
    """
    dist = like(grid, -1)
    q = deque(sources)
    for r, c in sources:
        dist[r][c] = 0
    while q:
        r, c = q.popleft()
        for nr, nc in nbrs(grid, r, c, dirs):
            if dist[nr][nc] == -1 and ok(grid[nr][nc]):
                dist[nr][nc] = dist[r][c] + 1
                q.append((nr, nc))
    return dist