Python :: Aufgabe #234

2 Lösungen Lösungen öffentlich

Das Problemspiel der spagetti-essenden Philosophen

Anfänger - Python von hollst - 04.12.2019 um 18:44 Uhr
wiki
https://de.wikipedia.org/wiki/Philosophenproblem


Fünf Philosophen sitzen um einen runden Tisch, vor jedem ein Teller voll mit Spagetti und links davon eine Gabel (BILD 1).
Um von dem Teller Spagetti essen zu können, benötigt man allerdings zwei Gabeln. Die zweite Gabel kann man sich von seinem
rechten Nachbarn borgen, sofern dieser nicht gerade selber beim Essen ist. Außerdem sollte man seine eigene Gabel auch nicht gerade
an seinen linken Nachbarn verborgt haben.

Das Spiel beginnt beim ersten Philosophen und geht Schritt für Schritt wie folgt reihum:

Jeder Philosoph kann sich in einem von drei möglichen Zuständen befinden,
u. z. denkend (Zustand 1, zu Beginn alle fünf Philosophen), hungernd (2) oder essend (3).

Ein denkender Philosoph kann per Zufallsentscheidung entweder in diesem Zustand 1 verweilen (dann geht der Zeiger sofort weiter an
seinen rechten Nachbarn) oder sich für "Essenwollen" entscheiden (Übergang von Zustand 1 in Zustand 2). In diesem Fall muss er prüfen,
ob ihm zwei Gabeln zur Verfügung stehen. Wenn Ja geht er von Zusand 2 in den Zustand 3 über und kann (sagen wir) zwei [Variable E wie Essen] Runden lang essen. Nach den zwei [E] Runden wird er zunächst wieder zum denkenden Philosophen (Zustand 1), der geleerte Teller wird sofort wieder aufgefüllt, falls der Philosoph erneut Hunger bekommt.

Hat er allerdings keine zwei Gabeln zur Verfügung, bleibt er die Runde hungrig (er verharrt im Zustand 2). Bekommt ein Philosoph
(sagen wir) zehn [Variable T wie Tod] Runden lang hintereinander nichts zu essen, ist er verhungert und das Gelage auch zu ende.

Die Frage lautet, nach wie vielen Runden (abhängig von E und T) ist im Durchschitt der erste Philosoph verhungert. Viel Spaß!

Lösungen:

1x
vote_ok
von Klaus (730 Punkte) - 22.02.2020 um 12:41 Uhr
Der Code ist besonders ausführlich, um exemplarisch den Einsatz der OOP zu zeigen. Die Konstanten können modifiziert und damit verschiedene Szenarien simuliert werden.

Quellcode ausblenden Python-Code
import random as rnd

# Definition der Konstanten / diese können modifiziert werden

# Anzahl der Philosophen am Tisch
NUMBER_OF_PHILOSOPHER = 5

# Wahrscheinlichkeit, mit der der denkende Philosoph zu essen beginnt
RANDOM_EATING_FACTOR = 0.5

# Anzahl an Runden, die ein essender Philosoph isst
EATING_ROUNDS = 2

# Anzahl der Runden, bis ein hungernder Philosoph stirbt
DEATH_ROUND = 10

# Anzahl der Durchläufe, die simuliert werden
NUMBER_OF_ITERATIONS = 1000

# Anzeige jeder einzelnen Runde / alternativ: Anzeige eines Fortschrittbalkens
OUTPUT_PER_ROUND = False

# Anzahl der Durchläufe, ab denen der Fortschrittsbalken angezeigt wird
SHOW_PROGRESS_BAR_ROUNDS = 200

# Beeinflusst die Aktion eines Philosophen, der hungrig ist, aber nicht beide Gabeln hat
# 'both' - er sichert sich sowohl die rechte, als auch die linke Gabel
# 'left' - er sichert sich nur die linke Gabel
# 'right' - er sichert sich nur die rechte Gabel
# 'none' - er sichert sich keine Gabel
SAVE_FORK = 'both'

# Legt fest, ob alle SAVE_FORK-Varianten nacheinander simuliert werden oder nicht
SIMULATE_ALL_VARIANTS = True


