#!/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][:]))