import matplotlib.pyplot as plt
import random
import math 


# =============================================
# 1. Flocon de Von Koch
# =============================================

def decoupe1(A, B):
    """Découpage dans le sens trigonométrique (gauche)"""
    C = A + (B - A)/3
    D = A + 2*(B - A)/3
    
    # Rotation de 60° = π/3 dans le sens trigonométrique
    E1 = C + (D - C) * math.exp(1j * math.pi / 3)
    
    return [A, C, E1, D]


def decoupe2(A, B):
    """Découpage dans le sens anti-trigonométrique (droite)"""
    C = A + (B - A)/3
    D = A + 2*(B - A)/3
    
    # Rotation de -60°
    E2 = C + (D - C) * math.exp(-1j * math.pi / 3)
    
    return [A, C, E2, D]


def decoupepoly(P):
    """Applique decoupe1 sur chaque segment du polygone"""
    nouveau = []
    n = len(P)
    for i in range(n-1):                    # on évite de boucler sur le dernier
        segment = decoupe1(P[i], P[i+1])
        nouveau.extend(segment[:-1])        # on ajoute tout sauf le dernier point (déjà dans le suivant)
    nouveau.append(P[-1])                   # on referme avec le dernier point
    return nouveau


def VonKoch(P, n):
    """Applique n fois le découpage de Von Koch"""
    Q = P[:]
    for _ in range(n):
        Q = decoupepoly(Q)
    return Q


# Triangle équilatéral de base
triangle = [0, 2, 1 + 1j*math.sqrt(3)]   # troisième point à hauteur √3

# Flocon avec decoupe1 (classique)
flocon = VonKoch(triangle, 4)

X = [z.real for z in flocon]
Y = [z.imag for z in flocon]

plt.figure(figsize=(8,8))
plt.plot(X, Y, 'b-', linewidth=1)
plt.axis("equal")
plt.axis("off")
plt.title("Flocon de Von Koch (n=4)")
plt.show()


# Avec decoupe2 (question 7)
flocon2 = VonKoch(triangle, 4)
X2 = [z.real for z in flocon2]
Y2 = [z.imag for z in flocon2]

plt.figure(figsize=(8,8))
plt.plot(X2, Y2, 'r-', linewidth=1)
plt.axis("equal")
plt.axis("off")
plt.title("Flocon avec decoupe2")
plt.show()


# =============================================
# 2. Jeu du Chaos
# =============================================

def chaos(S, n):
    """Jeu du chaos sur un triangle (ou polygone) S"""
    points = []
    
    # Point de départ aléatoire à l'intérieur
    A, B, C = S[0], S[1], S[2]
    p, q, r = random.random(), random.random(), random.random()
    M = (p*A + q*B + r*C) / (p + q + r)
    points.append(M)
    
    for _ in range(n):
        sommet = random.choice(S)           # choix aléatoire d'un sommet
        M = (M + sommet) / 2                # milieu
        points.append(M)
    
    return points


# Test sur triangle équilatéral
triangle = [0, 2, 1 + 1j*math.sqrt(3)]
resultat = chaos(triangle, 10000)

X = [z.real for z in resultat]
Y = [z.imag for z in resultat]

plt.figure(figsize=(8,8))
plt.scatter(X, Y, s=0.5, color='blue', alpha=0.6)
plt.axis("equal")
plt.axis("off")
plt.title("Jeu du Chaos - Triangle (10000 points)")
plt.show()


# Sur pentagone régulier
def pentagone():
    P = []
    for k in range(5):
        theta = k * 2 * math.pi / 5
        P.append(complex(math.cos(theta), math.sin(theta)))
    return P

resultat5 = chaos(pentagone(), 20000)
X5 = [z.real for z in resultat5]
Y5 = [z.imag for z in resultat5]

plt.figure(figsize=(8,8))
plt.scatter(X5, Y5, s=0.5, color='red', alpha=0.6)
plt.axis("equal")
plt.axis("off")
plt.title("Jeu du Chaos - Pentagone")
plt.show()


# =============================================
# 3. Algorithme glouton - Rendu de monnaie
# =============================================

VALEURS = [200, 100, 50, 20, 10, 5, 2, 1]   # en centimes

# Variable globale pour la caisse (question 5)
CAISSE = [10, 10, 20, 30, 50, 100, 200, 500]   # exemple de stock


def pieces2cents(pieces):
    """Convertit une liste de pièces en montant total en centimes"""
    total = 0
    for i in range(len(pieces)):
        total = total + pieces[i] * VALEURS[i]
    return total


def rendu_glouton(montant):
    """Rend le montant avec le minimum de pièces (algorithme glouton)"""
    reste = montant
    pieces = [0] * len(VALEURS)
    
    for i in range(len(VALEURS)):
        while reste >= VALEURS[i]:
            pieces[i] = pieces[i] + 1
            reste = reste - VALEURS[i]
    return pieces


def rendu_glouton2(montant):
    """Version avec stock limité dans la caisse"""
    reste = montant
    pieces = [0] * len(VALEURS)
    
    for i in range(len(VALEURS)):
        while reste >= VALEURS[i] and CAISSE[i] > 0:
            pieces[i] = pieces[i] + 1
            CAISSE[i] = CAISSE[i] - 1
            reste = reste - VALEURS[i]
    return pieces, reste   # reste = ce qu'on n'a pas pu rendre


# Tests
print("Rendu glouton de 277 centimes :", rendu_glouton(277))
print("Total vérifié :", pieces2cents(rendu_glouton(277)), "centimes")

p, reste = rendu_glouton2(450)
print("Rendu avec caisse limitée :", p)
print("Reste non rendu :", reste, "centimes")