Tot el que has après en aquest curs cap en una frase: tria bé les teves dades i el codi s'escriu sol. Aquesta última lliçó et proposa demostrar-t'ho amb tres projectes integradors de dificultat creixent. No són exercicis d'una sola estructura: cadascun obliga a combinar-ne diverses, a justificar cada tria amb el seu Big O i a verificar amb timeit que les promeses es compleixen. Hi trobaràs enunciats detallats, requisits per estructura, arquitectura suggerida, fites incrementals i criteris de "fet" — però no codi tancat: el codi, aquesta vegada, és teu.

1. Com abordar els projectes
2. Projecte 1: TaskFlow complet en consola
3. Projecte 2: Planificador d'esprints
4. Projecte 3: Motor de cerca de tasques
5. Com autoavaluar-se amb timeit
6. Tancament del curs

• Ordre recomanat: 1 → 2 → 3. El projecte 1 integra peces ja construïdes; el 2 exigeix dissenyar un algorisme al damunt; el 3 demana dissenyar estructura i algorisme alhora.
• Abans de programar cada peça, escriu una línia: "operació dominant → estructura triada → cost". És el mètode de 08-01 convertit en hàbit.
• Reutilitza les teves classes dels mòduls anteriors (la taula-xuleta de 08-02 és el teu inventari). Reescriure des de zero només allò que el projecte demani millorar.
• Fites petites: cada projecte porta fites incrementals; no passis a la següent sense que l'anterior funcioni amb dades de prova. Un projecte a mitges que funciona ensenya més que un de complet que no arrenca.
• Criteri general de "fet": funciona amb els casos de prova, cada estructura està justificada per escrit i les mesures de timeit (secció 5) confirmen els costos promesos.

Integra les peces construïdes durant el curs en una única aplicació de consola coherent: un menú en bucle que permeti gestionar tasques i projectes fent servir, per sota, les estructures adequades per a cada operació. És un projecte d'integració: la dificultat no és en cap peça, sinó que totes comparteixin un mateix magatzem de tasques sense dessincronitzar-se.

Arquitectura suggerida en tres capes, perquè les estructures no es barregin amb la interfície:

