kleinere Optimierungen und Dokumentation

6 files changed, 187 insertions, 24 deletions

diff --git a/alphametiken.md b/alphametiken.md
new file mode 100644
index 0000000..ca8e96d
--- /dev/null
+++ b/alphametiken.md
@@ -0,0 +1,41 @@
+Alphametiken
+============
+
+Das Programm ist in zwei Teile gegliedert:
+
+* `löse(zu_lösendes_Alphametikum)` gibt eine Liste mit allen Lösungen eines Alphametikums in dem Format `[['Rechnung', {'Buchstabe': zugehörige_Zahl, ...}], ...]` zurück (zum Beispiel `[['8928-3164=5764', {'Ü': 9, 'F': 8, 'W': 7, 'N': 2, 'Z': 5, 'I': 4, 'E': 6, 'D': 3, 'R': 1}]]` für `FÜNF-DREI=ZWEI`).
+
+* `generiere(Länge)` gibt ein Alphametikum als String zurück (zum Beispiel `FÜNF-DREI=ZWEI`), für welches mindestens eine Lösung vorhanden ist.
+
+Alphametikum lösen
+------------------
+
+Die Funktion `ersetze`, aufgerufen durch `löse`, ersetzt jeweils den ersten Buchstaben im Alphametikum durch eine Zahl, nacheinander 0 bis 9. Für den Rest des Alphametikum-Strings wird die Funktion rekursiv aufgerufen. Ist der letzte Buchstabe ersetzt, wird mithilfe von Pythons `eval`-Funktion überprüft, ob die ersetzten Zahlen zu einer wahren Gleichung führen. Ist dies der Fall, wird die gefundene Lösung in einer Liste festgehalten und nach Überprüfen aller Kombinationen zurückgegeben.
+Der Ausnahmefall, dass die Lösung eine Null als erste Ziffer einer Zahl hat, wird durch einen regulären Ausdruck `re.search` überprüft. Um gleiche Zahlen nicht an mehrere Buchstaben zu verteilen wird in der rekursiven Funktion die Liste an bereits verwendeten Zahlen mitgegeben.
+
+Beispiel für eine Lösung:
+```
+>>> import alphametiken
+>>> alphametiken.löse("SEND + MORE = MONEY")
+[['9567 + 1085 = 10652', {'O': 0, 'N': 6, 'M': 1, 'E': 5, 'Y': 2, 'S': 9, 'D': 7, 'R': 8}]]
+```
+
+Alphametikum finden
+-------------------
+
+Zum Finden von Alphametiken in der Form `FÜNF-DREI=ZWEI` ist es zuerst nötig, eine valide Gleichung - hier `5-3=2` zu finden. Um dies für eine beliebige Länge zu tun, wird in der Funktion `generiere` ein Template erstellt, in dem `_` dann durch ein zufälliges Rechenzeichen, `x` und `y` durch eine zufällige Zahl von 0-9 ersetzte wird, sodass bei einer Länge von 1 dieses Schema entsteht:
+```
+x_x=y
+```
+das nun auf Richtigkeit, wieder durch `eval`, geprüft wird. Eine Gleichung wie `5-3=2` wird schließlich mithilfe von Zahlwörtern abgebildet: `FÜNF-DREI=ZWEI`. Jetzt wird mit `löse` geprüft, ob eine Lösung vorhanden ist. Wenn ja, endet die Funktion, sonst wird nach einer neuen Gleichung gesucht.
+`random.choice` und `random.randrange` dienen hier zum Finden zufälliger Rechenzeichen und Zahlen.
+
+
+TODO FIXME BEISPIELE + LÖSUNG
+
+Beispiel für ein Alphametikum mit mehr als 20 Zeichen:
+```
+>>> import alphametiken
+>>> alphametiken.generiere(3)
+'FÜNF-ZWEI+VIER-ZWEI=FÜNF'
+```
diff --git a/alphametiken.py b/alphametiken.py
index ff13108..37c0c2e 100755
--- a/alphametiken.py
+++ b/alphametiken.py
@@ -10,12 +10,14 @@ import re, random
 Alphametik = "SUCHEN-MACHT=SPASS"
 
 Zahlen = ["EINS", "ZWEI", "DREI", "VIER", "FÜNF", "SECHS", "SIEBEN", "ACHT", "NEUN", "ZEHN"]
+#Rechenzeichen = ["+", "-", "*", "/"]
+Rechenzeichen = ["+", "-"] # schneller
 
 # Liste der Buchstaben erstellen aus `wort`
 def buchstaben_liste(wort):
     buchstaben = []
     for c in wort:
-        if (c not in "+-*/= ") and (c not in buchstaben):
+        if (c not in Rechenzeichen) and (c not in buchstaben) and (c not in " ="):
             buchstaben.append(c)
 
     return buchstaben
@@ -51,6 +53,10 @@ def ersetze(b, wort, benutzte_zahlen = [], lösungen = [], alle_buchstaben = Non
 
     return lösungen
 
+# kleiner Wrapper, der die Benutzung von `ersetze` vereinfacht
+def löse(alpham):
+    return ersetze(buchstaben_liste(alpham), alpham)
+
 # gibt ein zufälliges Alphametik mit `länge` "Ziffern" vor dem Gleichheitszeichen zurück
 def generiere(länge = 1):
     while True:
@@ -59,7 +65,7 @@ def generiere(länge = 1):
             alphametik = "x" + "_x" * länge + "=y" # Template für Rechnung
 
             for j in range(länge + 1): # zufällige Rechenzeichen einsetzen
-                alphametik = alphametik.replace("_", random.choice(["+", "-", "*", "/"]), 1)
+                alphametik = alphametik.replace("_", random.choice(Rechenzeichen), 1)
 
             alphametik = alphametik.replace("y", str(random.randrange(1, 9))) # Ergebnis
             for j in range(länge + 2):
@@ -71,12 +77,12 @@ def generiere(länge = 1):
         for j in range(1, 10):
             alphametik = alphametik.replace(str(j), Zahlen[j - 1])
 
-        l = ersetze(buchstaben_liste(alphametik), alphametik)
+        l = löse(alphametik)
         if len(l) > 0:
             return alphametik # Geschafft, wir haben eines gefunden!
 
 if __name__ == "__main__":
-    l = ersetze(buchstaben_liste(Alphametik), Alphametik)
+    l = löse(Alphametik)
 
     if len(l) == 0:
         print("Keine Lösungen vorhanden")
diff --git a/buffet_lotterie.md b/buffet_lotterie.md
new file mode 100644
index 0000000..8a125c0
--- /dev/null
+++ b/buffet_lotterie.md
@@ -0,0 +1,63 @@
+Buffet-Lotterie
+===============
+
+Das Programm besteht aus der Funktion `denke(Anzahl_Teilnehmer, Silben_als_Liste)`, die die Lösung auf der Konsole ausgibt.
+
+Gedanken dazu
+-------------
+
+* Es ist egal, wer welche Silbe sagt. Wichtig ist nur, wer die letzte spricht und wie oft das Geburtstagskind die Möglichkeit hat, zwei zu sprechen.
+* Es ist - für das Geburtstagskind - egal, in welcher Reihenfolge es Eine und Zwei Silben spricht, solange die Anzahl an Zweisilbern insgesamt gleich bleibt, denn
+* Es ist von Anfang an klar, nach wie vielen Runden das Geburtstagskind drankommt und wie viele Silben es spricht. Bei der gleichen Anzahl an Silben und Start-Teilnehmern ist die Anzahl an Runden, die das Geburtstagskind braucht, um zum Essen zu kommen konstant.
+
+Lösung
+------
+
+Nach langem Nachdenken ergaben sich die Formeln
+```
+e = floor((len(silben) + offset) / teilnehmer)
+offset = ((len(silben) + offset - 1) % teilnehmer) % (teilnehmer - 1)
+```
+wobei `e` die Anzahl Runden darstellt, die das Geburtstagskind eine Silbe sagen durfte, bis jemand zum Essen ging und
+`offset` - mit dem Startwert 0 - die Nummer des Teilnehmers, der als nächstes anfangt hat.
+Um dann noch auszurechnen, wie weit diese Teilnehmernummer `offset` vom Geburtstagskind entfernt ist, kann man 
+```
+fehlt_noch = (offset - 1) % (teilnehmer - 1) + 1
+```
+benutzen.
+Diese Berechnungen werden in einer Schleife durchgeführt. Um zu berechnen, wie oft das Geburtstagskind optimalerweise zwei Silben sagen muss, ist es nötig, die Gesamtzahl an `e`s zu behalten. Das geschieht in `einfluss`.
+Jedes Mal, nachdem ein Teilnehmer in der Rechnung die Runde verlässt, wird geprüft, ob der `einfluss` groß genug ist, um die Lücke `fehlt_noch` auszugleichen. Wenn ja, ist die Aufgabe gelöst und das Geburtstagskind kann `fehlt_noch`-mal zwei Silben nennen und früher Essen gehen.
+Die Lösung wird durch Zustands-Nachrichten verständlicher gemacht.
+
+Beispiele
+---------
+
+6 Teilnehmer mit "Informatik kann uns..."
+```
+>>> import buffet_lotterie
+>>> buffet_lotterie.denke(6, ['In', 'for', 'ma', 'tik', 'kann', 'uns', 'wei', 'sen', 'wer', 'als', 'Nächs', 'ter', 'kommt', 'zum', 'Spei', 'sen'])
+Nach 2 Runden fängt der 4. an. Es sind dann noch 5 Teilnehmer im Spiel.
+Es fehlten 3 bis zum Geburtstagskind
+Nach 3 Runden fängt der 4. an. Es sind dann noch 4 Teilnehmer im Spiel.
+Es fehlten 3 bis zum Geburtstagskind
+Das Geburtstagskind muss erst 3-mal 'zwei Silben' und dann nur noch 'eine Silbe' sagen, bis es dran ist.
+```
+
+28 Teilnehmer, wie in der Aufgabe
+```
+>>> buffet_lotterie.denke(28, ['In', 'for', 'ma', 'tik', 'kann', 'uns', 'wei', 'sen', 'wer', 'als', 'Nächs', 'ter', 'kommt', 'zum', 'Spei', 'sen'])
+Nach 0 Runden fängt der 16. an. Es sind dann noch 27 Teilnehmer im Spiel.
+Nach 1 Runden fängt der 4. an. Es sind dann noch 26 Teilnehmer im Spiel.
+Es fehlten 3 bis zum Geburtstagskind
+Nach 0 Runden fängt der 19. an. Es sind dann noch 25 Teilnehmer im Spiel.
+Nach 1 Runden fängt der 9. an. Es sind dann noch 24 Teilnehmer im Spiel.
+Es fehlten 8 bis zum Geburtstagskind
+Nach 1 Runden fängt der 1. an. Es sind dann noch 23 Teilnehmer im Spiel.
+Es fehlten 23 bis zum Geburtstagskind
+Nach 0 Runden fängt der 16. an. Es sind dann noch 22 Teilnehmer im Spiel.
+Nach 1 Runden fängt der 9. an. Es sind dann noch 21 Teilnehmer im Spiel.
+Es fehlten 8 bis zum Geburtstagskind
+Nach 1 Runden fängt der 3. an. Es sind dann noch 20 Teilnehmer im Spiel.
+Es fehlten 2 bis zum Geburtstagskind
+Das Geburtstagskind muss erst 2-mal 'zwei Silben' und dann nur noch 'eine Silbe' sagen, bis es dran ist.
+```
diff --git a/buffet_lotterie.py b/buffet_lotterie.py
index 82a8d75..a868e66 100755
--- a/buffet_lotterie.py
+++ b/buffet_lotterie.py
@@ -5,22 +5,26 @@ from math import floor
 Anzahl_teilnehmer = 6
 Silben = ['In', 'for', 'ma', 'tik', 'kann', 'uns', 'wei', 'sen', 'wer', 'als', 'Nächs', 'ter', 'kommt', 'zum', 'Spei', 'sen']
 
-teilnehmer = Anzahl_teilnehmer
-fehlt_noch = float("inf")
-einfluss = 0
-offset = 0
-while fehlt_noch > 0:
-    e = floor((len(Silben) + offset) / teilnehmer) # e Runden ist das Geburtstagskind dran, bis einer gehen darf
-    offset = ((len(Silben) + offset - 1) % teilnehmer) % (teilnehmer - 1) # nach e Runden fängt Teilnehmer Nummer `offset` an, 0 ist das Geburtstagskind
+def denke(anzahl_teilnehmer, silben):
+    teilnehmer = anzahl_teilnehmer
+    fehlt_noch = float("inf")
+    einfluss = 0
+    offset = 0
+    while fehlt_noch > 0:
+        e = floor((len(silben) + offset) / teilnehmer) # e Runden ist das Geburtstagskind dran, bis einer gehen darf
+        offset = ((len(silben) + offset - 1) % teilnehmer) % (teilnehmer - 1) # nach e Runden fängt Teilnehmer Nummer `offset` an, 0 ist das Geburtstagskind
 
-    einfluss += e # Geburtstagskind kann insgesamt `e`-mal dem Essen näher kommen
-    fehlt_noch = (offset - 1) % (teilnehmer - 1) + 1 # um jetzt dran sein zu müssen, hätte das Geburtstagskind `fehlt_noch`-mal zwei Silben sagen müssen
+        einfluss += e # Geburtstagskind kann insgesamt `e`-mal dem Essen näher kommen
+        fehlt_noch = (offset - 1) % (teilnehmer - 1) + 1 # um jetzt dran sein zu müssen, hätte das Geburtstagskind `fehlt_noch`-mal zwei Silben sagen müssen
 
-    print("Nach " + str(e) + " Runden fängt der " + str(offset + 1) + ". an. Es sind dann noch " + str(teilnehmer - 1) + " Teilnehmer im Spiel.")
-    if e > 0: # falls das Geburtstagskind dran kam
-        print("Es fehlten " + str(fehlt_noch) + " bis zum Geburtstagskind")
-        if fehlt_noch < einfluss:
-            print("Das Geburtstagskind muss erst " + str(fehlt_noch) + "-mal 'zwei Silben' und dann nur noch 'eine Silbe' sagen, bis es dran ist.")
-            break
+        print("Nach " + str(e) + " Runden fängt der " + str(offset + 1) + ". an. Es sind dann noch " + str(teilnehmer - 1) + " Teilnehmer im Spiel.")
+        if e > 0: # falls das Geburtstagskind dran kam
+            print("Es fehlten " + str(fehlt_noch) + " bis zum Geburtstagskind")
+            if fehlt_noch < einfluss:
+                print("Das Geburtstagskind muss erst " + str(fehlt_noch) + "-mal 'zwei Silben' und dann nur noch 'eine Silbe' sagen, bis es dran ist.")
+                break
 
-    teilnehmer -= 1 # einer geht
+        teilnehmer -= 1 # einer geht
+
+if __name__ == "__main__":
+    denke(Anzahl_teilnehmer, Silben)
diff --git a/faehre_fuellen.md b/faehre_fuellen.md
new file mode 100644
index 0000000..8cec7b9
--- /dev/null
+++ b/faehre_fuellen.md
@@ -0,0 +1,48 @@
+Fähre füllen
+============
+
+Die Lösung zu Fähre füllen beinhaltet wie gefordert zwei Strategien `strategie_a`, `strategie_b`.
+Beide Funktionen nehmen eine Liste mit Autolängen als Eingabe und geben ein `dict` mit der Länge und Anzahl aller Autos zurück. Mit `print` wird angegeben, wo die Autos einsortiert werden.
+
+Strategie A
+-----------
+
+Die Fahrzeuge werden möglichst weit links angeordnet. Am effizienten ist das bei einer Folge wie beispielsweise
+```
+6, 6, 6, 15, 15, 15, ...
+```
+da hierbei die meiste Anzahl an Fahrzeugen hineinpasst, verglichen mit B.
+
+Strategie B
+-----------
+
+Die Fahrzeuge werden möglichst gleichmäßig auf die drei Spalten verteilt. Die Folge vom Beispiel in A) würde dazu führen, dass nur 3 Fahrzeuge (`6, 6, 6`) Platz hätten. In dem Beispiel
+```
+8, 8, 8, 5, 5, 5, 5, 5, 5, ...
+```
+werden für A) 8 Fahrzeuge eingeordnet und für B) 9.
+
+TODO FIXME BEISPIELE ANWENDEN
+
+Beispiele
+---------
+
+```
+>>> import faehre_fuellen
+>>> faehre_fuellen.strategie_a([15, 15, 15, 15, 15, 6, 6, 6])
+6 wurde eingeordnet in die Reihe 0
+6 wurde eingeordnet in die Reihe 0
+6 wurde eingeordnet in die Reihe 0
+15 wurde eingeordnet in die Reihe 1
+15 wurde eingeordnet in die Reihe 2
+Das Fahrzeug 15 hat nicht mehr gepasst
+{'anzahl': [3, 1, 1], 'länge': [18, 15, 15]}
+>>>
+>>>
+>>> faehre_fuellen.strategie_b([15, 15, 15, 15, 15, 6, 6, 6])
+6 wurde eingeordnet in Reihe 0
+6 wurde eingeordnet in Reihe 1
+6 wurde eingeordnet in Reihe 2
+Das Fahrzeug 15 hat nicht mehr gepasst
+{'anzahl': [1, 1, 1], 'länge': [6, 6, 6]}
+```
diff --git a/faehre_fuellen.py b/faehre_fuellen.py
index bbc909e..d71d374 100755
--- a/faehre_fuellen.py
+++ b/faehre_fuellen.py
@@ -79,7 +79,8 @@ def strategie_b(abfolge):
 
     return faehre
 
-print("\n=== Strategie A ===\n")
-print(strategie_a(Beispiel[:]))
-print("\n=== Strategie B ===\n")
-print(strategie_b(Beispiel[:]))
+if __name__ == "__main__":
+    print("\n=== Strategie A ===\n")
+    print(strategie_a(Beispiel[:]))
+    print("\n=== Strategie B ===\n")
+    print(strategie_b(Beispiel[:]))