>>50604Meinetwegen kannst du den Spoiler weglassen. Anders als bei normalem Text, muss man sich in Kode sowieso erst reinlesen. Da ist das unnötig.
Ich habe auch mal geguckt, ob man das entkäfern kann, aber dem Faden auf Meta nach zu urteilen, wird das keiner entgegennehmen.
>>50214Erstmal ein paar Bemerkungen zu deinem Kode:
> stringnum = str(number)
Das scheint eine einfache Sache zu sein, aber Typumwandlungen haben versteckte Kosten. Mit str(165) etwa wandelst du unter der Haube ein hexadezimales A5 in 31 36 35 um. Ich weiß nicht, wie das in Püthon implementiert ist, aber vermutlich wird er da dreimal teilen. Gerade wenn du das in jedem Schleifendurchlauf ausführst, kommt da Einiges zusammen. Wenn das in deinem Programm andererseits nur ein oder wenige Male ausgeführt wird, kannst du das ruhig nehmen, weil das vermutlich eher verstanden wird.
> for i in range(len(stringnum))
Du brauchst hier nur die Hälfte der Länge, sonst prüfst du die Stellen doppelt.
for i in range(len(stringum) // 2)
Der Doppelschrägstrich ist hier wichtig, weil
range eine ganze Zahl haben möchte.
> if stringnum[i-1] != stringnum[-i]
Du vergleichst hier zuerst (mit
i = 0) die letzte Stelle mit der nullten und in der nächsten Iteration (
i = 1) die nullte mit der letzten Stelle (also genau andersum). Zumindest lesbarer wäre:
if stringnum[i] != stringnum[-i-1]
> for j in range(Highest_Possible_3digit-100):
Die Konstante müsstest du normalerweise in einem Kommentar begründen. Warum soll die Schleife gerade nach 898 Durchläufen enden?
Okeh, mittlerweile raff ich's, wegen der Dreistelligkeit. Kommentar wäre hier angebracht. Jemand anders guckt vielleicht nicht solange auf deinen Kode. ;)Meine LösungIch habe wieder eine effizientere Implementierung schreiben können.
Die Effizienzsteigerung ist sogar größer als bei >>50257, wobei du in derselben Zeit zwei weitere Aufgaben erledigt hast. Einholen werde ich dich so sicher nicht, aber ich habe halt Spaß daran, alles zu zerdenken.. Die Idee ist im Grunde die: Ich erzeuge mir Palindromzahlen nach folgendem Muster:
999999
998899
997799
...
Für jede davon gucke ich, ob ich ein ganzzahliges Faktorenpaar (wie (91; 99) für die 9009 im Beispiel) finde. Ich prüfe aber nicht alle möglichen Faktoren von 99..x, sondern nur die „sinnvollen“.
Die Palindromzahlen erzeuge ich ganz billig: Ich nehme die erste Hälfte der Stellen und spiegele sie auf die zweite. Dafür brauche ich eine Funktion, um Zahlen zu spiegeln (idealerweise ohne Typumwandlung, s.o.):
def spiegelzahl(n):
r = 0
while n != 0:
r *= 10
r += n % 10
n //= 10
return r
Also spiegelzahl(48) = 84 und spiegelzahl(123) = 321 usw. Das kommt im Generator palindromzahl zum Einsatz:
def palindromzahl(s):
'Erzeuge Palindromzahl mit 2*s Stellen in absteigender Reihenfolge.'
for v in range(10 ** s - 1, 0, -1): # v = vordere Hälfte der Zahl
p = v * 10 ** s + spiegelzahl(v)
v -= 1
yield int(p)
Das
v ist für zwei Stellen gleich 99. Mit
> v * 10 ** n
verschiebt man die 99 um zwei Stellen nach links (9900) und addiert zum Schluss die Spiegelzahl. Auf diese Weise bekommen wir die Palindrome auch in streng absteigender Reihenfolge, was später wichtig sein wird.
Meinen größten Geistesblitz hatte ich bei der Faktorenzerlegung. Beim Beispiel ist die Lösung ja zu finden, indem man nur den ersten Faktor bis 91 dekrementiert und die 99 in Ruhe lässt. Was ist aber, wenn der zweite Faktor dieses Mal nicht gerade 999 ist, sondern der sich auch ändert? Wie finde ich den, wenn ich Teilen vermeiden möchte?
Man kann sich relativ fix eine Tabelle wie Bildverwandt zusammenstellen, wo man die Produkte für alle Faktorenkombinationen einträgt. Erstmal fällt auf, dass man sich die Hälfte sparen kann, weil 98 * 99 == 99 * 98 usw.
Wenn du das mit dem Kode vergleichst: li ist der linke Faktor, re der rechte, und p ist der Spalteninhalt.Dann wollte ich eine Reihenfolge in das Ganze bringen. Mein Palindromzahlgenerator arbeitet ja auch streng absteigend. Es sollte ja klar sein, dass die Produkte kleiner werden, je mehr man sich auf der Achse von der 99 wegbewegt. Tatsächlich folgen die Zahlen mit abnehmendem Wert den Gegendiagonalen von unten links nach oben rechts (im Bild rot nachgezeichnet).
Den roten Gegendiagonalen kann man (ohne teilen oder malnehmen zu müssen) nach rechts oben folgen, indem man den linken Faktor abzieht und den rechten addiert. Genauso kann man sich in der Tabelle fortbewegen: Willst du eine Zeile nach unten, schaust du in die Spaltenüberschrift und ziehst die Zahl von dem Produkt in der Spalte ab.
Wenn du oben rechts angekommen bist, setzt du einfach wieder auf die Hauptdiagonale zurück (gelbe Markierung). Die folgt einer Schlängellinie, wofür man wechselweise einmal nach rechts und einmal nach unten muss. Ich habe mir hier mit diagli und diagre ausgeholfen. Das geht bestimmt schöner.
def maxpalindrom(s):
'Finde größte Palindromzahl mit zwei s-stelligen Faktoren'
li = diagli = diagre = limax = 10 ** s - 1
p = diagre * diagli
z = palindromzahl(s)
k = next(z) # Kanditat
while k != p:
if li == limax: # auf die Hauptdiagonale zurücksetzen
if diagli == diagre:
diagre -= 1
else:
diagli -= 1
li = diagli
re = diagre
p = li * re
else: # der Gegendiagonale nach oben rechts folgen
p -= li
re -= 1
p += re
li += 1
if p < k:
try:
k = next(z)
except StopIteration:
print(f'Für {s} Stelle(n) gibt es das wohl nicht.')
return
print(p, li, re)
Wir haben jetzt Palindrome und Produkte der Größe nach sortiert vorliegen. Wir gehen also die Faktorkombinationen nach dem erwähnten Zickzack-Muster ab und vergleichen sie mit dem aktuellen Palindromzahlkanditaten
k. Wenn
p kleiner als
k wird, wissen wir, dass es mit diesem Kandidaten nichts mehr wird, denn alle folgenden
p werden ja kleiner sein. Also tauschen wir ihn durch den nächsten Kandidaten aus, solange bis wir einen gefunden haben (oder uns die Palindromzahlen ausgehen, wie bei maxpalindrom(1)).