Karten sortieren in Python

Inhalt

5.2. Karten sortieren in Python#

Wir gehen nicht davon aus, dass Sie bereits jetzt alles verstehen was wir im Folgenden programmieren werden. Ziel ist es aufzuzeigen, dass sich der Programmiercode kaum von unserer vorheriger Beschreibung unterscheidet und wir durch Programmiersprachen einen präzisen und vorgefertigten Kontext geschenkt bekommen. Wir müssen diesen lediglich kennenlernen! Was sich also ändert ist der Kontext. Dieser ist in unserem Fall durch die Programmiersprache Python (ihrer Syntax und Semantik) und der verwendeten Python-Module vorgegeben.

Exercise 5.2 (Karten sortieren in Python)

Implementieren Sie Ihren Algorithmus in Python.

Im folgenden präsentieren wir eine Lösung. Beachten Sie, dass es uns dabei nicht um die Laufzeit unseres Programms geht. Die Lösung ist weder effizient noch besonders elegant und das ist für den Anfang auch in Ordnung.

5.2.1. Modellierung der Karten und Hand#

Da unser Kontext natürlich keine physikalische Hand definiert, müssen wir diese anderweitig modellieren. Hierbei kommt die Abstraktion ins Spiel.

Exercise 5.3 (Modellierung)

Welche Eigenschaften der Hand benötigen wir und welche sind überflüssig?

Die ausschlaggebenden Eigenschaften der Karten auf der Hand sind:

Jede der \(n\) Karten hat einen von \(n\) nummerierten Plätzen auf der Hand (Reihenfolge)
Karten können von der Hand gelöscht und hinzugefügt werden
Es gibt eine (totale) Ordnungsrelation der Karten

Wir modellieren jede Karte als Zeichenkette. Zum Beispiel steht 'Bube' für einen der Buben des Kartendecks. Je nachdem welches Kartendeck Sie verwenden, können Sie die Namen entsprechend anpassen. Wir lassen alle unnötigen Informationen weg (Abstraktion). Darunter fällt beispielweise die Kartenfarbe.

Eine Hand modellieren wir als Liste von Karten (Liste von Zeichenketten).

Liste (Python)

Eine Python Liste repräsentiert ein endliches veränderbares mathematisches Tupel. Elemente können an jeder Position aus der Liste entfernt und eingefügt werden. Die Position eines Elements in der Liste nennen wir Index.

Sei lst eine Liste und n die Anzahl ihrer Elemente, so sind

lst[0], lst[1], ..., lst[n-1]

ihre Elemente.

Folgende Liste ist ein Beispiel für eine Hand mit 6 Karten.

hand = ['9', '6', '6', 'Bube', 'Ass', '7']
hand

['9', '6', '6', 'Bube', 'Ass', '7']

Der Befehl

del hand[3]
hand

['9', '6', '6', 'Ass', '7']

löscht das vierte Element (das Element mit Index 3) aus der Liste. Um das Element wieder einzufügen können wir

hand.insert(3, 'Bube')
hand

['9', '6', '6', 'Bube', 'Ass', '7']

verwenden.

5.2.2. Modellierung der Ordungsrelation#

Für die Modellierung der Ordnung gibt es ebenfalls viele verschiedene Möglichkeiten. Eine Lösung besteht darin den Index eines weiteren Tupels als Ordnung zu verwenden. Das Tupel muss lediglich alle möglichen Kartentypen geordnet enthalten. Wir verwenden diesmal keine list sondern ein unveränderbares Python tuple.

Tupel (Python)

Ein Python Tupel repräsentiert ein endliches unveränderbares mathematisches Tupel. Die Position eines Elements im Tupel nennen wir Index.

Sei tpl ein Tupel und n die Anzahl seiner Elemente, so sind

tpl[0], tpl[1], ..., tpl[n-1]

seine Elemente.

cards = ('6', '7', '8', '9', '10', 'Bube', 'Dame', 'König', 'Ass')

Um die konkrete Implementierung von cards an einer zentralen Stelle ändern zu können, ist es sinnvoll eine Python-Funktion zu schreiben, welche cards zurückgibt. Sie brauchen noch ein wenig Erfahrung um den Unterschied und die Vorzüge zu verstehen.

def get_cards():
    return cards

Um die Ordnung einer Karte card zu bestimmen, iterieren wir durch alle cards und sobald wir die entsprechende Karte gefunden haben, geben wir den Index zurück.

def index_of(card):
    for index in range(len(get_cards())):
        if cards[index] == card:
            return index

