Cursus — Fly-in pendiente

Llevar una flota de drones de una base a un destino a través de un grafo de zonas con capacidad limitada, en el menor número de turnos posible. Proyecto de grafos en Python del rank 03 de 42next.

De dónde viene — Encontrar el camino más corto en un grafo es un problema resuelto desde 1959 (Dijkstra). Lo difícil empieza cuando no hay un viajero sino muchos, y no caben todos a la vez por el mismo sitio: eso se llama multi-agent path finding, y es el problema de los robots de un almacén, del tráfico aéreo o de los trenes de una red ferroviaria. Ya no basta con el camino más corto; hay que repartir a los agentes por varios caminos, decidir quién espera y cuándo, y evitar que se bloqueen entre sí. Quien conozca el camino antiguo de 42 reconocerá la idea de lem-in (hormigas que cruzan un hormiguero en el mínimo de turnos); Fly-in la lleva a Python con drones y le añade tipos de zona con coste distinto y capacidades en nodos y aristas. El prólogo del enunciado habla de no reinventar la rueda… y a continuación prohíbe toda librería de grafos: aquí la rueda se reinventa a propósito, para entender cómo gira.

Qué pide

Rank: 03 Lenguaje: Python ≥ 3.10 Estilo: orientado a objetos, flake8 + mypy Individual/grupo: no confirmado

Una simulación completa que lee un mapa de zonas, calcula cómo mover todos los drones desde la zona de inicio hasta la de destino respetando las reglas de capacidad y de movimiento, imprime los movimientos turno a turno en un formato fijo y muestra visualmente lo que pasa. Se puntúa por el número total de turnos: cuantos menos, mejor.

Restricciones del proyecto:

Más las reglas comunes de los proyectos de Python de 42next: docstrings PEP 257, excepciones controladas (si revienta en la evaluación, no es funcional), recursos con context managers, .gitignore y un Makefile con install, run, debug, clean y lint (y lint-strict opcional). Todos los ficheros van en la raíz del repositorio.

Lo que hay que entregar, según el enunciado: un parser del formato de entrada, un motor de simulación que respete las reglas, uno o varios algoritmos de rutas que minimicen los turnos, un sistema de visualización (colores en terminal o interfaz gráfica) y una salida en el formato especificado.

01El formato del mapa

El ejemplo del enunciado:

nb_drones: 5

start_hub: hub 0 0 [color=green]
end_hub: goal 10 10 [color=yellow]
hub: roof1 3 4 [zone=restricted color=red]
hub: roof2 6 2 [zone=normal color=blue]
hub: corridorA 4 3 [zone=priority color=green max_drones=2]
hub: tunnelB 7 4 [zone=normal color=red]
hub: obstacleX 5 5 [zone=blocked color=gray]
connection: hub-roof1
connection: hub-corridorA
connection: roof1-roof2
connection: roof2-goal
connection: corridorA-tunnelB [max_link_capacity=2]
connection: tunnelB-goal

Las coordenadas sirven para dibujar; la distancia del problema la dan las conexiones y los tipos de zona, no la geometría.

02El parser

El enunciado enumera lo que hay que validar:

Cualquier otro error detiene el programa con un mensaje claro que diga la línea y la causa. El enunciado recomienda escribir mapas propios para probar casos límite.

Qué te obliga a aprender — El parseo defensivo que ya apareció en A-Maze-ing: no fiarse de la entrada, distinguir «mal formado» de «bien formado pero inválido» (una conexión a una zona que no existe) y dar errores útiles. Con pydantic o dataclasses, más los tipos de mypy, el modelo de datos queda validado antes de que el algoritmo lo toque.

03Turnos, capacidades y tipos de zona

La simulación avanza en turnos discretos. En cada turno, cada dron puede moverse a una zona adyacente (si hay capacidad), empezar un movimiento hacia una zona restringida (que tarda dos turnos) o quedarse quieto.

