Cursus — A-Maze-ing rank 02

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.

De qué va el proyecto — Generar laberintos es un clásico de la informática porque, debajo del juego, es teoría de grafos pura: cada celda es un nodo, cada pared que se abre es una arista, y un laberinto perfecto (un único camino entre dos puntos cualesquiera) es exactamente un árbol generador de la cuadrícula. Por eso los algoritmos famosos de generación — el recursive backtracker (búsqueda en profundidad), Prim o Kruskal, que el propio enunciado cita — son los mismos que se usan para diseñar redes o en generación procedimental de contenido en videojuegos. Resolver el laberinto, a su vez, es buscar el camino más corto en un grafo.

El proyecto es además una pieza de algo más grande: el enunciado pide que el generador sea un paquete instalable con 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.

GGlosario de teoría

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.

Grafos

Grafo, nodo y arista

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.

Grado de un nodo

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.

Grafo conexo

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.

Ciclo y bucles independientes

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.

Árbol y árbol generador

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.

Laberinto perfecto

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.

Callejón sin salida y trenzado (braiding)

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.

Algoritmos

Búsqueda en profundidad (DFS) y backtracking

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.

Búsqueda en anchura (BFS)

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.

Pila (LIFO)

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.

Cola (FIFO) y deque

Una 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.

Recursión y límite de recursión

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.

Algoritmo de Prim

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.

Pseudoaleatorio y semilla

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.

Bits y formato

Máscara de bits

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.

Hexadecimal

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}".

Códigos de escape ANSI

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.

Python

Excepción y traceback

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».

Context manager y with

Un 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.

dataclass

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").

Anotaciones de tipo y mypy

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.

flake8 y PEP 8

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.

Docstring y PEP 257

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.

Módulo, paquete y wheel

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.

Entorno virtual

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.

Licencia de software

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.

01Qué pide

Rank: 02Lenguaje: Python 3.10+Grupo: en equipo (el README pide los roles de cada miembro; tamaño no indicado)Entrega: repositorio Git

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.

02El repositorio

Entrega: a_maze_ing.py, maze_config.py, maze_output.py, maze_display.py, mazegen/, mazegen-1.0.0-py3-none-any.whl, pyproject.toml, config.txt, Makefile, LICENSE.md, README.md, .gitignore

Cada fichero hace una sola cosa, y solo mazegen/ sabe generar laberintos:

FicheroPapel
a_maze_ing.pyprograma principal: config → generación → fichero → menú
maze_config.pylee y valida el fichero de configuración
maze_output.pyescribe el fichero hexadecimal
maze_display.pydibujo en terminal con colores ANSI
mazegen/generator.pyla clase MazeGenerator (lo reutilizable)
pyproject.tomlmetadatos 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.

Qué te obliga a aprender — A separar el modelo (el laberinto como datos) de todo lo demás. Como 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.

03El fichero de configuración

Fichero: maze_config.py, config.txt

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:

ClaveValorPor defecto
WIDTH, HEIGHTtamaño en celdas, de 1 a 200obligatoria
ENTRY, EXITceldas x,y (columna, fila), distintasobligatoria
OUTPUT_FILEruta del fichero de salidaobligatoria
PERFECTTrue/False (también 1/0, yes/no)obligatoria
SEEDentero ≥ 0; misma semilla, mismo laberintoaleatoria
ALGORITHMbacktracker o primbacktracker
# 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.

Qué te obliga a aprender — A escribir un parser defensivo: validar antes de trabajar y convertir cada fallo en un mensaje útil en vez de un traceback. El truco es tener una excepción propia (ConfigError) que el main captura en un solo sitio, en lugar de llenar el código de print y sys.exit.

04La cuadrícula y las paredes

Fichero: mazegen/generator.py

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.

Qué te obliga a aprender — Máscaras de bits, ahora en Python: cuatro booleanos empaquetados en un nibble que se consultan con & 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.

05El «42»

Fichero: mazegen/generator.py

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

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.

06Laberinto perfecto: backtracker

Fichero: mazegen/generator.pyConfiguración: PERFECT=True
	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.

El segundo algoritmo: Prim aleatorio (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.

Por qué el backtracker — Es el algoritmo más sencillo que garantiza un laberinto perfecto, se explica en dos frases (DFS con retroceso) y da los pasillos largos y retorcidos que hacen bonito y difícil un laberinto. Toda la aleatoriedad sale de un único 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.

07Tablero Pac-Man: trenzado

Fichero: mazegen/generator.pyConfiguración: PERFECT=False (por defecto)

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.

Qué te obliga a aprender — A salir del árbol a propósito y razonar con grafos: grado de un nodo (un callejón es grado 1), ciclos (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.

08Camino más corto y fichero de salida

Ficheros: mazegen/generator.py, maze_output.py

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».

Qué te obliga a aprender — BFS con una cola (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.

09La visualización

Ficheros: maze_display.py, a_maze_ing.pyModo: terminal, colores ANSI

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.

10El paquete mazegen y la licencia

Ficheros: mazegen/, pyproject.toml, mazegen-1.0.0-py3-none-any.whl, LICENSE.md
[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.

Qué te obliga a aprender — Cómo se distribuye el código Python: un wheel es un zip con el código listo para instalar; un sdist (.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.

11Cómo se ha comprobado

Test: packs/cursus/M2/201_A-Maze-ing/test/runner.py (zentest)

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.

12Puntos delicados

13Fuente

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.

?Preguntas probables de la evaluación

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ú.

Generación

¿Por qué el backtracker da siempre un laberinto perfecto?

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

¿Por qué una pila explícita y no recursión?

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

¿Cómo haces el tablero no perfecto sin romper la conectividad?

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

¿Cómo es reproducible si es aleatorio?

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

¿Qué pasa con el «42» si el laberinto es pequeño?

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

Salida y camino

Lee esta cifra del fichero: 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

¿Cómo sabes que el camino es el más corto?

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

¿Cómo garantizas que dos celdas vecinas no se contradicen?

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

Errores y entrada

¿Qué pasa con una configuración mala? ¿Puede salir un traceback?

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

¿Por qué un 2×2 con 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

Lint, paquete y cambios en directo

Pasa 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

Reconstruye el paquete y úsalo desde otro sitio.

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

Cambia el dibujo del «42» o añade un color.

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