Algorithmen I: Einfache Algorithmen und Struktogramme

Lernziele

Slides Algorithmen I

• 2er Gruppen
• Jede Person nimmt Blatt Papier (ja Papier, nicht Laptop!!!)
• Notiere für blinde Partnerin Algorithmus, der sie von aktueller Position (am Pult sitzend) zum Wasserhahn des Zimmers bringt und dort trinken lässt.
• Notiere den Algorithmus in Python-Pseudocode. Verwende als Elemente wie:
  while ...:, while not ...:, if ...:, if ... else: if ... elif ... else: my_variable = ...
  
  
• Regeln:
  • Person ist blind, sieht also nichts.
  • Person kann sich nur schrittweise nach vorne, hinten, links oder rechts bewegen. Zulässig ist z.B.: „Mache einen Schritt nach vorne.“ oder „Mache einen Schritt nach rechts.“
  • Algorithmus soll auch für andere (z.B. sehr grosse oder kleine) Person gehen. „Mache 7 Schritte nach vorne“ funktioniert also nicht, da 7 Schritte für unterschiedliche Personen unterschiedliche Distanzen sind.
  • Person hat kein Gefühl für Distanzen. „Laufe $2$m nach vorne“ ist also unzulässig.
  • Person kann sich drehen, z.B. „Drehe dich um 90 Grad nach rechts“.
  • Einzige Sensoren, die Person hat sind nach vorne gerichtete Hände. Mit diesen können Hindernisse (Wände und Tische) detektiert werden.
  • Die Wege sollen frei von Rucksäcken usw. sein. Andere Personen werden ignoriert.
    
    
• Ausführen:
  • Nimm Algorithmus von Kollegin …
  • … und halte direkt vor Augen, s.d. du lesen aber sonst möglichst wenig sehen kannst.
  • Befolge nun Algorithmus * ganz genau* so, wie er da steht. Interpretiere oder korrigiere nichts!
  • Führt dich der Algorithmus zum Ziel?
    
    
• Zusatzaufgabe: Der Algorithmus soll von jedem beliebigen Sitzplatz im Schulzimmer funktionieren. Passe deinen Algorithmus entsprechend an.
  
  

• Regeln:
  • $21$ Bleistifte
  • Zwei Spieler:innen nehmen abwechselnd je 1-3 Stifte weg.
  • Wer die letzten Stifte nehmen kann, hat gewonnen.
• Warum ist das Spiel interessant?
  • Es gibt eine optimale Spielstrategie, …
  • welche dem Computer als Algorithmus beigebracht werden kann.
• Auftrag & Ziel:
  • Gegeneinander spielen (verwendet eure Stifte)
  • Optimale Spielstrategie finden …
  • … und als Algorithmus in menschlicher Sprache formulieren
• Online-Spiel: https://upload.wikimedia.org/wikipedia/commons/4/4d/Subtraction_game_SMIL.svg

  

Notiere den Algorithmus für das Subtraction Game nun in Python-Pseudocode. Schreibe den Code für einen „Computer“, der gegen einen menschlichen „Spieler“ spielen soll. Natürlich soll das Ziel sein, dass der Computer wenn immer möglich gewinnt.

Mögliche Befehle z.B.:

• Anweisung für Computer: „Nimm 3 Stifte.“
• Aufforderung an Spieler, Stifte zu nehmen: „x = Spieler nimmt Stifte“.
• Statement: „Spieler hat 2 Stifte genommen.“

Versionen:

• Version 1: Der Computer beginnt. Natürlich muss der Computer immer gewinnen.
  
  
• Version 2: Der Spieler beginnt. Der Computer gewinnt, sobald der Spieler einen Fehler macht.

Implementiere nun eine 2-Player Version des Subtraction Games in Python. Die Idee ist also, dass zwei Personen an einem Computer gegeneinander das Subtraction Game spielen können. Es geht also nicht darum, dem Computer die optimale Strategie beizubringen. Der Code muss schlussendlich nur erkennen, wenn das Spiel zu Ende ist und dann den Gewinner („Spieler 1“ oder „Spieler 2“) ausrufen. Man kann davon ausgehen, dass die Spieler immer korrekte Eingaben machen, also Zahlen von 1 bis 3.

Gib den Spielern immer nützliche Rückmeldungen, z.B.

