Planificar un proyecto con PERT y el camino crítico, con su diagrama de Gantt

1import math
2import sys
3
4
5def num(x):
6    """Un número con un decimal y coma: 4,2 (los restos de redondeo como -0,0000001 son 0)"""
7    if abs(x) < 1e-9:
8        x = 0.0
9    return f"{x:.1f}".replace(".", ",")
10
11
12def tabla(tareas, orden, plan):
13    print("Tarea  Duración  Inicio     Fin  Holgura")
14    for t in orden:
15        p = plan[t]
16        print(f"{t:<6}{num(p['dur']):>9}{num(p['ini']):>8}{num(p['fin']):>8}{num(p['holgura']):>9}{'  *' if p['critica'] else ''}")
17
18def leer(lineas):
19    """{id: (o, m, p, [dependencias], nombre)} en el orden de entrada, o None si hay errores."""
20    tareas, plazo, ok = {}, None, True
21    for n, linea in enumerate(lineas, 1):
22        p = linea.split()
23        if not p:
24            continue
25        if p[0] == "plazo" and len(p) == 2 and p[1].isdigit():
26            plazo = int(p[1])
27            continue
28        try:
29            o, m, pe = (float(x.replace(",", ".")) for x in p[1:4])
30            assert len(p) >= 6 and p[0] not in tareas
31        except (ValueError, AssertionError):
32            print(f"Línea {n}: no se entiende «{linea.strip()}»")
33            ok = False
34            continue
35        if not 0 <= o <= m <= pe:
36            print(f"Línea {n}: la tarea {p[0]} tiene estimaciones incoherentes (deben cumplir 0 ≤ O ≤ M ≤ P)")
37            ok = False
38            continue
39        deps = [] if p[4] == "-" else p[4].split(",")
40        tareas[p[0]] = (o, m, pe, deps, " ".join(p[5:]))
41    for t, (_, _, _, deps, _) in tareas.items():
42        for d in deps:
43            if d not in tareas:
44                print(f"La tarea {t} depende de {d}, que no existe")
45                ok = False
46    return (tareas, plazo) if ok else (None, None)
47
48
49def orden_topologico(tareas):
50    """Las tareas en un orden en que cada una va después de sus dependencias, o el ciclo si lo hay."""
51    estado, orden = {}, []
52
53    def visitar(t, camino):
54        if estado.get(t) == "hecha":
55            return None
56        if estado.get(t) == "en curso":
57            return camino[camino.index(t):] + [t]
58        estado[t] = "en curso"
59        for d in tareas[t][3]:
60            ciclo = visitar(d, camino + [t])
61            if ciclo:
62                return ciclo
63        estado[t] = "hecha"
64        orden.append(t)
65        return None
66
67    for t in tareas:
68        ciclo = visitar(t, [])
69        if ciclo:
70            return None, ciclo
71    return orden, None
72
73
74def calcular(tareas, orden):
75    plan = {}
76    for t in orden:                                   # pasada hacia delante: lo antes posible
77        o, m, p, deps, _ = tareas[t]
78        dur = (o + 4 * m + p) / 6
79        ini = max((plan[d]["fin"] for d in deps), default=0)
80        plan[t] = {"dur": dur, "var": ((p - o) / 6) ** 2, "ini": ini, "fin": ini + dur}
81    total = max(p["fin"] for p in plan.values())
82    sucesores = {t: [s for s in orden if t in tareas[s][3]] for t in orden}
83    for t in reversed(orden):                         # pasada hacia atrás: lo más tarde posible
84        fin_tarde = min((plan[s]["ini_tarde"] for s in sucesores[t]), default=total)
85        plan[t]["ini_tarde"] = fin_tarde - plan[t]["dur"]
86        plan[t]["holgura"] = plan[t]["ini_tarde"] - plan[t]["ini"]
87        plan[t]["critica"] = abs(plan[t]["holgura"]) < 1e-9
88        plan[t]["fin_tarde"] = fin_tarde
89    return plan, total
90
91
92def camino_critico(tareas, orden, plan, total):
93    """Desde la primera tarea crítica que acaba al final, hacia atrás por predecesoras críticas encadenadas."""
94    actual = next(t for t in orden if plan[t]["critica"] and abs(plan[t]["fin"] - total) < 1e-9)
95    camino = [actual]
96    while True:
97        previa = next((d for d in tareas[actual][3] if plan[d]["critica"] and abs(plan[d]["fin"] - plan[actual]["ini"]) < 1e-9), None)
98        if previa is None:
99            return list(reversed(camino))
100        camino.append(previa)
101        actual = previa
102
103
104def fila_gantt(p, dias):
105    """# o = los días de la tarea, . los de holgura: un día d cuenta si [d, d+1) se solapa con el intervalo."""
106    fila = ""
107    for d in range(dias):
108        if d < p["fin"] - 1e-9 and d + 1 > p["ini"] + 1e-9:
109            fila += "#" if p["critica"] else "="
110        elif d < p["fin_tarde"] - 1e-9 and d + 1 > p["fin"] + 1e-9:
111            fila += "."
112        else:
113            fila += " "
114    return fila.rstrip()
115
116
117def main():
118    tareas, plazo = leer(sys.stdin.read().splitlines())
119    if tareas is None:
120        print("No se puede planificar")
121        return
122    if not tareas:
123        print("No hay tareas")
124        return
125    orden, ciclo = orden_topologico(tareas)
126    if ciclo:
127        print("Hay un ciclo de dependencias: " + " → ".join(ciclo))
128        return
129    plan, total = calcular(tareas, orden)
130    tabla(tareas, list(tareas), plan)
131    camino = camino_critico(tareas, orden, plan, total)
132    sigma = math.sqrt(sum(plan[t]["var"] for t in camino))
133    print(f"Duración prevista: {num(total)} días (σ = {num(sigma)})")
134    print("Camino crítico: " + " → ".join(camino))
135    if plazo is not None:
136        prob = 100.0 if sigma == 0 and plazo >= total else 0.0 if sigma == 0 else 50 * (1 + math.erf((plazo - total) / (sigma * math.sqrt(2))))
137        print(f"Probabilidad de acabar en {plazo} días: {num(prob)} %")
138    print("Gantt (# crítica, = no crítica, . holgura):")
139    dias = math.ceil(total - 1e-9)
140    for t in tareas:
141        print(f"{t:<6}{fila_gantt(plan[t], dias)}".rstrip())
142
143
144main()