RO-Project-S6/test_phase2.py at main · Neithennn/RO-Project-S6 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
"""Tests rapides de la phase 2.

- Nord-Ouest sur problem_05 : cout > 425.
- Balas-Hammer sur problem_05 : cout proche de 425 (l'optimum cite par le cours).
- Validite (lignes/colonnes equilibrees) des deux propositions sur les 12 problemes.
"""
from __future__ import annotations

import sys
from pathlib import Path

ROOT = Path(__file__).resolve().parent
sys.path.insert(0, str(ROOT / "src"))

from cost import total_cost  # noqa: E402
from initial_propositions import balas_hammer, nord_ouest  # noqa: E402
from io_utils import display_proposition, read_problem  # noqa: E402


def _check_valid(problem: dict, proposition: list[list[int]], label: str) -> None:
    """Verifie que la proposition respecte provisions/commandes et est positive."""
    n, m = problem["n"], problem["m"]
    for i in range(n):
        s = sum(proposition[i])
        assert s == problem["provisions"][i], (
            f"{label} : ligne P{i + 1} somme={s} != provision {problem['provisions'][i]}"
        )
    for j in range(m):
        s = sum(proposition[i][j] for i in range(n))
        assert s == problem["commands"][j], (
            f"{label} : colonne C{j + 1} somme={s} != commande {problem['commands'][j]}"
        )
    for i in range(n):
        for j in range(m):
            assert proposition[i][j] >= 0, (
                f"{label} : valeur negative en (P{i + 1}, C{j + 1})"
            )


def test_problem_05() -> None:
    print("=" * 70)
    print("Tests sur problem_05.txt")
    print("=" * 70)
    p = read_problem(ROOT / "problems" / "problem_05.txt")

    print("\n>>> Nord-Ouest sur problem_05")
    no = nord_ouest(p)
    display_proposition(p, no)
    no_cost = total_cost(p, no)
    _check_valid(p, no, "Nord-Ouest")
    assert no_cost > 425, f"NO devrait donner > 425, obtenu {no_cost}"
    print(f"\nNO : cout = {no_cost} (> 425 OK, contraintes respectees)")

    print("\n\n>>> Balas-Hammer sur problem_05 (verbose)")
    bh = balas_hammer(p, verbose=True)
    print()
    display_proposition(p, bh)
    bh_cost = total_cost(p, bh)
    _check_valid(p, bh, "Balas-Hammer")
    assert bh_cost == 425, f"BH attendu 425 (optimum), obtenu {bh_cost}"
    print(f"\nBH : cout = {bh_cost} (= 425, optimum, contraintes respectees)")


def test_validity_all_problems() -> None:
    print("\n" + "=" * 70)
    print("Validite des deux algorithmes sur les 12 problemes (verbose=False)")
    print("=" * 70)
    print(
        f"{'Fichier':<20s}{'NO cost':>12s}{'BH cost':>12s}{'BH/NO':>10s}  "
        f"{'gain':>8s}"
    )
    print("-" * 70)
    for path in sorted((ROOT / "problems").glob("problem_*.txt")):
        p = read_problem(path)

        no = nord_ouest(p)
        _check_valid(p, no, f"NO {path.name}")
        no_cost = total_cost(p, no)

        bh = balas_hammer(p, verbose=False)
        _check_valid(p, bh, f"BH {path.name}")
        bh_cost = total_cost(p, bh)

        ratio = bh_cost / no_cost if no_cost > 0 else float("nan")
        gain = no_cost - bh_cost
        print(
            f"{path.name:<20s}{no_cost:>12d}{bh_cost:>12d}{ratio:>10.3f}  "
            f"{gain:>8d}"
        )


if __name__ == "__main__":
    test_problem_05()
    test_validity_all_problems()
    print("\nTous les tests sont passes.")