TipoCoste de entrarNotas
normal1 turnopor defecto
restricted2 turnosel dron queda «en la conexión» un turno y tiene que llegar en el siguiente: no puede esperar en ella
priority1 turnodebe preferirse al buscar rutas
blocked—inaccesible; una ruta que la use no es válida

Reglas de ocupación:

Qué te obliga a aprender — A modelar un sistema por estados: la foto del turno t más las reglas dan la foto del turno t+1. La regla de «salir libera plaza en el mismo turno» permite que una fila de drones avance a la vez por un pasillo de capacidad 1; y la de las zonas restringidas obliga a reservar la llegada antes de salir, porque una vez en la conexión no hay marcha atrás. Las dos juntas hacen que el orden en que procesas los drones dentro de un turno importe.

04El algoritmo de rutas

Lo que el enunciado exige que el algoritmo tenga en cuenta:

Y que sea adaptable: mapas distintos pueden pedir estrategias distintas. El enunciado deja preguntas para la defensa: qué complejidad tiene, si funciona con muchos drones, si recalculas o guardas caminos y cómo afecta a la memoria.

Qué te obliga a aprender — La caja de herramientas clásica de grafos, escrita a mano: representar un grafo (listas de adyacencia), recorrerlo (BFS), caminos mínimos con pesos (Dijkstra, con su cola de prioridad) y, cuando hay capacidades, la familia de los flujos (cuántas unidades caben a la vez por una red, el problema del flujo máximo de Ford y Fulkerson, 1956). Un truco conocido de la literatura para meter el tiempo en el grafo es la red expandida en el tiempo: copiar cada zona una vez por turno, de forma que «esperar» sea una arista más. La lección de fondo es que un camino mínimo por dron no es lo mismo que un plan mínimo para la flota: con 25 drones y pasillos de capacidad 1, el camino más corto puede ser el peor si todos lo eligen.

05Salida, visualización y puntuación

Una línea por turno con los movimientos de ese turno separados por espacios, cada uno como D<ID>-<zona>, o D<ID>-<conexión> para un dron que está en vuelo hacia una zona restringida. Los drones que no se mueven no aparecen; los que llegan al destino dejan de seguirse. Ejemplo del enunciado:

D1-roof1 D2-corridorA
D1-roof2 D2-tunnelB
D1-goal D2-goal

Además, la simulación tiene que verse: colores en la terminal con los movimientos y el estado de las zonas, una interfaz gráfica, o las dos cosas. Los colores del mapa están para eso.

Objetivos de rendimiento con los mapas del enunciado (se revisan en la evaluación):

NivelMapaDronesObjetivo
Fácil (< 10)Linear path2≤ 6 turnos
Simple fork4≤ 8
Basic capacity4≤ 6
Medio (10–30)Dead end trap5≤ 12
Circular loop6≤ 15
Priority puzzle5≤ 12
Difícil (< 60)Maze nightmare8≤ 30
Capacity hell12≤ 35
Ultimate challenge15≤ 45
Challenger (opcional)The Impossible Dream25récord: 45

Métricas secundarias opcionales: drones movidos por turno, turnos medios por dron, coste total de los caminos y calidad de la visualización. El bonus es cumplir todos los objetivos de la tabla y batir el récord de 45 turnos del mapa Challenger. Los mapas de la evaluación pueden ser distintos.

El README (en inglés) añade a las secciones habituales una descripción detallada del algoritmo y la estrategia, la documentación de la visualización y un ejemplo de entrada y salida.

Puntos delicados

Fuente

El enunciado no está aún en el pack. Esta ficha sale de una transcripción pública del enunciado en inglés (versión 1.6), contrastada con el README y los mapas de otras dos entregas (los nombres de los mapas y las reglas coinciden):

Los mapas oficiales vienen adjuntos al enunciado en la intra. No confirmado: si se hace individual o en grupo, y las horas estimadas.