Projecteuler: Lösung zu Problem 8

Projecteuler: Lösungen mit Python und C++

Und weiter geht es in der Lösungen zu Projecteuler Problemen mit Python Serie. Heute steht das achte Problem auf dem Plan. Dieses etwas andere Problem als die bisherigen wird, wie gewohnt, erläutert, die Herausforderung hierbei werden eingegrenzt und die Lösung mit Python nach bestem Wissen und Gewissen herausgefunden.

Problemvorstellung

Die Aufgabenstellung des achten Problems ist, wie bereits beim siebten, sehr kurz geraten. Und trotzdem bekommt der unvorbereitete Besucher der Projekteuler-Seite etwas das Grausen, wenn er die Aufgabenstellung sieht. Neben der textlichen Anweisung, was zu tun ist, wird nämlich das Untersuchungsobjekt gleich mitgeliefert.

Aber nur der Reihe nach: zuerst die Aufgabenstellung ins Deutsche übersetzten:

Finde das größte Produkt von fünf aufeinander folgenden Ziffern innerhalb einer Zahl mit 1000-Stellen.

Nach der Problembeschreibung folgt das Untersuchungsobjekt:
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

Zum heutigen Zeitpunkt haben sich genau 52538 mutige Projecteuler-Teilnehmer an die Aufgabe mit erfolgreichem Ausgang getraut. Das entspricht grob der Hälfte der insgesamt 115013 registrierten Leidensgenossen.

Problemeingrenzung

Unbeeindruckt von der Wucht großer Zahlen machen wir uns an die Problemanalyse und -eingrenzung heran.

Die erste Idee, welche sich beinahe sofort in die Gedanken einmischt, ist die straight-forward-Methode: Man nehme die ersten fünf Ziffern, multipliziere sie und vergleiche sie mit dem Produkt der Ziffern 2-6. So läuft man durch das ganze Feld, bis man am Ende angekommen ist. Das ist eine sehr simple Methode, die todsicher zum richtigen Ergebnis führt.

Doch so einfach möchten wir uns das ganze bloß nicht machen. Nach dem Motto “Warum einfach, wenn es auch kompliziert geht?” überdenken wir die offensichtlichen Nachteile der simplen, ersten Idee:

  1. In erster Linie wäre die Aufgabe so viel zu einfach. Der Reiz des Unmöglichen geht verloren!
  2. In zweiter Linie sind wir sparsame Menschen und sehen sofort, dass bei der trivialen Lösung sehr oft multipliziert wird. Genauer betrachtet, stellen wir fest, dass in einer Reihe wie (2 3 4 5 0 5 5 2 3) genau 20 mal eine Multiplikation durchgeführt wird, ohne dass ein Produkt größer als 0 herauskommt.

Ok, das sind uns Nachteile genug, um die Lösung nochmal zu überdenken.

Schauen wir uns einen Ausschnitt aus der ersten Ziffernreihe an und veranschaulichen uns, wie die Produkte gebildet werden:

624919225119674426574742355349194934
62491
_24919
__49192
___91922
...

Was erkennen wir daraus?

  1. Zuerst muss ein reguläres Produkt aus fünf Ziffern gebildet werden.
  2. Das nachfolgende Produkt besteht zu einem Großteil aus den Ziffern seines Vorgängers. Lediglich die erste Ziffer entfällt und eine neue kommt hinzu.

Diese Erkenntnisse können wir uns nun zu Nutze machen, indem wir vom Vorgänger stets die erste Zahl dividieren und die nächste multiplizieren! Dadurch haben wir die Anzahl an Rechenoperationen halbiert.

Da der neue Vorschlag nun neben der Multiplikation auch eine Division aufweist, müssen wir zusätzliche Vorsicht walten lassen, denn durch Null teilen ist verboten.

Nach dem Motto “Vorbeugen ist besser als Bekämpfen” sieht jeder ein, dass das Problem mit der Division durch Null nicht auftreten kann, wenn keine Vorgänger null sind, also kein Quintett eine Null enthält. Das realisieren wir folgendermaßen:

  1. Solange keine Null auftritt, die zur Bildung eines neuen Produkts nötig wäre, kann der bisher beschriebene Algorithmus durchgeführt werden.
  2. Sobald eine Null auftritt, wird die Bildung des Quintetts abgebrochen. Danach wird versucht, ein neues Quintett aus den fünf Ziffern nach der Null zu bilden. Sollte hierbei wieder eine Null vorkommen, so wird der Vorgang wieder abgebrochen und ein neues Quintett mit den Ziffern nach dieser zweiten Null gebildet.

