Toca consolidar. En este módulo has construido una tabla hash desde cero (05-01 y 05-02) y has aprendido a exprimir dict y set con los patrones profesionales de 05-03: indexar, agrupar, contar, invertir. Esta lección no introduce teoría nueva: son seis ejercicios progresivos, todos con sabor TaskFlow, que cubren los usos que con más frecuencia te encontrarás en el trabajo (y en las entrevistas técnicas): detectar duplicados, agrupar por clave derivada, buscar por etiquetas, cachear resultados caros, resolver el clásico two-sum y extender tu propia TablaHash. Intenta resolver cada uno antes de mirar la solución; el enunciado siempre da la pista de qué estructura usar — la habilidad que entrenas es ver por qué.

1. Ejercicio 1: el primer id duplicado (y cuánto cuesta no usar hash)
2. Ejercicio 2: agrupar títulos anagramáticos
3. Ejercicio 3: buscador de etiquetas AND/OR
4. Ejercicio 4: caché de costes de proyecto (memoización)
5. Ejercicio 5: two-sum sobre estimaciones de horas
6. Ejercicio 6: extender la TablaHash de 05-02
7. Errores comunes, soluciones y cierre del módulo

Una importación masiva ha metido ids repetidos en TaskFlow. Escribe dos versiones de primer_duplicado(ids), que devuelva el primer id que aparece por segunda vez (o None): una sin tabla hash (solo comparaciones entre elementos, O(n²)) y otra con un set de vistos (O(n)). Después mídelas con timeit (como en 01-02) para n = 1.000, 10.000 y 20.000 ids con el duplicado al final (peor caso). Anota el factor de mejora en cada n: ¿crece o se mantiene? ¿Por qué?

Control de calidad editorial: queremos detectar títulos de tareas que son anagramas entre sí (mismas letras, otro orden — típico de duplicados con palabras reordenadas, como "Plan web" y "Web plan"). Escribe agrupar_anagramas(titulos) que devuelva los grupos de títulos anagramáticos. Pista central del módulo: agrupar es cuestión de elegir la clave canónica correcta — una que sea igual para todos los miembros del grupo y hashable. Ignora mayúsculas y espacios.

Empaqueta el índice invertido de 05-03 en una clase BuscadorEtiquetas con tres métodos: indexar(tarea) (registra la tarea en el índice invertido y en el índice por id), buscar_and(*etiquetas) y buscar_or(*etiquetas), que devuelven títulos ordenados por id. Requisitos: una etiqueta inexistente no debe romper nada (en AND colapsa el resultado a vacío; en OR simplemente no aporta), y las tareas sin campo etiquetas deben poder indexarse sin error.

TaskFlow modela proyectos compuestos: cada proyecto tiene horas propias y una lista de subproyectos (que pueden repetirse y compartirse entre proyectos). El coste total es recursivo (módulo 3): horas propias + suma de costes de los subproyectos.

Escribe coste(nombre) recursiva y directa, con un contador global de llamadas. Después escribe coste_cacheado(nombre), que use un dict como caché (patrón memoización): antes de calcular, mira si el resultado ya está; después de calcular, guárdalo. Compara el número de llamadas de ambas para "p0". Ambas deben devolver el mismo total.

Un clásico absoluto, en versión TaskFlow: tienes pares (id, horas_estimadas) y una jornada de 8 horas. Escribe par_que_llena(tareas, jornada=8) que devuelva los ids de dos tareas distintas cuyas horas sumen exactamente la jornada, o None. Datos de prueba: [("T-01", 3), ("T-02", 7), ("T-03", 2), ("T-04", 5), ("T-05", 6)]. La versión evidente compara todas las parejas (O(n²)); la buena hace una sola pasada con un dict. Pista: cuando miras una tarea de h horas, la pregunta exacta es "¿he visto ya una de jornada - h horas?" — y responder "¿he visto ya...?" en O(1) es la especialidad de este módulo.

Dos encargos sobre tu propia tabla de encadenamiento. (a) Añade el método claves(), que devuelva una lista con todas las claves almacenadas (recorre las cubetas; recuerda que la ListaEnlazada es iterable y cada dato es un par [clave, valor]). (b) Comprueba experimentalmente el redimensionado automático: inserta los pares (i, str(i)) para i de 0 a 99 partiendo de capacidad 8, y verifica tres cosas — que la capacidad final es la esperada (calcúlala a mano primero: ¿en qué inserciones se supera 0.75?), que el factor de carga final queda por debajo del umbral, y que tras todos los redimensionados ninguna clave se ha perdido (las 100 recuperables con obtener y claves() completo).