• „Es verbleiben … Stifte“
• „Spieler 2 ist am Zug“.
• „Spieler 1 hat gewonnen!“

Tipp: Programmiere eine 'Endlosschleife' und breche dann mit break aus dieser aus, sobald jemand gewonnen hat.

Zusatzoptionen:

1. In der while-Schleife hat es jetzt wahrscheinlich 2x quasi identischen Code: Einmal für Spieler 1 und einmal für Spieler 2. Schreibe den Code kürzer, so dass der Code darin etwa halbiert wird.
2. Stelle sicher, dass die Spieler nur zulässige Eingaben ($1-3$) machen. Wenn ein Spieler eine unzulässige Eingabe macht (z.B. $4$), so hat er sofort verloren.
3. Wie die letzte Option, diesmal soll der Spieler aber (beliebig oft) eine weiter Chance erhalten. Der Spieler wird also darauf hingewiesen, dass er eine unzulässige Eingabe gemacht hat und soll aufgefordert werden, eine neue Eingabe zu tätigen.
4. Füge eine Art GUI, also ein Graphische Oberfläche, hinzu. Zeichne z.B. mit der Turtle die Stifte.
5. Implementiere eine Zeitlimite pro Zug von z.B. $3$ Sekunden. Hat ein Spieler länger, so hat er sofort verloren. Verwende dazu das Time-Modul:

   import time
    
   t_anfang = time.time() # Zeit in ms, speichere in t_anfang
    
   # irgendwelchen Code
    
   t_end = time.time() # Zeit in ms ein bisschen später
   t_vergangen = t_end - t_anfang # bestimme, wie viel Zeit zwischen den beiden Messungen vergangen
   print(t_vergangen)

6. Spielmodus modifizieren: Bisher haben wir das Subtraction Game immer mit 21 Stiften und Zügen von bis zu 3 Stiften gespielt. Man könnte aber z.B. auch be 28 Starten und 1-4 Stifte ziehen. Diese Startbedingungen (Anzahl Stifte zum Start und max. Anzahl Stifte pro Zug) könnte man in einer gewissen Range zufällig wählen. Verwende dazu das random-Modul. Lasse es dir von ChatGPT erklären.

Implementiere verschiedene Versionen des Subtraction Games nun in Python. Gib dem Spieler immer nützliche Rückmeldungen, z.B. „Es verbleiben … Stifte“ oder „Spieler, nimm 1-3 Stifte“.

Versionen:

• Version 1: Der Computer beginnt. Natürlich muss der Computer immer gewinnen.
  
  
• Version 2: Der Spieler beginnt. Der Computer gewinnt, sobald der Spieler einen Fehler macht.
  
  

Code die ultimative Version des Subtraction Game mit Python:

• Der Spieler soll am Anfang entscheiden können, ob er gegen Mensch oder Computer spielen will. Dazu soll er z.B. M (für Mensch) oder C für Computer eingeben. Quasi Kombination der letzten beiden Aufgaben.
• Der Code soll auch mit falschen Eingaben umgehen können: Wir eine unzulässige Eingabe gemacht, wird Spieler aufgefordert, es erneut zu versuchen
• Implementiere weitere optionale Features, die du der Aufgabenstellung von Subtraction Game 3.0.
• Sei kreativ, bringe eigene Ideen ein!

Skunky ist ein Stinktier, welches gerne Schätze sucht (und noch lieber findet)! Programmiere dein Skunky also so, dass es zum Schatz findet. Sammle dabei Münzen und meide das Feuer, denn sonst ist aus die Maus (resp. aus das Stinktier).

1. Tutorial Um den Skunky-Code ausführen zu können, muss man installiert und eingerichtet haben.
   1. richtiges Python 3
   2. Visual Studio Code mit den nötigen Extensions
   3. PyGame (mit pip installieren)
2. Skunky-Code mit Bildern:
   1. Erstelle auf deinem Computer einen Ordner für deinen Skunky Code.
   2. Lade das folgende Zip-File herunter, welches vordefinierten Code und einige Bilder beinhaltet: skunky.zip
   3. Extrahiere das Zip-File …
   4. und ziehe es in den vorbereiteten Ordner.
   5. Öffne nun deinen Ordner mit VSCode und beginne darin zu arbeiten.

Zu Beginn (erste Zeile des Codes) muss sämtlicher Skunky-Code importiert werden:

from skunky import *

