CodExpress — Nivel Avanzado (Algoritmos + Rendimiento)

Tiempo: 3 horas · Meta: completar 7 u 8 mini-retos y, si te alcanza, una app integrada (código 3900) que reutilice tus propias implementaciones. Lenguajes: Python, Java o C++ (solo librerías estándar).

Flujo de trabajo (fork & PR)

1. Haz fork y clónalo.
2. Usa un <ALIAS> sin espacios ni acentos (tu usuario de GitHub o nombre-apellido en minúsculas).
3. Cada mini-reto va en un archivo con formato exacto: <CODIGO_RETO>_<ALIAS>_v<N>.<ext> (ej.: 3005_lina-rojas_v1.py o 3005_lina-rojas_v1.cpp).
4. Si haces la app, crea 3900_<ALIAS>_app/ con README.md (cómo ejecutar), y si quieres src/ y requirements.txt.
5. Abre un Pull Request a main titulado: <ALIAS> — Entrega Nivel Avanzado.

---

Códigos (Nivel Avanzado)

• Mini-retos: 3001–3008 (elige 7 u 8).
• App integrada: 3900 (Smart Routes & Data).

Nombre de archivo obligatorio: <CODIGO_RETO>_<ALIAS>_v<N>.<ext>

---

Mini-retos (entrega 7 u 8)

Usa solo la librería estándar. Al final de cada archivo incluye, en comentarios, 3 pruebas (entrada → salida esperada). La salida se compara literalmente. Indica en comentario la complejidad esperada de tu solución.

Código	Nombre	Requisitos técnicos y verificación	Entrada / Salida	Archivo	Docs útiles
3001	Sort Bench (O(n²) vs O(n log n))	Implementa bubble (o insertion) y quicksort/mergesort propios. Cuenta comps y swaps e imprime tiempo en ms. Verifica que ambos producen exactamente el mismo arreglo final. Genera los datos con --seed (reproducible). No uses sort de la librería.	Modo A: lista en stdin (N y N enteros). Modo B: GEN N --seed=S. Salida (dos líneas): algo, comps=..., swaps=..., ms=....	3001_<ALIAS>_v1.(py|java|cpp)	Python: time · C++: chrono · Java: nanoTime
3002	Búsqueda binaria (izquierda)	En arreglo ordenado, responde Q consultas y devuelve el índice del primer elemento ≥ x (leftmost lower_bound). Si no existe, imprime −1. Evita overflow en Java/C++ usando mid = l + (r-l)/2. O(Q log N).	Entrada: N, línea con N enteros, Q, luego Q valores. Salida: Q líneas con índices.	3002_<ALIAS>_v1.(py|java|cpp)	C++: lower_bound (referencia) · Py: bisect (no usar directamente)
3003	BFS en grafo (ruta + niveles)	Grafo no dirigido con V hasta 105, E hasta 2·105. Imprime distancia mínima y la ruta determinista de s a t (vecinos explorados en orden ascendente de id). O(V+E) usando deque/queue.	Entrada: V E, E líneas u v, luego s t. Salida: dist=K y en la línea siguiente la ruta u->...->t; si no hay, NO.	3003_<ALIAS>_v1.(py|java|cpp)	Py: deque · C++: queue
3004	DFS: tiempos y topológico	Calcula tin/tout por vértice y detecta ciclo. Si no hay ciclos, imprime un orden topológico. Determinismo: itera vecinos en orden ascendente. En Python ajusta recursionlimit o haz DFS iterativo.	Entrada: V E, E líneas u v (dirigido). Salida: si hay ciclo, CYCLE. Si no, una línea: topo: v1 v2 ....	3004_<ALIAS>_v1.(py|java|cpp)	Py: sys.setrecursionlimit · C++: vector
3005	Dijkstra (camino y distancias)	Peso positivo. Implementa con priority_queue/heapq. Distancias desde s y ruta exacta a t. O((V+E) log V). Si t es inalcanzable: INF. En caso de empate por distancia, desempata por id de predecesor menor (determinismo).	Entrada: V E, E líneas u v w (dirigido o no; se indicará 0/1 en primera línea), y s t. Salida: dist[t]=X y en la siguiente línea la ruta; o INF.	3005_<ALIAS>_v1.(py|java|cpp)	Py: heapq · Java: PriorityQueue
3006	WordCount top-k (streaming)	Lee texto por stdin, normaliza Unicode (NFKD), elimina signos, casefold. Calcula frecuencias en streaming (no cargues todo si es grande). Imprime top-k (k en la primera línea) con desempate lexicográfico ascendente. Determinista.	Entrada: primera línea k, luego texto libre hasta EOF. Salida: k líneas palabra conteo.	3006_<ALIAS>_v1.(py|java|cpp)	Py: unicodedata · Counter (o mapa propio)
3007	BST (insert/find/delete + rango)	Árbol binario de búsqueda sin librerías balanceadas. Soporta ADD x, DEL x, HAS x, PREV x, NEXT x. Imprime INORDER al llamar PRINT. Implementa correctamente los 3 casos de borrado.	Entrada: múltiples comandos (uno por línea). Salida: respuestas a HAS/PREV/NEXT/PRINT.	3007_<ALIAS>_v1.(py|java|cpp)	C++: punteros · Py: clases
3008	Heapsort + métricas	Implementa binary heap y heapsort ascendente. Cuenta sift_up/sift_down y compara con n log n. Prohíbido usar sort de la librería. Determinista.	Entrada: N y N enteros. Salida: una línea con el arreglo ordenado y otra con sift_up=.. sift_down=...	3008_<ALIAS>_v1.(py|java|cpp)	Py: heapq (solo referencia) · C++: vector