index_of('Bube')

Um zwei Karten vergleichen zu können, vergleichen wir ihre Indices.

index_of('7') < index_of('König')

True

Wir packen den Vergleich zweier Karten card1 und card2 in eine weitere Python-Funktion.

def is_smaller(card1, card2):
    i = index_of(card1)    # finde Position von Karte 1
    j = index_of(card2)    # finde Position von Karte 2
    return i < j           # Falls Position von Karte 1 < Position von Karte 2 gib wahr zurück, sonst falsch

Die Funktion is_smaller(card1, card2) gibt genau dann True (wahr) zurück, wenn die Karte card1 kleiner ist als die Karte card2. Wir haben somit unseren Kontext erweitert.

5.2.3. Sortieralgorithmus#

Blicken wir zurück auf unseren Sortieralgorithmus.

H <- unsere Hand mit Karten
S <- ein leerer Stapel
Solange noch Karten auf der Hand H sind:
    Lege kleinste Karte auf der Hand H auf Stapel S 

In Python sieht das ganz wie folgt aus.

def stack_sort(hand):                               # Sei H unsere Hand mit Karten (Argument der Funktion)
    stack = [];                                     # Sei S ein leerer Stapel
    while len(hand) > 0:                            # Solange noch Karten auf der Hand H sind:
        stack.append(remove_smallest_card(hand))    # Lege kleinste Karte auf der Hand H auf Stapel S 
    return stack                                    # Gib den Stapel zurück (Rückgabewert)

Wir haben die Logik in eine Funktion gepackt, sodass wir diese bequem Aufrufen können. Wir haben unseren Kontext um diese Funktion erweitert. Leider ist die Funktion remove_smallest_card in unserem Kontext noch nicht definiert. Das holen wir nach.

def remove_smallest_card(hand):    # Sei H unsere Hand mit Karten (Argument der Funktion)
    i = find_smallest_index(hand)  # Finde Position der kleinsten Karte auf der Hand
    card = hand[i]                 # Merke dir Karte an der Position der kleinsten Karte auf der Hand
    del hand[i]                    # Lösche Karte an der Position der kleinsten Karte auf der Hand
    return card                    # Gib gemerkte Karte zurück (Rückgabewert)

Wir haben das Problem remove_smallest_card in Unterprobleme aufgeteilt (Dekomposition). Die Funktion find_smallest_index soll uns den Index der kleinsten Karte auf der Hand zurückgeben.

def find_smallest_index(hand):
    index = 0                                # Merke dir Position 0
    for i in range(len(hand)):               # Gehe durch alle Positionen 0 bis (Anzahl der Karten auf der Hand) - 1
        if is_smaller(hand[i], hand[index]): # Falls Karte an Position i kleiner ist als an der gemerkten Position
            index = i                        # Merke dir Position i
    return index                             # Gib gemerkte Position zurück  

Jetzt ist alles in unserem Kontext definiert was notwendig ist und wir können den Sortieralgorithmus stack_sort ausführen. Lassen Sie uns die Hand hand sortieren:

stack_sort(hand)

['6', '6', '7', '9', 'Bube', 'Ass']

Was passiert wenn wir richtig viele Karten sortieren? Der folgende Code erzeugt eine durchgemischte Hand mit 1000 Karten. Wir erweitern dafür den Kontext um ein Paket random welches Funktionen für die Wahrscheinlichkeitsrechnung enthält.

import random
hand = [random.choice(get_cards()) for _ in range(1000)]
hand

