#!/usr/bin/env python3

# Brute_Force_Vergleich.py
"""
Kapitel Einfuehrung: Warum Ausprobieren scheitert.
Vergleicht vollständige Enumeration mit einem Constraint-Solver an einem
Zuordnungsproblem wachsender Größe (n Mitarbeiter auf n Aufgaben).
"""

import itertools
import math
import time

import numpy as np
from ortools.sat.python import cp_model


def erzeuge_kostenmatrix(n: int, seed: int = 7) -> np.ndarray:
    """Zufällige, aber reproduzierbare Kosten: Wer bearbeitet welche Aufgabe wie teuer?"""
    rng = np.random.default_rng(seed)
    return rng.integers(low=10, high=100, size=(n, n))


def loese_brute_force(kosten: np.ndarray) -> tuple[float, tuple, int]:
    """
    Probiert ALLE n! Zuordnungen durch und behält die beste.
    Rückgabe: (bester Kostenwert, beste Permutation, Anzahl geprüfter Kombinationen)
    """
    n = len(kosten)
    bester_wert = math.inf
    beste_zuordnung = None
    geprueft = 0

    # itertools.permutations(range(n)) liefert nacheinander jede Reihenfolge
    for zuordnung in itertools.permutations(range(n)):
        # zuordnung[i] = Aufgabe, die Mitarbeiter i übernimmt
        wert = sum(kosten[i][zuordnung[i]] for i in range(n))
        geprueft += 1
        if wert < bester_wert:
            bester_wert = wert
            beste_zuordnung = zuordnung

    return bester_wert, beste_zuordnung, geprueft


def loese_mit_solver(kosten: np.ndarray) -> tuple[float, tuple]:
    """Dasselbe Problem als Constraint-Programm — der Solver probiert NICHT alles durch."""
    n = len(kosten)
    modell = cp_model.CpModel()

    # x[i][j] = 1  <=>  Mitarbeiter i übernimmt Aufgabe j
    x = [[modell.NewBoolVar(f"x_{i}_{j}") for j in range(n)] for i in range(n)]

    for i in range(n):
        modell.AddExactlyOne(x[i][j] for j in range(n))   # jeder genau eine Aufgabe
    for j in range(n):
        modell.AddExactlyOne(x[i][j] for i in range(n))   # jede Aufgabe genau einmal

    modell.Minimize(sum(int(kosten[i][j]) * x[i][j] for i in range(n) for j in range(n)))

    loeser = cp_model.CpSolver()
    loeser.parameters.max_time_in_seconds = 30.0
    status = loeser.Solve(modell)
    if status not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        raise RuntimeError("Solver fand keine Lösung.")

    zuordnung = tuple(
        next(j for j in range(n) if loeser.Value(x[i][j]) == 1) for i in range(n)
    )
    return loeser.ObjectiveValue(), zuordnung


if __name__ == "__main__":
    print("=" * 72)
    print("   VOLLSTÄNDIGES DURCHPROBIEREN  vs.  OPERATIONS RESEARCH")
    print("=" * 72)
    print(f"{'n':>3} | {'Kombinationen':>18} | {'Brute Force':>14} | {'Solver':>10} | gleich?")
    print("-" * 72)

    for n in [4, 6, 8, 9, 10]:      # n = 11 dauert bereits ~2 Minuten
        kosten = erzeuge_kostenmatrix(n)

        t0 = time.perf_counter()
        wert_bf, zuord_bf, geprueft = loese_brute_force(kosten)
        zeit_bf = time.perf_counter() - t0

        t0 = time.perf_counter()
        wert_or, zuord_or = loese_mit_solver(kosten)
        zeit_or = time.perf_counter() - t0

        gleich = "ja" if abs(wert_bf - wert_or) < 1e-9 else "NEIN!"
        print(f"{n:>3} | {geprueft:>18,} | {zeit_bf:>11.4f} s | {zeit_or:>7.4f} s | {gleich}")

    print("-" * 72)
    # Hochrechnung: Wie lange bräuchte Brute Force bei n = 20?
    kombis_20 = math.factorial(20)
    # Messbasis: Prüfungen pro Sekunde aus dem letzten Lauf schätzen
    pro_sekunde = geprueft / max(zeit_bf, 1e-9)
    jahre = kombis_20 / pro_sekunde / (60 * 60 * 24 * 365.25)
    print(f"Hochrechnung für n = 20: {kombis_20:,} Kombinationen")
    print(f"Bei gemessenen {pro_sekunde:,.0f} Prüfungen/s wären das {jahre:,.0f} Jahre.")
    print("Der Solver löst dieselbe Instanz in Sekundenbruchteilen.")
    print("=" * 72)