Requisitos mínimos por mini-reto

• E/S exacta (la comparación es literal).
• 3 pruebas (entrada → salida) en comentarios al final del archivo.
• Complejidad indicada en comentario (y que cumpla con los límites).
• Solo librería estándar; nada de frameworks externos.
• Nomenclatura exacta del archivo. Nombre incorrecto: −5%.

---

App integrada (3900) — Smart Routes & Data

Código	Debe reutilizar	Qué agrega	Entregables	Puntaje máx.
3900	3001, 3003, 3005, 3006, 3008	CLI que permite: (1) cargar/redimensionar grafos; (2) comparar ordenamientos (3001) en datasets generados con --seed; (3) rutas mínimas (3003/3005) con impresión de camino; (4) análisis de texto (3006) para logs. Incluye un comando bench que guarda resultados en un CSV/JSON.	Carpeta 3900_<ALIAS>_app/ con README.md (comandos), src/, y un archivo benchmarks.(csv|json) con al menos 3 corridas reproducibles.	220

• Reutiliza tus funciones/clases: impórtalas o muévelas a src/ sin reescribir.
• Incluye una tabla de tiempos con tamaños crecientes y semilla fija.
• Los recorridos de grafo deben ser deterministas (orden de vecinos).

---

Puntajes — Nivel Avanzado

• Mini-reto (máx. 110 pts): funciona y cumple complejidad (60%) · casos borde / 3 pruebas (20%) · claridad/estructura (10%) · defensa breve (10%).
• App 3900 (máx. 220 pts): integración real (50%) · diseño y cohesión (20%) · manejo de errores y CLI usable (20%) · README/benchmarks (10%).

Bonificaciones creativas (opcionales, suman — tope +120 pts por equipo)

• Visualizador de rutas (GUI o TUI) para 3900: muestra nodos, aristas y el camino encontrado (Tkinter/Swing/Qt/curses): +40 pts.
• Paralelización (multi-thread/Procesos) en algún módulo de 3900 (p. ej., generación de datasets o wordcount por shards): +25 pts.
• Perfilado (reporte con time/chrono o contadores propios) comparando implementaciones y tamaños: +15 pts.
• Reproducibilidad: script que corre 3 benches con la misma semilla y deja benchmarks.json/.csv con promedios y desvío: +10 pts.
• Tests automatizados (unittest/JUnit/asserts) ≥8 casos: +10 pts.
• Validadores de entrada (detectan formatos inválidos y reportan línea/causa): +10 pts.
• Top-k eficiente en 3006 con min-heap + streaming (sin ordenar todo): +10 pts.

---

Anti-IA desde la consigna (verificación incorporada)

• Determinismo en orden de vecinos, empates y formato exacto de salida (rutas, top-k, etc.).
• Semillas obligatorias para generación de datos/bench (3001, 3900).
• Complejidad exigida (rechazamos O(n²) donde no corresponda; se probará con tamaños “trampa”).
• Edición en vivo (≤2 min) durante la defensa: se puede pedir cambiar el formato, tamaño o un criterio de desempate.

---

Checklist final

• 7 u 8 mini-retos con nombres correctos: 300x_<ALIAS>_vN.(py|java|cpp).
• 3 pruebas por archivo (en comentarios) y complejidad indicada.
• Si hiciste la app: 3900_<ALIAS>_app/ + README.md + benchmarks.(csv|json).
• PR: <ALIAS> — Entregas Nivel Avanzado.

Documentación

Python · Java · C++ · deque (Py) · heapq (Py) · PriorityQueue (Java) · priority_queue (C++) · unicodedata