class Philosopher:
    """ Stellt einen einzelnen Philosophen dar
        Attribute:
            name (string) - Name des Philosophen
            right_neighbour (Philosopher) - rechts nebensitzender Philosoph
            free_left_fork (bool) - ist die linke Gabel verfügbar?
            got_left_fork (bool) - hat er eine linke Gabel in der Hand?
            got_right_fork (bool) - hat er eine rechte Gabel in der Hand?
            state (string) - aktuelle Zustandsbeschreibung ('thinking' / 'hungry' / 'eating')
            eating_round (int) - Anzahl der Runden, die der Philosoph bereits isst
            hungry_round (int) - Anzahl der Runden, die der Philosoph bereits hungert
        Methoden:
            start_eating() - Philosoph beginnt mit dem Essen
            stop_eating() - Philosoph beendet das Essen
            save_fork() - Philosoph sichert sich, wenn er nicht essen kann, schon einmal die Gabel
                          entsprechend der Konstanten SAVE_FORK """

    def __init__(self, index):
        self.name = f'Philosoph_{index+1}'
        self.right_neighbour = None
        self.free_left_fork = True
        self.got_left_fork = False
        self.got_right_fork = False
        self.state = 'thinking'
        self.eating_round = 0
        self.hungry_round = 0

    def start_eating(self):
        self.state = 'eating'
        self.free_left_fork = False
        self.got_left_fork = True
        self.right_neighbour.free_left_fork = False
        self.got_right_fork = True
        self.eating_round = 1
        self.hungry_round = 0

    def stop_eating(self):
        self.state = 'thinking'
        self.free_left_fork = True
        self.got_left_fork = False
        self.right_neighbour.free_left_fork = True
        self.got_right_fork = False
        self.eating_round = 0


    def save_fork(self):
        if SAVE_FORK == 'none':
            # Es wird sich keine Gabel gesichert
            pass
        if SAVE_FORK == 'left' or SAVE_FORK == 'both':
            # Es wird sich die linke Gabel schon einmal gesichert
            if self.free_left_fork:
                self.free_left_fork = False
                self.got_left_fork = True
        if SAVE_FORK == 'right' or SAVE_FORK == 'both':
            # Es wird sich die rechte Gabel schon einmal gesichert
            if self.right_neighbour.free_left_fork:
                self.right_neighbour.free_left_fork = False
                self.got_right_fork = True


class Table:
    """ Stellt den Tisch mit Philosophen dar
        Attribute:
            table_participants (list) - Liste der am Tisch sitzenden Philosophen
            number_of_active_philosopher (int) - Nummer des agierenden Philosophen
            number_of_rounds (int) - Nummer der aktuellen Runde
        Methoden:
            participants_take_place() - Philosophen werden der Liste table_participants zugewiesen
            look_at_right_neighbour() - jedem Philosoph wird sein rechter Nachbar als Attribut zugeordnet
            force_action() - der aktive Philosoph führt seine Aktion entsprechend der Bedingungen durch
            next_philosopher() - der nächste Philosoph ist an der Reihe, ggf. Erhöhung der Rundenzahl """

    def __init__(self):
        self.table_participants = []
        self.number_of_active_philosopher = NUMBER_OF_PHILOSOPHER - 1
        self.number_of_rounds = 0

    def participants_take_place(self):
        # die Philosophen setzen sich an den Tisch
        for index in range(NUMBER_OF_PHILOSOPHER):
            self.table_participants.append(Philosopher(index))

    def look_at_right_neighbour(self):
        # die Philosophen registieren ihren rechten Nachbarn
        for index in range(NUMBER_OF_PHILOSOPHER - 1):
            self.table_participants[index].right_neighbour = self.table_participants[index+1]
        # vom letzten Philosophen ist der erste Philosoph der rechte Nachbar
        self.table_participants[NUMBER_OF_PHILOSOPHER - 1].right_neighbour = self.table_participants[0]

    def force_action(self):
        active_philosopher = self.table_participants[self.number_of_active_philosopher]

        # es ist ein denkender Philosoph
        if active_philosopher.state == 'thinking':
            # Essensentscheidung als Zufallsereignis
            eating_decision = rnd.random()
            # Philosoph entscheidet sich zu essen
            if eating_decision < RANDOM_EATING_FACTOR:
                # Zwei Gabeln stehen zur Verfügung
                if (active_philosopher.free_left_fork or active_philosopher.got_left_fork) and \
                        (active_philosopher.right_neighbour.free_left_fork or active_philosopher.got_right_fork):
                    active_philosopher.start_eating()
                else:
                    active_philosopher.state = 'hungry'
                    active_philosopher.hungry_round = 1

                    # Selektion, ob eine freie Gabel sich schon gesichert wird, obwohl noch nicht gegessen werden kann
                    active_philosopher.save_fork()

            # Philosoph isst nicht, sondern denkt weiter
            else:
                # es passiert nichts
                pass
            # Aktiver Philosoph ist in beiden Fällen nicht gestorben
            return False

        # es ist ein essender Philosoph
        elif active_philosopher.state == 'eating':
            # Anzahl an Essensrunden noch nicht erreicht
            if active_philosopher.eating_round <= EATING_ROUNDS:
                active_philosopher.eating_round += 1
            # Anzahl an Essensrunden wurde erreicht
            else:
                active_philosopher.stop_eating()
            # Aktiver Philosoph ist in beiden Fällen nicht gestorben
            return False

        # es ist ein hungriger Philosoph
        elif active_philosopher.state == 'hungry':
            # jetzt stehen Gabeln zur Verfügung
            if (active_philosopher.free_left_fork or active_philosopher.got_left_fork) and \
                    (active_philosopher.right_neighbour.free_left_fork or active_philosopher.got_right_fork):
                active_philosopher.start_eating()
            # es stehen weiterhin keine Gabeln zur Verfügung
            else:
                active_philosopher.hungry_round += 1
                active_philosopher.save_fork()
                if active_philosopher.hungry_round >= DEATH_ROUND:
                    return True

    def next_philosopher(self):
        self.number_of_active_philosopher += 1
        if self.number_of_active_philosopher >= NUMBER_OF_PHILOSOPHER:
            self.number_of_rounds += 1
            self.number_of_active_philosopher = 0


