Skript um Dinnerhopping zu optimieren

dinnerhopping

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Ein Dinnerhopping soll organisiert werden.

# Es nehmen 42 Personen in 21 Teams teil.

n_teams = 21

from random import randrange

# Diese Funktion setzt wer wann kocht. Und schaut dann nach Kollisionen.
# Erfahrungswerte zeigen, dass etwa 68% der Permutationen ungültig sind.
def koch_permutation():
    # Bei jedem Team kann gekocht werden, es gibt also eigentlich 21 Küchen.
    # Es werden nacHeinander drei Mahlzeiten eingenommen.

    koch_vor = [False for i in xrange(n_teams)]
    koch_haupt = [False for i in xrange(n_teams)]
    koch_nach = [False for i in xrange(n_teams)]

    # Es soll koch_vor[i] + koch_haupt[i] + koch_nach[i] = 1 gelten.
    # Außerdem sum(koch_*) = 7.

    # Verteile die teams zufällig auf die Kochzeiten

    noch_kochen = range(n_teams)
    kochzeit = [0 for i in xrange(n_teams)]

    # Vorspeisen
    for i in xrange(7):
        koch_team_nummer = noch_kochen.pop(randrange(len(noch_kochen)))
        koch_vor[koch_team_nummer] = True
        kochzeit[koch_team_nummer] = 1

    # Hauptmahlzeiten
    for i in xrange(7):
        koch_team_nummer = noch_kochen.pop(randrange(len(noch_kochen)))
        koch_haupt[koch_team_nummer] = True
        kochzeit[koch_team_nummer] = 2

    # Nachspeisen
    for i in xrange(7):
        koch_team_nummer = noch_kochen.pop(randrange(len(noch_kochen)))
        koch_nach[koch_team_nummer] = True
        kochzeit[koch_team_nummer] = 3

    # Es gibt einige Einschränkungen zu beachten:
    # Ein paar Teams teilen sich eine Küche, sie sollten nicht gleichzeitig kochen.
    # B.z.w. Dort können nicht 6*2 = 12 Personen gleichzeitig essen!

    if (kochzeit[1] == kochzeit[2]) or (kochzeit[3] == kochzeit[4]) or (kochzeit[5] == kochzeit[6]):
        return None

    return (koch_vor, koch_haupt, koch_nach, kochzeit)

def kollisionsfreie_kochzeiten():
    result = None
    while result is None:
        result = koch_permutation()
    return result

def personen_verteilen(kochzeit):
    vorkocher   = []
    hauptkocher = []
    nachkocher  = []
    for i in xrange(len(kochzeit)):
        if kochzeit[i] == 1:
            vorkocher.append(i)
        elif kochzeit[i] == 2:
            hauptkocher.append(i)
        elif kochzeit[i] == 3:
            nachkocher.append(i)
        else:
            raise "Eine illegale Kochzeit steht in der Kochzeitliste"

    # Jetzt wird jedem Team ein Ort zum Essen zugewiesen.
    # Dafür erstelle ich eine Liste mit Vorspeisenplätzen, davon wählt jeder aus.

    wo_esse_ich_vorspeise = [None for i in xrange(21)]
    wo_esse_ich_hauptspeise = [None for i in xrange(21)]
    wo_esse_ich_nachspeise = [None for i in xrange(21)]

    vorspeise_platzkarten = range(7)*2
    hauptspeise_platzkarten = range(7)*2
    nachspeise_platzkarten = range(7)*2

    # Vorspeise
    for i in xrange(21):
        # Koche ich die Vorspeise selber?
        if kochzeit[i] == 1:
            # Ich esse bei mir selbst
            wo_esse_ich_vorspeise[i] = i
        else:
            # Ziehe eine zufällige Platzkarte
            platzkarte = vorspeise_platzkarten.pop(randrange(len(vorspeise_platzkarten)))
            wo_esse_ich_vorspeise[i] = vorkocher[platzkarte]

    # Hauptspeise
    for i in xrange(21):
        if kochzeit[i] == 2:
            # Ich esse bei mir selbst
            wo_esse_ich_hauptspeise[i] = i
        else:
            # Ziehe eine zufällige Platzkarte
            platzkarte = hauptspeise_platzkarten.pop(randrange(len(hauptspeise_platzkarten)))
            wo_esse_ich_hauptspeise[i] = hauptkocher[platzkarte]

    # Nachspeise
    for i in xrange(21):
        if kochzeit[i] == 3:
            # Ich esse bei mir selbst
            wo_esse_ich_nachspeise[i] = i
        else:
            # Ziehe eine zufällige Platzkarte
            platzkarte = nachspeise_platzkarten.pop(randrange(len(nachspeise_platzkarten)))
            wo_esse_ich_nachspeise[i] = nachkocher[platzkarte]

    # print wo_esse_ich_vorspeise
    # print wo_esse_ich_hauptspeise
    # print wo_esse_ich_nachspeise

    return (wo_esse_ich_vorspeise, wo_esse_ich_hauptspeise, wo_esse_ich_nachspeise)

def bewerte_verteilung(wo_vor, wo_haupt, wo_nach):
    # Analysiert die Verteilung und gibt eine Punktzahl.

    # Erst wird eine Liste erzeugt, die für alle Teams nachsieht mit wem sie sich treffen.
    bekanntschaften = [[False for die_anderen in xrange(21)] for ich_selbst in xrange(21)]

    for i in xrange(21):
        for j in xrange(21):
            # Ich zähle mich selbst nicht mit
            if i == j:
                continue
            if wo_vor[j] == wo_vor[i]:
                bekanntschaften[i][j] = True
            if wo_haupt[j] == wo_haupt[i]:
                bekanntschaften[i][j] = True
            if wo_nach[j] == wo_nach[i]:
                bekanntschaften[i][j] = True

    # Jetzt wird geprüft, ob sich die beiden Teams, die sich hassen treffen.
    if bekanntschaften[2][3]:
        return -1000.0, None

    # Ab jetzt sind die Identitäten nicht mehr wichtig, also wird nur noch die Zahl der Partner aufsummiert.
    zahl_bekanntschaften = [-10000 for i in xrange(21)]
    for i in xrange(21):
        zahl_bekanntschaften[i] = sum(bekanntschaften[i])

    return sum(zahl_bekanntschaften), zahl_bekanntschaften

maximum = 0
for i in xrange(10000):
    v, h, n, kochzeit = kollisionsfreie_kochzeiten()
    v, h, n = personen_verteilen(kochzeit)
    (wert, einzelwert) = bewerte_verteilung(v, h, n)
    if wert > maximum:
        maximum = wert
        print wert, einzelwert
    if wert == 126:
        break