Tabelle ausgeben

Was ich bislang mit eigenen - sehr unschönen - Funktionen bewerkstelligt habe, kann man auch mittels front(wert,Formatierung) erledigen, was Weigend auf S. 253 vorstellt.

In diesem Zusammenhang ist die Format String Syntax bzw. die Format Specification Mini-Language zu beachten.

SQLite

Ich überlege wieder einmal etwas mit SQLite zu arbeiten und suche nützliche Ressourcen im Netz, weil die Dokumentation in den Tutorials und Handbüchern für meine Begriffe meist ziemlich schlecht - weil lückenhaft - ist.

Ressourcen

Zunächst nützliche Seiten im Internet, die bei der Arbeit mit SQLite helfen können:

• Die Seite des Herstellers unter www.sqlite.org.

• Die Dokumentation der DB-API in der offiziellen Python Dokumentation.

Lose Sammlung (Qualität?):

• URL > http://www.devshed.com/c/a/Python/Using-SQLite-in-Python/
• URL > http://www.blog.pythonlibrary.org/2012/07/18/python-a-simple-step-by-step-sqlite-tutorial/
• URL > http://openbook.galileocomputing.de/python/python_kapitel_19_003.htm#mjea5883d439a425e2f974548b406b56c0
• URL > http://zetcode.com/db/sqlitepythontutorial/
• URL > http://www.doughellmann.com/PyMOTW/sqlite3/index.html
• URL >
• 
  

Jetzt eine Art Notizzettel.

Die Datenbank

Was möchte ich tun:

• Eine Datenbank anlegen

Tabellen

Was möchte ich tun:

• Eine Tabelle anlegen
• Eine Tabelle löschen

Daten

Was möchte ich tun:

• Daten eintragen
• Daten updaten
• Daten löschen
• Daten abfragen

Fibonacci-Folge

Eine kleine Aufgabe für zwischendurch ist die Programmierung einer Funktion, die die Fibonacci-Folge bzw. das Element n dieser Folge ausgibt.

Rekursive Umsetzung

Hier eine rekursive Umsetzung, die auf meinem System für den Zahlenraum bis etwa 30 einigermaßen flott unterwegs ist, sich anschließend aber festfährt:

def fib(n):
    ''' Rekursive Funktion, die fuer eine Ganzzahl n
    die Fibonacci-Zahl zurueckgibt

    '''
    if n < 2:
        return n
    else:
        return fib(n-2) + fib(n-1)



for i in range(0,100):
    print(i,fib(i))

Eine zweite Umsetzung

Bei diesem Skript, befüllt die Funktion eine Liste und nutzt sie für die Berechnung. Nachteil ist, dass die Liste bei jedem Funktionsaufruf neu erzeugt werden muss, was nicht sehr sinnvoll ist. Das Skript wirkt zunächst recht performant:

def fib(n):
    ''' Rekursive Funktion, die fuer eine Ganzzahl n
    die Fibonacci-Zahl zurueckgibt

    '''
    fibfolge = [0,1,1]
    if n < 2:
        return n
    else:
        for i in range(2,n+1):
            result = fibfolge[i-1] + fibfolge[i]
            fibfolge.append(result)
        return result

Man beachte den Artikel „Fibonacci numbers (Python)“ im LiteratePrograms-Wiki.

Project Euler: Problem 3

Bei Problem 3 des Projects Euler gilt es folgende Aufgabe zu bewältigen:

Die Primfaktoren von 13195 sind 5, 7, 13 und 29. Was ist der größte Primfaktor der Zahl 600851475143?

Hier ist im Kern eine Primfaktorzerlegung gefordert, was für mich ein Skript erledigt und die richtige Antwort zurückgibt. Das Skript war um folgende Zeilen zu ergänzen:

n = 600851475143
print(max(primfaktoren_bestimmen(n)))

Das Skript lieferte die richtige Antwort in Millisekunden zurück. Hier findet sich eine Lösung des Problems vom mathblog.dk.

Das Modul „decimal“

Mit dem Modul „decimal“ ist eine bessere Genauigkeit bei Berechnungen möglich.

Fakultät

Die Fakultät einer Zahl ist „in der Mathematik eine Funktion, die einer natürlichen Zahl das Produkt aller natürlichen Zahlen kleiner und gleich dieser Zahl zuordnet“ (Wikipedia).

n	n!
0	1
1	1
2	2
3	6
4	24
5	120
6	720
7	5.040
8	40.320
9	362.880
10	3.628.800

Das Ganze lässt sich rekursiv formulieren:

def fakultaet(x):
    if x > 1:
        return x * fakultaet(x - 1)
    else:
        return 1

Und auch iterativ:

def fakultaet(n):
    ''' Gibt die Fakultaet
    einer Zahl n zurueck

    '''

    if n <= 1:
        return 1
    else:
        for i in range(1,n):
            n *= i
        return n

Was ist performanter? Eigentlich würde ich erwarten, dass die rekursive Lösung weniger performant ist.

Project Euler: Problem 45

Bei Problem 45 des Projects Euler soll diejenige Zahl > 40755 gefunden werden, die sowohl eine Dreieckszahl als auch pentagonal und hexagonal ist.

Die Formeln zur Berechnung der Zahlenfolgen sind der Aufgabenstellung beigegeben.

T(n) = n (n + 1) / 2

P(n) = n (3 n -1) / 2

H(n) = n (2n - 1)

Die erste Zahl, für die diese Bedingung zutrifft ist 40755.

T(285) = P(165) = H(143) = 40755

Die nächste Zahl, die diese Bedingung erfüllt, wird gesucht.

Für die verschiedenen Zahlen ergeben sich folgende Zahlenfolgen:

T(n) → 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, ... 

P(n) → 1, 5, 12, 22, 35, 51, 70, 92, 117, 145, 176, 210, 247, 287, 330, 376, 425, 477, 532, ... 

H(n) → 1, 6, 15, 28, 45, 66, 91, 120, 153, 190, 231, 276, 325, 378, 435, 496, 561, 630, 703, ... 

