#!/usr/bin/env python3

Beispiel = []
Beispiel.append("5,23; 4,41; 3,33; 13,13; 9,12; 4,38; 6,34; 5,37; 4,11; 3,74; 10,62")
Beispiel.append("4,14; 3,63; 3,92; 7,95; 5,23; 3,30; 4,86; 15,06")
Beispiel.append("6,96; 5,06; 3,77; 3,95; 3,91; 3,54; 4,26; 4,03; 5,43; 4,04; 4,43; 4,12; 2,78")


# das Beispiel wird geparst
for j in range(len(Beispiel)):
    Beispiel[j] = [float(k.replace(",", ".")) for k in Beispiel[j].split("; ")]

# vorgegebene Konstanten in Meter umgerechnet
Faehrenlaenge = 20
Faehrenbreite = 3
Abstand = 0.3

# `abfolge`: Eine Liste mit Längen von Autos
# gibt ein dict zurück, welches "anzahl" und "länge" aller Autos enthält
def strategie_a(Abfolge):
    abfolge = Abfolge[:]
    # `faehre` hält die Anzahl an Fahrzeugen und deren Gesamtlänge in einem dict
    faehre = {"anzahl": [0] * Faehrenbreite, "länge": [0] * Faehrenbreite}

    while len(abfolge):
        success = False
        # Fahrzeuge werden aus der Schlange gepopt
        fahrzeug = abfolge.pop()

        # jetzt wird das Fahrzeug möglichst weit links eingeordnet
        for j in range(Faehrenbreite):
            # dazu wird bei allen Parkreihen überprüft, ob das Fahrzeug passt
            if fahrzeug + faehre["länge"][j] < Faehrenlaenge - Abstand * (faehre["anzahl"][j] - 1):
                faehre["länge"][j] += fahrzeug
                faehre["anzahl"][j] += 1

                print(str(fahrzeug) + " wurde eingeordnet in die Reihe " + str(j))
                success = True
                break

        if success == False:
            print("Das Fahrzeug " + str(fahrzeug) + " hat nicht mehr gepasst")
            # ...und abfahren
            break

    # Wichtig: in `faehre["länge"][x]` ist der Abstand nicht einberechnet
    return faehre
    
# siehe `strategie_a`
def strategie_b(Abfolge):
    abfolge = Abfolge[:]
    faehre = {"anzahl": [0] * Faehrenbreite, "länge": [0] * Faehrenbreite}

    j = 0
    while len(abfolge):
        success = False
        fahrzeug = abfolge.pop()
        # Fahrzeuge werden möglichst gleichmäßig von links nach rechts verteilt
        for k in range(Faehrenbreite):
            l = j + k
            if l >= Faehrenbreite:
                l -= Faehrenbreite

            if fahrzeug + faehre["länge"][l] < Faehrenlaenge - Abstand * (faehre["anzahl"][l] - 1):
                faehre["länge"][l] += fahrzeug
                faehre["anzahl"][l] += 1

                print(str(fahrzeug) + " wurde eingeordnet in Reihe " + str(l))
                success = True
                break

        if success == False:
            print("Das Fahrzeug " + str(fahrzeug) + " hat nicht mehr gepasst")
            break

        j += 1
        if j == Faehrenbreite:
            j = 0

    return faehre

if __name__ == "__main__":
    print("\n=== Strategie A ===\n")
    print(strategie_a(Beispiel[:]))
    print("\n=== Strategie B ===\n")
    print(strategie_b(Beispiel[:]))