class Simulation:
    """ Steuert die Simulation
        Attribute:
            actual_iteration (int) - Anzahl des aktuellen Durchlaufes
            number_of_rounds_overall (int) - Anzahl der Runden über alle Durchläufe hinweg
            philosopher_is_dead (bool) - ist ein Philosoph schon tot?
            table (Table) - Verwaltet den Tisch mit den Philosophen
        Methoden:
            start_simulation() - Führt die Simulation entsprechend der iteration aus
        """

    def __init__(self):
        self.actual_iteration = 0
        self.number_of_rounds_overall = 0
        self.philosopher_is_dead = False
        self.table = None
        # Durchläuft die Anzahl an Iterationen
        for index in range(NUMBER_OF_ITERATIONS):
            self.start_simulation()
        # Ausgabe der Durchschnittswerte
        print(f'Im Mittelwert der {NUMBER_OF_ITERATIONS} Versuche verstarb der erste Philosoph in Runde '
              f'{int(self.number_of_rounds_overall / NUMBER_OF_ITERATIONS)}.\n')

    def start_simulation(self):
        self.actual_iteration += 1
        self.table = Table()
        self.table.participants_take_place()
        self.table.look_at_right_neighbour()
        # solange kein Philosoph gestorben ist
        while not self.philosopher_is_dead:
            self.table.next_philosopher()
            # die Methode force_action gibt zurück (bool), ob ein Philosoph gestorben ist
            self.philosopher_is_dead = self.table.force_action()
        # für die nächste Iteration wird der Wert zurückgesetzt
        self.philosopher_is_dead = False
        self.number_of_rounds_overall += self.table.number_of_rounds

        # Ausgabe der Ergebnisse der jeweiligen Runde
        if OUTPUT_PER_ROUND:
            print(f'Durchgang {self.actual_iteration:4}: '
                  f'{self.table.table_participants[self.table.number_of_active_philosopher].name} ist in Runde '
                  f'{self.table.number_of_rounds} gestorben.')
        # Anzeige eines Fortschrittbalkens, dann Ausgabe der Mittelwerte
        elif NUMBER_OF_ITERATIONS >= SHOW_PROGRESS_BAR_ROUNDS:
            if self.actual_iteration == 1:
                print('FORTSCHRITT (je 10%) ', end='')
            # alle 10% wird ein Punkt gesetzt
            if self.actual_iteration % int(NUMBER_OF_ITERATIONS/10) == 0:
                print('. ', end='')
            if self.actual_iteration == NUMBER_OF_ITERATIONS:
                print('FERTIG')