Solución 1: primer duplicado, con medición

Resultados en una máquina de referencia (los tuyos variarán en valor absoluto, no en forma):

Comentario: el factor de mejora crece con n — de ×277 a ×3.322 — y tenía que ser así: O(n²) frente a O(n) significa que la ventaja es proporcional a n, no una constante. Duplicar n (10.000 → 20.000) cuadruplica el tiempo del cuadrático (1,86 → 7,55 s: ×4,05, la firma exacta del O(n²) que aprendiste en 01-04) y solo duplica el del set. Con el millón de registros del experimento de 01-02, el cuadrático necesitaría horas; el set, una fracción de segundo. Es el mismo veredicto de aquel experimento, pero ahora entiendes el mecanismo completo: cada in vistos es un cálculo de casilla, no un recorrido.

Solución 2: anagramas por clave canónica

Comentario: toda la inteligencia está en clave_anagrama. Dos títulos son anagramas si y solo si, tras normalizar (minúsculas, sin espacios) y ordenar sus letras, producen la misma secuencia: "roma" y "amor" se convierten ambos en ('a','m','o','r'). Esa forma canónica cumple los dos requisitos de una buena clave de agrupación: es igual para todo el grupo y es hashable (tupla de caracteres — una lista de sorted a secas fallaría con TypeError, ejercicio 1 de 05-03). El resto es el patrón defaultdict(list) de agrupación de 05-03, en O(n · k log k) con k = longitud del título. Nota fina: este es exactamente el defecto que hacía mala a hash_suma en 05-02 (ignorar el orden), usado aquí a propósito — cuando quieres que los anagramas coincidan, una clave insensible al orden es la herramienta correcta. La misma propiedad es virtud o defecto según el contrato que necesites.

Solución 3: buscador AND/OR

Comentario: la clase reúne las piezas sueltas de 05-03 en un objeto con los índices siempre sincronizados — indexar toca los dos, cumpliendo la regla de mantenimiento que enunciamos allí. _ids centraliza la defensa get(..., set()): la etiqueta desconocida se comporta como conjunto vacío, que es neutro en el OR (| con vacío no añade nada) y aniquilador en el AND (& con vacío da vacío) — exactamente la semántica pedida, sin un solo if especial. La tarea 9, sin etiquetas, se indexa sin error gracias a t.get("etiquetas", []) y simplemente no aparece en búsquedas. Cada consulta cuesta O(suma de tamaños de los conjuntos implicados), independiente del total de tareas indexadas.

Solución 4: memoización con un dict

Comentario: mismo resultado (10.235 horas), pero 2.047 llamadas contra 11. La versión directa explota porque cada proyecto usa dos veces el siguiente: p0 provoca 2 cálculos de p1, 4 de p2... 1024 de p10 — total 2¹¹−1 = 2047, crecimiento exponencial. La caché lo desactiva: cada proyecto se calcula una sola vez (11 proyectos, 11 llamadas); las apariciones repetidas se resuelven con una consulta O(1) al dict. El patrón se llama memoización y su receta es siempre la misma: ¿está en la caché? devuélvelo; calcula; guarda; devuelve. Requisito imprescindible: la clave de caché debe ser hashable e identificar completamente la entrada (aquí el nombre basta porque el coste solo depende del proyecto). Este dúo función-recursiva-más-caché reaparecerá con los recorridos de árboles (módulo 6) y grafos (módulo 7), donde "no repetir trabajo ya hecho" es la diferencia entre lo instantáneo y lo intratable. Python lo trae empaquetado en functools.lru_cache, que puedes explorar por tu cuenta: es exactamente este dict, como decorador.

Solución 5: two-sum en una pasada

Comentario: la versión O(n²) probaría las 10 parejas; esta hace una pasada y por cada tarea una consulta O(1). El giro mental es el importante: en vez de preguntar "¿qué pareja suma 8?" (pregunta sobre parejas: cuadrática), preguntamos por cada tarea "¿existe ya mi complemento exacto?" (pregunta sobre una clave: la especialidad del hash). La traza: T-01 (3 h) busca 5 — no está — y se registra; T-02 (7) busca 1 — no; T-03 (2) busca 6 — no; T-04 (5) busca 3 — sí, es T-01 → ('T-01', 'T-04'). Detalles finos: registrar la tarea después de buscar impide emparejarla consigo misma (con jornada 8, una tarea de 4 h solo casa con otra de 4 h, y así ocurre); y si hay varias respuestas válidas, devuelve la primera alcanzable, con sus dos miembros lo más tempranos posible. Este truco del complemento resuelve una familia entera de problemas ("¿dos elementos con diferencia d?", "¿dos etiquetas que cubran el filtro?") y es probablemente el ejercicio de tabla hash más preguntado en entrevistas.

