import random
import math

Initialplatzierung = [["A","B","C"],
                      ["D","E","F"],
                      ["G","H","I"]]

def Kosten(Platzierung):
    Positionen = {}
    for j in range(3):
        for i in range(3):
            Positionen[Platzierung[j][i]] = (j,i)
    Verbindungen = [("A","B"),("A","C"),("A","D"),
                    ("B","C"),("B","E"),("B","H"),
                    ("C","F"),
                    ("D","F"),
                    ("E","H"),
                    ("G","H"),("G","I"),
                    ("H","I")]
    summe = 0
    for (p,q) in Verbindungen:
        delta_x = abs(Positionen[p][0]-Positionen[q][0])
        delta_y = abs(Positionen[p][1]-Positionen[q][1])
        summe += delta_x + delta_y
    return summe

def OptimizePairwiseInterchange(Platzierung):
    aktuelleKosten = Kosten(Platzierung)
    print("PairwiseInterchange: Kosten der Initialplatzierung: ",
          aktuelleKosten)
    j = 0
    while j < 3:
        i = 0
        while i < 3:
            print("tausch von",Platzierung[j][i],"...")
            m = 0
            while m < 3:
                n = 0
                while n < 3:
                    if not ((m == j) and (n == j)):
                        z = Platzierung[j][i]
                        Platzierung[j][i] = Platzierung[m][n]
                        Platzierung[m][n] = z
                        neueKosten = Kosten(Platzierung)
                        if neueKosten < aktuelleKosten:
                            print("... mit",Platzierung[j][i],
                                  "bringt eine Verbesserung (Kosten",
                                  neueKosten, ")")
                            aktuelleKosten = neueKosten
                            j = -1
                            i = 3
                            m = 3
                            n = 3
                        else:
                            z = Platzierung[j][i]
                            Platzierung[j][i] = Platzierung[m][n]
                            Platzierung[m][n] = z
                            print("... mit", Platzierung[m][n],
                                  "bringt keine Verbesserung (Kosten",
                                  neueKosten, ")")
                    n += 1
                m += 1
            i += 1
        j += 1

def FisherYatesPermutateRandom(P):
    n = len(P)
    i = n-1
    while i > 1:
        zz = random.randint(0,i)
        v = P[i]
        P[i] = P[zz]
        P[zz] = v
        i -= 1

def Permutate3x3(Platzierung):
    P = [x for x in range(9)]
    FisherYatesPermutateRandom(P)
    for k in range(9):
        j = P[k] // 3
        i = P[k] % 3
        m = k // 3
        n = k % 3 
        z = Platzierung[j][i]
        Platzierung[j][i] = Platzierung[m][n]
        Platzierung[m][n] = z
        
def OptimizeSimulatedAnnealingAufgabe(Platzierung):
    aktuelleKosten = Kosten(Platzierung)
    for T in [10,4,1.6,0.64]:
        print("T =",T)
        for i in range(5):
            neuePlatzierung = Platzierung.copy()
            Permutate3x3(neuePlatzierung)
            neueKosten = Kosten(Platzierung)
            print("neuePlatzierung:")
            print(neuePlatzierung[0])
            print(neuePlatzierung[1])
            print(neuePlatzierung[2],"Kosten:",neueKosten)
            delta = neueKosten-aktuelleKosten
            if (delta < 0) or (random.random() < math.exp(-delta/T)):
                Platzierung = neuePlatzierung
                aktuelleKosten = neueKosten

def OptimizeSimulatedAnnealing(Platzierung):
    T = 10
    aktuelleKosten = Kosten(Platzierung)
    Kostenliste = [(aktuelleKosten,T)]
    while T >= 0.2:
        for i in range(100):
            neuePlatzierung = Platzierung.copy()
            Permutate3x3(neuePlatzierung)
            neueKosten = Kosten(Platzierung)
            delta = neueKosten-aktuelleKosten
            if (delta < 0) or (random.random() < math.exp(-delta/T)):
                Platzierung = neuePlatzierung
                aktuelleKosten = neueKosten
                print("akzeptiere neue Platzierung: ")
                print(" delta =",delta)
                print(" T =",T)
                print(" aktuelleKosten =",aktuelleKosten)
                Kostenliste.append((aktuelleKosten,T))
        T = T / 2
    return Kostenliste