if __name__ == '__main__':

    if SIMULATE_ALL_VARIANTS:
        iterations = ['none', 'left', 'right', 'both']
        translate_iterations = {'none': 'keine Gabel',
                                'left': 'nur die linke Gabel',
                                'right': 'nur die rechte Gabel',
                                'both': 'beide Gabeln'}
        for element in iterations:
            SAVE_FORK = element
            print(f'VARIANTE: Der Philosoph sichert sich {translate_iterations[element]}, wenn er hungrig ist, aber '
                  f'wegen fehlender Gabeln nicht essen kann.')
            simulation = Simulation()
    else:
        simulation = Simulation()
vote_ok
von kaschperl (210 Punkte) - 24.02.2020 um 15:24 Uhr
Quellcode ausblenden Python-Code
import random
import pandas as pd
import statistics


class Phil:
    '''Stellt einen Philosophen dar

    Zustände Philosoph Status:
    D = Denken
    H = Hungrig
    E = Essen
    T = Tot

    Zustände der Gabel des Philosophen
    T = auf dem Tisch
    H = linke Hand
    V = verliehen / steht nicht zur Verfügung'''

    def __init__(self, number, name, neighbour):
        self.number = number
        self.name = name
        self.status = 'D'
        self.status_round_count = 0
        self.fork = 'T'
        self.right_neighbour = neighbour

        #self.print_Phil()

    def print_Phil(self):
        print(f'Nummer: {self.number}')
        print(f'Name: {self.name}')
        print(f'Status: {self.status}')
        print(f'Status Runde: {self.status_round_count}')
        print(f'Fork: {self.fork}')
        print(f'Rechter Nachbar: {self.right_neighbour}')