• estructures.py: copia-hi les teves classes del curs tal qual (o importa-les d'on les tinguis).
• nucli.py: una classe TaskFlow que encapsula la coordinació. Parteix de l'esquelet NucliTaskFlow de 08-01 i amplia'l. Regla d'or: la interfície mai no toca una estructura directament; tota modificació passa per un mètode del nucli, que actualitza totes les estructures afectades (dict, índex, monticle, graf...) en la mateixa crida.
• Per al desfer, guarda a la pila accions invertibles: per exemple ("crear", id) es desfà esborrant, ("moure", id, columna_origen, columna_desti) es desfà movent a l'inrevés. Comença suportant desfer només per a crear/esborrar/moure; amplia-ho després.
• Per a les dependències, mantén la convenció del mòdul 7: aresta A→B significa "B depèn d'A". Abans d'afegir una dependència, simula-la i comprova hi_ha_cicle; si en crea, rebutja-la amb un missatge clar.

Fites incrementals: (1) menú + crear/llistar/consultar sobre el dict; (2) tauler per columnes i moviment; (3) desfer/refer; (4) safata d'urgències amb esborrat mandrós; (5) etiquetes i índex invertit; (6) projectes jeràrquics amb pressupostar; (7) dependències + ordre de treball; (8) registre d'esdeveniments i poliment.

Criteris de "fet": cap operació del menú no recorre el dict complet llevat de "llistar-ho tot"; crear 10 000 tasques de prova no degrada la consulta per id ni l'extracció d'urgents; desfer immediatament després de qualsevol operació deixa el sistema en l'estat anterior (comprova-ho comparant el dict abans i després); afegir una dependència circular és impossible.

Donat un backlog de tasques —cadascuna amb id, titol, prioritat, hores i una llista depen_de— i una capacitat d'esprint en hores (p. ex. 40), genera una llista d'esprints vàlids: cap tasca no apareix abans que les seves dependències, cap esprint no supera la capacitat i, a igualtat de condicions, entren abans les de més prioritat. A més, el planificador ha de calcular la ruta crítica del projecte i avisar dels colls d'ampolla: tasques que, si es retarden, retarden l'entrega completa.

L'algorisme central és el Kahn per nivells del planificador del mòdul 7, amb un volt de rosca: dins de cada nivell no és igual l'ordre, perquè la capacitat és limitada.

1. Valida el backlog: tota dependència apunta a un id existent i hi_ha_cicle retorna fals. Si no, informa'n i atura't — un pla sobre un graf invàlid no significa res.
2. Calcula el grau d'entrada de cada tasca. Les de grau 0 són elegibles: fica-les en un monticle per (prioritat, comptador, id).
3. Per omplir un esprint: extreu elegibles del monticle mentre càpiguen en les hores restants de l'esprint. Decisió de disseny que has de prendre i documentar: si la més prioritària no hi cap però una de menys prioritària sí, la saltes (aprofites capacitat) o tanques l'esprint (respectes prioritat estricta)? Totes dues són defensables; un deque de "no hi van cabre" que es reintenta abans de l'esprint següent és una solució intermèdia elegant.
4. En "completar" un esprint, redueix el grau d'entrada de les dependents de les seves tasques; les que arribin a 0 entren al monticle d'elegibles. Repeteix fins a buidar el backlog.
5. Ruta crítica: amb les hores com a pes, calcula per a cada tasca l'instant més primerenc de fi (màxim sobre les seves dependències + les seves hores, en ordre topològic) i, cap enrere, el més tardà. Les tasques amb marge 0 formen la ruta crítica: marca-les a la sortida ("si migrar la base de dades es retarda, es retarda tot").

Fites incrementals: (1) càrrega i validació del backlog; (2) ordre topològic pla; (3) nivells paral·lels; (4) esprints amb capacitat i prioritat; (5) ruta crítica i avisos; (6) sortida llegible (taula per esprint amb hores usades/lliures).

Criteris de "fet": amb un backlog artificial de 1 000 tasques i dependències aleatòries sense cicles, planifica en força menys d'un segon; cap tasca no apareix en un esprint anterior a alguna de les seves dependències (escriu un verificador automàtic: és un bucle amb un set de completades — O(V+E) — i és part del projecte); la suma d'hores de cada esprint no supera la capacitat; la durada total estimada coincideix amb la longitud de la ruta crítica quan la capacitat és "infinita".

Construeix el cercador de TaskFlow: donat un corpus de tasques, ha de respondre consultes de text lliure ("informe mensual client") retornant les k tasques més rellevants, en temps interactiu encara que hi hagi desenes de milers de tasques. Opcionalment, autocompletar mentre s'escriu. És el projecte més obert: hi ha decisions de disseny sense resposta única, i documentar-les és part de la feina.

• Indexació. Normalitza cada títol/descripció (minúscules, sense accents, trossejat per espais i signes — compte: "això"→"aixo" és acceptable aquí; documenta la decisió). Per a cada paraula, afegeix l'id al set de l'índex invertit. Guarda també un Counter de paraules per tasca per al rànquing. Indexar ha de ser O(total de paraules).
• Consulta. Trosseja la consulta igual que el corpus (mateixa normalització o res no casarà!). Recupera els set d'ids de cada paraula. Decisió de disseny: intersecció (totes les paraules: precís, pocs resultats) o unió (alguna paraula: flexible, molts)? Suggeriment: unió, i que el rànquing premiï qui té més paraules.
• Rànquing. Puntuació simple i suficient: suma, per a cada paraula de la consulta, de la seva freqüència a la tasca, amb un plus per paraula diferent coberta; desempata per prioritat de la tasca (número més baix primer!). Extreu el top-k amb monticle, mai ordenant la llista completa de candidats.
• Autocompletar (opcional). Implementa almenys la versió de 08-01 (llista ordenada + bisect). Si t'atreveixes amb el trie: un node és un dict caràcter→fill més una marca de fi de paraula; inserir i cercar prefix són O(longitud). Compara memòria i velocitat de totes dues amb el teu corpus i escriu dos paràgrafs amb la conclusió — aquest petit informe val més que el codi.
• Memòria cau. Un dict consulta_normalitzada→resultats. En indexar una tasca nova, buida-la (o invalida només les consultes afectades si vols un repte extra fent servir el mateix índex invertit).

Fites incrementals: (1) normalitzador + índex invertit amb cerca d'una paraula; (2) consultes multiparaula amb unió; (3) rànquing + top-k amb monticle; (4) memòria cau amb invalidació; (5) autocompletar; (6) mesura comparativa (secció següent).

Criteris de "fet": amb 20 000 tasques sintètiques (genera títols combinant un vocabulari d'unes 200 paraules), la consulta respon en mil·lisegons; cercar una paraula inexistent retorna buit sense error; afegir una tasca la fa trobable immediatament; la cerca amb memòria cau calenta és mesurable i clarament més ràpida que en fred.

La promesa de cada estructura és un Big O; la teva última tasca del curs és auditar les teves pròpies promeses, com vam fer al mòdul 1. El mètode: mesura la mateixa operació amb n, 10n i 100n elements i comprova la forma del creixement — O(1) amb prou feines es mou, O(log n) suma una quantitat fixa per salt, O(n) multiplica per 10, O(n²) per 100.

timeit executa l'operació moltes vegades i en fa la mitjana, eliminant el soroll d'una mesura solta; mesurem amb la tasca "central" per no afavorir casos límit. Casos de prova suggerits, un per promesa clau:

Si una mesura contradiu la teoria, enhorabona: acabes de trobar el millor exercici del curs. Persegueix-ne la causa amb la taula de símptomes de 08-01.

Adaptem la secció a consells d'enfocament de projectes:

• Començar per la interfície. El menú bonic és la trampa clàssica: són hores d'input/print que no exerciten res. Nucli primer, provat des d'un script; interfície al final.
• No escriure dades de prova generables. Necessites funcions que fabriquin 10 000 tasques sintètiques en un segon; sense elles no hi ha fita verificable ni timeit possible. Escriu-les a la fita 1.
• Sincronització a mà. Si la interfície actualitza el dict aquí i l'índex allà, la dessincronització és qüestió de temps. Tota escriptura passa pel nucli; és la lliçó del patró de 08-01.
• Perfeccionisme d'estructura. Dubtes entre deque i LlistaEnllacada per a una columna del tauler? Tria'n una, anota per què, continua. Canviar-la després costarà poc precisament si has respectat el TAD (concepte transversal 1).
• Saltar-se la justificació escrita. La línia "operació → estructura → cost" per peça converteix el projecte en material de portfolio i d'entrevista. Sense ella, és només codi que funciona avui.
• Comparar-se amb biblioteques reals. El teu motor de cerca no competeix amb Elasticsearch. L'objectiu és que les teves promeses de cost es compleixin i sàpigues explicar-les.

En aquesta lliçó, els projectes són els exercicis: tria'n almenys un (idealment els tres, en ordre) i porta'l fins als seus criteris de "fet". No hi ha solució tancada per copiar — les guies orientatives de cada projecte són el teu mapa, i les mesures de timeit el teu corrector automàtic.

La "solució" de cada projecte és una autoavaluació en tres comprovacions, comunes als tres:

1. Funcional: els criteris de "fet" del projecte es compleixen amb les teves dades de prova generades (inclòs el verificador automàtic, en el cas del planificador).
2. De cost: les mesures de la taula de timeit mostren la forma de creixement promesa en multiplicar n per 10 i per 100.
3. De criteri: pots recórrer el teu codi i, peça per peça, recitar "operació dominant → estructura → cost → per què no les alternatives". Si alguna peça no supera aquest interrogatori, revisa 08-01; si el superen totes, el curs ha complert el seu objectiu amb tu.

Enhorabona: has arribat al final del curs d'Estructures de Dades. Vas començar amb un dict solt anomenat tasca i acabes sent capaç de dissenyar, justificar i mesurar un sistema complet — tauler, desfer, urgències, índexs, jerarquies, dependències i cerca — triant en cada peça l'estructura que abarateix l'operació que de debò importa. Aquesta és la filosofia que voldríem que t'emportessis gravada: primer les dades, després el codi. Els algorismes s'obliden i es tornen a consultar; el criteri, un cop adquirit, es queda. Practica'l en cada revisió de codi, en cada disseny i en cada entrevista: pregunta sempre quines operacions dominen i quina estructura les serveix millor. TaskFlow és teu, el teu criteri també. Ha estat un plaer construir amb tu. Fins aquí el curs — i fins on tu vulguis arribar a partir d'ara.