Was haben wir damit erreicht? In erster Linie teilen wir nie wieder durch Null und in zweiter Linie werden kein Quintett mit einer Null gebildet und somit diese unnötigen Multiplikationen eingespart.

Damit sind wir erst einmal zufrieden. Wie das in Python-Code aussieht, steht im folgenden Abschnitt.

Problemlösung

Neben den rein mathematischen Schwierigkeiten bei dem 8.Problem, treffen wir noch auf ein rein programmiertechnisches Problem, nämlich dem Import der gegebenen Zahl. Ich habe mich dafür entschieden, die Zahl von der Projecteuler-Webseite in eine einzelne Datei (data.dat) zu kopieren und im Python-Programm nur die Datei zu importieren. Dabei bietet es sich an, die Zeilenumbrüche zu ignorieren und die ganze Zahl in einem eindimensionalen Numpy-Array zu speichern.

Der langen Rede kurzer Sinn, heute mal am Stück:

import numpy as np
import time as t
fileO =  open('data.dat','r')
peData = fileO.read()
def create_long_array(data):
    fdata = np.array([])
    
    print("Following data will be red:")
    print(data+"\n")
    for lines in data:
        for item in lines:
            if (item != "\n"):
                fdata = np.append(fdata,float(item))
    return fdata
def search_greatest_product(data,N):
    Ndata = len(data)
    print("%i values will be checked!" %Ndata)
    print("Product interval: %i\n" %N)
    greatest = 1
    for i in range(0,N):
        greatest = greatest * data[i]
    greater = greatest
    
    i = N
    while (i <= Ndata-1):
        
        factor = data[i]
        if (factor == 0):
            j = 1
            k = i
            greater = 1
            
            while ((j <= N) & (k<=Ndata-N)):
                k = i + j
                factor = data[k]
                if (factor == 0):
                    j = 1
                    i = k
                    greater = 1
                else:
                    greater = greater * data[k]
                    j = j + 1
            i = i+j-1
        else:
            greater = greater / data[i-N] * data[i]
        if (greater > greatest):
            print("Found greater product: %i - %i" %(greatest, greater))
            greatest = greater
        i = i + 1
    return greatest
    
fdata = create_long_array(peData)
t0 = t.time()
greatest = search_greatest_product(fdata,5)
tn = t.time()
print("\nFound solution: %i in %.15f seconds!" %(greatest,tn-t0))

Wie elegant die Realisierung des Lösungsvorschlags ist, kann ich als Anfänger nicht wirklich beurteilen. Das Gute an dem gesamten Konzept ist auf jede Fall, dass beliebige Zahlen eingegeben werden können. Es wird immer das größte Produkt der N aufeinander folgenden Zahlen gefunden.

Lösungsanalyse

Wird das vorgeschlagene Programm auf das 8.Projecteuler-Problem losgelassen, so liefert es folgende Ausgabe in der Konsole:

Following data will be red:
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
1000 values will be checked!
Product interval: 5
Found greater product: 882 -> 1764
Found greater product: 1764 -> 6048
Found greater product: 6048 -> 15552
Found greater product: 15552 -> 16128
Found greater product: 16128 -> 18144
Found greater product: 18144 -> 40824
Found solution: 40824 in 0.022379159927368 seconds!

Mit diesem Ergebnis bewegen wir uns erwartungsgemäß in den Grenzen, die von Projecteuler vorgegeben sind und haben auf Anhieb die richtige Zahl gefunden.

Schlusswort

Wahrscheinlich merken die Leser schon an der Länge der Artikels, dass es mir viel Spaß bereitet hat, dieses Problem zu lösen, obwohl es eher eines von den einfacheren Problem war. Wie auch immer, es ist gelöst und vielleicht auf einem nicht ganz konventionellen Wege.

Andere Lösungsvorschläge in den Kommentaren, oder Aussagen zu meinem Lösungsvorschlag sind wie immer sehr willkommen.

Kommentar absenden

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind markiert *

Du kannst folgende HTML-Tags benutzen: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>