class PhilTable:
    '''Steuerung der Philosophen beim Essen.'''

    def __init__(self, rounds_to_eat, rounds_to_death, tables_to_play):
        self.rounds_to_eat = rounds_to_eat
        self.rounds_to_death = rounds_to_death
        self.tables_to_play = tables_to_play
        self.phil_list = [Phil(x, "Philosoph " + str(x+1), x-1) for x in range(5)]
        self.round = 0
        self.STATUS_Dic = {"D": "denkt",
                           "H": "ist hungrig",
                           "E": "am essen",
                           "T": "ist Tot"}
        self.LEFTFORKDIC = {"T": "auf dem Tisch",
                            "H": "in der Hand",
                            "V": "ist verliehen"}
        self.RIGHTFORKDIC = {"T": "auf dem Tisch",
                             "V": "in der Hand",
                             "H": "nicht verfügbar"}
        self.results_of_death = []

        # Korrektur des right_neighbour für den ersten Philosophen
        self.phil_list[0].right_neighbour = len(self.phil_list)-1
        self.table_status()
        self.get_results()
        #self.return_rounds()

    def get_results(self):
        '''Durchschnitt ermitteln wie lange alle am Leben sind'''
        for x in range(self.tables_to_play):
            self.results_of_death.append(self.return_rounds())
            self.reset_table()
        print(f'Ergebnisse: {self.results_of_death}')
        print(f'Durchschnitt: {statistics.mean(self.results_of_death)}')

    def reset_table(self):
        '''Philosophen wiederbeleben
           denkend, Gabeln auf den Tisch und Counter auf 0'''
        self.round = 0
        for phil in self.phil_list:
            phil.status = 'D'
            phil.fork = 'T'
            phil.status_round_count = 0

    def take_fork_from_right(self, phil_no):
        '''True - Gabel auf dem Tisch / verfügbar - Gabel wird entwendet
           False - Gabel nicht auf dem Tisch / nicht verfügbar'''
        ret = (self.phil_list[phil_no].fork == 'T')
        if ret is True:
            self.phil_list[phil_no].fork = 'V'
        return ret

    def take_own_fork_from_left(self, phil_no):
        '''True - Gabel auf dem Tisch / verfügbar - Gabel wird entwendet
           False - Gabel nicht auf dem Tisch / nicht verfügbar'''
        ret = (self.phil_list[phil_no].fork == 'T')
        if ret is True:
            self.phil_list[phil_no].fork = 'H'
        return ret

    def return_fork(self, phil_no):
        '''Gabel wird auf den Tisch gelegt'''
        self.phil_list[phil_no].fork = 'T'

    def set_status(self, phil_no, status):
        '''Setzt den Status
           Der Rundenzähler wird auf 0 gestellt'''
        self.phil_list[phil_no].status = status
        self.phil_list[phil_no].status_round_count = 0

    def count_up_status_round_count(self):
        '''Nach jedder Runde wird der Counter um eins erhöht'''
        for phil in self.phil_list:
            phil.status_round_count += 1

    def table_status(self):
        '''Ausgabe aller Statusinformationen in Tabellenform'''
        print(f'#### Status Runde {self.round} ###')
        status_pd = pd.DataFrame(index=['Status',
                                        'Runden im Status',
                                        'seine linke Gabel',
                                        'Nachbars Gabel (rechts)',
                                        'rechter Nachbar'])
        for phil in self.phil_list:
            new_col = [self.STATUS_Dic[str(phil.status)],
                       str(phil.status_round_count),
                       self.LEFTFORKDIC[str(phil.fork)],
                       self.RIGHTFORKDIC[self.phil_list[phil.right_neighbour].fork],
                       str(self.phil_list[phil.right_neighbour].name)]
            status_pd[str(phil.name)] = new_col
        print(status_pd)
        print(f'#### ENDE Status Runde {self.round} ###')

    def return_rounds(self):
        '''Rundensteuerung'''
        while True:
            self.round += 1
            print(f'### Round {self.round} ###')
            for phil in self.phil_list:
                if phil.status == "D":
                    if phil.status_round_count > self.rounds_to_death:
                        self.set_status(phil.number, 'T')
                        print(f'{phil.name} hat zu lange gedacht und ist dabei verhungert!!!')
                        break
                    if random.randint(0, 1) == 1:
                        self.set_status(phil.number, 'H')
                        print(f'{phil.name} bekommt jetzt Hunger.')
                    else:
                        print(f'{phil.name} denkt bis nächste Runde weiter.')
                if phil.status == "E":
                    if phil.status_round_count >= self.rounds_to_eat:
                        self.return_fork(phil.number)
                        self.return_fork(phil.right_neighbour)
                        self.set_status(phil.number, 'D')
                        print(f'{phil.name} ist mit Essen fertig!.')
                        print(f'{phil.name} legt seine linke Gabel wieder auf den Tisch.')
                        print(f'{phil.name} gibt die rechte Gabel an seinen rechten Nachbarn {self.phil_list[phil.right_neighbour].name} zurück.')
                        print(f'{phil.name} fängt das Denken wieder an.')
                    else:
                        print(f'{phil.name} isst noch eine Runde.')
                if phil.status == "H":
                    # linke Gabel
                    if self.take_own_fork_from_left(phil.number):
                        print(f'{phil.name} nimmt seine linke Gabel in die Hand.')
                    elif phil.fork == 'H':
                        print(f'{phil.name} hat hunger und seine linke Gabel in der Hand.')
                    else:
                        print(f'{phil.name} hat hunger, aber seine linke Gabel verliehen.')
                    # rechte Gabel
                    if self.take_fork_from_right(phil.right_neighbour):
                        print(f'{phil.name} ergattert die Gabel von seinem rechten Nachbarn {self.phil_list[phil.right_neighbour].name}.')
                    else:
                        print(f'{phil.name} hat hunger, aber sein rechter Nachbar {self.phil_list[phil.right_neighbour].name} braucht seine Gabel selbst.')
                    # Essen?
                    if (phil.fork == 'H') and (self.phil_list[phil.right_neighbour].fork == 'V'):
                        self.set_status(phil.number, 'E')
                        print(f'{phil.name} fängt das Essen an.')
                    else:
                        print(f'{phil.name} hungert seit {phil.status_round_count} Runden.')
                        if phil.status_round_count > self.rounds_to_death:
                            self.set_status(phil.number, 'T')
                            print(f'{phil.name} ist verhungert!!!')
                            break
            # nächste Runde vorbereiten
            self.count_up_status_round_count()
            self.table_status()
            # input('Return for next Round')
        print(f'Das Spiel endete nach {self.round} Runden!')
        return self.round


if __name__ == "__main__":
    PhilTable(2, 10, 10)

# Example:
# Ergebnisse: [1851, 666, 1614, 1298, 254, 2047, 796, 1102, 5056, 59]
# Durchschnitt: 1474.3