Skip to content

pydsa.grid

Grid helpers preloaded by sitecustomize: scan a grid, list a cell's in-bounds neighbours, test for and list the border cells, build a table by shape or by size, read a grid's shape, write one value or a stream of values into many cells, read or set a row or a column, multi-source BFS.

Cell module-attribute

Cell = Tuple[int, int]

CARDINALS module-attribute

CARDINALS: Tuple[Cell, ...] = (
    (-1, 0),
    (0, -1),
    (0, 1),
    (1, 0),
)

DIAGONALS module-attribute

DIAGONALS: Tuple[Cell, ...] = (
    (-1, -1),
    (-1, 1),
    (1, -1),
    (1, 1),
)

ALL_EIGHT module-attribute

ALL_EIGHT: Tuple[Cell, ...] = CARDINALS + DIAGONALS

Grid

Bases: list

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

Source code in pydsa/grid.mu
145
146
147
148
149
150
151
152
153
154
155
class Grid extends list
  """A list of rows that also takes a (row, col) pair as an index."""

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

  def __setitem__(k, v) -> none
    if type(k) is tuple
      list.__getitem__(self, k[0])[k[1]] = v
    else
      list.__setitem__(self, k, v)
155
156
157
158
159
160
161
162
163
164
165
class Grid(list):
    """A list of rows that also takes a (row, col) pair as an index."""

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

    def __setitem__(self, k, v) -> None:
        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,
    eq=None,
    lt=None,
    lte=None,
    gt=None,
    gte=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).

Source code in pydsa/grid.mu
21
22
23
24
25
26
27
28
29
30
def cells(
  grid: Sequence[Sequence[Any]], start: int=0, eq=none, lt=none, lte=none, gt=none, gte=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)."""
  for i in start..<len grid
    for j in start..<len grid[0]
      if _holds(grid[i][j], eq, lt, lte, gt, gte)
        yield i, j
25
26
27
28
29
30
31
32
def cells(grid: Sequence[Sequence[Any]], start: int = 0, eq=None, lt=None, lte=None, gt=None, gte=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)."""
    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,
    c: Optional[int] = None,
    dirs: Sequence[Cell] = CARDINALS,
    eq=None,
    lt=None,
    lte=None,
    gt=None,
    gte=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).

Source code in pydsa/grid.mu
32
33
34
35
36
37
38
39
40
41
42
43
44
def nbrs(
  grid: Sequence[Sequence[Any]], r, c: int?=none, dirs: Sequence[Cell]=CARDINALS,
  eq=none, lt=none, lte=none, gt=none, gte=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)."""
  if c is none
    r, c = r
  for dr, dc in dirs
    nr, nc = r + dr, c + dc
    if in_bounds(grid, nr, nc) and _holds(grid[nr][nc], eq, lt, lte, gt, gte)
      yield nr, nc
35
36
37
38
39
40
41
42
43
44
def nbrs(grid: Sequence[Sequence[Any]], r, c: Optional[int] = None, dirs: Sequence[Cell] = CARDINALS, eq=None, lt=None, lte=None, gt=None, gte=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)."""
    if c is None:
        r, c = r
    for dr, dc in dirs:
        nr, nc = r + dr, c + dc
        if in_bounds(grid, nr, nc) and _holds(grid[nr][nc], eq, lt, lte, gt, gte):
            yield nr, nc

in_bounds