Auffälligkeiten? Mir fällt auf, dass jedes zweite Element der Dreieckszahlen (T(n)) auch in der Zahlenfolge der hexagonalen Zahlen (H(n)) auftaucht:

1, 6, 15, 28, 45, 66, 91, 120, 153 usw.

Das heißt, dass ich die Dreieckszahlen nicht berechnen muss. Jede hexagonale Zahl ist zugleich immer eine Dreieckszahl. Mit einer Brute-Force-Methode lässt sich und ließ sich das Problem lösen (mir ist gerade aufgefallen, dass ich es schon einmal gelöst hatte):

pzahlen = [int(i * (3 * i - 1) / 2) for i in range(1,1000000)]

hzahlen = [int(i * (2 * i - 1)) for i in range(1,500000)]

print("Suche jetzt ein Element, das in allen drei Listen auftaucht.")

for i in pzahlen:

    if i in hzahlen:

        print(i)

Nachteil an diesem Verfahren ist sicherlich der Lärm, den der Lüfter produziert. Nicht sinnvoll. Ich habe hier beim MathBlog eine Lösung für das Problem gefunden, die ich nun implementieren will.

Der Lösungsweg erscheint recht einfach:

• Erzeuge hexagonale Zahlen und prüfe, ob es sich dabei um eine pentagonale Zahl handelt.

Verständnis: (1) Dieser Lösungsweg ist besser, weil nicht erst zwei Listen erzeugt werden müssen, sondern nur die Werte einer Liste hinsichtlich ihrer Eigenschaften zu prüfen sind. (2) Die hexagonalen Zahlen wurden ausgewählt, weil hier deutlich weniger Zahlen zu prüfen sind. (3) Ein weiteres, nicht ausgeschöpftes Potential zur Optimierung wäre es, erst die hexagonalen Zahlen ab 143 zu prüfen, weil 143 ja bereits ein Ergebnis (vgl. Aufgabenstellung) war.

In Python-Code könnte da so aussehen:

import math


def is_polygonal(n):
    ''' Pruefung auf Basis der Formel
    der Wikipedia, Rueckgabewerte True and False

    '''
    result = (math.sqrt(24 * n + 1) + 1) / 6
    if int(result) == result:
        return True
    else:
        return False


for i in range(1,100000):
    # Berechne eine hexagonale Zahl
    hexagonale_zahl = i * (2 * i - 1)
    # Pruefe das
    if is_polygonal(hexagonale_zahl):
        # Ausgabe
        print(hexagonale_zahl)

Die Lösung wird jetzt in wenigen Millisekunden ausgespuckt. Da ich die Prüfformel nicht selbst herleiten konnte, war ich auf die Formel in der Wikipedia angewiesen.

Coderian Cipher

Betrachtet man das Problem 9 (2012) bei HP Codewars, so erkennt man schnell, dass es sich letztlich um eine Caesar-Verschlüsselung handelt, mit der ich mich bereits einmal befasst habe und die zunächst einmal nicht sonderlich anspruchsvoll ist.

Ein gewisser Anspruch kommt in die Aufgabe, weil die Verschiebung über den beigegebenen Schlüssel ermittelt werden soll. Eigentlich müsste man hier eine Dechiffrierung über die Buchstabenhäufigkeit erreichen können, andererseits gibt es hierfür zu wenig Material. Nach einiger Zeit (5. Februar 2013) habe ich jetzt eine lauffähige Lösung für das Problem gecodet:

''' Coderian Cipher - HP codewars 2012
Beschreibung:   Loesung fuer das Problem Nr. 9 von HP codewars 2012
Version:        1. Loesung, 1. Ansatz
Autor:          Pixewakb, pixewakb@gmail.com
Startdatum:     04.02.2013
Enddatum:       05.02.2013
Letzte Bearb.:  05.02.2013
Probleme:       Das Skript duerfte einiges an Optimierungspotential haben

'''

message ="XYVOIC ERH FSCWIRFIVVC SR VCI AMXL E WMHI SJ XYRE WEPEH KEY YONR"


def dechiffrieren(message):
    ''' Erledigt das vollstaendige Dechiffrieren
    und gibt die decodierte Message zurueck

    '''
    # Variablen und Messsage splitten
    verschiebung = 0        # beruecksichtigt nur eine positive Verschiebung (!)
    text,keyword = message.split(" KEY ")

    # Text zurichten
    text = text.upper().replace(" ","")

    # Jetzt muss die Verschiebung ermittelt werden
    # (1) Berechne für jeden Buchstaben a in text eine Verschiebung
    # (2) Pruefe die Verschiebung anhand des Schluesselwortes
    # (3) Wenn Pruefung gelingt, dann stoppe das und gib die Verschiebung raus

    for i,a in enumerate(text):
        # a - verschluesselter Buchstabe
        # b - entschluesselter Buchstabe
        b = keyword[0]

        # print(ord(a),ord(b),sep=" - ",end=";")
        if ord(a) > ord(b):
            verschiebung = ord(a) - ord(b)
            # print(verschiebung)
        elif ord(a) < ord(b):
            verschiebung = -1 * (90 - ord(b) + ord(a) - 64)
            # print(verschiebung)
        else:
            verschiebung = 0
            # print(verschiebung)

        # Verschiebung wird bereits korrekt mit -4 ermittelt (!)

        # Pruefe, ob die Verschiebung zum Keyword passt,
        # sonst weiterpruefen

        # Ermittle die Sequenz :D
        testword = text[i:i+4]
        # Das Testword wird mittels Verschiebung umgetauscht und
        # gegen das keyword geprueft, wenn testword == keyword, dann
        # return verschiebung (!)
        test = []
        for a in testword:

            if ord(a) + verschiebung < ord("A"):
                wert = chr(ord(a) + verschiebung + 26)
            elif ord(a) + verschiebung > ord("Z"):
                wert = chr(ord(a) + verschiebung - 26)    
            else:
                wert = chr(ord(a) + verschiebung)
            test.append(wert)
            
        # print(test,keyword)
        if "".join(test) == keyword:
            print("Verschiebung gefunden! >>>",verschiebung)
            break
    
    # Verschiebung - der Wert sollte berechnet werden (!)    :-((
    # verschiebung = -4   # Muss Negativ sein (!)

    # Dechiffriere mit der Verschiebung den Satz
    # und gib das Ergebnis zurueck!
    result = []
    for a in message[:-9]:

        if a == " ":
            pass
        elif ord(a) + verschiebung < ord("A"):
            a = chr(ord(a) + verschiebung + 26)
        elif ord(a) + verschiebung > ord("Z"):
            a = chr(ord(a) + verschiebung - 26)
        else:
            a = chr(ord(a) + verschiebung)
        result.append(a)
            
    return "".join(result)