Diese Zeile kommt pro Code nur genau einmal vor - und zwar in der allerersten Zeile des Codes.

Als nächstes muss Skunky erstellt werden. Dies geht genau gleich wie bei der Turtle:

fritz = Skunky()

Im Gegensatz zur Turtle kann man aber hier noch Einstellungen vornehmen. Diese werden in die runden Klammern geschrieben:

fritz = Skunky(delay_time=700,cell_size=70,world_map=1)

Diese Angaben bedeuten das Folgende:

• delay_time=700: Zeit in ms zwischen zwei Frames. Je höher, desto langsamer.
• cell_size=70: Breite/Höhe einer Zelle in Pixel (px)
• world_map=1: Auswahl Labyrinth. Kann vorgefertigte verwenden oder eigene designen.
• Gibt noch weitere.

Im Free Walk Mode kann man Skunky mit den Pfeiltasten steuern. Das Ziel ist natürlich, den Schatz zu finden.

fritz = Skunky(delay_time=700,cell_size=70,world_map=1)
fritz.free_walk_mode()

Der folgende Code erzeugt ein einfaches 5×5 Labyrinth:

my_labyrinth = [
    "ttttt",
    "tgfpt",
    "t f t",
    "tc  t",
    "ttttt",
]
 
skunky = Skunky(world_map=my_labyrinth)

Um ein Level zu designen, erstellen wir also eine Liste (werden wir später genau besprechen) mit Strings. Verschiedene Buchstaben erzeugen verschiedene Elemente: * "p": Player, muss genau einen haben * "t": Baum (tree), harmloses Hindernis * "f": Feuer, gefährliches Hindernis (→ GameOver bei Kollision) * "c": Münze (coin), kann aufgesammelt werden * "g": Schatztruhe, das Ziel (goal) des Spiels

Spannender wird es aber, wenn man den Skunky einprogrammiert, wie es sich bewegen soll. Dazu gibt es eine Reihe von Befehlen:

# Importiere zuerst (erste Zeile des Codes) den benötigten Skunky-Code. Ohne diese geht gar nichts.
from skunky import *
 
# Ein Skunky erzeugen, gib ihm einen selbstgewählten Namen
fritz = Skunky(delay_time=700,cell_size=70,world_map=1)
 
# Skunky bewegen
fritz.move() # macht einen Schritt vorwärts
fritz.left() # dreht sich um 90 Grad nach links
fritz.right() # dreht sich um 90 Grad nach rechts
 
# Situation überprüfen, benötigt in Verzweigungen (if...) und Schleifen (while):
fritz.is_in_front_of_obstacle() # True oder False, je nachdem, ob vor Hindernis (Baum oder Feuer) steht
fritz.is_left_of_obstacle() # True oder False, je nachdem, ob links neben Hindernis steht
fritz.is_right_of_obstacle() # True oder False, je nachdem, ob rechts neben Hindernis steht
 
# Weiteres
fritz.show_indefinitely() # Kann als letzte Zeile verwendet werden. Game bricht nicht ab wenn GameOver oder GameWin

Finde im Free Walk Mode (siehe Theorie oben), also mithilfe der Pfeiltasten, aus den ersten beiden Labyrinthen (world_map=0 und world_map=1).

1. Designe ein eigenes, möglichst gutes Labyrinth (siehe Theorie oben) und finde aus diesem im Free Walk Mode heraus.
2. Tausche es dann mit deinen Kolleginnen.
3. Schicke dann sowohl einen Screenshot als auch den Code deines Labyrinths (also die Liste mit den Strings, nicht ein Screenshot davon) per Teams an die LP. Die besten Labyrinths werden dann in den Code aufgenommen.

Löse nun die das erste Labyrinth mit Code (world_map=0), also nicht im Free-Walk-Mode. Starte dafür mit dem unten abgedruckten Code (lies oben nach, was genau die einzelnen Befehle machen). Verwende nun ausschliesslich die folgenden Funktionen: move(), left() und right(), um den Skunky zum Schatz zu bringen.

from skunky import *
 
fritz = Skunky(delay_time=700,cell_size=30,world_map=0)
 
fritz.right()
fritz.move()
 
fritz.show_indefinitely()

Mache eine Kopie von deinem Code für B3 und verbessere diesen (falls nötig). Man sollte nie zwei oder mehr identische Befehle (move,left,right). Stattdessen soll man mit einer while-Schleife den gleichen Befehl wiederholen.

