#!/usr/bin/env python3

# Bellman_Minimalbeispiel.py
"""
Kapitel Dynamische Programmierung: Die Handrechnung zur Rueckwaertsinduktion als Code.
Zeigt die Wertfunktionstabelle und die optimale Politik Schritt fuer Schritt.
"""

import numpy as np

GESAMT = 3          # zu verkaufende Einheiten
PERIODEN = 2        # Anzahl Verkaufsperioden


def kosten(menge: int) -> float:
    """Ueberproportionale Marktauswirkung: doppelte Menge kostet vierfach."""
    return float(menge ** 2)


def loese_rueckwaerts():
    # V[t, x] = minimale Restkosten, wenn zu Beginn von Periode t noch x Stueck offen sind
    V = np.full((PERIODEN + 1, GESAMT + 1), np.inf)
    politik = np.zeros((PERIODEN, GESAMT + 1), dtype=int)

    # Endbedingung: nach der letzten Periode darf nichts mehr offen sein
    V[PERIODEN, 0] = 0.0

    print("=" * 70)
    print("  RUECKWAERTSINDUKTION SCHRITT FUER SCHRITT")
    print("=" * 70)

    for t in range(PERIODEN - 1, -1, -1):
        letzte_periode = (t == PERIODEN - 1)
        print(f"\nStufe t = {t}" + ("  (letzte Periode: alles muss weg)" if letzte_periode
                                    else "  (freie Wahl der Menge)"))
        print(f"  {'Zustand x':>10} | {'beste Aktion':>12} | {'Sofortkosten':>13} | "
              f"{'V[t+1]':>9} | {'V[t]':>8}")
        print("  " + "-" * 62)

        for x in range(GESAMT + 1):
            aktionen = [x] if letzte_periode else range(x + 1)
            bester_wert, beste_aktion, beste_teile = np.inf, 0, (0.0, 0.0)

            for n in aktionen:
                rest = x - n
                sofort = kosten(n)
                zukunft = V[t + 1, rest]
                gesamt = sofort + zukunft
                if gesamt < bester_wert:
                    bester_wert, beste_aktion = gesamt, n
                    beste_teile = (sofort, zukunft)

            V[t, x] = bester_wert
            politik[t, x] = beste_aktion
            print(f"  {x:>10} | {beste_aktion:>12} | {beste_teile[0]:>13.1f} | "
                  f"{beste_teile[1]:>9.1f} | {bester_wert:>8.1f}")

    return V, politik


if __name__ == "__main__":
    V, politik = loese_rueckwaerts()

    # --- Vorwaertspfad: der optimalen Politik folgen ---------------------
    print("\n" + "=" * 70)
    print("  OPTIMALER PFAD (Vorwaertssimulation)")
    print("=" * 70)
    bestand = GESAMT
    gesamtkosten = 0.0
    for t in range(PERIODEN):
        aktion = politik[t, bestand]
        gesamtkosten += kosten(aktion)
        print(f"  Periode {t}: Bestand {bestand} -> verkaufe {aktion} "
              f"(Kosten {kosten(aktion):.1f}) -> Rest {bestand - aktion}")
        bestand -= aktion

    print(f"\n  Gesamtkosten: {gesamtkosten:.1f}  (V[0, {GESAMT}] = {V[0, GESAMT]:.1f})")
    assert abs(gesamtkosten - V[0, GESAMT]) < 1e-9, "Pfadkosten != Wertfunktion!"

    # --- Vergleich mit naiven Strategien ---------------------------------
    alles_sofort = kosten(GESAMT)
    print(f"\n  Zum Vergleich - alles in Periode 0 verkaufen: {alles_sofort:.1f}")
    print(f"  Ersparnis durch Stueckelung: {alles_sofort - gesamtkosten:.1f} "
          f"({(1 - gesamtkosten/alles_sofort)*100:.0f} %)")
    print("=" * 70)