in_bounds(
    grid: Sequence[Sequence[Any]],
    r,
    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.mu
46
47
48
49
50
51
def in_bounds(grid: Sequence[Sequence[Any]], r, c: 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
  0 <= r < len grid and 0 <= c < len grid[0]
47
48
49
50
51
52
def in_bounds(grid: Sequence[Sequence[Any]], r, 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,
    c: Optional[int] = None,
) -> bool

True if (r, c) lies on the border of grid. is_edge(grid, p) takes the cell as one pair.

Source code in pydsa/grid.mu
53
54
55
56
57
58
def is_edge(grid: Sequence[Sequence[Any]], r, c: int?=none) -> bool
  """True if (r, c) lies on the border of grid. is_edge(grid, p) takes the
  cell as one pair."""
  if c is none
    r, c = r
  r == 0 or c == 0 or r == len grid - 1 or c == len grid[0] - 1
55
56
57
58
59
60
def is_edge(grid: Sequence[Sequence[Any]], r, c: Optional[int] = None) -> bool:
    """True if (r, c) lies on the border of grid. is_edge(grid, p) takes the
    cell as one pair."""
    if c is None:
        r, c = r
    return r == 0 or c == 0 or r == len(grid) - 1 or c == len(grid[0]) - 1

edges

edges(
    grid: Sequence[Sequence[Any]],
    eq=None,
    lt=None,
    lte=None,
    gt=None,
    gte=None,
) -> Iterator[Cell]

Every (i, j) on the border of grid, each once, in row-major order. With eq, lt, lte, gt or gte, only the cells whose value passes them all (see _holds).

Source code in pydsa/grid.mu
60
61
62
63
64
65
66
67
68
def edges(
  grid: Sequence[Sequence[Any]], eq=none, lt=none, lte=none, gt=none, gte=none
) -> Iterator[Cell]
  """Every (i, j) on the border of grid, each once, in row-major order.
  With eq, lt, lte, gt or gte, only the cells whose value passes them all
  (see _holds)."""
  for i, j in cells(grid, eq=eq, lt=lt, lte=lte, gt=gt, gte=gte)
    if is_edge(grid, i, j)
      yield i, j
63
64
65
66
67
68
69
def edges(grid: Sequence[Sequence[Any]], eq=None, lt=None, lte=None, gt=None, gte=None) -> Iterator[Cell]:
    """Every (i, j) on the border of grid, each once, in row-major order.
    With eq, lt, lte, gt or gte, only the cells whose value passes them all
    (see _holds)."""
    for i, j in cells(grid, eq=eq, lt=lt, lte=lte, gt=gt, gte=gte):
        if is_edge(grid, i, j):
            yield i, j

table

table(*dims: int, fill=0) -> list

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.mu
70
71
72
73
74
75
def table(*dims: int, fill=0) -> list
  """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."""
  len dims == 1 ? [fill] * dims[0] : [table(*dims[1:], fill=fill) for _ in 0..<dims[0]]
72
73
74
75
76
77
def table(*dims: int, fill=0) -> list:
    """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."""
    return [fill] * dims[0] if len(dims) == 1 else [table(*dims[1:], fill=fill) for _ in range(0, dims[0])]

like

like(grid: Sequence[Sequence[Any]], fill=0) -> list[list]
Source code in pydsa/grid.mu
77
78
def like(grid: Sequence[Sequence[Any]], fill=0) -> [list]
  table(len grid, len grid[0], fill=fill)
80
81
def like(grid: Sequence[Sequence[Any]], fill=0) -> list[list]:
    return table(len(grid), len(grid[0]), fill=fill)

shape

shape(*seqs, 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.mu
80
81
82
83
84
85
86
87
88
89
90
91
92
def shape(*seqs, 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."""
  dims = [len(s) for s in seqs]
  if len seqs == 1
    x = seqs[0]
    while dims[-1] and isinstance(x[0], list)
      x = x[0]
      dims <- len x
  last_index ? tuple(d - 1 for d in dims) : tuple(dims)
84
85
86
87
88
89
90
91
92
93
94
95
96
def shape(*seqs, 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."""
    dims = [len(s) for s in seqs]
    if len(seqs) == 1:
        x = seqs[0]
        while dims[-1] and isinstance(x[0], list):
            x = x[0]
            dims.append(len(x))
    return tuple(d - 1 for d in dims) if last_index else tuple(dims)

put

put(grid: List[List[Any]], at: Iterable[Cell], v) -> 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.mu
 98
 99
100
101
102
103
104
def put(grid: List[List[Any]], at: Iterable[Cell], v) -> 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
104
105
106
107
108
109
110
def put(grid: List[List[Any]], at: Iterable[Cell], v) -> 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

A copy of row i.

Source code in pydsa/grid.mu
106
107
108
def row(grid: Sequence[Sequence[Any]], i: int) -> list
  """A copy of row i."""
  list(grid[i])
113
114
115
def row(grid: Sequence[Sequence[Any]], i: int) -> list:
    """A copy of row i."""
    return list(grid[i])

col

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

A copy of column j, top to bottom.

Source code in pydsa/grid.mu
110
111
112
def col(grid: Sequence[Sequence[Any]], j: int) -> list
  """A copy of column j, top to bottom."""
  [r[j] for r in grid]
118
119
120
def col(grid: Sequence[Sequence[Any]], j: int) -> list:
    """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) -> None

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

Source code in pydsa/grid.mu
114
115
116
def set_row(grid: List[List[Any]], i: int, v) -> 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 grid[i]), v)
123
124
125
def set_row(grid: List[List[Any]], i: int, v) -> 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) -> None

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

Source code in pydsa/grid.mu
118
119
120
def set_col(grid: List[List[Any]], j: int, v) -> 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 grid), v)
128
129
130
def set_col(grid: List[List[Any]], j: int, v) -> 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] | Cell,
    dirs: Sequence[Cell] = CARDINALS,
    eq=None,
    lt=None,
    lte=None,
    gt=None,
    gte=None,
) -> list[list[int]]

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

sources is a list of cells, or one cell. With eq, lt, lte, gt or gte, only the cells whose value passes them all are entered (see _holds). Sources are entered unconditionally at distance 0.

Source code in pydsa/grid.mu
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
def grid_bfs(
  grid: Sequence[Sequence[Any]], sources: Sequence[Cell] | Cell, dirs: Sequence[Cell]=CARDINALS,
  eq=none, lt=none, lte=none, gt=none, gte=none
) -> [[int]]
  """Steps from the nearest source to every cell; -1 where none reaches.

  sources is a list of cells, or one cell. With eq, lt, lte, gt or gte,
  only the cells whose value passes them all are entered (see _holds).
  Sources are entered unconditionally at distance 0.
  """
  if sources and isinstance(sources[0], int)
    sources = [sources]
  ret 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, eq=eq, lt=lt, lte=lte, gt=gt, gte=gte)
      if dist[nr][nc] == -1
        dist[nr][nc] = dist[r][c] + 1
        q <- (nr, nc)
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
def grid_bfs(grid: Sequence[Sequence[Any]], sources: Sequence[Cell] | Cell, dirs: Sequence[Cell] = CARDINALS, eq=None, lt=None, lte=None, gt=None, gte=None) -> list[list[int]]:
    """Steps from the nearest source to every cell; -1 where none reaches.

    sources is a list of cells, or one cell. With eq, lt, lte, gt or gte,
    only the cells whose value passes them all are entered (see _holds).
    Sources are entered unconditionally at distance 0.
    """
    if sources and isinstance(sources[0], int):
        sources = [sources]
    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, eq=eq, lt=lt, lte=lte, gt=gt, gte=gte):
            if dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1
                q.append((nr, nc))
    return dist