1 files changed, 100 insertions, 0 deletions
diff --git a/src/faehre_fuellen.py b/src/faehre_fuellen.py
new file mode 100755
index 0000000..2c84b5d
--- /dev/null
+++ b/src/faehre_fuellen.py
@@ -0,0 +1,100 @@
+#!/usr/bin/env python3
+# -*- coding: utf-8 -*-
+# getestet mit Python 2.7.8 und 3.4.2
+'''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")
+
+
+# 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(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}
+
+    while len(abfolge):
+        success = False
+        # Fahrzeuge werden aus der Schlange gepopt
+        fahrzeug = abfolge.pop()
+
+        # jetzt wird das Fahrzeug möglichst weit links eingeordnet
+        for k in range(FAEHRENBREITE):
+            # dazu wird bei allen Parkreihen überprüft, ob das Fahrzeug passt
+            if fahrzeug + faehre["länge"][k] < \
+                FAEHRENLAENGE - ABSTAND * (faehre["anzahl"][k] - 1):
+
+                faehre["länge"][k] += fahrzeug
+                faehre["anzahl"][k] += 1
+
+                print(str(fahrzeug) + " wurde eingeordnet in die Reihe " + \
+                    str(k))
+                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(vabfolge):
+    '''Sortiert eine Abfolge von Fahrzeugen möglichst gleichmäßig ein'''
+    abfolge = vabfolge[:]
+    faehre = {"anzahl": [0] * FAEHRENBREITE, "länge": [0] * FAEHRENBREITE}
+
+    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):
+            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):
+
+                faehre["länge"][diese_spalte] += fahrzeug
+                faehre["anzahl"][diese_spalte] += 1
+
+                print(str(fahrzeug) + " wurde eingeordnet in Reihe " + \
+                    str(diese_spalte))
+                success = True
+                break
+
+        if success == False:
+            print("Das Fahrzeug " + str(fahrzeug) + " hat nicht mehr gepasst")
+            break
+
+        spalte += 1
+        if spalte == FAEHRENBREITE:
+            spalte = 0
+
+    return faehre
+
+if __name__ == "__main__":
+    print("\n=== Strategie A ===\n")
+    print(strategie_a(BEISPIEL[0][:]))
+    print("\n=== Strategie B ===\n")
+    print(strategie_b(BEISPIEL[0][:]))