Wie B4 (Skunky mit move, left & right zum Ziel bringen), allerdings für eines der beiden nächsten Labyrinthe: world_map=1 (mittelgross) und world_map=2 (gross).

Wir nennen zwei Labyrinthe äquivalent, wenn sie mit der gleichen Art Weg gelöst werden können. Dabei können sich die Anzahl Schritte, die auf den einzelnen Abschnitten gelaufen werden müssen aber unterscheiden. Zum Beispiel sind die folgenden beiden Labyrinthe äquivalent:

Die Codes dafür sind:

lab1 = [
    "tttttttttt",
    "g    ttttt",
    "tttf ttttt",
    "t    t p t",
    "t    t   t",
    "t  ftt   t",
    "f    f   t",
    "f        t",
    "tttttttttt",
]
 
lab2 = [
    "tttttttttttt",
    "g     tttttt",
    "t     tttttt",
    "ttt   tt p t",
    "t     tt   t",
    "t  ftttt   t",
    "f    ttf   t",
    "f    ttf   t",
    "f    fff   t",
    "f          t",
    "tttttttttttt"
]

Schreibe nun einen Code, der Skunky zum Ziel bringt und für alle äquivalenten Labyrinthe funktioniert. Verwende dazu weiter die Funktionen is_in_front_of_obstacle(), is_left_of_obstacle(), is_right_of_obstacle() (siehe Theorie oben).

Schreibe von Hand einen Code, der den Skunky zum Ziel bringt. Der gleiche Code soll für die beiden Labyrinthe unten sowie alle äquivalenten funktionieren. Programmiere den Code dann am Schluss am Computer.

Verwende dazu die folgenden Funktionen. Auf Papier dürfen auch die folgenden Abkürzungen verwendet werden:

lab_1 = [
    "tttttttttttttt",
    "tttt       p t",
    "tttt ttttttfft",
    "tttt t ttttttt",
    "tf   t      gt",
    "tttt ffff tfft",
    "tttt ffff t  t",
    "tttt ffff tt t",
    "tttt      t  t",
    "tttttttttttttt",
]
 
lab_2 = [
    "tttttttttttttttttt",
    "tttttt         p t",
    "tttttt ttttttttfft",
    "tttttt tttfff ttft",
    "tttttt tttfff   gt",
    "f      tttttt tfft",
    "tttttt ffffff t ft",
    "tttttt ffffff t ft",
    "tttttt ffffff t ft",
    "tttttt ffffff t  t",
    "tttttt ffffff tt t",
    "tttttt        t  t",
    "tttttttttttttttttt",
]

Optional: Wie die letzte Aufgabe, einfach für die folgenden Labyrinthe:

lab_1 = [
    "ttttttttttttttttttt",
    "tgt  t    t       t",
    "t t    t  t  t f  t",
    "t t  t tf t  t  fft",
    "t t ft   tttttt   t",
    "t t f  t t        t",
    "t t ft t t  ttt   t",
    "t t  t tft  t     t",
    "t t  t tft  t ttttt",
    "t    t      t   p t",
    "ttttttttttttttttttt",
]
 
lab_2 = [
    "tttttttttttttttttttttt",
    "tgt  t    t       ff t",
    "t t    tfft   t f    t",
    "t t  t t  t   t  fffft",
    "t t  t   ttttttt     t",
    "t t  t t t           t",
    "t t  t t t   ttttttt t",
    "t t ft t t   ttttttt t",
    "t t ft t t   ttttttt t",
    "t t f  t t   t       t",
    "t t ft t t   t fffff t",
    "t t ft tft   t ttttttt",
    "t    t       t      pt",
    "tttttttttttttttttttttt",
]

Der Code unten (muss aufklappen) erzeugt ein zufälliges Labyrinth, in welchem genau ein Weg von links nach rechts zum Ziel führt. Der Funktion in der Zeile lab = create_random_world_with_path(20,5,25) kann man drei Werte übergeben:

• Wert 1 (hier 20): Anzahl Zellen in $x-$Richtung
• Wert 2 (hier 5): Anzahl Zellen in $y-$Richtung
• Wert 3 (hier 25): Wert zwischen 1 und 100, je kleiner, desto mehr Abbiegungen im Weg

Auftrag (wenn räumlich möglich):

