Performance von Problem 30 bei Project Euler

[ospubis]

Hallo,

hin und wieder schaue ich mir die Probleme bei http://projecteuler.net/ an und versuche die zu lösen. Das Problem 30 verlangt, dass alle Zahlen gefunden werden, die gleich der Summe ihrer fünften Potenzen sind. Also beispielsweise ist 4150=4^5+1^5+5^5+0^5. Ich habe das auf zwei verschiedenen Wegen gelöst. Die erste untenstehende Lösung ist etwa dreimal so schnell wie die zweite. Seht ihr bei den Lösungen eventuell noch mehr Potenzial zur Verbesserung?

Lösung1:

Code: Alles auswählen

potenzen = []
for i in xrange (10):
    potenzen.append(i**5)

print potenzen
zahlen = []
for i in xrange (4):
    for j in xrange (10):
        for k in xrange (10):
            for l in xrange (10):
                for m in xrange (10):
                    for n in xrange (10):
                        summe = potenzen[i] + potenzen[j] + potenzen[k] + potenzen[l] + potenzen[m] + potenzen[n]
                        zahl = 100000*i + 10000*j + 1000*k + 100*l + 10*m + n

                        if summe > zahl or zahl > 354295:
                            break

                        if zahl == summe and zahl > 1:
                            print zahl

Lösung2:

Code: Alles auswählen

def zahlliste (n):

    zahlen = []
    while n > 0:
        letzte_stelle = n % 10
        zahlen.append(letzte_stelle)
        n -= letzte_stelle
        n /= 10

    zahlen.reverse()
    return zahlen

max_number = 6*9**5
for i in xrange(2,max_number+1):
    a = zahlliste(i)
    summe = 0
    for j in xrange(len(a)):
        summe += a[j]**5

    if summe == i:
        print summe

[rads]

Summe = (Zahl^(Exp+1)-1)/(Zahl-1)

oder ist es schon wieder so spät, das ich wieder spinne?
http://de.wikipedia.org/wiki/Geometrische_Reihe

[BlackJack]

@ospubis: Du schreibst teilweise etwas umständliches Python. Zum Beispiel ist der Zugriff über den Index im zweiten Programm unnötig, weil Du direkt über die Elemente von `a` iterieren könntest.

Das umdrehen der Zahlenliste ist unnötig weil die Reihenfolge bei der anschliessenden Addition der Werte keine Rolle spielt.

In der ``while``-Schleife kann man sicher Gebrauch von der `divmod()`-Funktion machen.

Und warum berechnest Du die Potenzen nicht in einer Tabelle wie im ersten Programm? Den Inhalt der ``for``-Schleife kann man letztendlich auf diese beiden Zeilen reduzieren:

Code: Alles auswählen

    if sum(potenzen[j] for j in zahlliste(i)) == i:
        print summe

Eventuell bringt auch der erste Ansatz etwas wenn man ihn rekursiv formuliert und abbricht sobald die Bedingung nicht mehr erfüllt werden kann. Da kommt es dann aber darauf an, ob die Einsparung von nichtverfolgten Abzweigungen die Kosten des rekursiven Aufrufs überwiegen.

[BlackJack]

@rads: Ich mag jetzt auch nicht mehr so viel nachdenken, aber ist bei der Formel der Exponent nicht eine Laufvariable, bei diesem Problem hier aber bei jedem Summanden konstant!?

[rads]

@Blackjack

ja wir sollten Feierabend machen, aber ich habe gerade händisch nachgerechnet

(Zahl^(Exp+1)-1)/(Zahl-1) == Zahl^0+Zahl^1+...+Zahl^Exp
Die Formel geht halt bei zahl^0 los, aber das könnte man ja mit -2 anpassen.

Kann sein das ich die Aufgabenstellung falsch verstanden habe, aber ich dachte genau das wollen wir

ps. Exp wäre in diesem Fall 5

[ospubis]

Danke für eure Hinweise. Ich habe die Ideen von Blackjack mal umgesetzt. Jedoch wird das Programm nicht wesentlich schneller. Das Problem liegt whs. im Zerlegen der Zahl.

Wie könnte ich das erste Programm verbessern, dass ich nicht die geschachtelten Schleifen verwende? Ich finde das irgendwie hässlich.

[BlackJack]

@rads: Der Exponent soll bei allen Summanden gleich sein, nämlich 5. Zahl hingegen kann an jeder Stelle ein beliebiger Wert zwischen 0 und 9 sein.

[rads]

@BlackJack Oh jetzt verstehe ich, müsste ich in meinem Papula schauen, gibts bestimmt auch eine Reihe. Natürlich habe ich den jetzt nicht dabei. Aber danke

[pillmuncher]

Wie könnte ich das erste Programm verbessern, dass ich nicht die geschachtelten Schleifen verwende? Ich finde das irgendwie hässlich.

Ich auch. Also so:

Code: Alles auswählen

data = ([(i*10**j, i**5) for i in xrange(10)] for j in xrange(6))

for each in product(*data):
    vs, ps = zip(*each)
    n = sum(vs)
    if n == sum(ps) > 1:
        print n

Nicht, dass die erst Zeile irgendwie schön wäre :K

[BlackJack]

@pillmuncher: Schön kompakt, aber ein bisschen langsam

Das läuft bei mir 2.66 Sekunden. Eine selbstgeschriebene rekursive Lösung schafft's hier in 0.76 Sekunden. Das Abbrechen bei Zweigen die kein Ergebnis bringen können, bringt anscheinend tatsächlich etwas. Aber selbst ohne diese Optimierung läuft's nur 1.25 Sekunden lang.

Dafür ist es länger und hässlicher.

Edit: Die Lösung nach C portiert -- der C64 braucht ca. 18 Minuten und 12 Sekunden.