diff options
| -rwxr-xr-x | faehre_fuellen.py | 87 |
1 files changed, 50 insertions, 37 deletions
diff --git a/faehre_fuellen.py b/faehre_fuellen.py index ae17427..caa8b9c 100755 --- a/faehre_fuellen.py +++ b/faehre_fuellen.py @@ -1,26 +1,32 @@ #!/usr/bin/env python3 +# -*- coding: utf-8 -*- +'''Stellt zwei Strategien zur Lösung der Fähre-Füllen-Aufgabe''' -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") +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("; ")] +# 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 +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[:] +def strategie_a(vabfolge): + '''Sortiert eine Abfolge von Fahrzeugen möglichst weit links ein''' + abfolge = vabfolge[:] # `faehre` hält die Anzahl an Fahrzeugen und deren Gesamtlänge in einem dict - faehre = {"anzahl": [0] * Faehrenbreite, "länge": [0] * Faehrenbreite} + faehre = {"anzahl": [0] * FAEHRENBREITE, "länge": [0] * FAEHRENBREITE} while len(abfolge): success = False @@ -28,13 +34,16 @@ def strategie_a(Abfolge): fahrzeug = abfolge.pop() # jetzt wird das Fahrzeug möglichst weit links eingeordnet - for j in range(Faehrenbreite): + for k 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 + if fahrzeug + faehre["länge"][k] < \ + FAEHRENLAENGE - ABSTAND * (faehre["anzahl"][k] - 1): - print(str(fahrzeug) + " wurde eingeordnet in die Reihe " + str(j)) + faehre["länge"][k] += fahrzeug + faehre["anzahl"][k] += 1 + + print(str(fahrzeug) + " wurde eingeordnet in die Reihe " + \ + str(k)) success = True break @@ -43,29 +52,33 @@ def strategie_a(Abfolge): # ...und abfahren break - # Wichtig: in `faehre["länge"][x]` ist der Abstand nicht einberechnet + # 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} +def strategie_b(vabfolge): + '''Sortiert eine Abfolge von Fahrzeugen möglichst gleichmäßig ein''' + abfolge = vabfolge[:] + faehre = {"anzahl": [0] * FAEHRENBREITE, "länge": [0] * FAEHRENBREITE} - j = 0 + spalte = 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 + for k in range(FAEHRENBREITE): + diese_spalte = spalte + k + if diese_spalte >= FAEHRENBREITE: + diese_spalte -= FAEHRENBREITE + + if fahrzeug + faehre["länge"][diese_spalte] < FAEHRENLAENGE \ + - ABSTAND * (faehre["anzahl"][diese_spalte] - 1): - if fahrzeug + faehre["länge"][l] < Faehrenlaenge - Abstand * (faehre["anzahl"][l] - 1): - faehre["länge"][l] += fahrzeug - faehre["anzahl"][l] += 1 + faehre["länge"][diese_spalte] += fahrzeug + faehre["anzahl"][diese_spalte] += 1 - print(str(fahrzeug) + " wurde eingeordnet in Reihe " + str(l)) + print(str(fahrzeug) + " wurde eingeordnet in Reihe " + \ + str(diese_spalte)) success = True break @@ -73,14 +86,14 @@ def strategie_b(Abfolge): print("Das Fahrzeug " + str(fahrzeug) + " hat nicht mehr gepasst") break - j += 1 - if j == Faehrenbreite: - j = 0 + spalte += 1 + if spalte == FAEHRENBREITE: + spalte = 0 return faehre if __name__ == "__main__": print("\n=== Strategie A ===\n") - print(strategie_a(Beispiel[:])) + print(strategie_a(BEISPIEL[:])) print("\n=== Strategie B ===\n") - print(strategie_b(Beispiel[:])) + print(strategie_b(BEISPIEL[:])) |