Solución 6: claves() y el redimensionado, auditado

Comentario: (a) claves() recorre el array de cubetas y, dentro de cada una, la ListaEnlazada (su __iter__ del módulo 2 entrega cada par; nos quedamos par[0]). El coste O(n + capacidad) tiene su matiz: con la tabla muy vacía, el término capacidad domina — visitar 256 cubetas para 3 claves. Por eso el dict real mantiene estructura extra para iterar solo lo ocupado. (b) La capacidad final se predice a mano con la regla "tras insertar, si n/capacidad > 0.75, duplicar": se supera con n = 7 (7/8 = 0,875 → 16), n = 13 (→ 32), n = 25 (→ 64), n = 49 (→ 128) y n = 97 (→ 256). Cinco redimensionados, capacidad final 256 y factor 0,39 — y las tres comprobaciones en True: cada rehashing reinsertó los pares con la capacidad nueva sin perder ninguno. Fíjate en la elegancia de la última línea: obtener funciona después de que todas las claves hayan cambiado de cubeta hasta cinco veces, porque guardar y buscar siempre comparten el mismo _indice. Tu tabla, construida con la ListaEnlazada del módulo 2, supera la misma auditoría que pasaría un dict.

• Elegir claves de agrupación no hashables (ejercicio 2): sorted(texto) devuelve una lista — envuélvela en tuple antes de usarla como clave. Es el tropiezo más repetido en agrupaciones por clave derivada.
• Cachear funciones que dependen de más de lo que dice la clave (ejercicio 4): si coste dependiera también de una tarifa global mutable, la caché devolvería resultados obsoletos al cambiarla. La clave de memoización debe capturar toda la entrada — o la caché debe invalidarse cuando el contexto cambie.
• En two-sum, registrar antes de buscar (ejercicio 5): permite emparejar una tarea consigo misma (una de 4 h "encontrándose" para sumar 8). El orden buscar-luego-registrar no es estilo: es corrección.
• Medir con datos que esconden el peor caso (ejercicio 1): con el duplicado al principio, ambas versiones parecen instantáneas y la medición no enseña nada. Al comparar algoritmos, construye la entrada que fuerza el trabajo máximo — como hicimos colocándolo al final.
• Olvidar la copia defensiva al intersecar (ejercicio 3): arrancar el AND con resultado = self._ids(et[0]) sin copiar y luego usar &=... muta el conjunto del índice, corrompiéndolo para futuras consultas. set(...) primero, operar después.
• Consejo final del módulo: guarda el BuscadorEtiquetas y la caché de memoización; ambos vuelven en los proyectos del módulo 8, y el patrón "¿lo he visto ya?" del ejercicio 1 es literalmente el conjunto visitados del BFS del módulo 7.

Fin del módulo 5 — y de una deuda que arrastrábamos desde la lección 01-02. Ya no solo sabes que el dict es O(1): sabes por qué (clave → hash → casilla, sobre el acceso directo del array de 01-05), sabes qué lo amenaza (colisiones, funciones hash malas, factor de carga desbocado) y sabes qué lo defiende (encadenamiento, hash uniforme, redimensionado) — hasta el punto de haber construido y auditado tu propia TablaHash. En estos ejercicios el hash ha demostrado su rango: convirtió un O(n²) en O(n) dos veces (duplicados y two-sum), un coste exponencial en lineal (memoización), y dio a TaskFlow un buscador de etiquetas y un detector de anagramas en un puñado de líneas. Pero no olvides la frontera que trazamos en 05-03: todo este poder responde a preguntas de clave exacta. Pídele a tu índice "las tareas ordenadas por id" o "todas las de prioridad entre 1 y 3" y el hash enmudece — sus claves están esparcidas a propósito, sin noción de vecindad ni de orden. Para responder a eso hace falta una estructura que mantenga las claves organizadas jerárquicamente, donde cada paso descarte la mitad del espacio: los árboles, protagonistas del módulo 6. Allí nos espera, además, una promesa pendiente del módulo 4: abrir por fin la caja negra de heapq y ver el montículo por dentro (06-07). Nos vemos en los árboles.