docs for maze-dataset v1.1.0
Contents
[PyPI] [PyPI - Downloads] [Checks] [Coverage] [code size, bytes] [GitHub
commit activity] [GitHub closed pull requests]
maze-dataset
This package provides utilities for generation, filtering, solving,
visualizing, and processing of mazes for training ML systems. Primarily
built for the maze-transformer interpretability project. You can find
our paper on it here: http://arxiv.org/abs/2309.10498
This package includes a variety of maze generation algorithms, including
randomized depth first search, Wilson’s algorithm for uniform spanning
trees, and percolation. Datasets can be filtered to select mazes of a
certain length or complexity, remove duplicates, and satisfy custom
properties. A variety of output formats for visualization and training
ML models are provided.
----------------- ----------------- ----------------- -----------------
[Maze generated [Maze generated [Maze with random [MazePlot with
via percolation] via constrained heatmap] solution]
randomized depth
first search]
----------------- ----------------- ----------------- -----------------
Installation
This package is available on PyPI, and can be installed via
pip install maze-dataset
Docs
The full hosted documentation is available at
https://understanding-search.github.io/maze-dataset/.
Additionally:
- our notebooks serve as a good starting point for understanding the
package:
- the notebooks page in the docs has links to the rendered
notebooks
- the notebooks folder has the source notebooks
- combined, single page docs are available as:
- plain text
- html
- github markdown
- pandoc markdown
- test coverage reports are available on the coverage page or the
coverage/ folder
- generation benchmark results are available on the benchmarks page or
the benchmarks/ folder
Usage
Creating a dataset
To create a MazeDataset, which inherits from torch.utils.data.Dataset,
you first create a MazeDatasetConfig:
from maze_dataset import MazeDataset, MazeDatasetConfig
from maze_dataset.generation import LatticeMazeGenerators
cfg: MazeDatasetConfig = MazeDatasetConfig(
name="test", # name is only for you to keep track of things
grid_n=5, # number of rows/columns in the lattice
n_mazes=4, # number of mazes to generate
maze_ctor=LatticeMazeGenerators.gen_dfs, # algorithm to generate the maze
maze_ctor_kwargs=dict(do_forks=False), # additional parameters to pass to the maze generation algorithm
)
and then pass this config to the MazeDataset.from_config method:
dataset: MazeDataset = MazeDataset.from_config(cfg)
This method can search for whether a dataset with matching config hash
already exists on your filesystem in the expected location, and load it
if so. It can also generate a dataset on the fly if needed.
Conversions to useful formats
The elements of the dataset are SolvedMaze objects:
>>> m = dataset[0]
>>> type(m)
maze_dataset.maze.lattice_maze.SolvedMaze
Which can be converted to a variety of formats:
# visual representation as ascii art
m.as_ascii()
# RGB image, optionally without solution or endpoints, suitable for CNNs
m.as_pixels()
# text format for autoreregressive transformers
from maze_dataset.tokenization import MazeTokenizerModular, TokenizationMode
m.as_tokens(maze_tokenizer=MazeTokenizerModular(
tokenization_mode=TokenizationMode.AOTP_UT_rasterized, max_grid_size=100,
))
# advanced visualization with many features
from maze_dataset.plotting import MazePlot
MazePlot(maze).plot()
[textual and visual output formats]
Development
This project uses Poetry for development. To install with dev
requirements, run
poetry install --with dev
A makefile is included to simplify common development tasks:
- make help will print all available commands
- all tests via make test
- unit tests via make unit
- notebook tests via make test_notebooks
- formatter (black, pycln, and isort) via make format
- formatter in check-only mode via make check-format
Citing
If you use this code in your research, please cite our paper:
@misc{maze-dataset,
title={A Configurable Library for Generating and Manipulating Maze Datasets},
author={Michael Igorevich Ivanitskiy and Rusheb Shah and Alex F. Spies and Tilman Räuker and Dan Valentine and Can Rager and Lucia Quirke and Chris Mathwin and Guillaume Corlouer and Cecilia Diniz Behn and Samy Wu Fung},
year={2023},
eprint={2309.10498},
archivePrefix={arXiv},
primaryClass={cs.LG},
url={http://arxiv.org/abs/2309.10498}
}
Submodules
- dataset
- generation
- maze
- plotting
- tokenization
- constants
- testing_utils
- token_utils
- utils
API Documentation
- SolvedMaze
- MazeDatasetConfig
- MazeDataset
- MazeDatasetCollection
- MazeDatasetCollectionConfig
- TargetedLatticeMaze
- LatticeMaze
- set_serialize_minimal_threshold
- LatticeMazeGenerators
- Coord
- CoordTup
- CoordList
- CoordArray
- Connection
- ConnectionList
- ConnectionArray
- SPECIAL_TOKENS
- VOCAB
- VOCAB_LIST
- VOCAB_TOKEN_TO_INDEX
View Source on GitHub
maze_dataset
[PyPI] [PyPI - Downloads] [Checks] [Coverage] [code size, bytes] [GitHub
commit activity] [GitHub closed pull requests]
maze-dataset
This package provides utilities for generation, filtering, solving,
visualizing, and processing of mazes for training ML systems. Primarily
built for the maze-transformer interpretability project. You can find
our paper on it here: http://arxiv.org/abs/2309.10498
This package includes a variety of maze generation algorithms, including
randomized depth first search, Wilson’s algorithm for uniform spanning
trees, and percolation. Datasets can be filtered to select mazes of a
certain length or complexity, remove duplicates, and satisfy custom
properties. A variety of output formats for visualization and training
ML models are provided.
----------------- ----------------- ----------------- -----------------
[Maze generated [Maze generated [Maze with random [MazePlot with
via percolation] via constrained heatmap] solution]
randomized depth
first search]
----------------- ----------------- ----------------- -----------------
Installation
This package is available on PyPI, and can be installed via
pip install maze-dataset
Docs
The full hosted documentation is available at
https://understanding-search.github.io/maze-dataset/.
Additionally:
- our notebooks serve as a good starting point for understanding the
package:
- the notebooks page in the docs has links to the rendered
notebooks
- the notebooks folder has the source notebooks
- combined, single page docs are available as:
- plain text
- html
- github markdown
- pandoc markdown
- test coverage reports are available on the coverage page or the
coverage/ folder
- generation benchmark results are available on the benchmarks page or
the benchmarks/ folder
Usage
Creating a dataset
To create a MazeDataset, which inherits from torch.utils.data.Dataset,
you first create a MazeDatasetConfig:
from maze_dataset import MazeDataset, MazeDatasetConfig
from maze_dataset.generation import LatticeMazeGenerators
cfg: MazeDatasetConfig = MazeDatasetConfig(
name="test", # name is only for you to keep track of things
grid_n=5, # number of rows/columns in the lattice
n_mazes=4, # number of mazes to generate
maze_ctor=LatticeMazeGenerators.gen_dfs, # algorithm to generate the maze
maze_ctor_kwargs=dict(do_forks=False), # additional parameters to pass to the maze generation algorithm
)
and then pass this config to the
MazeDataset.from_config method:
dataset: MazeDataset = MazeDataset.from_config(cfg)
This method can search for whether a dataset with matching config hash
already exists on your filesystem in the expected location, and load it
if so. It can also generate a dataset on the fly if needed.
Conversions to useful formats
The elements of the dataset are SolvedMaze objects:
>>> m = dataset[0]
>>> type(m)
SolvedMaze
Which can be converted to a variety of formats:
### visual representation as ascii art
m.as_ascii()
### RGB image, optionally without solution or endpoints, suitable for CNNs
m.as_pixels()
### text format for autoreregressive transformers
from maze_dataset.tokenization import MazeTokenizerModular, TokenizationMode
m.as_tokens(maze_tokenizer=MazeTokenizerModular(
tokenization_mode=TokenizationMode.AOTP_UT_rasterized, max_grid_size=100,
))
### advanced visualization with many features
from maze_dataset.plotting import MazePlot
MazePlot(maze).plot()
[textual and visual output formats]
Development
This project uses Poetry for development. To install with dev
requirements, run
poetry install --with dev
A makefile is included to simplify common development tasks:
- make help will print all available commands
- all tests via make test
- unit tests via make unit
- notebook tests via make test_notebooks
- formatter (black, pycln, and isort) via make format
- formatter in check-only mode via make check-format
Citing
If you use this code in your research, please cite our paper:
@misc{maze-dataset,
title={A Configurable Library for Generating and Manipulating Maze Datasets},
author={Michael Igorevich Ivanitskiy and Rusheb Shah and Alex F. Spies and Tilman Räuker and Dan Valentine and Can Rager and Lucia Quirke and Chris Mathwin and Guillaume Corlouer and Cecilia Diniz Behn and Samy Wu Fung},
year={2023},
eprint={2309.10498},
archivePrefix={arXiv},
primaryClass={cs.LG},
url={http://arxiv.org/abs/2309.10498}
}
View Source on GitHub
class SolvedMaze(maze_dataset.maze.lattice_maze.TargetedLatticeMaze):
View Source on GitHub
Stores a maze and a solution
SolvedMaze
(
connection_list: jaxtyping.Bool[ndarray, 'lattice_dim=2 row col'],
solution: jaxtyping.Int8[ndarray, 'coord row_col'],
generation_meta: dict | None = None,
start_pos: jaxtyping.Int8[ndarray, 'row_col'] | None = None,
end_pos: jaxtyping.Int8[ndarray, 'row_col'] | None = None,
allow_invalid: bool = False
)
View Source on GitHub
- solution: jaxtyping.Int8[ndarray, 'coord row_col']
def get_solution_tokens
(self) -> list[str | tuple[int, int]]
View Source on GitHub
- maze: maze_dataset.maze.lattice_maze.LatticeMaze
View Source on GitHub
def from_lattice_maze
(
cls,
lattice_maze: maze_dataset.maze.lattice_maze.LatticeMaze,
solution: list[tuple[int, int]]
) -> maze_dataset.maze.lattice_maze.SolvedMaze
View Source on GitHub
def from_targeted_lattice_maze
(
cls,
targeted_lattice_maze: maze_dataset.maze.lattice_maze.TargetedLatticeMaze,
solution: list[tuple[int, int]] | None = None
) -> maze_dataset.maze.lattice_maze.SolvedMaze
View Source on GitHub
solves the given targeted lattice maze and returns a SolvedMaze
def get_solution_forking_points
(
self,
always_include_endpoints: bool = False
) -> tuple[list[int], jaxtyping.Int8[ndarray, 'coord row_col']]
View Source on GitHub
coordinates and their indicies from the solution where a fork is present
- if the start point is not a dead end, this counts as a fork
- if the end point is not a dead end, this counts as a fork
def get_solution_path_following_points
(self) -> tuple[list[int], jaxtyping.Int8[ndarray, 'coord row_col']]
View Source on GitHub
coordinates from the solution where there is only a single
(non-backtracking) point to move to
returns the complement of get_solution_forking_points from the path
def serialize
(self) -> dict[str, typing.Any]
View Source on GitHub
returns the class as a dict, implemented by using
@serializable_dataclass decorator
def load
(cls, data: Union[dict[str, Any], ~T]) -> Type[~T]
View Source on GitHub
takes in an appropriately structured dict and returns an instance of the
class, implemented by using @serializable_dataclass decorator
def validate_fields_types
(
self: muutils.json_serialize.serializable_dataclass.SerializableDataclass,
on_typecheck_error: muutils.errormode.ErrorMode = ErrorMode.Except
) -> bool
View Source on GitHub
validate the types of all the fields on a SerializableDataclass. calls
SerializableDataclass__validate_field_type for each field
Inherited Members
- start_pos
- end_pos
- get_start_pos_tokens
- get_end_pos_tokens
- connection_list
- generation_meta
- lattice_dim
- grid_shape
- n_connections
- grid_n
- heuristic
- nodes_connected
- is_valid_path
- coord_degrees
- get_coord_neighbors
- gen_connected_component_from
- find_shortest_path
- get_nodes
- get_connected_component
- generate_random_path
- as_adj_list
- from_adj_list
- as_adj_list_tokens
- as_tokens
- from_tokens
- as_pixels
- from_pixels
- as_ascii
- from_ascii
- validate_field_type
- diff
- update_from_nested_dict
class MazeDatasetConfig(maze_dataset.dataset.dataset.GPTDatasetConfig):
View Source on GitHub
config object which is passed to
MazeDataset.from_config to
generate or load a dataset
MazeDatasetConfig
(
*,
name: str,
seq_len_min: int = 1,
seq_len_max: int = 512,
seed: int | None = 42,
applied_filters: list[dict[typing.Literal['name', 'args', 'kwargs'], str | list | dict]] = ,
grid_n: int,
n_mazes: int,
maze_ctor: Callable = ,
maze_ctor_kwargs: dict = ,
endpoint_kwargs: dict[typing.Literal['except_when_invalid', 'allowed_start', 'allowed_end', 'deadend_start', 'deadend_end'], bool | None | list[tuple[int, int]]] =
)
- grid_n: int
- n_mazes: int
def maze_ctor
(
grid_shape: jaxtyping.Int8[ndarray, 'row_col'],
lattice_dim: int = 2,
accessible_cells: int | float | None = None,
max_tree_depth: int | float | None = None,
do_forks: bool = True,
randomized_stack: bool = False,
start_coord: jaxtyping.Int8[ndarray, 'row_col'] | None = None
) -> maze_dataset.maze.lattice_maze.LatticeMaze
View Source on GitHub
generate a lattice maze using depth first search, iterative
Arguments
- grid_shape: Coord: the shape of the grid
- lattice_dim: int: the dimension of the lattice (default: 2)
- accessible_cells: int | float |None: the number of accessible cells
in the maze. If None, defaults to the total number of cells in the
grid. if a float, asserts it is <= 1 and treats it as a proportion
of total cells (default: None)
- max_tree_depth: int | float | None: the maximum depth of the tree.
If None, defaults to 2 * accessible_cells. if a float, asserts it is
<= 1 and treats it as a proportion of the sum of the grid shape
(default: None)
- do_forks: bool: whether to allow forks in the maze. If False, the
maze will be have no forks and will be a simple hallway.
- start_coord: Coord | None: the starting coordinate of the generation
algorithm. If None, defaults to a random coordinate.
algorithm
1. Choose the initial cell, mark it as visited and push it to the stack
2. While the stack is not empty 1. Pop a cell from the stack and make
it a current cell 2. If the current cell has any neighbours which
have not been visited 1. Push the current cell to the stack 2.
Choose one of the unvisited neighbours 3. Remove the wall between
the current cell and the chosen cell 4. Mark the chosen cell as
visited and push it to the stack
- maze_ctor_kwargs: dict
- endpoint_kwargs: dict[typing.Literal['except_when_invalid', 'allowed_start', 'allowed_end', 'deadend_start', 'deadend_end'], bool | None | list[tuple[int, int]]]
- grid_shape: tuple[int, int]
View Source on GitHub
- grid_shape_np: jaxtyping.Int8[ndarray, 'row_col']
View Source on GitHub
- max_grid_n: int
View Source on GitHub
def stable_hash_cfg
(self) -> int
View Source on GitHub
def to_fname
(self) -> str
View Source on GitHub
convert config to a filename
def summary
(self) -> dict
View Source on GitHub
return a summary of the config
def serialize
(self) -> dict[str, typing.Any]
View Source on GitHub
returns the class as a dict, implemented by using
@serializable_dataclass decorator
def load
(cls, data: Union[dict[str, Any], ~T]) -> Type[~T]
View Source on GitHub
takes in an appropriately structured dict and returns an instance of the
class, implemented by using @serializable_dataclass decorator
def validate_fields_types
(
self: muutils.json_serialize.serializable_dataclass.SerializableDataclass,
on_typecheck_error: muutils.errormode.ErrorMode = ErrorMode.Except
) -> bool
View Source on GitHub
validate the types of all the fields on a SerializableDataclass. calls
SerializableDataclass__validate_field_type for each field
Inherited Members
- name
- seq_len_min
- seq_len_max
- seed
- applied_filters
- validate_field_type
- diff
- update_from_nested_dict
class MazeDataset(typing.Generic[+T_co]):
View Source on GitHub
a maze dataset class. This is a collection of solved mazes, and should
be initialized via
MazeDataset.from_config
MazeDataset
(
cfg: maze_dataset.dataset.maze_dataset.MazeDatasetConfig,
mazes: Sequence[maze_dataset.maze.lattice_maze.SolvedMaze],
generation_metadata_collected: dict | None = None
)
View Source on GitHub
- cfg: maze_dataset.dataset.maze_dataset.MazeDatasetConfig
- mazes: list[maze_dataset.maze.lattice_maze.SolvedMaze]
- generation_metadata_collected: dict | None
def data_hash
(self) -> int
View Source on GitHub
def as_tokens
(
self,
maze_tokenizer,
limit: int | None = None,
join_tokens_individual_maze: bool = False
) -> list[list[str]] | list[str]
View Source on GitHub
return the dataset as tokens according to the passed maze_tokenizer
the maze_tokenizer should be either a MazeTokenizer or a
MazeTokenizerModular
if join_tokens_individual_maze is True, then the tokens of each maze are
joined with a space, and the result is a list of strings. i.e.:
>>> dataset.as_tokens(join_tokens_individual_maze=False)
[["a", "b", "c"], ["d", "e", "f"]]
>>> dataset.as_tokens(join_tokens_individual_maze=True)
["a b c", "d e f"]
def generate
(
cls,
cfg: maze_dataset.dataset.maze_dataset.MazeDatasetConfig,
gen_parallel: bool = False,
pool_kwargs: dict | None = None,
verbose: bool = False
) -> maze_dataset.dataset.maze_dataset.MazeDataset
View Source on GitHub
generate a maze dataset given a config and some generation parameters
def download
(
cls,
cfg: maze_dataset.dataset.maze_dataset.MazeDatasetConfig,
**kwargs
) -> maze_dataset.dataset.maze_dataset.MazeDataset
View Source on GitHub
def load
(
cls,
data: Union[bool, int, float, str, list, Dict[str, Any], NoneType]
) -> maze_dataset.dataset.maze_dataset.MazeDataset
View Source on GitHub
load from zanj/json
def serialize
(self) -> Union[bool, int, float, str, list, Dict[str, Any], NoneType]
View Source on GitHub
serialize to zanj/json
def update_self_config
(self)
View Source on GitHub
update the config to match the current state of the dataset (number of
mazes, such as after filtering)
def custom_maze_filter
(
self,
method: Callable[[maze_dataset.maze.lattice_maze.SolvedMaze], bool],
**kwargs
) -> maze_dataset.dataset.maze_dataset.MazeDataset
View Source on GitHub
filter the dataset using a custom method
Inherited Members
- from_config
- save
- read
- FilterBy
- filter_by
class MazeDatasetCollection(typing.Generic[+T_co]):
View Source on GitHub
a collection of maze datasets
MazeDatasetCollection
(
cfg: maze_dataset.dataset.collected_dataset.MazeDatasetCollectionConfig,
maze_datasets: list[maze_dataset.dataset.maze_dataset.MazeDataset],
generation_metadata_collected: dict | None = None
)
View Source on GitHub
- cfg: maze_dataset.dataset.collected_dataset.MazeDatasetCollectionConfig
- maze_datasets: list[maze_dataset.dataset.maze_dataset.MazeDataset]
- generation_metadata_collected: dict | None
- dataset_lengths: list[int]
View Source on GitHub
- dataset_cum_lengths: jaxtyping.Int[ndarray, 'indices']
View Source on GitHub
- mazes: list[maze_dataset.maze.lattice_maze.LatticeMaze]
View Source on GitHub
def generate
(
cls,
cfg: maze_dataset.dataset.collected_dataset.MazeDatasetCollectionConfig,
**kwargs
) -> maze_dataset.dataset.collected_dataset.MazeDatasetCollection
View Source on GitHub
def download
(
cls,
cfg: maze_dataset.dataset.collected_dataset.MazeDatasetCollectionConfig,
**kwargs
) -> maze_dataset.dataset.collected_dataset.MazeDatasetCollection
View Source on GitHub
def serialize
(self) -> Union[bool, int, float, str, list, Dict[str, Any], NoneType]
View Source on GitHub
def load
(
cls,
data: Union[bool, int, float, str, list, Dict[str, Any], NoneType]
) -> maze_dataset.dataset.collected_dataset.MazeDatasetCollection
View Source on GitHub
def as_tokens
(
self,
maze_tokenizer,
limit: int | None = None,
join_tokens_individual_maze: bool = False
) -> list[list[str]] | list[str]
View Source on GitHub
return the dataset as tokens
if join_tokens_individual_maze is True, then the tokens of each maze are
joined with a space, and the result is a list of strings. i.e.: >>>
dataset.as_tokens(join_tokens_individual_maze=False) [[“a”, “b”, “c”],
[“d”, “e”, “f”]] >>> dataset.as_tokens(join_tokens_individual_maze=True)
[“a b c”, “d e f”]
def update_self_config
(self) -> None
View Source on GitHub
update the config of the dataset to match the actual data, if needed
for example, adjust number of mazes after filtering
Inherited Members
- from_config
- save
- read
- data_hash
- FilterBy
- filter_by
class MazeDatasetCollectionConfig(maze_dataset.dataset.dataset.GPTDatasetConfig):
View Source on GitHub
maze dataset collection configuration, including tokenizers and shuffle
MazeDatasetCollectionConfig
(
*,
name: str,
seq_len_min: int = 1,
seq_len_max: int = 512,
seed: int | None = 42,
applied_filters: list[dict[typing.Literal['name', 'args', 'kwargs'], str | list | dict]] = ,
maze_dataset_configs: list[maze_dataset.dataset.maze_dataset.MazeDatasetConfig]
)
- maze_dataset_configs: list[maze_dataset.dataset.maze_dataset.MazeDatasetConfig]
def summary
(self) -> dict
View Source on GitHub
return a summary of the config
- n_mazes: int
View Source on GitHub
- max_grid_n: int
View Source on GitHub
- max_grid_shape: tuple[int, int]
View Source on GitHub
- max_grid_shape_np: jaxtyping.Int8[ndarray, 'row_col']
View Source on GitHub
def stable_hash_cfg
(self) -> int
View Source on GitHub
def to_fname
(self) -> str
View Source on GitHub
convert config to a filename
def serialize
(self) -> dict[str, typing.Any]
View Source on GitHub
returns the class as a dict, implemented by using
@serializable_dataclass decorator
def load
(cls, data: Union[dict[str, Any], ~T]) -> Type[~T]
View Source on GitHub
takes in an appropriately structured dict and returns an instance of the
class, implemented by using @serializable_dataclass decorator
def validate_fields_types
(
self: muutils.json_serialize.serializable_dataclass.SerializableDataclass,
on_typecheck_error: muutils.errormode.ErrorMode = ErrorMode.Except
) -> bool
View Source on GitHub
validate the types of all the fields on a SerializableDataclass. calls
SerializableDataclass__validate_field_type for each field
Inherited Members
- name
- seq_len_min
- seq_len_max
- seed
- applied_filters
- validate_field_type
- diff
- update_from_nested_dict
class TargetedLatticeMaze(maze_dataset.maze.lattice_maze.LatticeMaze):
View Source on GitHub
A LatticeMaze with a start and end position
TargetedLatticeMaze
(
*,
connection_list: jaxtyping.Bool[ndarray, 'lattice_dim=2 row col'],
generation_meta: dict | None = None,
start_pos: jaxtyping.Int8[ndarray, 'row_col'],
end_pos: jaxtyping.Int8[ndarray, 'row_col']
)
- start_pos: jaxtyping.Int8[ndarray, 'row_col']
- end_pos: jaxtyping.Int8[ndarray, 'row_col']
def get_start_pos_tokens
(self) -> list[str | tuple[int, int]]
View Source on GitHub
def get_end_pos_tokens
(self) -> list[str | tuple[int, int]]
View Source on GitHub
def from_lattice_maze
(
cls,
lattice_maze: maze_dataset.maze.lattice_maze.LatticeMaze,
start_pos: jaxtyping.Int8[ndarray, 'row_col'],
end_pos: jaxtyping.Int8[ndarray, 'row_col']
) -> maze_dataset.maze.lattice_maze.TargetedLatticeMaze
View Source on GitHub
def serialize
(self) -> dict[str, typing.Any]
View Source on GitHub
returns the class as a dict, implemented by using
@serializable_dataclass decorator
def load
(cls, data: Union[dict[str, Any], ~T]) -> Type[~T]
View Source on GitHub
takes in an appropriately structured dict and returns an instance of the
class, implemented by using @serializable_dataclass decorator
def validate_fields_types
(
self: muutils.json_serialize.serializable_dataclass.SerializableDataclass,
on_typecheck_error: muutils.errormode.ErrorMode = ErrorMode.Except
) -> bool
View Source on GitHub
validate the types of all the fields on a SerializableDataclass. calls
SerializableDataclass__validate_field_type for each field
Inherited Members
- connection_list
- generation_meta
- lattice_dim
- grid_shape
- n_connections
- grid_n
- heuristic
- nodes_connected
- is_valid_path
- coord_degrees
- get_coord_neighbors
- gen_connected_component_from
- find_shortest_path
- get_nodes
- get_connected_component
- generate_random_path
- as_adj_list
- from_adj_list
- as_adj_list_tokens
- as_tokens
- from_tokens
- as_pixels
- from_pixels
- as_ascii
- from_ascii
- validate_field_type
- diff
- update_from_nested_dict
class LatticeMaze(muutils.json_serialize.serializable_dataclass.SerializableDataclass):
View Source on GitHub
lattice maze (nodes on a lattice, connections only to neighboring nodes)
Connection List represents which nodes (N) are connected in each
direction.
First and second elements represent rightward and downward connections,
respectively.
Example: Connection list: [ [ # down [F T], [F F] ], [ # right [T F], [T
F] ] ]
Nodes with connections N T N F F T N T N F F F
Graph: N - N | N - N
Note: the bottom row connections going down, and the right-hand
connections going right, will always be False.
LatticeMaze
(
*,
connection_list: jaxtyping.Bool[ndarray, 'lattice_dim=2 row col'],
generation_meta: dict | None = None
)
- connection_list: jaxtyping.Bool[ndarray, 'lattice_dim=2 row col']
- generation_meta: dict | None = None
- lattice_dim
View Source on GitHub
- grid_shape
View Source on GitHub
- n_connections
View Source on GitHub
- grid_n: int
View Source on GitHub
def heuristic
(a: tuple[int, int], b: tuple[int, int]) -> float
View Source on GitHub
return manhattan distance between two points
def nodes_connected
(
self,
a: jaxtyping.Int8[ndarray, 'row_col'],
b: jaxtyping.Int8[ndarray, 'row_col'],
/
) -> bool
View Source on GitHub
returns whether two nodes are connected
def is_valid_path
(
self,
path: jaxtyping.Int8[ndarray, 'coord row_col'],
empty_is_valid: bool = False
) -> bool
View Source on GitHub
check if a path is valid
def coord_degrees
(self) -> jaxtyping.Int8[ndarray, 'row col']
View Source on GitHub
Returns an array with the connectivity degree of each coord. I.e., how
many neighbors each coord has.
def get_coord_neighbors
(
self,
c: jaxtyping.Int8[ndarray, 'row_col']
) -> jaxtyping.Int8[ndarray, 'coord row_col']
View Source on GitHub
Returns an array of the neighboring, connected coords of c.
def gen_connected_component_from
(
self,
c: jaxtyping.Int8[ndarray, 'row_col']
) -> jaxtyping.Int8[ndarray, 'coord row_col']
View Source on GitHub
return the connected component from a given coordinate
def find_shortest_path
(
self,
c_start: tuple[int, int],
c_end: tuple[int, int]
) -> jaxtyping.Int8[ndarray, 'coord row_col']
View Source on GitHub
find the shortest path between two coordinates, using A*
def get_nodes
(self) -> jaxtyping.Int8[ndarray, 'coord row_col']
View Source on GitHub
return a list of all nodes in the maze
def get_connected_component
(self) -> jaxtyping.Int8[ndarray, 'coord row_col']
View Source on GitHub
get the largest (and assumed only nonsingular) connected component of
the maze
TODO: other connected components?
def generate_random_path
(
self,
except_when_invalid: bool = True,
allowed_start: list[tuple[int, int]] | None = None,
allowed_end: list[tuple[int, int]] | None = None,
deadend_start: bool = False,
deadend_end: bool = False,
endpoints_not_equal: bool = False
) -> jaxtyping.Int8[ndarray, 'coord row_col']
View Source on GitHub
return a path between randomly chosen start and end nodes within the
connected component
Note that setting special conditions on start and end positions might
cause the same position to be selected as both start and end.
Parameters:
- except_when_invalid : bool deprecated. setting this to False will
cause an error. (defaults to True)
- allowed_start : CoordList | None a list of allowed start positions.
If None, any position in the connected component is allowed
(defaults to None)
- allowed_end : CoordList | None a list of allowed end positions. If
None, any position in the connected component is allowed (defaults
to None)
- deadend_start : bool whether to force the start position to be a
deadend (defaults to False) (defaults to False)
- deadend_end : bool whether to force the end position to be a deadend
(defaults to False) (defaults to False)
- endpoints_not_equal : bool whether to ensure tha the start and end
point are not the same (defaults to False)
Returns:
- CoordArray a path between the selected start and end positions
Raises:
- ValueError : if the connected component has less than 2 nodes and
except_when_invalid is True
def as_adj_list
(
self,
shuffle_d0: bool = True,
shuffle_d1: bool = True
) -> jaxtyping.Int8[ndarray, 'conn start_end coord']
View Source on GitHub
def from_adj_list
(
cls,
adj_list: jaxtyping.Int8[ndarray, 'conn start_end coord']
) -> maze_dataset.maze.lattice_maze.LatticeMaze
View Source on GitHub
create a LatticeMaze from a list of connections
[!NOTE] This has only been tested for square mazes. Might need to
change some things if rectangular mazes are needed.
def as_adj_list_tokens
(self) -> list[str | tuple[int, int]]
View Source on GitHub
def as_tokens
(
self,
maze_tokenizer: maze_dataset.tokenization.maze_tokenizer.MazeTokenizer | maze_dataset.tokenization.maze_tokenizer.TokenizationMode | maze_dataset.tokenization.maze_tokenizer.MazeTokenizerModular
) -> list[str]
View Source on GitHub
serialize maze and solution to tokens
def from_tokens
(
cls,
tokens: list[str],
maze_tokenizer: maze_dataset.tokenization.maze_tokenizer.MazeTokenizer | maze_dataset.tokenization.maze_tokenizer.TokenizationMode | maze_dataset.tokenization.maze_tokenizer.MazeTokenizerModular
) -> maze_dataset.maze.lattice_maze.LatticeMaze
View Source on GitHub
Constructs a maze from a tokenization. Only legacy tokenizers and their
MazeTokenizerModular analogs are supported.
def as_pixels
(
self,
show_endpoints: bool = True,
show_solution: bool = True
) -> jaxtyping.Int[ndarray, 'x y rgb']
View Source on GitHub
def from_pixels
(
cls,
pixel_grid: jaxtyping.Int[ndarray, 'x y rgb']
) -> maze_dataset.maze.lattice_maze.LatticeMaze
View Source on GitHub
def as_ascii
(self, show_endpoints: bool = True, show_solution: bool = True) -> str
View Source on GitHub
return an ASCII grid of the maze
def from_ascii
(cls, ascii_str: str) -> maze_dataset.maze.lattice_maze.LatticeMaze
View Source on GitHub
def serialize
(self) -> dict[str, typing.Any]
View Source on GitHub
returns the class as a dict, implemented by using
@serializable_dataclass decorator
def load
(cls, data: Union[dict[str, Any], ~T]) -> Type[~T]
View Source on GitHub
takes in an appropriately structured dict and returns an instance of the
class, implemented by using @serializable_dataclass decorator
def validate_fields_types
(
self: muutils.json_serialize.serializable_dataclass.SerializableDataclass,
on_typecheck_error: muutils.errormode.ErrorMode = ErrorMode.Except
) -> bool
View Source on GitHub
validate the types of all the fields on a SerializableDataclass. calls
SerializableDataclass__validate_field_type for each field
Inherited Members
- validate_field_type
- diff
- update_from_nested_dict
def set_serialize_minimal_threshold
(threshold: int | None) -> None
View Source on GitHub
class LatticeMazeGenerators:
View Source on GitHub
namespace for lattice maze generation algorithms
def gen_dfs
(
grid_shape: jaxtyping.Int8[ndarray, 'row_col'],
lattice_dim: int = 2,
accessible_cells: int | float | None = None,
max_tree_depth: int | float | None = None,
do_forks: bool = True,
randomized_stack: bool = False,
start_coord: jaxtyping.Int8[ndarray, 'row_col'] | None = None
) -> maze_dataset.maze.lattice_maze.LatticeMaze
View Source on GitHub
generate a lattice maze using depth first search, iterative
Arguments
- grid_shape: Coord: the shape of the grid
- lattice_dim: int: the dimension of the lattice (default: 2)
- accessible_cells: int | float |None: the number of accessible cells
in the maze. If None, defaults to the total number of cells in the
grid. if a float, asserts it is <= 1 and treats it as a proportion
of total cells (default: None)
- max_tree_depth: int | float | None: the maximum depth of the tree.
If None, defaults to 2 * accessible_cells. if a float, asserts it is
<= 1 and treats it as a proportion of the sum of the grid shape
(default: None)
- do_forks: bool: whether to allow forks in the maze. If False, the
maze will be have no forks and will be a simple hallway.
- start_coord: Coord | None: the starting coordinate of the generation
algorithm. If None, defaults to a random coordinate.
algorithm
1. Choose the initial cell, mark it as visited and push it to the stack
2. While the stack is not empty 1. Pop a cell from the stack and make
it a current cell 2. If the current cell has any neighbours which
have not been visited 1. Push the current cell to the stack 2.
Choose one of the unvisited neighbours 3. Remove the wall between
the current cell and the chosen cell 4. Mark the chosen cell as
visited and push it to the stack
def gen_prim
(
grid_shape: jaxtyping.Int8[ndarray, 'row_col'],
lattice_dim: int = 2,
accessible_cells: int | float | None = None,
max_tree_depth: int | float | None = None,
do_forks: bool = True,
start_coord: jaxtyping.Int8[ndarray, 'row_col'] | None = None
) -> maze_dataset.maze.lattice_maze.LatticeMaze
View Source on GitHub
def gen_wilson
(
grid_shape: jaxtyping.Int8[ndarray, 'row_col']
) -> maze_dataset.maze.lattice_maze.LatticeMaze
View Source on GitHub
Generate a lattice maze using Wilson’s algorithm.
Algorithm
Wilson’s algorithm generates an unbiased (random) maze sampled from the
uniform distribution over all mazes, using loop-erased random walks. The
generated maze is acyclic and all cells are part of a unique connected
space.
https://en.wikipedia.org/wiki/Maze_generation_algorithm#Wilson’s_algorithm
def gen_percolation
(
grid_shape: jaxtyping.Int8[ndarray, 'row_col'],
p: float = 0.4,
lattice_dim: int = 2,
start_coord: jaxtyping.Int8[ndarray, 'row_col'] | None = None
) -> maze_dataset.maze.lattice_maze.LatticeMaze
View Source on GitHub
generate a lattice maze using simple percolation
note that p in the range (0.4, 0.7) gives the most interesting mazes
Arguments
- grid_shape: Coord: the shape of the grid
- lattice_dim: int: the dimension of the lattice (default: 2)
- p: float: the probability of a cell being accessible (default: 0.5)
- start_coord: Coord | None: the starting coordinate for the connected
component (default: None will give a random start)
def gen_dfs_percolation
(
grid_shape: jaxtyping.Int8[ndarray, 'row_col'],
p: float = 0.4,
lattice_dim: int = 2,
accessible_cells: int | None = None,
max_tree_depth: int | None = None,
start_coord: jaxtyping.Int8[ndarray, 'row_col'] | None = None
) -> maze_dataset.maze.lattice_maze.LatticeMaze
View Source on GitHub
dfs and then percolation (adds cycles)
- Coord =
- CoordTup = tuple[int, int]
- CoordList = list[tuple[int, int]]
- CoordArray =
- Connection =
- ConnectionList =
- ConnectionArray =
- SPECIAL_TOKENS = _SPECIAL_TOKENS_BASE(ADJLIST_START='', ADJLIST_END='', TARGET_START='', TARGET_END='', ORIGIN_START='', ORIGIN_END='', PATH_START='', PATH_END='', CONNECTOR='<-->', ADJACENCY_ENDLINE=';', PADDING='')
- VOCAB = _VOCAB_BASE(ADJLIST_START='', ADJLIST_END='', TARGET_START='', TARGET_END='', ORIGIN_START='', ORIGIN_END='', PATH_START='', PATH_END='', CONNECTOR='<-->', ADJACENCY_ENDLINE=';', PADDING='', COORD_PRE='(', COORD_INTRA=',', COORD_POST=')', TARGET_INTRA='=', TARGET_POST='||', PATH_INTRA=':', PATH_POST='THEN', NEGATIVE='-', UNKNOWN='', TARGET_A='TARGET_A', TARGET_B='TARGET_B', TARGET_C='TARGET_C', TARGET_D='TARGET_D', TARGET_E='TARGET_E', TARGET_F='TARGET_F', TARGET_G='TARGET_G', TARGET_H='TARGET_H', TARGET_I='TARGET_I', TARGET_J='TARGET_J', TARGET_K='TARGET_K', TARGET_L='TARGET_L', TARGET_M='TARGET_M', TARGET_N='TARGET_N', TARGET_O='TARGET_O', TARGET_P='TARGET_P', TARGET_Q='TARGET_Q', TARGET_R='TARGET_R', TARGET_S='TARGET_S', TARGET_T='TARGET_T', TARGET_U='TARGET_U', TARGET_V='TARGET_V', TARGET_W='TARGET_W', TARGET_X='TARGET_X', TARGET_Y='TARGET_Y', TARGET_Z='TARGET_Z', TARGET_NORTH='TARGET_NORTH', TARGET_SOUTH='TARGET_SOUTH', TARGET_EAST='TARGET_EAST', TARGET_WEST='TARGET_WEST', TARGET_NORTHEAST='TARGET_NORTHEAST', TARGET_NORTHWEST='TARGET_NORTHWEST', TARGET_SOUTHEAST='TARGET_SOUTHEAST', TARGET_SOUTHWEST='TARGET_SOUTHWEST', TARGET_CENTER='TARGET_CENTER', PATH_NORTH='NORTH', PATH_SOUTH='SOUTH', PATH_EAST='EAST', PATH_WEST='WEST', PATH_FORWARD='FORWARD', PATH_BACKWARD='BACKWARD', PATH_LEFT='LEFT', PATH_RIGHT='RIGHT', PATH_STAY='STAY', I_000='+0', I_001='+1', I_002='+2', I_003='+3', I_004='+4', I_005='+5', I_006='+6', I_007='+7', I_008='+8', I_009='+9', I_010='+10', I_011='+11', I_012='+12', I_013='+13', I_014='+14', I_015='+15', I_016='+16', I_017='+17', I_018='+18', I_019='+19', I_020='+20', I_021='+21', I_022='+22', I_023='+23', I_024='+24', I_025='+25', I_026='+26', I_027='+27', I_028='+28', I_029='+29', I_030='+30', I_031='+31', I_032='+32', I_033='+33', I_034='+34', I_035='+35', I_036='+36', I_037='+37', I_038='+38', I_039='+39', I_040='+40', I_041='+41', I_042='+42', I_043='+43', I_044='+44', I_045='+45', I_046='+46', I_047='+47', I_048='+48', I_049='+49', I_050='+50', I_051='+51', I_052='+52', I_053='+53', I_054='+54', I_055='+55', I_056='+56', I_057='+57', I_058='+58', I_059='+59', I_060='+60', I_061='+61', I_062='+62', I_063='+63', I_064='+64', I_065='+65', I_066='+66', I_067='+67', I_068='+68', I_069='+69', I_070='+70', I_071='+71', I_072='+72', I_073='+73', I_074='+74', I_075='+75', I_076='+76', I_077='+77', I_078='+78', I_079='+79', I_080='+80', I_081='+81', I_082='+82', I_083='+83', I_084='+84', I_085='+85', I_086='+86', I_087='+87', I_088='+88', I_089='+89', I_090='+90', I_091='+91', I_092='+92', I_093='+93', I_094='+94', I_095='+95', I_096='+96', I_097='+97', I_098='+98', I_099='+99', I_100='+100', I_101='+101', I_102='+102', I_103='+103', I_104='+104', I_105='+105', I_106='+106', I_107='+107', I_108='+108', I_109='+109', I_110='+110', I_111='+111', I_112='+112', I_113='+113', I_114='+114', I_115='+115', I_116='+116', I_117='+117', I_118='+118', I_119='+119', I_120='+120', I_121='+121', I_122='+122', I_123='+123', I_124='+124', I_125='+125', I_126='+126', I_127='+127', I_128='+128', I_129='+129', I_130='+130', I_131='+131', I_132='+132', I_133='+133', I_134='+134', I_135='+135', I_136='+136', I_137='+137', I_138='+138', I_139='+139', I_140='+140', I_141='+141', I_142='+142', I_143='+143', I_144='+144', I_145='+145', I_146='+146', I_147='+147', I_148='+148', I_149='+149', I_150='+150', I_151='+151', I_152='+152', I_153='+153', I_154='+154', I_155='+155', I_156='+156', I_157='+157', I_158='+158', I_159='+159', I_160='+160', I_161='+161', I_162='+162', I_163='+163', I_164='+164', I_165='+165', I_166='+166', I_167='+167', I_168='+168', I_169='+169', I_170='+170', I_171='+171', I_172='+172', I_173='+173', I_174='+174', I_175='+175', I_176='+176', I_177='+177', I_178='+178', I_179='+179', I_180='+180', I_181='+181', I_182='+182', I_183='+183', I_184='+184', I_185='+185', I_186='+186', I_187='+187', I_188='+188', I_189='+189', I_190='+190', I_191='+191', I_192='+192', I_193='+193', I_194='+194', I_195='+195', I_196='+196', I_197='+197', I_198='+198', I_199='+199', I_200='+200', I_201='+201', I_202='+202', I_203='+203', I_204='+204', I_205='+205', I_206='+206', I_207='+207', I_208='+208', I_209='+209', I_210='+210', I_211='+211', I_212='+212', I_213='+213', I_214='+214', I_215='+215', I_216='+216', I_217='+217', I_218='+218', I_219='+219', I_220='+220', I_221='+221', I_222='+222', I_223='+223', I_224='+224', I_225='+225', I_226='+226', I_227='+227', I_228='+228', I_229='+229', I_230='+230', I_231='+231', I_232='+232', I_233='+233', I_234='+234', I_235='+235', I_236='+236', I_237='+237', I_238='+238', I_239='+239', I_240='+240', I_241='+241', I_242='+242', I_243='+243', I_244='+244', I_245='+245', I_246='+246', I_247='+247', I_248='+248', I_249='+249', I_250='+250', I_251='+251', I_252='+252', I_253='+253', I_254='+254', I_255='+255', CTT_0='0', CTT_1='1', CTT_2='2', CTT_3='3', CTT_4='4', CTT_5='5', CTT_6='6', CTT_7='7', CTT_8='8', CTT_9='9', CTT_10='10', CTT_11='11', CTT_12='12', CTT_13='13', CTT_14='14', CTT_15='15', CTT_16='16', CTT_17='17', CTT_18='18', CTT_19='19', CTT_20='20', CTT_21='21', CTT_22='22', CTT_23='23', CTT_24='24', CTT_25='25', CTT_26='26', CTT_27='27', CTT_28='28', CTT_29='29', CTT_30='30', CTT_31='31', CTT_32='32', CTT_33='33', CTT_34='34', CTT_35='35', CTT_36='36', CTT_37='37', CTT_38='38', CTT_39='39', CTT_40='40', CTT_41='41', CTT_42='42', CTT_43='43', CTT_44='44', CTT_45='45', CTT_46='46', CTT_47='47', CTT_48='48', CTT_49='49', CTT_50='50', CTT_51='51', CTT_52='52', CTT_53='53', CTT_54='54', CTT_55='55', CTT_56='56', CTT_57='57', CTT_58='58', CTT_59='59', CTT_60='60', CTT_61='61', CTT_62='62', CTT_63='63', CTT_64='64', CTT_65='65', CTT_66='66', CTT_67='67', CTT_68='68', CTT_69='69', CTT_70='70', CTT_71='71', CTT_72='72', CTT_73='73', CTT_74='74', CTT_75='75', CTT_76='76', CTT_77='77', CTT_78='78', CTT_79='79', CTT_80='80', CTT_81='81', CTT_82='82', CTT_83='83', CTT_84='84', CTT_85='85', CTT_86='86', CTT_87='87', CTT_88='88', CTT_89='89', CTT_90='90', CTT_91='91', CTT_92='92', CTT_93='93', CTT_94='94', CTT_95='95', CTT_96='96', CTT_97='97', CTT_98='98', CTT_99='99', CTT_100='100', CTT_101='101', CTT_102='102', CTT_103='103', CTT_104='104', CTT_105='105', CTT_106='106', CTT_107='107', CTT_108='108', CTT_109='109', CTT_110='110', CTT_111='111', CTT_112='112', CTT_113='113', CTT_114='114', CTT_115='115', CTT_116='116', CTT_117='117', CTT_118='118', CTT_119='119', CTT_120='120', CTT_121='121', CTT_122='122', CTT_123='123', CTT_124='124', CTT_125='125', CTT_126='126', CTT_127='127', I_N256='-256', I_N255='-255', I_N254='-254', I_N253='-253', I_N252='-252', I_N251='-251', I_N250='-250', I_N249='-249', I_N248='-248', I_N247='-247', I_N246='-246', I_N245='-245', I_N244='-244', I_N243='-243', I_N242='-242', I_N241='-241', I_N240='-240', I_N239='-239', I_N238='-238', I_N237='-237', I_N236='-236', I_N235='-235', I_N234='-234', I_N233='-233', I_N232='-232', I_N231='-231', I_N230='-230', I_N229='-229', I_N228='-228', I_N227='-227', I_N226='-226', I_N225='-225', I_N224='-224', I_N223='-223', I_N222='-222', I_N221='-221', I_N220='-220', I_N219='-219', I_N218='-218', I_N217='-217', I_N216='-216', I_N215='-215', I_N214='-214', I_N213='-213', I_N212='-212', I_N211='-211', I_N210='-210', I_N209='-209', I_N208='-208', I_N207='-207', I_N206='-206', I_N205='-205', I_N204='-204', I_N203='-203', I_N202='-202', I_N201='-201', I_N200='-200', I_N199='-199', I_N198='-198', I_N197='-197', I_N196='-196', I_N195='-195', I_N194='-194', I_N193='-193', I_N192='-192', I_N191='-191', I_N190='-190', I_N189='-189', I_N188='-188', I_N187='-187', I_N186='-186', I_N185='-185', I_N184='-184', I_N183='-183', I_N182='-182', I_N181='-181', I_N180='-180', I_N179='-179', I_N178='-178', I_N177='-177', I_N176='-176', I_N175='-175', I_N174='-174', I_N173='-173', I_N172='-172', I_N171='-171', I_N170='-170', I_N169='-169', I_N168='-168', I_N167='-167', I_N166='-166', I_N165='-165', I_N164='-164', I_N163='-163', I_N162='-162', I_N161='-161', I_N160='-160', I_N159='-159', I_N158='-158', I_N157='-157', I_N156='-156', I_N155='-155', I_N154='-154', I_N153='-153', I_N152='-152', I_N151='-151', I_N150='-150', I_N149='-149', I_N148='-148', I_N147='-147', I_N146='-146', I_N145='-145', I_N144='-144', I_N143='-143', I_N142='-142', I_N141='-141', I_N140='-140', I_N139='-139', I_N138='-138', I_N137='-137', I_N136='-136', I_N135='-135', I_N134='-134', I_N133='-133', I_N132='-132', I_N131='-131', I_N130='-130', I_N129='-129', I_N128='-128', I_N127='-127', I_N126='-126', I_N125='-125', I_N124='-124', I_N123='-123', I_N122='-122', I_N121='-121', I_N120='-120', I_N119='-119', I_N118='-118', I_N117='-117', I_N116='-116', I_N115='-115', I_N114='-114', I_N113='-113', I_N112='-112', I_N111='-111', I_N110='-110', I_N109='-109', I_N108='-108', I_N107='-107', I_N106='-106', I_N105='-105', I_N104='-104', I_N103='-103', I_N102='-102', I_N101='-101', I_N100='-100', I_N099='-99', I_N098='-98', I_N097='-97', I_N096='-96', I_N095='-95', I_N094='-94', I_N093='-93', I_N092='-92', I_N091='-91', I_N090='-90', I_N089='-89', I_N088='-88', I_N087='-87', I_N086='-86', I_N085='-85', I_N084='-84', I_N083='-83', I_N082='-82', I_N081='-81', I_N080='-80', I_N079='-79', I_N078='-78', I_N077='-77', I_N076='-76', I_N075='-75', I_N074='-74', I_N073='-73', I_N072='-72', I_N071='-71', I_N070='-70', I_N069='-69', I_N068='-68', I_N067='-67', I_N066='-66', I_N065='-65', I_N064='-64', I_N063='-63', I_N062='-62', I_N061='-61', I_N060='-60', I_N059='-59', I_N058='-58', I_N057='-57', I_N056='-56', I_N055='-55', I_N054='-54', I_N053='-53', I_N052='-52', I_N051='-51', I_N050='-50', I_N049='-49', I_N048='-48', I_N047='-47', I_N046='-46', I_N045='-45', I_N044='-44', I_N043='-43', I_N042='-42', I_N041='-41', I_N040='-40', I_N039='-39', I_N038='-38', I_N037='-37', I_N036='-36', I_N035='-35', I_N034='-34', I_N033='-33', I_N032='-32', I_N031='-31', I_N030='-30', I_N029='-29', I_N028='-28', I_N027='-27', I_N026='-26', I_N025='-25', I_N024='-24', I_N023='-23', I_N022='-22', I_N021='-21', I_N020='-20', I_N019='-19', I_N018='-18', I_N017='-17', I_N016='-16', I_N015='-15', I_N014='-14', I_N013='-13', I_N012='-12', I_N011='-11', I_N010='-10', I_N009='-9', I_N008='-8', I_N007='-7', I_N006='-6', I_N005='-5', I_N004='-4', I_N003='-3', I_N002='-2', I_N001='-1', PATH_PRE='STEP', ADJLIST_PRE='ADJ_GROUP', ADJLIST_INTRA='&', ADJLIST_WALL='', RESERVE_708='', RESERVE_709='', RESERVE_710='', RESERVE_711='', RESERVE_712='', RESERVE_713='', RESERVE_714='', RESERVE_715='', RESERVE_716='', RESERVE_717='', RESERVE_718='', RESERVE_719='', RESERVE_720='', RESERVE_721='', RESERVE_722='', RESERVE_723='', RESERVE_724='', RESERVE_725='', RESERVE_726='', RESERVE_727='', RESERVE_728='', RESERVE_729='', RESERVE_730='', RESERVE_731='', RESERVE_732='', RESERVE_733='', RESERVE_734='', RESERVE_735='', RESERVE_736='', RESERVE_737='', RESERVE_738='', RESERVE_739='', RESERVE_740='', RESERVE_741='', RESERVE_742='', RESERVE_743='', RESERVE_744='', RESERVE_745='', RESERVE_746='', RESERVE_747='', RESERVE_748='', RESERVE_749='', RESERVE_750='', RESERVE_751='', RESERVE_752='', RESERVE_753='', RESERVE_754='', RESERVE_755='', RESERVE_756='', RESERVE_757='', RESERVE_758='', RESERVE_759='', RESERVE_760='', RESERVE_761='', RESERVE_762='', RESERVE_763='', RESERVE_764='', RESERVE_765='', RESERVE_766='', RESERVE_767='', RESERVE_768='', RESERVE_769='', RESERVE_770='', RESERVE_771='', RESERVE_772='', RESERVE_773='', RESERVE_774='', RESERVE_775='', RESERVE_776='', RESERVE_777='', RESERVE_778='', RESERVE_779='', RESERVE_780='', RESERVE_781='', RESERVE_782='', RESERVE_783='', RESERVE_784='', RESERVE_785='', RESERVE_786='', RESERVE_787='', RESERVE_788='', RESERVE_789='', RESERVE_790='', RESERVE_791='', RESERVE_792='', RESERVE_793='', RESERVE_794='', RESERVE_795='', RESERVE_796='', RESERVE_797='', RESERVE_798='', RESERVE_799='', RESERVE_800='', RESERVE_801='', RESERVE_802='', RESERVE_803='', RESERVE_804='', RESERVE_805='', RESERVE_806='', RESERVE_807='', RESERVE_808='', RESERVE_809='', RESERVE_810='', RESERVE_811='', RESERVE_812='', RESERVE_813='', RESERVE_814='', RESERVE_815='', RESERVE_816='', RESERVE_817='', RESERVE_818='', RESERVE_819='', RESERVE_820='', RESERVE_821='', RESERVE_822='', RESERVE_823='', RESERVE_824='', RESERVE_825='', RESERVE_826='', RESERVE_827='', RESERVE_828='', RESERVE_829='', RESERVE_830='', RESERVE_831='', RESERVE_832='', RESERVE_833='', RESERVE_834='', RESERVE_835='', RESERVE_836='', RESERVE_837='', RESERVE_838='', RESERVE_839='', RESERVE_840='', RESERVE_841='', RESERVE_842='', RESERVE_843='', RESERVE_844='', RESERVE_845='', RESERVE_846='', RESERVE_847='', RESERVE_848='', RESERVE_849='', RESERVE_850='', RESERVE_851='', RESERVE_852='', RESERVE_853='', RESERVE_854='', RESERVE_855='', RESERVE_856='', RESERVE_857='', RESERVE_858='', RESERVE_859='', RESERVE_860='', RESERVE_861='', RESERVE_862='', RESERVE_863='', RESERVE_864='', RESERVE_865='', RESERVE_866='', RESERVE_867='', RESERVE_868='', RESERVE_869='', RESERVE_870='', RESERVE_871='', RESERVE_872='', RESERVE_873='', RESERVE_874='', RESERVE_875='', RESERVE_876='', RESERVE_877='', RESERVE_878='', RESERVE_879='', RESERVE_880='', RESERVE_881='', RESERVE_882='', RESERVE_883='', RESERVE_884='', RESERVE_885='', RESERVE_886='', RESERVE_887='', RESERVE_888='', RESERVE_889='', RESERVE_890='', RESERVE_891='', RESERVE_892='', RESERVE_893='', RESERVE_894='', RESERVE_895='', RESERVE_896='', RESERVE_897='', RESERVE_898='', RESERVE_899='', RESERVE_900='', RESERVE_901='', RESERVE_902='', RESERVE_903='', RESERVE_904='', RESERVE_905='', RESERVE_906='', RESERVE_907='', RESERVE_908='', RESERVE_909='', RESERVE_910='', RESERVE_911='', RESERVE_912='', RESERVE_913='', RESERVE_914='', RESERVE_915='', RESERVE_916='', RESERVE_917='', RESERVE_918='', RESERVE_919='', RESERVE_920='', RESERVE_921='', RESERVE_922='', RESERVE_923='', RESERVE_924='', RESERVE_925='', RESERVE_926='', RESERVE_927='', RESERVE_928='', RESERVE_929='', RESERVE_930='', RESERVE_931='