print(dechiffrieren(message))

Problem aus meiner Sicht ist, dass mir der Quelltext etwas lang vorkommt und es wahrscheinlich noch deutliches Optimierungspotential gibt.

Letter Distribution

Bei HP Codewars war 2012 als Aufgabe 8 für einen Text die Häufigkeit der auftretenden Buchstaben zu ermitteln und "grafisch" in der Konsole auszugeben.

import string


def text_analysieren(text):
    ''' Der Text soll analysiert werden und
    die Zahl des Auftretens der Buchstaben zurueckgegeben
    werden. Die Satzzeichen und das EOF ignoriere ich
    einfach. Die Funktion wird damit sehr knapp.

    '''
    result = {}
    
    # Verarbeiten
    for a in string.ascii_lowercase:
        result[a] = text.lower().count(a)
    
    return result


def analyseergebnis_ausgeben(analyseergebnis):
    ''' Erledige die Ausgabe, an die folgende
    Anfordeungen gestellt sind:
    a.) Buchstabe und Anzahl in einer Zeile
    b.) Für jedes Auftreten ein "*"
    c.) Zwei oder mehr Buchstaben mit identischer
        Haeufigkeit des Auftretens sollen in
        alphabetischer Reihenfolge ausgegeben
        werden

    '''
    # Ich schaue mir die Daten an
    keys = analyseergebnis.keys()
    values = list(analyseergebnis.values())
    values.sort(reverse=True)

    # Ich drehe das Wörterbuch um und
    # muss vermeiden, dass Buchstaben ueberschrieben werden
    w2 = {}
    liste = []
    
    for key in keys:
        item = w2.get(analyseergebnis[key],0)
        if item == 0:
            w2[analyseergebnis[key]] = [key]
        else:
            item.append(key)
            w2[analyseergebnis[key]] = item

    # Wir holen uns die Schluessel
    keys = list(w2.keys())
    keys.sort(reverse=True)
    
    for key in keys:
        liste = w2[key]
        liste.sort()
        for a in liste:
            print(a.upper(),"*" * key)        
        

text = """I have a dream that one day this nation will rise up and live out the true
meaning of its creed: "We hold these truths to be self-evident, that all men
are created equal." I have a dream that my four little children will one day
live in a nation where they will not be judged by the color of their skin but
by the content of their character.
###"""

analyseergebnis = text_analysieren(text)
analyseergebnis_ausgeben(analyseergebnis)

Das Skript erledigt die Aufgabe ist aber wahrscheinlich noch nicht elegant genug. Insbesondere das Schieben der Daten von einem Wörterbuch ins nächste könnte vielleicht umgangen werden; das ist ein Bauchgefühl.

Was die Ausgabe angeht, so gibt obiges Skript für den Beispieltext (siehe Quelltext) ein korrektes Ergebnis aus:

E ***************************************
T *******************************
A **********************
I ********************
H ******************
L *****************
N *****************
R ****************
O ***************
D ************
U ********
C *******
S *******
Y ******
B *****
F *****
M *****
V *****
W *****
G **
J *
K *
P *
Q *
X
Z 

Optimierung gewünscht ;D

Peter’s Peppers

Bei HP Codewars war 2012 als Aufgabe 5 eine Lösung für folgendes Problem zu entwickeln:

Ein Geschäft verkauft Paprika in Paketen zu 6, 11 oder 13 Paprikas. Der Preis pro Verpackung ist gleich, nur die Größen sind verschieden. Ein Skript soll nun eine Zahl n (n < 1000) erhalten und die kleinste Kombination von Paketen für den Versand finden. 13er-Pakete sollen bevorzugt werden.

Als Beispiele werden Bestellungen von 42, 55, 27 und 88 Paprikas gegeben. Das Skript soll seine Ausgabe in einer bestimmten Form erledigen:

42 peppers can be packed most economically in:
1 package of 13
1 package of 11
3 packages of 6
5 total packages.

bzw.

27 peppers cannot be packed.

Das Problem sieht stark nach einem Graphentheorie-Problem aus, was ich aber noch nicht beherrsche. Folgendes Skript arbeitet korrekt, ist aber bei einem größeren n nicht mehr sehr performant:

def packen(n):
    ''' Algorithmus, der die beste Kombination
    von 13er-, 11er- und 6er-Paketen Paprika ermitteln
    und zurueckgeben soll. Kann keine Loesung gefunden
    werden, dann wird 0,0,0 zurueckgegeben

    '''
    ergebnisliste = []
    
    for a in range(0,n // 13 + 1):
        for b in range(0,n // 11 + 1):
            for c in range(0,n // 6 + 1):
                if a * 13 + b * 11 + c * 6 == n:
                    # print(a,b,c)
                    ergebnis = a,b,c
                    ergebnisliste.append(ergebnis)

    ergebnisliste.sort()     
    if len(ergebnisliste) == 0:
        return 0,0,0
    else:
        return ergebnisliste.pop()


bestellungen = [6,31,42,55,27,88,79,802,999,964]

for bestellung in bestellungen:
    a,b,c = packen(bestellung)

    packages_gesamtzahl = a + b + c

    if a == 0 and b == 0 and c == 0:
        print("{} peppers cannot be packed.\n".format(bestellung))
    else:
        print("{} peppers can be packed most economically in:".format(bestellung))

        for package, value in zip([a,b,c], [13,11,6]):
            if package > 1:
                print("{} packages of {}".format(package,value))
            elif package == 1:
                print("{} package of {}".format(package,value))
                
        print("{} total packages.\n".format(packages_gesamtzahl))

Ich denke, dass das Problem besser zu lösen sein müsste. In einem ersten Schritt ist mir jedenfalls für die Funktion eine Vereinfachung eingefallen:

def packen(n):
    ''' Algorithmus, der die beste Kombination
    von 13er-, 11er- und 6er-Paketen Paprika ermitteln
    und zurueckgeben soll. Kann keine Loesung gefunden
    werden, dann wird 0,0,0 zurueckgegeben
 
    '''    
    for a in range(n // 13,-1,-1):
        for b in range(0,n // 11 + 1):
            for c in range(0,n // 6 + 1):
                if a * 13 + b * 11 + c * 6 == n:
                    # print(a,b,c)
                    ergebnis = a,b,c
                    return ergebnis
    return 0,0,0

Ich kann die Funktion eindampfen, weil ich nicht mehr alle möglichen Kombinationen erfassen will, sondern jetzt vom größtmöglichen Faktor von 13 starte und gegen 0 runterzähle. Der erste "Treffer" kann direkt zurückgegeben werden, weil hier die Bedingung - größtmögliche Anzahl der 13er-Pakete - erfüllt ist. Für die Anzahl der 11er- und 6er-Pakete gibt es in der Aufgabenstellung keine Bedingung.

Teilbarkeit durch 11 (Divide by 11)

Als Problem 2 beim HP Codewars-Wettbewerb 2011 galt es einen Algorithmus zu implementieren, der eine gegebene Zahl n dahin überprüft, ob die Zahl durch 11 teilbar ist. Ursprünglich wurde der Algorithmus 1897 durch Charles Dodgson (a.k.a. Lewis Carroll) entwickelt.

Der Algorithmus:

• Solange die Zahl mindestens aus zwei Ziffern besteht, soll eine neue Zahl gebildet werden,
• wobei die Einer-Zahl entfernt wird
• und von der gekürzten Zahl subtrahiert wird.
• Falls die verbleibende zweistellige Zahl durch 11 teilbar ist, dann ist auch die ursprüngliche Zahl durch 11 teilbar.

Seine Implementierung in Python:

def teste_teilbarkeit_11(n):
    '''Der Algorithmus prueft, ob eine Zahl
    durch 11 teilbar ist. Entwickelt wurde das
    Verfahren durch Reverend Charles Dodgson 1897

    '''
    print(n)
        
    while len(str(n)) >= 2:

        if n < 11:
            return False
        elif len(str(n)) == 2 and str(n)[0] == str(n)[1]:
            return True
        else:
            n = int(str(n)[:-1]) - int(str(n)[-1])
            print(n)


n = 161408196180

liste = [11,33,121,143,144,161408196180, 195024706980990699675294451800000]

for item in liste:
    if teste_teilbarkeit_11(item) == True:
        print("\nThe number {} is divisible by 11.\n".format(item))
    else:
        print("\nThe number {} is not divisible by 11.\n".format(item))

Es funktioniert. Alternativ eine Umsetzung, die ganz auf Modulo, größer/kleiner als und damit eben nicht auf Umwandlung der Zahl in Strings setzen muss.

def teste_teilbarkeit_11(n):
    '''Der Algorithmus prueft, ob eine Zahl
    durch 11 teilbar ist. Entwickelt wurde das
    Verfahren durch Reverend Charles Dodgson 1897
 
    '''
    print(n)
         
    while n >= 11:
 
        if 11 <= n <= 99 and n % 11 == 0:
            return True
        else:
            n = n // 10 - n % 10
            print(n)
            
    return False

Auch das geht, was die Konsolenausgabe zeigt:

161408196180
16140819618
1614081953
161408192
16140817
1614074
161403
16137
1606
154
11

The number 161408196180 is divisible by 11.

Der Algorithmus war mir bislang nicht bekannt.

Project Euler Nr. 37

Der Wikipedia-Artikel „Truncatable prime“ bietet die Lösung für die, die nicht selbst rechnen wollen. Ferner sei auf den Artikel „Truncatable Prime“ auf mathworld.wolfram.com verwiesen.

Beim Problem Nr. 37 vom Project Euler sind die 11 Primzahlen gesucht, bei denen man sowohl von rechts nach links, als auch von links nach rechts jeweils eine Ziffer wegnehmen kann und dennoch jeweils eine Primzahl erhält. Die Zahlen 2, 3, 5 und 7 sind ausgenommen. Als Beispiel wird die Zahl 3797 genannt.

Meine Vorüberlegung betrifft die Primzahlen im Zahlenraum von 1 bis 100:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.

Jede Primzahl, auf die das zutrifft, muss mindestens zweistellig sein und die äußersten Ziffern rechts und links müssen jeweils Primzahlen sein, d. h. die Primzahl muss - falls sie mindestens dreistellig ist - mit 23, 29, 31, 37, 53, 59, 71, 73 oder 79 beginnen.

2 - 23 - 29
3 - 31- 37
5 - 53 - 59
7 - 71 - 73 - 79

Im Zahlenbereich von 1 bis 100 können schon einmal 4 Primzahlen gefunden werden, die zur gesuchten Menge gehören:

23, 37, 53, 73.

Ausschließen kann ich alle Primzahlen, die mit einer 1, 4, 6, 8 oder 9 beginnen sowie alle, die mit einer 1 oder 9 (alle Zahlen, die auf 0, 2, 4, 6 oder 8 enden, sind durch 2 teilbar und somit keine Primzahlen) enden, direkt ausschließen und muss sie nicht näher prüfen.

Ich kann ferner alle Primzahlen ausschließen, die eine 4, 6, 8 oder 0 enthalten, weil dann bei der Trunkierung unweigerlich eine gerade Zahl herauskommen muss. Ein Sonderfall ist die 2, weil sie zwar an erster Stelle auftauchen darf, nicht aber an einer anderen Stelle.

3547 - 354 - 35 - 3

3547 - 547 - 47 - 7

In diesem Fall wäre auch 35 keine Primzahl (7 * 5).

Wie kann ein Algorithmus aussehen, der das Problem löst?

• Zunächst einmal muss ich Primzahlen ermitteln, die in eine Prüfliste aufgenommen werden.
• Dann muss ich die Primzahlen durchlaufen, um sie zu prüfen. Auslassen kann ich alle Zahlen, die eine 4, 6, 8 oder 0 enthalten oder mit 1 oder 9 enden oder beginnen.
• Schließlich muss ich für jede "Form" der Primzahl prüfen, ob sie wiederum in der Liste der Primzahlen enthalten ist. Dazu müssen die verschiedenen trunkierten Zahlen erstellt werden.
• Wenn ich 11 Primzahlen gefunden habe, dann kann ich die Prüfung abbrechen.

Schauen wir mal. Zunächst einmal die Funktion, die von rechts bzw. links jeweils eine Ziffer trunkiert - hier ein Beispiel für die Zahl 12345:

zahl = 12345

zahl = str(zahl)
for i in range(1,len(zahl)):
    print(zahl[:len(zahl)-i]," - ",zahl[len(zahl)-i:])

Das ergibt in der Konsole dann:

1234  -  5
123  -  45
12  -  345
1  -  2345

Das funktioniert schon einmal.

Am Ende muss man die Summe für die Liste [23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797, ...] bilden.

Spielereien mit Listen

Listen kann man immer gebrauchen.

Hier wird gefordert, dass das letzte Element einer Liste auf die erste Position verschoben wird. Hier ein mögliches Skript:

'''
Aufgabe:
Jeweils ein Element von hinten nehmen
und nach vorn auf Position 0 schieben

'''

liste = [77, 5, 13, 9, 63, 2]

item = [liste.pop()]

liste = item + liste

print(liste)

Faktorisierungsmethode von Fermat

Die Faktorisierungsmethode von Fermat berechnet zu einer ungeraden, zusammengesetzten Zahl n zwei Teiler a und b, für die gilt a * b = n. (Quelle)

Der Algorithmus

Folgendes ist zu bearbeiten:

• Hier folgt Quelltext...

Die Implementierung

Hier folgt Quelltext. Eine sehr frühe Implementierung.

import math


def __faktorisieren(n):
    ''' Funktion, die eine Zahl n faktorisiert,
    sobald 2 ganzzahlige Faktoren gefunden wurden,
    dann Rueckgabe der beiden Werte.
    Es werden nicht alle Faktoren fuer die Zahl
    n gesucht!

    '''
    n = int(n)
    zahl = math.sqrt(n)

    if int(zahl) == zahl:
        a = n // zahl
        b = zahl
        return a, b
    else:
        zahl = int(zahl)
        
        for i in range(zahl,n+1):

            if n / i == n // i:
                a = n // i
                b = i
                return a, b


def primfaktoren_bestimmen(n):
    ''' Funktion, die fuer eine Zahl n die
    Primzahlenfaktorisierung erledigt

    '''

    primzahlen = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
    result = [] # Nimmt das Ergebnis auf
    queue = []

    if n in primzahlen:
        return "Primzahl!"
    elif n == 1:
        print("Keine Faktorisierung möglich!")
        return n
    else:
        a, b = __faktorisieren(n)
        queue.append(a)
        queue.append(b)
        
        while True:
            
            x = queue.pop()
            
            if x in primzahlen:
                result.append(x)
            else:
                a, b = __faktorisieren(x)
                queue.append(a)
                queue.append(b)
            if len(queue) == 0:
                result.sort()
                result = [int(x) for x in result]
                return result


for i in range(2,100):
    print(i, primfaktoren_bestimmen(i))

Ich habe eine Primzahlliste für den Zahlenraum zwischen 1 und 100 beigegeben, um zu prüfen, ob die jeweilige Zahl noch einmal faktorisiert werden muss.

Eigentlich müsste das Skript aber auch selbst Primzahlen erkennen können: Eine Zahl n ist nämlich dann eine Primzahl, wenn als Faktoren die Zahlen 1 und n zurückkommen. Die Prüfung könnte auch dann an dieser Stelle enden und die Zahl n könnte der Ergebnisliste result beigegeben werden. Das ist (noch) nicht implementiert, wäre aber gerade für besonders große Zahlen interessant.

Zu diesem Eintrag gehört dieser Thread im Python-Forum.

Project Euler Nr. 5

Bei Problem Nr. 5 soll die kleinste positive Zahl gefunden werden, die ganzzahlig durch alle Zahlen von 1 bis 20 teilbar ist. Das Problem hatte ich vor einiger Zeit bereits gelöst. Mich interessieren hier einmal verschiedene Lösungen, um zu sehen, wie performant sie jeweils sind und wie weit ich den Quellcode optimieren kann.

Kategorie Brute-Force

Eine gangbare, aber nicht sehr performante Lösung ab n = 19.

def loesung_ermitteln(n):
    # Funktion, die nach einer Loesung fuer das
    # Problem Nr. 5 sucht: Kleinste Zahl, die durch
    # alle Zahlen von 1 bis 20 teilbar ist.
    zahl = n

    while True:
    
        for i in range(1,n+1):

            if zahl % i != 0:
                # print("Nächste Zahl",i)
                break

        if i == n:
            return zahl
        else:
            zahl += n


print("Arbeit an Problem Nr. 5")

# Ergebnis: 2520
print("10")
print(">>>",loesung_ermitteln(10))

input("Weiter?")

# Ergebnis: 9-stellige Zahl
print("20")
print(">>>",loesung_ermitteln(20)) 

Die einzige Optimierung ist, dass jeweils die zu prüfende Zahl um sich selbst erhöht wird. Eine Zahl die durch 10 teilbar sein soll, kann nur ein Vielfaches von 10 sein, also 10, 20, 30, 40, 50 usw.

Ich habe die Funktion unverändert gelassen, aber den Code im „Hauptprogramm“ angepasst:

print("Arbeit an Problem Nr. 5".center(40," "))

print("Zahl","Kleinstes gemeinsames Vielfaches",sep="\t")
print(40 * "=")

for zahl in range(1,21):
    print("{:>4}\t{:>32}".format(zahl,loesung_ermitteln(zahl)))

Das ergibt dann in der Konsole:

        Arbeit an Problem Nr. 5         
Zahl Kleinstes gemeinsames Vielfaches
========================================
   1                                1
   2                                2
   3                                6
   4                               12
   5                               60
   6                               60
   7                              420
   8                              840
   9                             2520
  10                             2520
  11                            27720
  12                            27720
  13                           360360
  14                           360360
  15                           360360
  16                           720720
  17                         12252240
  18                         12252240
  19                        232792560
  20                        232792560

Kategorie Mathematik soll helfen

Letztlich wird das kleinste gemeinsame Vielfache (kgV) der Zahlen 1 bis n gesucht. Für die Zahlen von 1 bis 10 ist das 2520. Die Mathematik müsste folglich helfen können. Wenn ich es richtig sehe, dann müsste ich hier mehrere Aufgaben bewältigen:

1. Primzahlen im Bereich 1 bis 20 bestimmen
2. Primfaktorzerlegung (Integer factorization) für die Zahlen 1 bis 20 leisten
3. Mathematisch mit (1) und (2) das kleinste gemeinsame Vielfache ermitteln.

Ich spiele die Primfaktorzerlegung manuell für den Zahlenraum 1 bis 20 durch:

Zahl	Primfaktor	Zahl	Primfaktor
1	1	11	Primzahl
2	Primzahl	12	2 ** 2 * 3
3	Primzahl	13	Primzahl
4	2 ** 2	14	2 * 7
5	Primzahl	15	3 * 5
6	2 * 3	16	2 ** 4
7	Primzahl	17	Primzahl
8	2 ** 3	18	2 * 3 ** 2
9	3 ** 2	19	Primzahl
10	2 * 5	20	2 ** 2 * 5

Wenn ich der Wikipedia folge, dann nimmt man für das kgV „alle Primfaktoren, die in irgendeiner der Zahlen vorkommen, mit der jeweils höchsten vorkommenden Potenz“. Daraus würde sich hier in diesem Fall ergeben:

kgV(1...20) = 1 * 2 ** 4 * 3 ** 2 * 5 * 7 * 11 * 13 * 17 * 19 = 232792560

Also: Das dürfte in der Umsetzung performanter sein. Die Primzahlen für den benötigten Bereich könnte man einem Skript beigeben, so dass hier nicht erst gesiebt werden muss. Die Primfaktorzerlegung performant zu implementieren (mögliche Algorithmen) dürfte anspruchsvoll sein und in geeigneter Form die Terme auszuwerten, ist erst einmal eine Herausforderung.

Die (3n+1)-Vermutung

Die (3n+1)-Vermutung bzw. das Collatz-Problem ist ein ungelöstes mathematisches Problem, welches erstmals 1937 vom Mathematiker Lothar Collatz formuliert wurde.

Die zu erzeugende Zahlenfolge folgt folgendem Bildungsgesetz:

• Beginne mit irgendeiner natürlichen Zahl n > 0.
• Ist n gerade, dann nimm n/2.
• Ist n ungerade, dann nimm 3n + 1.
• Wiederhole die Vorgehensweise mit der erhaltenen Zahl.

Konkret wird vermutet, dass jede so konstruierte Zahlenfolge in den Zyklus 4, 2, 1 mündet, dabei ist der Startwert bei n > 0 nicht relevant.

Der Algorithmus lässt sich mit Python implementieren:

# collatz_problem.py

from random import randint


def collatz_folge_erzeugen(n):
    ''' Erzeugt die Zahlenfolge entsprechend dem
    Algorithmus nach Collatz.

    '''
    while n != 1:
        if n % 2 == 0:
            n //= 2
        else:
            n = 3 * n + 1
        print(n, end=", ")
    print("...")

for i in range(0,1):

    n = randint(1,100)
    print("\n\nFolge für {}!".format(n))
    collatz_folge_erzeugen(n)

Man sollte beachten, dass die Bedingung bei while bewirkt, dass die Collatz-Folge nicht in den Zyklus 4, 2, 1 mündet, sondern beim ersten Auftreten endet.

Quersumme bilden

Quersumme für eine Zahl n bilden:

Ein Ansatz mit Generator und Stringoperation

def quersumme_bilden(n):
    ''' Gibt die Quersumme für eine Zahl n zueruck

    '''
    return sum(int(a) for a in str(n))



for i in range(10,89):
    print(i,quersumme_bilden(i))

In diesem Fall nutze ich einmal einen Generator anstelle von List Comprehension. Problem hier ist, dass keine Prüfung erfolgt, ob die übergebene Zahl n der Definition entspricht, d. h. ob es sich um eine natürliche Zahl handelt. Ein Fehler wird vom Programm selbst nicht ausgelöst oder behandelt.

Ein zweiter Ansatz mit Modulo und Ganzzahldivision

Auch diese Funktion gibt die Quersumme einer Ganzzahl aus:

def quersumme_bilden(n):
    ''' Ohne n in einen String
    umzuwandeln, soll die Quersumme
    berechnet werden

    '''
    quersumme = 0
    while n > 0:
        quersumme += n % 10
        n = n // 10
    return quersumme

print(format("Eingabe","10s"),format("Quersumme","10s"),sep="  ")
print("-" * 21)
for n in [9873216540,987654321,1004,25,36,29,49,18]:
    print(format(n,"10d"),format(quersumme_bilden(n),"10d"))

Im Augenblick könnte ich nicht sagen, welcher Ansatz schneller ist. Eigentlich sollte der zweite Ansatz performanter sein, weil keine Liste erzeugt und keine Typumwandlung erforderlich ist.

Römische Zahlen

Ein Skript soll römische Zahlen umrechnen und zurück.

Zunächst die Funktion, die eine Ganzzahl in eine römische Zahl konvertiert:

def int_to_roman(n):
    ''' Soll eine natuerliche Zahl > 0 und kleiner 4000
    erhalten und dafuer die roemische Zahl ausgeben.

    '''
    roman_numerals = []
    
    zahlen = {1000: "M",
              900: "CM",
              500: "D",
              400: "CD",
              100: "C",
              90: "XC",
              50: "L",
              40: "XL",
              10: "X",
              9: "IX",
              5: "V",
              4: "IV",
              1: "I"}

    if n > 0 and n < 4000 and type(n) == int:
        for zahl in sorted(zahlen.keys(),reverse=True):
            roman_numerals.append(n // zahl * zahlen[zahl])
            n = n % zahl

        return "".join(roman_numerals)


for i in [1984,534,923,12,18,1,2,23,456,234,872,3999]:
    print(i,int_to_roman(i),sep="\t")

Die Funktion, die eine natürliche Zahl in eine römische Zahl konvertiert, war recht einfach zu implementieren. Der Algorithmus funktioniert wie folgt: Für jeden Schlüssel im Wörterbuch "zahlen" führe folgendes aus: Dividiere die gegebene Zahl n durch die Zahl und füge nun der Liste das entsprechende römische Zahlzeichen entsprechend der Anzahl hinzu. Die Zahl n sei der Rest der Division von n durch die Zahl. Gib am Ende die römische Zahl zurück.

Die Funktion, die aus einer römischen Zahl eine natürliche Zahl macht, gefällt mir noch nicht, auch wenn das Skript funktioniert. Ich empfinde die Variante mit zwei Listen als unelegant:

def roman_to_int(roemische_zahl):
    ''' Soll eine roemische Zahl erhalten und
    dafuer die ganze Zahl ausgeben.

    '''

    zahlen = {"M": 1000,
              "D":  500,
              "C":  100,
              "L":   50,
              "X":   10, 
              "V":    5,
              "I":    1}
    
    liste = []
    
    for i,a in enumerate(roemische_zahl):
        if i == len(roemische_zahl) - 1:
            liste.append(zahlen[a])
        elif zahlen[a] < zahlen[roemische_zahl[i+1]]:
            liste.append(-1 * zahlen[a])
        else:
            liste.append(zahlen[a])
    
    return sum(liste)


for i in ["XXIII","CMXXIII","MCMLXXXIV","MMMCMXCIX"]:
    print(i,roman_to_int(i),sep="\t")

Alternative Lösungen bietet u. a. das Internet, d. h. auch, dass mein Skript wahrscheinlicher noch besser formuliert werden kann. Ganz spannend finde ich die Lösung von Tim Valenta hier bei ActiveState. Wenn ich es richtig sehe, dann vereinfacht er über map() das Vorhalten der Schlüssel und muss nicht - wie bei meiner obigen Lösung - zwei Wörterbücher einbauen. Seine Lösung für die Umrechnung von Ganzzahlen in römische Zahlen entspricht ziemlich gut meinem Ansatz. Der andere Ansatz ist deutlich knapper formuliert.

Project Euler Nr. 16

Bei Problem Nr. 16 sollen die Ziffern des Ergebnisses 2¹⁰⁰⁰ von addiert werden:

sum([int(i) for i in str(2 ** 1000)])

Mit list comprehensions lässt sich das Problem sehr knapp formulieren.

Vokabeln im Januar 2013

In der Rubrik Vokabeln möchte ich ab jetzt regelmäßig das notieren, was ich neu gelernt habe und dabei zugleich eine Art Monatsrückblick verfassen.

(1) Neu kennengelernt habe ich u. a. Generatoren bzw. Generatorausdrücke. Mir ist hier das praktische Einsatzgebiet noch nicht klar. Aber das kann ja noch kommen.

(2) Bei Wörterbüchern habe ich neu kennengelernt oder wieder gelernt, dass man folgendes formulieren kann:

>>> wörterbuch = {}
>>> wörterbuch.get("Wert!","-")
'-'

Vorteil hierbei ist, dass ein Wert zurückgegeben wird, falls der Schlüssel nicht im Wörterbuch vorhanden ist, d. h. es gibt keinen KeyError.

(3) Bei der Funktion enumerate() habe ich jetzt (erst) mitbekommen, dass ich den Startwert angeben kann, so dass erst ab einer bestimmten Zahl gezählt wird.

>>> liste = ["is","ea","id"]
>>> for i,item in enumerate(liste,1):
 print(i,item)

1 is
2 ea
3 id

Den entsprechenden Tooltip in der Konsole habe ich bislang jedesmal schlicht übersehen.

(4) Die Funktion eval() war in diesem Monat für mich auch neu. Mit Zeichenketten könnte man hier m. E. schnell einen sehr einfachen Taschenrechner programmieren, weil ein Term in Form einer Zeichenkette ausgewertet wird. Bei einem Taschenrechner würde das die Eingabe von zweistelligen Zahlen und größer erleichtern, weil eine Umrechnung in eine Zeichenkette unterbleiben könnte.

>>> eval("12+12")
24
>>> import math
>>> eval("12 + math.sqrt(64)")
20.0

Wahrscheinlich ist das nicht der eigentliche Grund, warum es die Funktion gibt, aber damit lässt sich schon einiges anstellen.

(5) Mit "STRING".isupper() kann man prüfen, ob ein String nur Großbuchstaben enthält. Das ist kürzer formuliert, als wenn ich das über eine Prüfung mittels Liste (ist a in der Liste der Großbuchstaben) machen würde.

Palindrom: Von Anna bis Otto

Ein Test, ob ein gegebenes Wort ein Palindrom ist, lässt sich einfach implementieren:

def palindrom_testen(wort):
    ''' Prueft, ob das uebergebene Wort ein Palindrom ist
    und gibt einen Wahrheitswert zurueck. Palindrom, dann True
    '''
    if wort.lower() == wort.lower()[::-1]:
        return True
    else:
        return False


for wort in ["Anna","Otto","Reittier","Rentner","Rotor","Blogger"]:
    if palindrom_testen(wort):
        print("{} ist ein Palindrom.".format(wort))
    else:
        print("{} ist kein Palindrom.".format(wort))

Sehr einfach.

BMI

BMI berechnen und Daten ausgeben.

(1) Berechnung des BMI



(2) Diagramm zur Entwicklung des Gewichts

Abb. 1: Die Entwicklung des Gewichts über die Zeit

Das Diagramm soll den Bereich des Idealgewichts anzeigen und zusätzlich die Messpunkte für das Gewicht grafisch aufbereitet zurückgeben. Grafisch aufbereitet bedeutet, dass die jeweilige Gewichtskategorie farblich codiert ist und je nach Kategorie eine unterschiedliche Farbe verwendet wird (Grün nach Rot).

Abb. 2: Die Farbcodes fürs Diagramm

Das Modul itertools

Ich müsste mir mal genauer die itertools („creating iterators for efficient looping“) ansehen. Da scheint es einige sehr interessante Funktionen zu geben, die ein „effizientes iterieren“ ermöglichen.

Primzahlen

Ich habe das Sieb des Eratosthenes schon vor einiger Zeit mal programmiert.

(1) Ein Ansatz mit Listen und list comprehensions

Der Algorithmus wirkt in dieser Form bereits sehr schnell.

def sieben(zahl):
    ''' Eine erste Implementierung des
    Sieb des Eratosthenes mit Listen
    '''
    liste = [2]
    liste.extend([i for i in range(3,zahl+1,2)])
 
    for z in range(2,zahl+1):
        if z in liste:
            exliste = [e * z for e in range(z,zahl+1) if e * z <= zahl]
            # print(z, exliste)
            if len(exliste) == 0:
                break
            else:
                for e in exliste:
                    if e in liste:
                        liste.remove(e)
    return liste
 
 
ergebnis = sieben(10000)
 
print(", ".join(map(str,ergebnis)),end=".\n")

Das Skript nutzt str.join(iterable) und map. Das Skript macht sich zunutze, dass nur die ungeraden Zahlen geprüft werden müssen, weil alle geraden Zahlen außer 2 keine Primzahlen sind. Sobald die exliste leer ist, wird die Löschung abgebrochen, weil angenommen wird, dass alle weiteren Listen auch leer sein werden.

(2) Ein Ansatz mit einem Wörterbuch

Mit dem Wörterbuch wirkt der Algorithmus noch etwas schneller:

def sieben(zahl):
    ''' Eine erste Implementierung des
    Sieb des Eratosthenes mit einem Woerterbuch
    '''
    keys = [2]
    keys.extend([i for i in range(3,zahl,2)])

    woerterbuch = {}

    for key in keys:
        woerterbuch[key] = True  # True = prime (!)
          
    for key in keys:
        if woerterbuch[key] == True:
            vielfache = [i * key for i in range(key,zahl+1) if i * key <= zahl]
            # print(key,vielfache)
            if len(vielfache) == 0:
                break
            else:
                for item in vielfache:
                    if item in woerterbuch:
                        woerterbuch[item] = False
    return [i for i in keys if woerterbuch[i] == True]

ergebnis = sieben(1000)

print(", ".join(map(str,ergebnis)),end=".\n")

Gefühlt ist das auch für größere Zahlen sehr zügig. Ich verzichte hier auf eine mitlaufende Ausgabe, was sich leicht durch einen weiteren print-Befehl nach der Zeile

if woerterbuch[key] == True:

realisieren ließe. In diesem Fall könnte der Aufbau einer weiteren Liste und die return-Anweisung entfallen.

Performanz-Test

Mit dem Modul profiler - entsprechend den Hinweisen von Michael Weigend (4. Aufl.) 2010 - ergab sich folgendes Bild:

Ich hätte nicht erwartet, dass die Umsetzung mit dem Wörterbuch so viel performanter ist. Inzwischen habe ich weiter am Code geschraubt, so dass beide Skripte eigentlich noch etwas performanter geworden sein müssten. Das zweite Skript schafft die Prüfung des Zahlenraums bis 1.000.000 jetzt in ca. 38,34 Sekunden statt ursprünglich etwa 42,18 Sekunden.

Feedback aus dem Python-Forum

Hier der Link zum Thread. Offensichtlich gibt es bei beiden Implementierungen noch deutliches Optimierungspotential.

tesseract mit Python

Bin gerade über die PyCologne-Seite auf Facebook zum Artikel „Python-Skript erkennt Gesichter, Haut und Texte“ von Anton Moser, Kerstin Ramer, Matthias Schrattenholzer, Rainer Poisel im LinuxMagazin, Ausgabe Juli 2012 gelangt. Nicht alles finde ich direkt interessant, aber die Möglichkeit auf tesseract mittels Python zuzugreifen, erscheint mir spannend und könnte ich zeitnah gebrauchen.

Der beim Artikel angegebene Link führt IMHO ins Nirvana, aber anscheinend wurde der Code auf github ausreichend geteilt, so findet er sich u. a. hier bei Juarez Bochi (jbochi) mit Verweis auf den ursprünglichen Autor Samuel Hoffstaetter (?) des Skripts - auf ihn verweist jedenfalls der Link des Linux Magazins.

Ich habe das Skript soeben zum Laufen bekommen. Einziges Manko ist m. E., dass es Python 2.7 verwendet und nicht direkt mit Python 3.2 läuft. Dafür habe ich mit der Installation jetzt aber FreeOCR 4.2 abgeschossen, auch eine Neuinstallation brachte es gerade nicht.

Manko bei Nutzung von python-tesseract ist lediglich, dass man keine Bildbereiche über ein GUI vorauswählen kann. Das geht mit FreeOCR.