['Ass',
 'Dame',
 'Bube',
 '7',
 '7',
 '10',
 '7',
 '10',
 'Ass',
 'Bube',
 '6',
 'Bube',
 '10',
 'Dame',
 '10',
 'Bube',
 'Ass',
 '6',
 '6',
 '7',
 'König',
 '9',
 'Dame',
 '10',
 '10',
 '7',
 'Dame',
 '6',
 '8',
 'König',
 'Ass',
 '10',
 'Bube',
 '10',
 '6',
 'König',
 '9',
 '7',
 'Bube',
 '6',
 'Dame',
 'Dame',
 '8',
 'Bube',
 'Dame',
 '10',
 '8',
 '9',
 '6',
 '8',
 '7',
 '10',
 'König',
 '8',
 '9',
 '10',
 '7',
 'Ass',
 '6',
 '9',
 'Dame',
 '9',
 'Bube',
 'König',
 '10',
 'Bube',
 'König',
 '10',
 '6',
 'König',
 'König',
 '7',
 '10',
 '9',
 'Bube',
 '7',
 'Ass',
 'König',
 'Ass',
 '8',
 'König',
 'Bube',
 'Bube',
 'König',
 'Bube',
 '7',
 '9',
 'Ass',
 'Ass',
 '7',
 'Dame',
 'Bube',
 'Dame',
 '8',
 'Ass',
 '6',
 'Ass',
 'Dame',
 '7',
 '6',
 'Bube',
 'Bube',
 'Ass',
 '8',
 '9',
 '9',
 '6',
 '8',
 '7',
 '8',
 'Dame',
 '7',
 '10',
 'Dame',
 'Dame',
 'Bube',
 '9',
 '10',
 '6',
 '6',
 '9',
 '10',
 '9',
 '6',
 'Dame',
 '9',
 '10',
 '9',
 '7',
 '9',
 '6',
 '8',
 'Dame',
 'Dame',
 'Bube',
 'Ass',
 'König',
 '8',
 '9',
 '10',
 '10',
 'König',
 'König',
 '6',
 '9',
 '9',
 'König',
 '9',
 'Bube',
 '7',
 'König',
 '8',
 '10',
 'Bube',
 '8',
 'Ass',
 'Bube',
 'Dame',
 '7',
 '7',
 'Bube',
 '7',
 '6',
 'Bube',
 '10',
 'Ass',
 '6',
 '7',
 '10',
 'König',
 '8',
 '8',
 'Dame',
 '9',
 'Bube',
 '8',
 'Bube',
 'Dame',
 'Ass',
 'Ass',
 'Ass',
 '9',
 '8',
 '6',
 'Dame',
 'König',
 'König',
 'König',
 'Ass',
 '10',
 'Bube',
 'Ass',
 '10',
 '6',
 'Bube',
 'Bube',
 '9',
 '7',
 '9',
 '8',
 '9',
 '10',
 '8',
 'Ass',
 '8',
 '7',
 'Dame',
 '10',
 '7',
 '9',
 'König',
 'Dame',
 '7',
 'König',
 '7',
 '6',
 '9',
 'Ass',
 'Dame',
 'Dame',
 '8',
 '8',
 '7',
 '6',
 'Dame',
 'König',
 'Bube',
 '8',
 '8',
 'Dame',
 'Bube',
 'König',
 '7',
 '6',
 'König',
 '9',
 '10',
 '7',
 '7',
 'Bube',
 '7',
 '9',
 'König',
 '9',
 '10',
 '9',
 '8',
 'Ass',
 '7',
 'Bube',
 'Dame',
 'König',
 '9',
 'Dame',
 '9',
 '8',
 '8',
 '6',
 'Bube',
 'König',
 '9',
 '7',
 '6',
 '10',
 'König',
 'Bube',
 'Bube',
 '10',
 '9',
 '10',
 '9',
 '9',
 'Bube',
 '8',
 'Bube',
 'König',
 'Dame',
 'König',
 'Ass',
 '6',
 'König',
 'Ass',
 'Ass',
 'Dame',
 '8',
 '8',
 '8',
 '10',
 '8',
 'Ass',
 'König',
 'Ass',
 'Ass',
 '7',
 'König',
 'Dame',
 '9',
 '8',
 'Dame',
 '9',
 'Bube',
 'Ass',
 'Ass',
 '7',
 '7',
 '7',
 'König',
 'Bube',
 'Bube',
 '7',
 '6',
 '10',
 'Ass',
 'Ass',
 '8',
 'Dame',
 'Dame',
 '7',
 'Ass',
 'Bube',
 '8',
 'König',
 '8',
 'König',
 '10',
 '8',
 'König',
 'Ass',
 'Ass',
 '6',
 '9',
 '8',
 '7',
 'König',
 '6',
 'Dame',
 'Bube',
 '8',
 'Bube',
 '9',
 'Bube',
 '7',
 '6',
 '7',
 '10',
 '10',
 '6',
 'Dame',
 'Dame',
 'Dame',
 '10',
 'Dame',
 'Dame',
 '7',
 'Ass',
 'König',
 '9',
 '7',
 'Ass',
 'Ass',
 '9',
 'Dame',
 '8',
 'Dame',
 'König',
 'Dame',
 '6',
 'König',
 '7',
 '10',
 'König',
 '9',
 '7',
 'Ass',
 '6',
 '8',
 'Dame',
 'Bube',
 '10',
 'Dame',
 '8',
 '7',
 '7',
 'König',
 '9',
 '10',
 '7',
 '9',
 'Dame',
 'Ass',
 '8',
 '6',
 'Ass',
 '9',
 'König',
 '7',
 '10',
 'König',
 '6',
 'König',
 'Ass',
 '7',
 '9',
 '7',
 '8',
 '6',
 'Dame',
 '9',
 '8',
 '6',
 '8',
 '10',
 '10',
 'Bube',
 'Ass',
 'Dame',
 'Ass',
 '8',
 'Dame',
 '9',
 'Ass',
 '8',
 'König',
 'Ass',
 'König',
 '9',
 'Ass',
 'Ass',
 '10',
 'Dame',
 'König',
 '7',
 'Ass',
 'Bube',
 '7',
 '7',
 '7',
 'Ass',
 'Dame',
 'Dame',
 'Dame',
 '10',
 '9',
 '9',
 'König',
 '10',
 'König',
 '7',
 '10',
 'König',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 '8',
 'König',
 'Ass',
 '9',
 'Ass',
 'Dame',
 '7',
 '9',
 '9',
 '6',
 'Bube',
 '6',
 '6',
 'Ass',
 '8',
 '6',
 '9',
 '7',
 'König',
 '7',
 '8',
 '7',
 'Dame',
 '8',
 'Ass',
 'König',
 '10',
 '9',
 'Bube',
 '6',
 'König',
 '9',
 '7',
 'Dame',
 'Ass',
 '10',
 '7',
 'Dame',
 '7',
 'König',
 'Bube',
 'König',
 'Bube',
 'Bube',
 '9',
 '7',
 'Dame',
 '7',
 '9',
 '6',
 'Bube',
 'Ass',
 'Bube',
 'König',
 '6',
 'Bube',
 'Ass',
 '9',
 'König',
 '9',
 '8',
 '7',
 '9',
 '9',
 'Bube',
 'König',
 '9',
 'Bube',
 '10',
 'Bube',
 '8',
 '10',
 'König',
 'Bube',
 '6',
 'Dame',
 '7',
 '10',
 '6',
 '9',
 'Dame',
 '7',
 'König',
 'Dame',
 'Bube',
 'Dame',
 '10',
 'Bube',
 '7',
 'Ass',
 'Ass',
 '8',
 '6',
 '9',
 '6',
 'Bube',
 '9',
 '7',
 '9',
 'Bube',
 '6',
 'Ass',
 'König',
 '6',
 '8',
 '7',
 '7',
 'König',
 'Dame',
 'Ass',
 '10',
 'Bube',
 '10',
 '9',
 '8',
 '6',
 'Bube',
 'Ass',
 '7',
 'König',
 'Bube',
 'König',
 'Bube',
 'Ass',
 '7',
 '9',
 '7',
 'Dame',
 '7',
 '8',
 'Dame',
 'König',
 'Dame',
 'Dame',
 '6',
 '6',
 '6',
 'Ass',
 'Ass',
 'Bube',
 'Ass',
 '6',
 '8',
 'König',
 'Ass',
 '8',
 '10',
 '8',
 '7',
 '10',
 '9',
 '9',
 'Dame',
 '6',
 'Dame',
 '7',
 '6',
 '8',
 '7',
 '7',
 '8',
 '10',
 '9',
 '6',
 '9',
 'Dame',
 '8',
 'König',
 'Ass',
 'König',
 '7',
 '9',
 '8',
 'Ass',
 '10',
 '8',
 '9',
 'König',
 'Dame',
 '6',
 'König',
 '6',
 'Ass',
 'Dame',
 'König',
 'Ass',
 '10',
 '7',
 'Bube',
 '8',
 'Bube',
 '10',
 '8',
 'Ass',
 '6',
 'Bube',
 'Ass',
 '9',
 '7',
 'König',
 'Dame',
 'König',
 '7',
 'König',
 '6',
 '8',
 '6',
 '10',
 'Ass',
 '6',
 'Bube',
 '7',
 '9',
 '9',
 '9',
 'Dame',
 'Dame',
 '10',
 '8',
 'Ass',
 'Dame',
 '9',
 'König',
 '6',
 'Dame',
 '6',
 'Dame',
 '10',
 '6',
 'König',
 'König',
 '8',
 '9',
 '10',
 'König',
 'Dame',
 'Dame',
 '6',
 '6',
 '9',
 'Bube',
 'Bube',
 'Bube',
 '10',
 '10',
 'Dame',
 '9',
 '6',
 '6',
 'Dame',
 '9',
 '7',
 '6',
 '10',
 '9',
 'Bube',
 'Bube',
 'König',
 'König',
 '9',
 '7',
 '10',
 'Bube',
 'Ass',
 '7',
 'Ass',
 'Bube',
 'König',
 '8',
 'Ass',
 '6',
 'Dame',
 'Bube',
 '10',
 '10',
 '6',
 'Ass',
 '8',
 '7',
 '6',
 '10',
 '9',
 'Dame',
 '7',
 'Dame',
 '6',
 '8',
 '7',
 'Dame',
 'Dame',
 'Dame',
 'Ass',
 '8',
 'Ass',
 'Dame',
 '6',
 'König',
 'König',
 '9',
 'Dame',
 '9',
 'König',
 '7',
 'Ass',
 '7',
 'König',
 'König',
 '6',
 '7',
 '6',
 'Ass',
 'Ass',
 '8',
 'König',
 '6',
 'Ass',
 '8',
 '9',
 '8',
 '9',
 'König',
 '10',
 'Dame',
 '6',
 'König',
 'Dame',
 'Ass',
 '8',
 '9',
 '8',
 'Dame',
 'Ass',
 'Ass',
 'König',
 'Dame',
 'Bube',
 'König',
 '7',
 'Ass',
 '10',
 'König',
 'Ass',
 'Dame',
 'König',
 'Dame',
 '8',
 '7',
 'König',
 '6',
 'Bube',
 'Dame',
 'Ass',
 '8',
 '8',
 'Ass',
 'Ass',
 'Ass',
 'Dame',
 '6',
 'Ass',
 '9',
 '6',
 '10',
 'Ass',
 '7',
 '7',
 'Dame',
 '10',
 'Dame',
 'Dame',
 '10',
 'Dame',
 '9',
 '9',
 'Bube',
 '8',
 'Bube',
 '10',
 'König',
 '10',
 'Ass',
 'Bube',
 '9',
 '10',
 '9',
 '9',
 '8',
 'König',
 'Dame',
 'König',
 '10',
 'Bube',
 '7',
 'Bube',
 '7',
 'König',
 '8',
 '10',
 'König',
 'Ass',
 '10',
 'König',
 'Bube',
 '7',
 '6',
 'Ass',
 '7',
 '9',
 'Dame',
 '9',
 'Dame',
 '6',
 '7',
 '7',
 '9',
 '9',
 'Bube',
 '8',
 '7',
 '8',
 '9',
 'Bube',
 '9',
 'Bube',
 'Bube',
 '7',
 'König',
 'König',
 'Bube',
 '9',
 'Ass',
 'Dame',
 '6',
 '7',
 'Dame',
 '9',
 '9',
 '8',
 'König',
 '8',
 '7',
 '9',
 '7',
 '10',
 '8',
 'Bube',
 '9',
 '10',
 'Ass',
 'Dame',
 '8',
 'König',
 '6',
 'Dame',
 'Bube',
 '7',
 'Bube',
 '6',
 'Dame',
 '7',
 '6',
 '10',
 '9',
 '10',
 'Ass',
 '8',
 '6',
 'Bube',
 '6',
 '10',
 '8',
 '8',
 'Dame',
 '6',
 '9',
 'Bube',
 'Dame',
 'König',
 '9',
 '7',
 '10',
 '7',
 'Bube',
 'Bube',
 'König',
 '7',
 'Bube',
 'Ass',
 'Dame',
 '6',
 'Bube',
 '8',
 '9',
 'Bube',
 'Dame',
 'Dame',
 'Bube',
 '6',
 '9',
 '10',
 '10',
 '8',
 'Ass',
 '8',
 '10',
 '6',
 '6',
 '10',
 'Bube',
 '10',
 '10',
 'Ass',
 'König',
 '10',
 'Ass',
 '6',
 '7',
 '7',
 'Ass',
 'Ass',
 '10',
 'König',
 '7',
 'Dame',
 '10',
 '8',
 'König',
 'Bube',
 '9',
 '9',
 '10',
 'Dame',
 'König',
 '9',
 '7',
 'Ass',
 '9',
 'Bube',
 '10',
 '7',
 'Ass',
 '8',
 '8',
 'Ass',
 'Ass',
 '7']

Sie werden merken, dass die Ausführung des folgenden Codes einen kurzen Moment dauert.

stack_sort(hand)

['6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '6',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '7',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '8',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '9',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 '10',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Bube',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'Dame',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'König',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass',
 'Ass']