1. Baue Labyrinth mit Stühlen nach.
2. Arbeite in kleinen Gruppen.
3. Auf Papier: Schreibt Code, der Skunky für jedes solche Labyrinth zum Ziel führt.
4. Probiert Code im echten Labyrinth aus, verbessert gegebenenfalls.
5. Schreibe Code in Python. Jede® schreibt eigenen Code.

Code

### IGNORE CODE FROME HERE ...
from skunky import Skunky
import random
from itertools import groupby
 
def create_random_world_with_path(n_x_tot=20,n_y_tot=5,probability_same=20):
    n_y = n_y_tot - 2; n_x = n_x_tot - 2 # remove frame
 
    # create list describing path
    path = [random.randint(0,n_y-1)]; x = 0
    while True:
        if x > n_x: break
        # first two entries must be identical
        if len(path) < 2: path.append(path[-1]); x += 1; continue
        # avoid changing lane if not at least 3 identical ones
        if len(set(path[-3:])) > 1: path.append(path[-1]); x += 1; continue
        # check if switch lane or not
        p = random.randint(1,100)
        if p < probability_same: path.append(path[-1]); x += 1
        else:
            if path[-1] == 0: path.append(1)
            elif path[-1] == n_y - 1: path.append(n_y-2)
            else: path.append(random.choice([path[-1]-1,path[-1]+1]))
 
    # convert path list into world map
    world = [['t'] for i in range(n_y)]
    x = 0
    for i,y in enumerate(path):
        world[y][x] = ' '
        if y == path[i-1] and i > 0:
            for i in range(n_y): world[i].append('t')
            x += 1; world[y][x] = ' '
 
    world[path[0]][0] = 'p'; world[path[-1]][len(world[0])-1] = 'g'
 
    # add frame around world and convert into string list
    for w in world: w.insert(0,'t'), w.append('t')
    world = [''.join(w) for w in world]
    world.insert(0,'t' * len(world[0])); world.append('t' * len(world[0]))
    return world
 
### IGNORE CODE UNTIL HERE. BELOW WRITE YOUR OWN CODE
lab = create_random_world_with_path(20,5,25)
 
fritz = Skunky(world_map=lab,delay_time=200,cell_size=30)
 
# here add your code
 
fritz.show_indefinitely()

Stelle dir vor, dass eines Tages dein Überleben davon abhängt, ob du aus einem Labyrinth herausfindest oder nicht. Wie gehst du vor? Es gibt einen einfachen Algorithmus, mit dem man aus fast jedem Labyrinth herausfindet. Das Ziel dieser Aufgabe ist, diesen Algorithmus selbst herauszufinden und dann für den Skunky zu implementieren.

1. Arbeite in 2er Gruppe
2. Holt beim Lehrer einen Ausdruck des folgenden Labyrinths:
3. Verwendet ein kleines Objekt als Skunky …
4. … und versucht verschiedene Ideen heraus, mit der der Skunky systematisch aus diesem und (fast) jedem anderen Labyrinth herausfindet. Findet eine Strategie / einen Algorithmus.
5. Diskutiert eure Strategie mit dem Lehrer.
6. Sobald ihr das OK vom Lehrer habt: Implementiert euren Algorithmus für den Skunky und probiert diesen für verschiedene Labyrinthe aus.

Ziemlich anspruchsvoll. Es hilft auch, wenn man schon weitere Programmierkonzepte wie Listen kennt.

1. Mit dem Algorithmus der letzten Aufgabe findet man aus fast allen Labyrinthen heraus. Es gibt aber solche, für die dieser Algorithmus nicht funktioniert. Für welche?
2. Ein Beispiel ist das Labyrinth unten. Implementiere einen Code, der den Skunky aus diesem (und jedem anderen Labyrinth) herausbringt.

Code Labyrinth

lab = [
    "ttttttttttttttt",
    "t             t",
    "t t ttttt ttt t",
    "t t t   tttgt t",
    "t t t t   t t t",
    "t t   ttt   t t",
    "t ttttt  tttt t",
    "t             t",
    "tttttttt tttttt",
    "t      t   t  t",
    "tf ttt ttt t tt",
    "t  tpt   t    t",
    "tf t ttt t  t t",
    "t  t      tt  t",
    "tf tttttt tt tt",
    "tf            t",
    "ttttttttttttttt",
]