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.
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:
networkx,
graphlib, etc.);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.
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
nb_drones: <número>.start_hub:, end_hub: o hub:, seguido de
nombre, coordenadas enteras x y y metadatos opcionales entre corchetes.zone= (por defecto
normal), color= (por defecto ninguno; cualquier palabra vale) y
max_drones= (por defecto 1).connection: a-b, bidireccionales, con
max_link_capacity= opcional (por defecto 1). Por eso los nombres de zona no
pueden llevar guiones.# son comentarios.Las coordenadas sirven para dibujar; la distancia del problema la dan las conexiones y los tipos de zona, no la geometría.
El enunciado enumera lo que hay que validar:
nb_drones en la primera línea y entero positivo (y el programa tiene que
aguantar cualquier número de drones);start_hub y un end_hub;a-b y
b-a son la misma);max_drones en inicio y fin se ignora (no tienen límite) y no es error.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.
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.
| Tipo | Coste de entrar | Notas |
|---|---|---|
normal | 1 turno | por defecto |
restricted | 2 turnos | el dron queda «en la conexión» un turno y tiene que llegar en el siguiente: no puede esperar en ella |
priority | 1 turno | debe preferirse al buscar rutas |
blocked | — | inaccesible; una ruta que la use no es válida |
Reglas de ocupación:
max_drones=N lo sube a N;
inicio y fin no tienen límite;max_link_capacity limita cuántos drones cruzan a la vez la misma
conexión;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.
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):
| Nivel | Mapa | Drones | Objetivo |
|---|---|---|---|
| Fácil (< 10) | Linear path | 2 | ≤ 6 turnos |
| Simple fork | 4 | ≤ 8 | |
| Basic capacity | 4 | ≤ 6 | |
| Medio (10–30) | Dead end trap | 5 | ≤ 12 |
| Circular loop | 6 | ≤ 15 | |
| Priority puzzle | 5 | ≤ 12 | |
| Difícil (< 60) | Maze nightmare | 8 | ≤ 30 |
| Capacity hell | 12 | ≤ 35 | |
| Ultimate challenge | 15 | ≤ 45 | |
| Challenger (opcional) | The Impossible Dream | 25 | ré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.
max_link_capacity limita cuántos drones la cruzan a la
vez, y las conexiones son bidireccionales.priority no es más barata: cuesta lo mismo que
normal, solo hay que preferirla a igualdad.a-b/b-a; metadatos desconocidos o sin cerrar.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.