Un generador de laberintos en Python: lee una configuración, genera un
laberinto (perfecto o tablero tipo Pac-Man) con un «42» en el centro, lo guarda en
hexadecimal, lo dibuja en la terminal con un menú y empaqueta la generación como módulo
pip reutilizable. El repo pasa mypy --strict y, en su versión con
espacios, flake8; y cientos de laberintos generados pasan el
maze_analyzer.py del enunciado, incluido el bonus de cero callejones.
pip porque se reutilizará en un
proyecto posterior, y el modo «no perfecto» tiene que producir un tablero directamente
usable en un juego tipo Pac-Man (que en 42next es un proyecto del rank 04). Es el primer
proyecto del cursus que piensa en quien va a usar tu código después.La página usa palabras de la teoría de grafos, de los algoritmos de búsqueda y de las herramientas de Python. Aquí está cada una explicada desde cero y con un ejemplo sacado del propio A-Maze-ing. En el resto de la página, la primera vez que sale uno de estos términos en cada tarjeta lleva un enlace a su entrada.
Un grafo es un conjunto de nodos (o vértices) unidos por aristas. Solo importa qué está conectado con qué, no dónde está dibujado. Sirve para modelar mapas, redes, dependencias… y laberintos.
En A-Maze-ing cada celda libre es un nodo y cada pared abierta entre dos celdas es una arista.
El laberinto del config.txt por defecto tiene 300 celdas, de las que 20 son del «42»,
así que el grafo tiene 280 nodos.
El número de aristas que salen de un nodo. En un laberinto, el número de paredes abiertas de una celda: de 0 a 4.
_degree(cell) es len(self.neighbours(cell)). Grado 1 es un callejón
sin salida, grado 2 un pasillo y grado 3 o 4 un cruce. Las celdas del «42» tienen grado 0.
Un grafo es conexo si desde cualquier nodo se puede llegar a cualquier otro siguiendo aristas. Si no, está partido en trozos aislados (componentes).
Es lo primero que mira maze_analyzer.py: «Reachable region: 280 cells (0
corridor(s) unreachable)». El borde libre alrededor del «42» está para que el dibujo no corte el
laberinto en dos.
Un ciclo es un camino que vuelve a su punto de partida sin repetir aristas. En un
laberinto, un circuito por el que se puede dar la vuelta. Los bucles independientes de un
grafo conexo son aristas − nodos + 1: cuántas aristas sobran respecto a lo mínimo
para tenerlo todo conectado, y por tanto cuántos ciclos «nuevos» hay.
_loops hace exactamente esa cuenta. Con la configuración por defecto, el laberinto
perfecto da 0 y el tablero Pac-Man 29, las «29 independent routes» del analizador. 29 bucles con 280
nodos son 308 aristas: 279 del árbol y 29 de más.
Un árbol es un grafo conexo sin ciclos. Con N nodos tiene siempre N − 1 aristas: si tuviera menos estaría partido, y si tuviera más habría un ciclo. Un árbol generador de un grafo es un árbol que usa todos sus nodos y solo aristas de ese grafo.
La cuadrícula con todas las paredes abiertas es el grafo; un laberinto perfecto es uno de sus árboles generadores. Con 280 celdas libres el backtracker abre exactamente 279 paredes.
Un laberinto con un único camino entre dos celdas cualesquiera: ni bucles ni zonas aisladas. Es lo mismo que decir que su grafo es un árbol.
Con PERFECT=True y la semilla 42, el analizador da 0 bucles y 29 callejones reales
(más 3 encerrados por el «42»). Todo árbol con más de un nodo tiene callejones: sus hojas, los
nodos de grado 1.
Un callejón sin salida es una celda con una sola abertura (grado 1). Trenzar un laberinto es abrirle paredes en los callejones hasta que no quede ninguno; el resultado tiene bucles y se parece a un tablero de Pac-Man, donde el jugador nunca queda acorralado sin escapatoria.
_braid recorre los callejones en orden aleatorio y abre una pared en cada uno,
mejor hacia otro callejón, porque así una sola pared arregla dos. Con el config.txt
por defecto quedan 0 callejones reales.
La búsqueda en profundidad (depth-first search) recorre un grafo avanzando siempre desde el último nodo alcanzado mientras pueda, y retrocediendo (backtracking) solo cuando se queda sin salidas. Es como recorrer un laberinto con la mano en la pared.
El «recursive backtracker» es un DFS que elige al azar la siguiente vecina y abre la pared que cruza. Como cada paso avanza todo lo que puede antes de volver, salen pasillos largos y retorcidos.
La búsqueda en anchura (breadth-first search) explora un grafo por capas: primero los vecinos del origen, luego los vecinos de esos, y así. Como llega a cada nodo por orden de distancia, la primera vez que lo alcanza es por un camino de longitud mínima. Vale para grafos sin pesos, donde todas las aristas cuestan lo mismo.
solution es un BFS desde la entrada. Con la configuración por defecto, el camino
tiene 39 pasos: 19 al este, 17 al sur y 3 al norte que obligan a bajar 3 más.
Una estructura en la que solo se mete y se saca por arriba: el último en entrar es el primero en
salir (last in, first out). En Python basta una lista con append y
pop.
_carve_backtracker guarda en stack el camino desde la entrada hasta
la celda actual. Avanzar es stack.append(nxt) y retroceder,
stack.pop(). Termina cuando la pila se vacía.
dequeUna cola es lo contrario de una pila: se mete por un lado y se saca por el otro, como en la
cola de un supermercado (first in, first out). collections.deque es la cola
de Python, con append y popleft en tiempo constante.
El BFS de solution la necesita para explorar por capas. Con una lista normal,
pop(0) movería todos los elementos una posición en cada paso.
Una función recursiva se llama a sí misma con un problema más pequeño. Cada llamada pendiente
ocupa un marco en la pila de llamadas, y Python corta cuando hay demasiadas: el límite por defecto
es 1000 (sys.getrecursionlimit()) y pasarlo lanza RecursionError.
Un backtracker recursivo bajaría un nivel por cada celda del pasillo actual, y en un laberinto de 200×200 hay 40 000 celdas. Por eso el código usa una pila explícita en vez de recursión.
Un algoritmo clásico para construir un árbol generador: se empieza en un nodo y en cada paso se añade una arista que conecte lo ya construido con un nodo nuevo. El original elige la arista más barata; la versión para laberintos elige una al azar.
_carve_prim guarda la frontera (las paredes entre lo construido y lo que
falta) y saca una al azar en cada paso. Da muchos pasillos cortos y ramificados.
De dónde viene: lo publicó Robert Prim en 1957; Vojtěch Jarník lo había descrito ya en 1930.
Un ordenador no genera azar de verdad: un generador pseudoaleatorio calcula una secuencia de números que parece aleatoria a partir de un valor inicial, la semilla. Con la misma semilla, la misma secuencia. El de Python es el Mersenne Twister.
random.Random(42).random() da siempre 0.6394267984578837. Por eso
SEED=42 da siempre el mismo laberinto: todas las elecciones salen de un único
random.Random(self.seed). Sin SEED, se elige una al azar y se muestra
para poder repetirla.
Un entero usado como conjunto de interruptores: cada bit dice sí o no a una cosa. Se consulta con
& (AND), se enciende con |= (OR) y se apaga con &= ~
(AND con el complemento, que tiene todos los bits a 1 menos ese).
Cada celda guarda sus paredes cerradas en 4 bits: norte 1, este 2, sur 4, oeste 8. Una celda
con norte y oeste cerradas vale 1 + 8 = 9. Abrir el este de una celda a 15 es
15 & ~2 = 13.
La base 16, con las cifras 0–9 y A–F. Cada
cifra equivale exactamente a 4 bits, así que un número de 4 bits cabe en una sola cifra.
Por eso el fichero de salida usa una cifra hexadecimal por celda: F son las cuatro
paredes (una celda del «42»), 9 norte y oeste, 0 ninguna.
to_hex la escribe con f"{walls:X}".
Secuencias que empiezan por el carácter ESC (\033) y que la terminal interpreta
como órdenes en vez de imprimirlas: cambiar colores, mover el cursor, borrar. Se llaman así por el
estándar ANSI X3.64.
_paint escribe \033[48;5;Nm (fondo del color N de la paleta de 256)
seguido de dos espacios y \033[0m (volver al color normal). Un bloque de pared blanca
es el color 255.
Una excepción es la forma de Python de señalar un error: se lanza con
raise, sube por las llamadas y se captura con try/except.
Si nadie la captura, el programa se para y escribe el traceback: la lista de llamadas por
las que pasó. En la evaluación, un traceback cuenta como «no funcional».
El proyecto define dos: ConfigError para la configuración y MazeError
para parámetros imposibles. main captura esas dos y OSError, imprime un
mensaje y devuelve 1: «Impossible maze: exit 10,7 falls inside the '42' pattern».
withUn objeto que sabe prepararse y recogerse: with lo abre al entrar en el bloque y
lo cierra al salir, también si dentro se lanza una excepción. El caso típico son los
ficheros.
read_config y write_maze abren con
with open(...) as stream:, que es lo que pide el enunciado. Sin with,
una excepción entre el open y el close dejaría el fichero abierto.
Un decorador de la biblioteca estándar que genera solo el __init__ (y la
representación y la comparación) de una clase a partir de sus campos anotados. Sirve para clases que
son sobre todo datos.
MazeConfig y DisplayState son dataclasses: MazeConfig
tiene ocho campos, los dos últimos con valor por defecto (seed=None,
algorithm="backtracker").
Las anotaciones (def _loops(self) -> int:, visited: Set[Cell])
dicen qué tipo se espera. Python no las comprueba al ejecutar; mypy las lee antes y
avisa de las incoherencias, como haría un compilador. --strict activa todas sus
comprobaciones.
El enunciado fija los flags de make lint; el repo pasa también
mypy --strict sin un aviso. Cell = Tuple[int, int] es un alias:
un nombre corto para un tipo largo.
PEP 8 es la guía de estilo oficial de Python: sangría de 4 espacios, líneas de 79 caracteres
como mucho, dos líneas en blanco entre funciones… flake8 es la herramienta que la
comprueba, con códigos como W191 («indentation contains tabs») o E101
(mezcla de tabuladores y espacios).
Los .py de este repo en packs/ llevan tabuladores a propósito, así que
flake8 da 1120 avisos, casi todos W191 y E101. La versión con
espacios, la que se entrega, pasa sin ninguno.
Un docstring es la cadena entre triples comillas que va como primera línea de un módulo, una
clase o una función: su documentación, accesible en tiempo de ejecución con help().
PEP 257 fija cómo se escriben: una primera línea que resume, una línea en blanco y luego el
detalle.
El docstring de MazeGenerator sigue el estilo Google, con secciones
Args:, Raises: y Attributes:. Algunos fragmentos de la página
lo omiten para ir al grano.
Un módulo es un fichero .py; un paquete, una carpeta de módulos
con un __init__.py. Un wheel (.whl) es un zip con el paquete
listo para instalar con pip, sin compilar nada; un sdist
(.tar.gz) son las fuentes para construirlo.
mazegen/ es el paquete, y su __init__.py decide qué se exporta
(__all__): MazeGenerator, MazeError, las direcciones,
Cell y ALGORITHMS. El wheel es
mazegen-1.0.0-py3-none-any.whl.
Una carpeta con su propio Python y sus propios paquetes, separada del sistema. Se crea con
python3 -m venv .venv y se activa con . .venv/bin/activate; desde ahí,
pip install instala solo dentro.
Es la forma de probar que el wheel funciona en limpio: instalarlo en un entorno nuevo e
importarlo desde fuera del repo. El Makefile excluye .venv de flake8 y
mypy.
El texto que dice qué pueden hacer otros con tu código. Sin licencia, el autor conserva todos los derechos y nadie puede reutilizarlo legalmente. Las permisivas (MIT, BSD, Apache) dejan hacer casi todo; las copyleft (GPL) obligan a que lo derivado se distribuya con la misma licencia.
LICENSE.md es MIT, y pyproject.toml lo declara con
license = "MIT" y license-files.
a_maze_ing.py que se ejecuta con
python3 a_maze_ing.py config.txt.mazegen-* (.whl o .tar.gz) en la
raíz del repositorio, con su LICENSE.md.install, run, debug,
clean y lint (flags de mypy fijados por el enunciado;
lint-strict opcional), y un README con secciones específicas.Bonus propuestos: un tablero no perfecto sin ningún callejón sin salida, varios algoritmos de generación y animación durante la generación. Esta solución hace los dos primeros.
Cada fichero hace una sola cosa, y solo mazegen/ sabe generar laberintos:
| Fichero | Papel |
|---|---|
a_maze_ing.py | programa principal: config → generación → fichero → menú |
maze_config.py | lee y valida el fichero de configuración |
maze_output.py | escribe el fichero hexadecimal |
maze_display.py | dibujo en terminal con colores ANSI |
mazegen/generator.py | la clase MazeGenerator (lo reutilizable) |
pyproject.toml | metadatos para reconstruir el .whl |
El Makefile no compila nada: es un menú de tareas.
install:
$(PYTHON) -m pip install --upgrade pip
$(PYTHON) -m pip install flake8 mypy build
run:
$(PYTHON) $(MAIN) $(CONFIG)
debug:
$(PYTHON) -m pdb $(MAIN) $(CONFIG)
build:
$(PYTHON) -m build --wheel --outdir .
rm -rf build *.egg-info mazegen.egg-info
lint:
flake8 . --exclude $(VENV)
mypy . --warn-return-any --warn-unused-ignores --ignore-missing-imports \
--disallow-untyped-defs --check-untyped-defs --exclude $(VENV)
Además de las reglas del enunciado hay build (regenera el wheel) y
lint-strict (mypy --strict), que también pasa.
Los .py de packs/ están sangrados con tabuladores a propósito, y los
fragmentos de esta página los muestran tal cual. Por eso, sobre esa copia, flake8 da
1120 avisos, casi todos W191 y E101. Si se cambia cada tabulador del
principio de línea por 4 espacios sale exactamente la versión que se entrega, y esa pasa
flake8 sin ninguno.
MazeGenerator no sabe nada de ficheros de
configuración ni de colores, se puede cambiar el dibujo ASCII por la MiniLibX — o llevarse
el generador al Pac-Man del rank 04 — sin tocar una línea de la generación.Un par CLAVE=VALOR por línea; las que empiezan por # son
comentarios. Las seis primeras claves son obligatorias; SEED y
ALGORITHM son añadidos propios, que el enunciado permite:
| Clave | Valor | Por defecto |
|---|---|---|
WIDTH, HEIGHT | tamaño en celdas, de 1 a 200 | obligatoria |
ENTRY, EXIT | celdas x,y (columna, fila), distintas | obligatoria |
OUTPUT_FILE | ruta del fichero de salida | obligatoria |
PERFECT | True/False (también 1/0, yes/no) | obligatoria |
SEED | entero ≥ 0; misma semilla, mismo laberinto | aleatoria |
ALGORITHM | backtracker o prim | backtracker |
# A-Maze-ing default configuration
# Mandatory keys
WIDTH=20
HEIGHT=15
ENTRY=0,0
EXIT=19,14
OUTPUT_FILE=maze.txt
PERFECT=False
# Optional keys
SEED=42
ALGORITHM=backtracker
La lectura va en dos pasos. Primero parse_lines convierte las líneas en un
diccionario y rechaza lo que no tiene forma de configuración:
def parse_lines(lines: list[str]) -> Dict[str, str]:
values: Dict[str, str] = {}
for number, raw in enumerate(lines, start=1):
line = raw.strip()
if not line or line.startswith("#"):
continue
if "=" not in line:
raise ConfigError(
f"line {number}: expected KEY=VALUE, got '{line}'"
)
key, value = (part.strip() for part in line.split("=", 1))
key = key.upper()
if key not in MANDATORY_KEYS + OPTIONAL_KEYS:
raise ConfigError(f"line {number}: unknown key '{key}'")
if key in values:
raise ConfigError(f"line {number}: key '{key}' is repeated")
if not value:
raise ConfigError(f"line {number}: '{key}' has no value")
values[key] = value
missing = [key for key in MANDATORY_KEYS if key not in values]
if missing:
raise ConfigError(f"missing mandatory key(s): {', '.join(missing)}")
return values
Una clave desconocida o repetida es un error a propósito: así un WIDHT=20
con una errata no se ignora en silencio. Después build_config convierte cada
valor y comprueba rangos y coherencia (la entrada dentro del laberinto, distinta de la
salida…). Todo fallo se convierte en una ConfigError con un mensaje legible,
incluido el de abrir el fichero:
def read_config(path: str) -> MazeConfig:
try:
with open(path, encoding="utf-8") as stream:
lines = stream.readlines()
except FileNotFoundError:
raise ConfigError(f"configuration file not found: {path}")
except IsADirectoryError:
raise ConfigError(f"{path} is a directory, not a file")
except (OSError, UnicodeDecodeError) as error:
raise ConfigError(f"cannot read {path}: {error}")
return build_config(parse_lines(lines))
El with es el context manager que pide el enunciado: el fichero se
cierra aunque haya una excepción dentro.
ConfigError) que el main captura en un solo sitio, en lugar de
llenar el código de print y sys.exit.El laberinto es una lista de listas, grid[y][x], y cada celda guarda sus
paredes cerradas en 4 bits, los mismos del fichero de salida:
NORTH = 1
EAST = 2
SOUTH = 4
WEST = 8
ALL_WALLS = NORTH | EAST | SOUTH | WEST
Se empieza con todas las celdas a ALL_WALLS (15, F) y generar
consiste solo en abrir paredes. Abrir una pared es tocar dos celdas: la propia y
la vecina, con la dirección contraria. Por eso todo pasa por un único método:
def _open(self, cell: Cell, direction: int) -> None:
"""Open a wall on both sides, so the encoding stays coherent."""
other = self._step(cell, direction)
self.grid[cell[1]][cell[0]] &= ~direction
self.grid[other[1]][other[0]] &= ~OPPOSITE[direction]
&= ~direction apaga ese bit y deja los otros tres como estaban. Como
ninguna otra parte del código toca grid directamente, es imposible que dos
vecinas no coincidan: la coherencia que comprueba maze_analyzer.py está
garantizada por construcción. El borde exterior nunca se abre porque solo se abren paredes
hacia celdas que existen.
& y se
modifican con |= y &= ~. Y una trampa de coordenadas: la
configuración usa (x, y) — columna, fila — pero una lista de listas se indexa
grid[fila][columna]. Aquí todas las celdas son (x, y) y el cambio
de orden ocurre solo al indexar.El dibujo es una plantilla de 7×5 donde # es una celda cerrada del todo:
PATTERN_42: Tuple[str, ...] = (
"#.#.###",
"#.#...#",
"###.###",
"..#.#..",
"..#.###",
)
def _place_pattern(self) -> None:
"""Close the "42" cells, centred, keeping a free border around."""
self.pattern_cells = set()
self.pattern_omitted = False
if not self.want_pattern:
return
if (self.width < PATTERN_WIDTH + 2
or self.height < PATTERN_HEIGHT + 2):
self.pattern_omitted = True
return
ox = (self.width - PATTERN_WIDTH) // 2
oy = (self.height - PATTERN_HEIGHT) // 2
cells = {
(ox + col, oy + row)
for row, line in enumerate(PATTERN_42)
for col, char in enumerate(line)
if char == "#"
}
for name, cell in (("entry", self.entry), ("exit", self.exit)):
if cell in cells:
raise MazeError(
f"{name} {cell[0]},{cell[1]} falls inside the '42' "
f"pattern"
)
self.pattern_cells = cells
pattern_omitted y el programa imprime el mensaje de error que pide el
enunciado.Los algoritmos tratan las celdas del «42» como si no existieran (_free
devuelve False), así que nunca se abre una pared hacia ellas y quedan cerradas
por los cuatro lados.
def _carve_backtracker(self) -> None:
"""Recursive backtracker (randomized depth-first search).
Implemented with an explicit stack instead of recursion, so big
mazes never hit Python's recursion limit.
"""
start = self.entry
visited: Set[Cell] = {start}
stack: List[Cell] = [start]
while stack:
cell = stack[-1]
options = [
d for d in DIRECTIONS
if self._free(self._step(cell, d))
and self._step(cell, d) not in visited
]
if not options:
stack.pop()
continue
direction = self._rng.choice(options)
nxt = self._step(cell, direction)
self._open(cell, direction)
visited.add(nxt)
stack.append(nxt)
Se parte de la entrada. En cada paso se mira la celda de arriba de la pila: si tiene
vecinas libres sin visitar, se elige una al azar, se abre la pared entre las dos y se
avanza; si no le queda ninguna, se retrocede (pop). Termina cuando la pila se
vacía, es decir, cuando ha vuelto al principio habiendo visitado todo.
Por qué sale perfecto: cada pared que se abre conecta una celda nueva con el laberinto ya hecho. Con N celdas libres se abren exactamente N−1 paredes y todas quedan conectadas: eso es un árbol, sin ningún bucle, con un único camino entre dos celdas cualesquiera. Una sala abierta de 3×3 es imposible, porque contendría un bucle.
La recursión clásica (visitar(celda) que se llama a sí misma) se ha
cambiado por una pila explícita: en un laberinto de 200×200 el camino puede tener decenas de
miles de pasos, y Python corta la recursión hacia los 1000 niveles.
ALGORITHM=prim, bonus) def _carve_prim(self) -> None:
"""Randomized Prim: grow the maze from a random frontier wall."""
start = self.entry
visited: Set[Cell] = {start}
frontier: List[Tuple[Cell, int]] = [(start, d) for d in DIRECTIONS]
while frontier:
index = self._rng.randrange(len(frontier))
frontier[index], frontier[-1] = frontier[-1], frontier[index]
cell, direction = frontier.pop()
nxt = self._step(cell, direction)
if not self._free(nxt) or nxt in visited:
continue
self._open(cell, direction)
visited.add(nxt)
frontier.extend((nxt, d) for d in DIRECTIONS)
En vez de avanzar por un único pasillo, Prim guarda la «frontera»: todas las paredes que
separan lo ya construido de lo que falta. En cada paso saca una al azar (el intercambio con
el último elemento hace que el pop sea O(1)) y, si al otro lado hay una celda
libre sin visitar, la abre. También da un árbol, pero con otra textura: muchos pasillos
cortos y ramificados en lugar de los largos y sinuosos del backtracker.
random.Random(seed): con la misma semilla y los mismos
parámetros, las elecciones son idénticas y el laberinto también. Lo «aleatorio» de un
ordenador es pseudoaleatorio.Con PERFECT=False se genera primero un laberinto perfecto y luego se le
quitan los callejones sin salida («trenzar», braiding):
def generate(self, seed: Optional[int] = None) -> List[List[int]]:
if seed is not None:
self.seed = seed
self._rng = random.Random(self.seed)
self.grid = [[ALL_WALLS] * self.width for _ in range(self.height)]
self._place_pattern()
if self.algorithm == "prim":
self._carve_prim()
else:
self._carve_backtracker()
if not self.perfect:
self._braid()
self._add_loops(2)
return self.grid
Partir del laberinto perfecto da la conectividad total gratis: solo se añaden aberturas, nunca se quitan, así que todo lo que estaba conectado lo sigue estando.
def _braid(self) -> None:
"""Remove dead-ends by opening one extra wall in each of them.
Opening towards another dead-end is preferred: it fixes two
dead-ends with a single wall.
"""
dead_ends = [c for c in self._free_cells() if self._degree(c) == 1]
self._rng.shuffle(dead_ends)
for cell in dead_ends:
if self._degree(cell) != 1:
continue
options = self._closed_inner_walls(cell)
self._rng.shuffle(options)
options.sort(
key=lambda d: self._degree(self._step(cell, d)) != 1
)
for direction in options:
if self._try_open(cell, direction):
break
Un callejón es una celda con una sola salida (grado 1). A cada uno se le abre una pared
más, preferentemente hacia otro callejón (el sort pone primero las direcciones
cuya vecina tiene grado 1), porque así una sola pared arregla dos. Cada pared abierta en un
árbol crea exactamente un bucle nuevo.
Lo que no se puede hacer es abrir salas: los pasillos son de 2 celdas de ancho como
mucho. _try_open abre la pared, mira si ha aparecido un bloque de 3×3 abierto
del todo que la contenga y, si es así, la vuelve a cerrar:
def _try_open(self, cell: Cell, direction: int) -> bool:
self._open(cell, direction)
if self._creates_open_area(cell, direction):
self._close(cell, direction)
return False
return True
def _block_open(self, x0: int, y0: int) -> bool:
if not (self._inside((x0, y0)) and self._inside((x0 + 2, y0 + 2))):
return False
for y in range(y0, y0 + 3):
for x in range(x0, x0 + 3):
if x < x0 + 2 and not self.is_open((x, y), EAST):
return False
if y < y0 + 2 and not self.is_open((x, y), SOUTH):
return False
return True
Por último, _add_loops(2) garantiza las «dos rutas independientes» del
enunciado en tableros pequeños donde el trenzado no basta. El número de bucles
independientes de un grafo conexo es aristas − nodos + 1:
def _loops(self) -> int:
cells = self._free_cells()
edges = sum(self._degree(c) for c in cells) // 2
return edges - len(cells) + 1
Las esquinas y el centro son pasillo siempre: el «42» deja un borde libre y su columna
central abierta. Y si el tablero es tan pequeño que no caben dos bucles (un 2×2 tiene
como mucho uno), el constructor lo rechaza con un MazeError en vez de entregar
un tablero que no cumple.
E − V + 1) y conectividad. Los únicos callejones que quedan son celdas
encerradas por el propio «42», que el analizador tolera porque no se pueden abrir sin
tocarlo. Resultado: con el config.txt por defecto, 0 callejones reales y 29
rutas independientes — el bonus de --max-dead-ends 0.El camino más corto en un grafo sin pesos es una búsqueda en anchura (BFS): se exploran las celdas por orden de distancia a la entrada, y la primera vez que se llega a una es por el camino más corto. Basta guardar de dónde se vino para reconstruirlo al revés:
def solution(self) -> List[Cell]:
self._require_grid()
previous: Dict[Cell, Optional[Cell]] = {self.entry: None}
queue: deque[Cell] = deque([self.entry])
while queue:
cell = queue.popleft()
if cell == self.exit:
break
for nxt in self.neighbours(cell):
if nxt not in previous:
previous[nxt] = cell
queue.append(nxt)
if self.exit not in previous:
return []
path: List[Cell] = []
step: Optional[Cell] = self.exit
while step is not None:
path.append(step)
step = previous[step]
path.reverse()
return path
solution_directions lo convierte en letras comparando cada par de celdas
consecutivas, y maze_output.py monta el fichero: una cifra hexadecimal por
celda, fila a fila, una línea vacía, la entrada, la salida y el camino.
def format_maze(gen: MazeGenerator) -> str:
lines = gen.to_hex()
lines.append("")
lines.append(f"{gen.entry[0]},{gen.entry[1]}")
lines.append(f"{gen.exit[0]},{gen.exit[1]}")
lines.append(gen.solution_directions())
return "\n".join(lines) + "\n"
Salida real del config.txt por defecto (filas del medio recortadas):
95395539555515513913
...
C4545456C54546C54446
0,0
19,14
SSESSESSSSEEESENESSSSEEENNEEESEESSESEEE
Lectura de una cifra: 9 = 1001 = norte y oeste cerradas (la
esquina de arriba a la izquierda); F = las cuatro, una celda del «42».
collections.deque, que saca por la izquierda en O(1); con una lista,
pop(0) sería O(n)). Es el mismo algoritmo que usará un fantasma de Pac-Man para
perseguir al jugador.El dibujo es una rejilla de (2·alto + 1) × (2·ancho + 1) bloques, cada uno
dos espacios con color de fondo. Los bloques impar/impar son celdas; los demás, paredes o
esquinas entre paredes:
██████████████████████████████████████████████████████████████████████████████████
██EE ██ ██ ██ ██
██··██████ ██ ██████████ ██ ██████████████████ ██████████ ██ ██ ██ ██ ██
██·· ██ ██ ██ ██ ██ ██ ██ ██
██··██████████████ ██ ██████████ ██████████ ██████████ ██████████████ ██ ██
██······ ██ ██ ██ ██ ██ ██ ██ ██
██ ██··██ ██ ██ ██████████████████ ██ ██████ ██ ██ ██ ██████████ ██ ██
██ ██··██ ██ ██ ██ ██ ██ ██ ██ ██ ██
██ ██··██████ ██████ ██ ██ ██ ██████ ██ ██████ ██████████ ██████████ ██
██ ██······██ ██ ██ ██ ██ ██ ██
██ ██████··██ ██ ██████████ ██████ ██████████████ ██ ██ ██ ██████████████
██ ██··██ ██ ██▒▒██ ██▒▒██ ██▒▒▒▒▒▒▒▒▒▒██ ██ ██ ██
██████ ██··██ ██ ██ ██▒▒██ ██▒▒██ ██████████▒▒██ ██ ██████████████ ██ ██
██ ██··██ ██ ██ ██▒▒██ ██▒▒██ ██▒▒██ ██ ██ ██ ██
██ ██████··██ ██ ██ ██▒▒██████▒▒██ ██████████▒▒██ ██ ██ ██ ██ ██████████
██ ··██ ██ ██▒▒▒▒▒▒▒▒▒▒██ ██▒▒▒▒▒▒▒▒▒▒██ ██ ██ ██ ██ ██
██ ██████··██████████ ██████████▒▒██ ██▒▒██████████ ██████████ ██ ██ ██ ██
██ ██··············██······██▒▒██ ██▒▒██ ██ ██ ██
██ ██ ██████ ██████··██··██··██▒▒██ ██▒▒██████████ ██████████ ██ ██████ ██
██ ██ ██ ██······██··██▒▒██ ██▒▒▒▒▒▒▒▒▒▒██ ██ ██ ██ ██
██ ██████ ██████ ██████████··██████ ██████████████████ ██ ██████ ██ ██ ██
██ ██ ██ ██ ██··██ ██··············██ ██ ██ ██ ██
██ ██ ██████ ██████ ██ ██··██ ██████··██████████··██ ██████ ██ ██████ ██
██ ██ ██ ██ ··██ ██··██ ██··········██ ██ ██
██ ██ ██ ██████████████████··██████ ██··██ ██ ██████████··██ ██████ ██ ██
██ ██ ██ ██··············██ ██ ██ ██··██ ██ ██ ██
██ ██████ ██ ██ ██ ██ ██████████ ██████ ██ ██ ██ ██··██████ ██ ██ ██
██ ██ ██ ██ ██ ██ ██ ██ ██······██ ██ ██ ██
██ ██ ██████ ██████ ██████ ██ ██████ ██████ ██ ██ ██████··██ ██ ██ ██
██ ██ ██ ············XX██
██████████████████████████████████████████████████████████████████████████████████
El laberinto del config.txt por defecto con el camino visible, en versión sin colores: █ paredes, ▒ el «42», · el camino, EE la entrada y XX la salida.
def _block_colour(gen: MazeGenerator, state: DisplayState, bx: int,
by: int, path_cells: Set[Cell],
path_links: Set[Tuple[Cell, Cell]]) -> int:
x, y = bx // 2, by // 2
if bx % 2 and by % 2: # a cell
cell = (x, y)
if cell in gen.pattern_cells:
return state.pattern_colour
if cell == gen.entry:
return ENTRY_COLOUR
if cell == gen.exit:
return EXIT_COLOUR
return PATH_COLOUR if cell in path_cells else OPEN
if bx % 2: # horizontal wall
above, below = (x, y - 1), (x, y)
if 0 < by < 2 * gen.height and gen.is_open(above, SOUTH):
return PATH_COLOUR if (above, below) in path_links else OPEN
return _wall_colour(gen, state, [above, below])
if by % 2: # vertical wall
left, right = (x - 1, y), (x, y)
if 0 < bx < 2 * gen.width and gen.is_open(left, EAST):
return PATH_COLOUR if (left, right) in path_links else OPEN
return _wall_colour(gen, state, [left, right])
corners = [(x - 1, y - 1), (x, y - 1), (x - 1, y), (x, y)]
return _wall_colour(gen, state, corners)
Las paredes que separan dos celdas del «42» toman el color del «42», así el número se ve relleno y no como un montón de cuadraditos. Después del dibujo sale el menú:
MENU = """
=== A-Maze-ing ===
1. Re-generate a new maze
2. Show/Hide path from entry to exit
3. Change wall colour
4. Change '42' colour
5. Quit"""
Ctrl-D (EOFError) sale limpiamente y Ctrl-C se captura en el
main: ni siquiera cortar el programa da un traceback.
[build-system]
requires = ["setuptools>=68", "wheel"]
build-backend = "setuptools.build_meta"
[project]
name = "mazegen"
version = "1.0.0"
readme = "mazegen/README.md"
license = "MIT"
license-files = ["LICENSE.md"]
requires-python = ">=3.10"
[tool.setuptools]
packages = ["mazegen"]
python3 -m build --wheel lee ese fichero y produce
mazegen-1.0.0-py3-none-any.whl (cualquier Python 3, código puro, cualquier
sistema). Para la evaluación, que pide reconstruirlo desde cero:
python3 -m venv .venv && . .venv/bin/activate
pip install build && python3 -m build --wheel --outdir .
pip install mazegen-1.0.0-py3-none-any.whl
Uso desde otro proyecto, que es lo que tiene que documentar el README:
from mazegen import MazeGenerator, EAST
gen = MazeGenerator(20, 15, entry=(0, 0), exit=(19, 14),
perfect=True, seed=42, algorithm="backtracker")
grid = gen.generate() # grid[y][x] = paredes cerradas de (x, y)
gen.is_open((3, 2), EAST) # ¿está abierta esa pared?
gen.solution() # camino más corto: [(0, 0), (1, 0), ...]
gen.solution_directions() # el mismo camino: "EESE..."
gen.pattern_cells # las celdas del «42»
gen.generate(seed=7) # otro laberinto
La documentación va dentro del propio paquete (mazegen/README.md, que es
además la descripción del wheel) y repetida en el README del repo. Lleva
py.typed, así que mypy comprueba los tipos también en el proyecto
que lo importe.
Licencia: MIT. Permite reutilizar, modificar y redistribuir el generador — que es lo que exige el enunciado para el proyecto posterior — con la única condición de conservar el aviso de copyright.
.tar.gz), las fuentes para construirlo; los dos salen de
pyproject.toml. Y licencias: sin licencia, el código es legalmente tuyo y nadie
puede reutilizarlo; las permisivas (MIT, BSD, Apache) dejan hacer casi todo; las
copyleft (GPL) obligan a que lo derivado siga siendo libre.mypy con los flags del enunciado y mypy --strict,
sin un aviso. flake8 pasa limpio en la versión con espacios; en la de
packs/, con tabuladores, da 1120 avisos de sangría.maze_analyzer.py, más una comprobación propia
de que no hay ningún bloque 3×3 abierto. Lo único que fallaba era el 2×2 en modo Pac-Man,
que es imposible y ahora da error.=, clave que falta, números raros, entrada fuera, entrada igual a salida,
entrada dentro del «42», salida no escribible…): todos con mensaje claro, código de
salida 1 y sin traceback.SEED dan
ficheros idénticos.El runner de test/ repite todo esto (36 casos) con zentest. Sobre la
copia con tabuladores da 35 OK y 1 KO, el de flake8.
_open por el que pasa todo.(x, y) en todo el código; grid[y][x]
solo al indexar.ConfigError, MazeError y
OSError se capturan en main; Ctrl-C y Ctrl-D también.PATTERN_42; un color nuevo, una línea en WALL_COLOURS; una clave
de configuración, OPTIONAL_KEYS y build_config.Enunciado oficial A-Maze-ing «This is the way», versión 2.2 (slug
a-maze-ing), en inglés: packs/cursus/M2/201_A-Maze-ing/en.subject.pdf
y subject.txt, más los adjuntos de extra/
(maze_analyzer.py y mlx-2.2.tgz). El código de esta ficha es el de
packs/cursus/M2/201_A-Maze-ing/repo/. El trasfondo sobre grafos, empaquetado y
licencias es conocimiento general, no del enunciado.
Lo que es fácil que pregunte quien te evalúe, con una respuesta corta y el enlace a la sección donde está explicado a fondo. Están agrupadas en: generación, salida y camino, errores y entrada, y lint, paquete y cambios en directo. Antes de mirar la respuesta, intenta contestar tú.
Porque cada pared que abre une la celda actual con una celda no visitada. Con N celdas libres se abren N − 1 paredes y todo queda conectado: eso es un árbol, sin bucles, con un único camino entre dos celdas. Con la configuración por defecto, 280 celdas y 279 paredes abiertas. → 06
Porque Python corta la recursión hacia los 1000 niveles y un DFS recursivo baja un nivel por celda del pasillo actual. En un laberinto de 200×200 (40 000 celdas) se pasaría de largo. Con una lista como pila el límite es la memoria. → 06
Se parte de un laberinto perfecto, que ya está conectado, y solo se abren paredes,
nunca se cierran: lo conectado sigue conectado. _braid abre una pared en cada callejón
y _add_loops(2) garantiza al menos dos bucles. Cada pared nueva que crearía un bloque
3×3 abierto se vuelve a cerrar. → 07
Toda elección sale de un único random.Random(self.seed), que es pseudoaleatorio:
misma semilla y mismos parámetros, mismas elecciones, mismo laberinto. El tester lo comprueba con
dos ejecuciones. Sin SEED se elige una al azar, y la leyenda la muestra para poder
repetirla. → 06
Necesita 9×7 celdas (la plantilla de 7×5 más un borde libre). Si no cabe, se omite y se
imprime «Error: the maze is too small to draw the '42' pattern (it needs at least 9x7 cells); it
was omitted.», pero el laberinto se genera y se guarda igual. Si la entrada o la salida caen dentro
del «42», es un MazeError. → 05
9. ¿Y F?Cada cifra son 4 bits de paredes cerradas: norte 1, este 2, sur 4, oeste 8.
9 = 8 + 1, oeste y norte cerradas: la esquina de arriba a la izquierda.
F = 15, las cuatro: una celda del «42». → 04,
08
Porque es un BFS: explora por orden de distancia a la entrada, así que la primera vez que llega
a una celda lo hace por un camino mínimo, y se guarda de dónde vino para reconstruirlo. Va con un
deque para sacar por la izquierda en tiempo constante. → 08
Abrir una pared toca siempre las dos celdas a la vez, en _open (y cerrarla, en
_close), y ninguna otra parte del código escribe en grid. El analizador da
«Wall coherence: OK». → 04
No. Todo fallo de lectura o de valor se convierte en ConfigError con un mensaje
(«line 1: unknown key 'WIDHT'», «configuration file not found: …») y parámetros imposibles en
MazeError. main los captura, igual que OSError al escribir, y
devuelve 1. Ctrl-C sale con «Bye!» y Ctrl-D cierra el menú. El tester prueba 12 errores.
→ 03, 09
PERFECT=False da error?Porque el enunciado pide al menos dos rutas independientes y un 2×2 solo admite un bucle. El
constructor calcula (width - 1) * (height - 1) (los bloques 2×2 posibles) y si es
menor que 2 lanza «a non-perfect (Pac-Man) board needs room for at least two loops». Mejor un error
claro que un tablero que no cumple. → 07
make lint delante de mí.mypy pasa con los flags del enunciado y con --strict. flake8
depende de la copia: la de packs/ lleva tabuladores a propósito y da 1120 avisos
(W191, E101); la que se entrega, con 4 espacios, no da ninguno. Antes de
la evaluación, comprueba que el repo de la entrega es la versión con espacios.
→ 11
En un entorno virtual limpio: pip install build, python3 -m build --wheel
--outdir . y pip install mazegen-1.0.0-py3-none-any.whl. Luego, desde fuera del
repo, from mazegen import MazeGenerator. pyproject.toml declara el
paquete, el README y la licencia. → 10
El dibujo es PATTERN_42 en generator.py: cambiar los #
basta, y el tamaño mínimo se recalcula con PATTERN_WIDTH y
PATTERN_HEIGHT. Ojo con la columna central, que conviene dejar libre. Un color es una
tupla más en WALL_COLOURS o PATTERN_COLOURS de
maze_display.py. → 12