/b/ – Passierschein A38
„Migranten müssen EC und Seine Werte akzeptieren“

Jetzt in Radio Ernstiwan:


Hail Odin! von Christenklatscher666

M3U - XSPF


Datei (max. 4)
Zurück zum
(Optional)
  • Erlaubte Dateiformate (Maximalgröße 25 MB oder angegeben)
    Bilder:  BMP, GIF, JPG, PNG, PSD   Videos:  FLV, MP4, WEBM  
    Archive:  7Z, RAR, ZIP   Audio:  MP3, OGG  
    Dokumente:  DJVU (50 MB), EPUB, MOBI, PDF (50 MB)  
  • Vor dem Posten bitte die Regeln lesen.
  • /b/ ist nicht gleich /b/. Bitte versucht euch an vernünftigen Diskussionen.

Nr. 50084
75 kB, 200 × 243
Mathe- und Programmierernsts aufgepasst!

Ich bin gerade auf Projekt Euler gestoßen. Es werden mathematische Probleme gestellt, die von dir gelöst werden wollen! Dafür muss man Programmieren.

https://projecteuler.net/about
Die Registrierung geht schnell und braucht keine Mehl oder sowas.

Ich werde jeden Tag einen Pfosten zur Diskussion eines Problemes erstellen, bis ich nicht mehr weiterkomme :3 Die ersten Probleme sahen auf jeden Fall machbar aus. Viel Spaß!
>>
Nr. 50085
395 Bytes, 1 Datei
https://projecteuler.net/problem=1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.


Meine angehangene Lösung besteht aus fünf Zeilen. Das geht sicherlich auch schneller, aber ich wollte es mir nicht kompliziert machen! Ein gutes Einsteigerproblem.
>>
Nr. 50090
635 kB, 720 × 540
Ohne deinen Vorschlag angeschaut zu haben hier erstmal meiner (in PHP oder so):

$summe = 0;

for ($count = 0; count <= 1000; count++) {

if (($count % 3 == 0) || ($count % 5 == 0) {
$summe = $summe + $count
}
}

echo $summe


Man könnte noch verbessern indem man den Zähler bei 3 starten lässt und man könnte Stilpunkte holen indem man statt der Modulo-Division bei der 3 erst die Quersumme bildet und prüft ob die Division dann ganzzahlig ist, und bei der 5 statt der Modulo-Division prüft ob die letzte Ziffer eine 5 oder eine 0 ist, beides könnte sogar schneller sein, besonders bei größeren Zahlen.
>>
Nr. 50092 Kontra
52 kB, 700 × 512
Okeh, ich sehe du hast fast die identische Lösung :3 Und wenn ich mir meinen Code (>>50090) noch mal anschaue finde ich einen Syntax- und einen Inhaltsfehler. Die anzuprangern überlasse ich den Folgepfostierern.
>>
Nr. 50094 Kontra
11 kB, 221 × 228
>>50092
Sagte ich "ein" Syntaxfehler? Ich meinte natürlich drei. Wer bietet mehr?
>>
Nr. 50097
>>50090
Da ich kein PHP kann, nur ein Inhaltsfehler:

for ($count = 0; count <= 1000; count++) {

Es muss kleiner sein, nicht kleiner gleich (hatte erst den gleichen Fehler :3 )
>>
Nr. 50107
3,2 MB, 1280 × 720, 0:21
11 kB, 412 × 168
>>50097
Richtig! Und sagte ich 3 Syntaxfehler? Ich meinte natürlich 5 YEEEEAAAAAAH!
>>
Nr. 50108
412 Bytes, 1 Datei
https://projecteuler.net/problem=2



Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.


Die Schwierigkeit hier lag darin, die Fibonacci-Zahlen zu generieren, das sollte aber für jemanden, der schonmal mit Schleifen gearbeitet hat, kein Problem sein. Ich hatte es erst kompliziert mit einer Unterfunktion gemacht, mich dann aber doch für eine einfachere, verständlichere Variante entschieden.
>>
Nr. 50148
519 Bytes, 1 Datei
https://projecteuler.net/problem=3

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?


Okeh, hier musste ich das erste Mal googlen. Traurig! ;_; Hatte mich von der Idee hier ( https://math.stackexchange.com/questions/389675/largest-prime-factor-of-600851475143 ) inspirieren lassen.
Von unten Anfangen, den kleinsten Teiler finden, dann die Ursprungszahl verkleinern und wiederholen.

Das war schon ziemlich kompliziert, habe etwas Sorge, dass es in naher Zukunft schon nicht mehr lösbar für mich wird ;_; Aber mal sehen, heute ist ja erstmal geschafft!
>>
Nr. 50170
89 kB, 1280 × 720
>>50108
Das wäre dann sowas wie:


$summe = 0;
$letztesElement = 1;
$vorletztesElement = 1;
$limit = 4000000;

while ($summe < $limit) {

$neuesElement = $letztesElement + $vorletztesElement;

if ($summe % 2 == 0) {
$summe = $summe + $neuesElement;
}

$vorletztesElement = $letztesElement;
$letztesElement = $neuesElement;
}

echo $summe;


Diesmal garantiert ohne Inhalts- und Syntaxfehler, g-ganz bestimbt!

>>50148
Bei dem habe ich null Ahnung. Könnte auch gurgeln, aber das ist einfach zu mühsam
>>
Nr. 50171
summe = 0
LE = 1
VLE = 1

NE = LE + VLE = 2

summe % 2 == 0? 0%2=0? Ja
-> summe = 0 + 2 = 2

VLE = LE = 1
LE = NE = 2

NE = LE + VLE = 3

summe % 2 == 0? 2%2=0? Ja
-> summe = 2+3 = 5

Liebe Grüße, dein Manuel
>>
Nr. 50172
>>50171
Danke Manuel. Da muss natürlich

if ($neuesElement % 2 == 0) {

stehen statt
if ($summe % 2 == 0) {


Aber ansonsten FEHLERFREI!!111einself
>>
Nr. 50186
Ernst wäre auch gerne so klug wie ihr ;___;
>>
Nr. 50214
592 Bytes, 1 Datei
https://projecteuler.net/problem=4

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.


Das hier war auch eher trickreich, aber nach Problem #3 war ich auf Tricks vorbereitet, hatte eine Idee, und habe sie umgesetzt.

Ich denke, die Hauptidee ist, die beiden großtmöglichen dreistelligen Zahlen zu multiplizieren, um herauszufinden, was die größtmögliche Zahl wird. Diese Zahl wird dann immer um 1 verringert und geprüft, ob die entstandene Zahl ein Palindrom ist. Wenn sie es ist, wird überprüft, ob sich die Zahl durch eine dreistellige Zahl teilen lässt, und wieder ein dreistelliger Integer bei raus kommt (der zweite Trick).
>>
Nr. 50257
47 kB, 960 × 640
>>50085
Auf Püthon 3 können wir uns einigen :3

Du hältst in ListOfSums alle Summanden im Speicher, nur um am Ende sums() drüberlaufen zu lassen. Das hat >>50090 besser gemacht, also nimm einfach
summe += i
in deine Schleife.

Das Problem lässt sich sehr viel schneller lösen: 3 + 6 + 9 ist ja dasselbe wie 3 * (1 + 2 + 3) und Summen á la 1 + 2 + 3 usw. musst du nie von Hand (oder mit einer Schleife) ausrechnen, denn dazu gibt es die Gaußsche Summenformel (s. Kode).


from timeit import timeit

def p1_ernst(n):
ls = []

for i in range(n):
if i % 3 == 0 or i % 5 == 0:
ls.append(i)

return sum(ls)

def _gsf(n):
'Gaußsche Summenformel'
# mit // wird ganzzahlig dividiert, das Produkt ist sowieso immer gerade
return n * (n + 1) // 2

def p1_meins(n):
# n//x ist eher eine Schätzung für den größten Summanden
# _gsf(n//5 - 1) funktioniert möglicherweise nicht bei allen n
return 3 * _gsf(n//3) + 5 * _gsf(n//5 - 1) - 15 * _gsf(n//15)

print('p1_ernst(1000): ', timeit('p1_ernst(1000)', setup='from __main__ import p1_ernst'))
print('p1_meins(1000): ', timeit('p1_meins(1000)', setup='from __main__ import p1_meins'))

In der endgültigen Summe aus beiden Reihen hätten wir dann allerdings 15, 30, 45 usw. doppelt drin, weil sie ja Vielfache von 3 und von 5 sind. Deswegen diese 15er-Reihe noch einmal abziehen.

Die Ergebnisse der Zeitmessung als kleiner Ansporn.
p1_ernst(1000): 108.88858116278425
p1_meins(1000): 0.6888215532526374
Mehr als hundert mal so schnell ist schon eine Ansage.

zl;ng Gaußsche Summenformel! Der Rest ist nur Beiwerk.
>>
Nr. 50260
52 kB, 640 × 640
87 kB, 500 × 564
>>50186
>Ernst wäre auch gerne so klug wie ihr ;___;
Bilder relatiert.

>>50257
Ernst, ich knie! Von nun an sollst du unser Sensei sein.
>>
Nr. 50265
>>50257
Jetzt komme ich mir sehr dumm vor :3 An solche mathematischen Tricks habe ich nicht gedacht, aber ja, kühle Lösung!
>>
Nr. 50266
650 Bytes, 1 Datei
https://projecteuler.net/problem=5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?


Ernst fühlt sich clever! Großteil meines Programmes ist das Finden der nötigen Divisoren, danach dann noch hochrechnen und schauen, ob es durch diese teilbar ist.
Alles in allem trotzdem etwas langsam, denke ich, da wird mich Ernst vermutlich wieder schlagen :3
>>
Nr. 50340
401 Bytes, 1 Datei
https://projecteuler.net/problem=6

The sum of the squares of the first ten natural numbers is,
$$1^2 + 2^2 + ... + 10^2 = 385$$

The square of the sum of the first ten natural numbers is,
$$(1 + 2 + ... + 10)^2 = 55^2 = 3025$$

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is $3025 - 385 = 2640$.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.


Ich dachte erst, dass es einen Trick gibt, aber dem war nicht so.
>>
Nr. 50348
>>50266
ohne zu programmieren: sowas wie 11*13*14*15*17*19?
>>
Nr. 50371
87 kB, 980 × 720
>>50260
>Sensei
Hehehehe, danke, Ernst-san. Durch's Erklären lerne ich natürlich auch dazu.

>>50265
>kühle Lösung
Danke, danke. Du sollst dir aber nicht dumm vorkommen. Die kühlen Lösungen kommen von alleine, wenn du dich in den Rechner hineinversetzt:

Stell dir vor, man gibt dir Stift und Papier und sagt: „Summiere mir alle Zahlen von eins bis x.“, dann denkst du doch automatisch: „Krieg ich das nicht einfacher hin?!“

>>50108
Das Paradebeispiel für den Fibonacci findest du in der Python-Doku:

a, b = 0, 1
while a < 10:
print(a)
a, b = b, a + b


https://docs.python.org/3/tutorial/introduction.html#first-steps-towards-programming


Die habe ich erstmal so erweitert, dass sie wie dein Skript funktioniert. Ich wollte aber den „teuren“ Modulo-Operator vermeiden. Teilen braucht von den Grundrechenarten am längsten auf deinem Prozessor. Auf den μCs wie dem Attiny hier im Bild gibt es keine DIV-Instruktion und es muss aufwändig „von Hand“ geteilt werden. Glücklicherweise kommen die geraden Zahlen in regelmäßigen Abständen vor:

2, 3, 5, 8, 13, 21, 34, ...

Die nächstbessere Lösung wäre also, in der Schleife immer bis drei zu zählen. Dann berechnen wir allerdings immer noch alle ungeraden Glieder, die uns nicht interessieren. Schauen wir uns mal nur die geraden Glieder an:

2, 8, 34, 144, 610, ...

Hier muss man herumprobieren, aber die Folge lässt sich ähnlich wie die Fibonacci-Folge aufbauen (s. letzte Zeile hinter dem Komma: Jedes Glied ist das Vierfache seines Vorgängers plus dem Vorvorgänger):

s = 0 # Summe
a, b = 2, 8 # gerade Zahlen der Fibonacci-Folge
while a < n:
s += a
a, b = b, 4 * b + a


Damit komme ich auf dieselbe Antwort wie du. Die Zeitersparnis ist nicht ganz so extrem, aber immerhin halbiert sich die Ausführungszeit. Das ist immer noch sehr gut.
>>
Nr. 50449
539 Bytes, 1 Datei
https://projecteuler.net/problem=7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?


Hier habe ich lange überlegen müssen, als ich mich dann aber hingesetzt habe, und es gecoded habe, war es einfacher.

Ich wusste, dass ich alle Primzahlen bis X brauchte, sonst wüsste ich ja nicht, welche die X-te ist. Das heißt, ich brauchte eine Methode, die möglichst schnell die Primeigenschaft prüft. Da ich glücklicherweise eine Liste erzeugte, die Primzahlen aufzählt, habe ich einfach die zu prüfende Zahl durch jedes Element der Primzahlliste geteilt und geschaut, ob es ordentlich teilt, wenn ja, ist es keine Primzahl. Primfaktorzerlegung sei Dank! :3

"Used_Time" war bei mir 4.670109510421753.
>>
Nr. 50450 Kontra
>>50449
Nachtrag: Ist natürlich nicht schneller mit einem Integer, vermutlich ist die Liste noch nicht lang genug :3
Auch: Man kann sich die Division durch 2 noch sparen, war aber faul!

>>50371
Das ist alles schon sehr clever. Da muss man aber auch erstmal drauf kommen!
>>
Nr. 50492
1021 Bytes, 1 Datei
https://projecteuler.net/problem=8

The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?


War so leicht wie erwartet. Habe ein Sliding Window gemacht, dass einfach über die Zahlen geschoben wurde und das Produkt ausgegeben hat. Nichts weiter optimiert, ganz simpel.

Used_Time: 0.007999897003173828
>>
Nr. 50542 Kontra
>>50492
Ich versuche gerade aufzuholen und finde es etwas müßig zig Zip-Dateien zu öffnen, die dann wenige Zeilen beinhalten. Willst du nicht lieber deine Lösung (ggf. mit Verderber) in den Faden schreiben?

Vielleicht kannst du auch mir zu liebe die Fragestellungen als
> Zitat
einfügen, damit sich das auch ordentlich umbricht.

Ansonsten Viel Erfolg beim Lösen. Bleib dran!
>>
Nr. 50561
25 kB, 405 × 577
>>50148
> Okeh, hier musste ich das erste Mal googlen. Traurig! ;_;
Nein, mach das ruhig öfter. Du willst ja auch etwas dazulernen. Das einzige Tabu wäre für mich, vorher in die Lösung zu schmulen. Aber damit bescheißt man sich ja auch nur selber. Nur falls der Eindruck entsteht, ich wüsste das hier aus dem Kopf: Eigentlich kann ich auch nur alles in die Suchmaschine einhacken und dann die Ergebnisse einigermaßen gut auf das Problem anwenden.

Für dieses Problem jedenfalls habe ich aber erstmal die 13195 auf dem Papier zerlegt. Beim ersten Schritt kann man offensichtlich durch fünf Teilen. Danach musste man probieren.

13195 / 5 = 2639 (<- glatte Zahl)
^Zähler ^Nenner

2639 / 2 = -- (<- keine glatte Zahl)
...
2639 / 7 = 377

377 / 2 = --
...
377 / 13 = 29

29 / 2 = --
...
29 / 29 = 1

Zum Probieren habe ich also für alle möglichen Teiler von 2 aufwärts geschaut, ob eine glatte Zahl herauskommt. Wenn das so war, war die glatte Zahl der neue Zähler. Dasselbe dann in Python:

z = 13195 # Zähler
n = 2 # Nenner
i = 1 # berechnete Teilungen

while n != z:
i += 1
t = z / n # Teilung probehalber
if t.is_integer():
z = t # übernehme glatte Zahl
else:
n += 1 # oder probier weiter

Mit i zählt man 31 Versuche, um auf das Ergebnis 29 zu kommen. Also probiert der Algorithmus stumpf jeden möglichen Teiler durch. Außerdem gibt es noch zwei Extra-Versuche, weil wir n nicht hochzählen, wenn wir eine glatte Zahl gefunden haben, denn Primfaktoren können sich ja auch wiederholen: 125 etwa ist gerade 5 * 5 * 5 oder 9 ist 3². Immerhin können wir davon ausgehen, dass n nicht wieder runtergezählt werden muss oder gar jedes Mal mit n = 2 wieder anfangen müssen.

Möchte man mit möglichst wenig Versuchen enden, könnte damit anfangen, immer nur durch jede zweite Zahl zu teilen, weil wir wissen, dass alle Primzahlen außer 2 ungerade sind. Das würde schon die Hälfte der Versuche einsparen. Tatsächlich ist nach der drei auch keine weitere Primzahl mehr durch drei teilbar (sonst wäre sie ja zusammengesetzt, also 3 * x, und nicht prim) und nach der fünf ist keine mehr dadurch teilbar usw. Wenn du jetzt immer alle Zahlen rausstreichst, die nicht prim sein können, bekommst du das sogenannte Sieb von Eratosthenes:

def primzahl(n): # alle generierten Primzahlen sind kleiner n
p = [] # Liste der gestrichenen Zahlen
i = 2 # laufende Nummer

while i * i < n: # wir laufen bis Wurzel n, ohne jedoch sqrt zu nutzen
if i not in p: # Primzahl i ist noch nicht gestrichen worden
yield i
for j in range(i * i, n, i): # alle Vielfache von i...
p.append(j) # ...herausstreichen
i += 1

Dabei möchte ich auf das kühle yield-Schlüsselwort hinweisen. Damit wird die Funktion nämlich zu einem Generator. Dieses yield funktioniert ähnlich wie return und gibt i (eine gefundene Primzahl) zurück. Generatoren werden etwas anders aufgerufen:

>>> p = primzahl(100)
>>> next(p)
2
>>> next(p)
3
>>> next(p)
5
>>> next(p)
7
>>>

Wir bekommen also immer nur die nächste Primzahl außer wir sagen
list(p)
[/spoiler]. Wir sparen uns also das Berechnen all der Primzahlen, die keine Primfaktoren in 13195 sind!

Mit dem Generator können wir also dafür sorgen, dass im Nenner immer nur eine Primzahl steht. Für 13195 brauchen wir dann 10 statt 31 Versuche. Auch wenn dadurch nicht der Zusatzaufwand für die Primzahlsuche berücksichtigt wird, kann man damit durchaus zufrieden sein.
>>
Nr. 50584 Kontra
>>50542
Ich mache einfach beides! :kühlgesicht:

>>50561
"yield" ist sicherlich praktisch, danke dafür.
>>
Nr. 50602
500 Bytes, 1 Datei
https://projecteuler.net/problem=9
A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.


import time
Starttime = time.time()
TargetSum = 1000
Found = False

for b in range(TargetSum):
for a in range(b):
c = (a*a+b*b)**(1/2)
if c.is_integer() and a+b+c==TargetSum:
Found = int(a*b*c)
if Found:
break
print(Found)
Endtime = time.time()
Used_Time = Endtime-Starttime
[/spoiler]
>>
Nr. 50604
535 Bytes, 1 Datei
Kot im Spoiler klappt nicht ;_;

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.


Meine Variante braucht etwa 30 Sekunden, ist vermutlich zu einfach.
>>
Nr. 50646
35 kB, 414 × 185
>>50604
Meinetwegen 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.

>>50214
Erstmal 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ösung

Ich 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)).
>>
Nr. 50653
Ernst hat im Winter 2011/2012 als Student in Nachtschichten bis Problem 50 oder so gelöst. Manche Probleme fand er bescheuert, da gab es nur die brutal-Gewalt-Lösung. Ernst wird Faden verfolgen und sehen, was Ernst tut, wenn es an das lösen von Diophantine-Gleichungen geht.

PS: Für manche Primzahl-Probleme lohnt sich eine Implementierung des Eratosthenes basierend auf Bitvektoren in Wortbreite. Das ist zwar auch irgendwie brute-Force, aber doch etwas eleganter. Lasst die Finger von Solovay-Strassen und so einem Scheiß.
PPS: Dictionaries sind Magie, Primfaktorzerlegungen auch.
>>
Nr. 50657
320 kB, 600 × 407
>Jemand anders guckt vielleicht nicht solange auf deinen Kode

Kommentare sind extra weggelassen, zur Übung für den Leser :3

Ich merke auf jeden Fall, dass du dir sehr viel Gedanken um jede Aufgabe machst, mir geht es nur darum, sie zu lösen, nicht, es schnell zu tun. Das klappt bisher. Dazu versuche ich, den Code so "allgemein" zu schreiben, dass der für andere Eingaben auch funktioniert (vgl. zum Beispiel Problem 8, welches für andere Zahlenblöcke und Fenstergrößen leicht anpassbar wäre). Ist aktuell alles noch nicht relevant, aber mal schauen.

Auch: Du bist mir vermutlich auch mathematisch viel, viel weiter voraus Kacknerd. Ich denke, da werde ich einige dicke Probleme kommen, wenn ich schonmal ein paar Aufgaben aus der Zukunft anschaue :3

Danke auf jeden Fall für deine ausführlichen Pfosten, sind immer interessant zu lesen!

>>50653
>Lasst die Finger von Solovay-Strassen und so einem Scheiß.
Bild relatiert! Ich hoffe, ich brauche so einen Zauberkram noch länger nicht :3
>>
Nr. 50660
2 kB, 1 Datei
https://projecteuler.net/problem=11

In the 20×20 grid below, four numbers along a diagonal line have been marked in red.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?


Ich hatte befürchtet, dass der Rohgewaltsansatz hier nicht funktioniert, aber das war nicht der Fall, lief recht schnell durch. In meiner Lösung hätte ich mir einige Kalkulationen sparen können, aber ich war zu faul :3

Zeile1 = "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08"
Zeile2 = "49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00"
Zeile3 = "81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65"
Zeile4 = "52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91"
Zeile5 = "22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80"
Zeile6 = "24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50"
Zeile7 = "32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70"
Zeile8 = "67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21"
Zeile9 = "24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72"
Zeile10 ="21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95"
Zeile11 ="78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92"
Zeile12 ="16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57"
Zeile13 ="86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58"
Zeile14 ="19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40"
Zeile15 ="04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66"
Zeile16 ="88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69"
Zeile17 ="04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36"
Zeile18 ="20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16"
Zeile19 ="20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54"
Zeile20 ="01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48"

NumToMult = 4
Zeilen = [Zeile1, Zeile2, Zeile3, Zeile4, Zeile5, Zeile6, Zeile7, Zeile8, Zeile9, Zeile10, Zeile11, Zeile12, Zeile13, Zeile14, Zeile15, Zeile16, Zeile17, Zeile18, Zeile19, Zeile20]
EmptyZeile = []
for i in range(len(Zeile1.split(" "))+2*(NumToMult-1)):
EmptyZeile.append(0)
Grid = [EmptyZeile, EmptyZeile, EmptyZeile]
for Zeile in Zeilen:
ZeileInt = [0, 0, 0]
SplitZeile = Zeile.split(" ")
for StringZahl in SplitZeile:
ZeileInt.append(int(StringZahl))
for i in range(NumToMult-1):
ZeileInt.append(0)
Grid.append(ZeileInt.copy())
for i in range(NumToMult-1):
Grid.append(EmptyZeile)

Debug = False
if Debug:
for i in range(len(Grid)):
for Element in Grid[i]:
if Element>=10:
print(Element, end= " ")
else:
print(" " + str(Element), end= " ")
print()
# Grid[x][y] = Zeile X, Spalte Y
# 3,3 -> 23,23
Highscore = 1
for i in range(NumToMult-1, len(Grid[0])-NumToMult+1):
for j in range(NumToMult-1, len(Grid)-NumToMult+1):
Up = Grid[i][j]
Down = Grid[i][j]
Left = Grid[i][j]
Right = Grid[i][j]
D1 = Grid[i][j]
D2 = Grid[i][j]
D3 = Grid[i][j]
D4 = Grid[i][j]
for k in range(1, NumToMult):
Up = Up * Grid[i-k][j] # Up
Down = Down * Grid[i+k][j] # Down
Left = Left * Grid[i][j-k] # Links
Right = Right * Grid[i][j+k] # Rechts
D1 = D1 * Grid[i-k][j-k] # Oben Links
D2 = D2 * Grid[i+k][j+k] # Unten Rechts
D3 = D3 * Grid[i-k][j+k] # Oben Rechts
D4 = D4 * Grid[i+k][j-k] # Unten Links
NewScores = [Up, Down, Left, Right, D1, D2, D3, D4]
if max(NewScores)>Highscore:
Highscore = max(NewScores)
print(Highscore)
>>
Nr. 50665
>>50660
Öh, finde das irgendwie umständlich. schreibst doch einfach

grid = [
[08, 02, 22, usw],
[49, 49, 99, usf],
etc
]

du müsstest dazu nur in den Zeilen das Leerzeichen durch Komma und Leerzeichen ersetzen und alle Zeilen mit eckigen Klammern umfassen. Das geht mit Editor-Magie sicher schneller, als das zu schreiben, was du da geschrieben hast.

>>50646
Integer-Division braucht auf modernen x86-CPUs so ca. 10 Zyklen, Durchsatz von so ca. 4. Es lohnt selten, das wegzuoptimieren.
>>
Nr. 50666
>>50660
Ein Gedanke:

wenn man das mit numpy machst, kann man einfach zeilenweise von links nach rechts drüber gehen, rotieren 90, zeilenweise von links nach rechts drüber gehen (ist dann von oben nach unten), rotieren 90, zeilenweise links nach rechts drüber gehen (ist dann rechts nach links), rotieren 90, zeilenweise links nach rechts drüber gehen (ist dann von unten nach oben)

Noch ein Gedanke: man muss sich da Produktberechnungen sparen können. Da wird ziemlich viel doppelt berechnet. Bernst wird nach der Weide drüber hirnen.
>>
Nr. 50671
>>50665
>Öh, finde das irgendwie umständlich.
War es, aber
>Dazu versuche ich, den Code so "allgemein" zu schreiben, dass der für andere Eingaben auch funktioniert
Wenn die Eingabe erst bearbeitet werden muss, zählt es nicht! :3

>>50666
Mit Modulen lässt sich da einiges leichter machen (manche Probleme würden damit zu einem Einzeiler werden), aber die Herausforderung ist ja, es ohne Module zu machen.
>>
Nr. 50831
25 kB, 537 × 457
>>50653
>Solovay-Strassen(-Test)
>probabilistischer Primzahltest, praktisch Monte-Carlo
Oho, was da wohl noch alles kommen mag? Zur Zeit wäre das wohl wie mit Kanonen auf Spatzen zu schießen.

Kannst du zu der Magie von dict() elaborieren?

>>50657
>weit voraus
Nein, ich verbrenne einfach nur wahnsinnig viel Zeit dafür. Vor diesem Faden wusste ich auch nicht, dass mir das soviel Spaß macht (danke dafür). Ehrlich gesagt, versuche ich jedes Mal eine möglichst kurze Antwort zu geben und dann sind im Nu wieder drei Stunden rum.

>>50348
Guter Ansatz. Weißt du die Lösung und wolltest sie aus Gründen nicht pfostieren oder ist das eine Frage, weil du's nicht genau weißt?


Wir suchen das kleinste gemeinsame Vielfache für Fakultät n. Das kgV(2, 3) ist genau 3! = (1 ⋅ ) 2 ⋅ 3, also 6. Das kgV(2, 3, 4) ist aber 12, und nicht 4! = 2 ⋅ 3 ⋅ 4 = 24. Warum?

Wir haben mit vier eine zusammengesetzte Zahl, also zweimal zwei. Wir betrachten also stattdessen die Reihe 2 ⋅ 3 ⋅ (2⋅2).

Jede durch vier teilbare Zahl ist auch durch zwei teilbar. Wir können also einmal eine zwei herauskürzen. Dann bleibt 3 ⋅ 2² = 12. Wir konnten also die zwei hoch eins sozusagen einsparen.

Dasselbe gilt für alle größeren Zahlen:
1) Wir zerlegen die zusammengesetzten Zahlen in die Primfaktoren. Wir haben dann eine Reihe wie 2 ⋅ 3 ⋅ 2² ⋅ 5 ⋅ (2⋅3).
2) Für jede Zahl in dieser Reihe behalten wir nur die mit dem höchsten Exponenten, weil sie ja alle die mit geringeren Exponenten sozusagen beinhalten. Der kgV(1..6) ist dann 2² ⋅ 3 ⋅ 5 = 60.

Was ist also der kgV(1..7)?
[spoiler]
2 ⋅ 3 ⋅ 4 ⋅ 5 ⋅ 6 ⋅ 7 => im Primzahlen zerlegen
2 ⋅ 3 ⋅ 2² ⋅ 5 ⋅ (2⋅3) ⋅ 7 => nur höchste Exponenten behalten
2² ⋅ 3 ⋅ 5 ⋅ 7 = 420 = kgV(1..7)


Der kgV(1..8)?

2 ⋅ 3 ⋅ 4 ⋅ 5 ⋅ 6 ⋅ 7 ⋅ 8
2 ⋅ 3 ⋅ 2² ⋅ 5 ⋅ (2⋅3) ⋅ 7 ⋅ 2³
2³ ⋅ 3 ⋅ 5 ⋅ 7 = 840 = kgV(1..8)


Zum Überprüfen: kgV(1..10)?

2 ⋅ 3 ⋅ 4 ⋅ 5 ⋅ 6 ⋅ 7 ⋅ 8 ⋅ 9 ⋅ 10
2 ⋅ 3 ⋅ 2² ⋅ 5 ⋅ (2⋅3) ⋅ 7 ⋅ 2³ ⋅ 3² ⋅ (2⋅5)
2³ ⋅ 3² ⋅ 5 ⋅ 7 = 2520 = kgV(1..10)

[/spoiler]

Beim Schreiben der Python-Lösung ist mir gerade aufgefallen, dass die Exponenten ja immer nur so groß sein können, dass die Potenz gerade kleiner oder gleich n ist (zumindest klappt's bei allen Beispielen bisher). Damit ist die Lösung letztlich so einfach, dass man sie von Hand in den Interpretierer eintippen kann:


>>> r = p = 1 # Resultat, Produkt
>>> for i in 2, 3, 5, 7, 11, 13, 17, 19: # Primzahlen kleiner n
... while p * i <= 20: # n = 20
... p *= i
... r *= p
... p = 1
...
>>> print(r)
232792560


Man kann das mit dem Primzahlgenerator aus >>50561 zu einer Funktion für beliebige n umschreiben. Man muss dann aber die Funktion so umschreiben, dass alle Primzahlen bis n und nicht nur bis √n berechnet werden.
>>
Nr. 50833
>>50665
>Es lohnt selten, das wegzuoptimieren.
Ich steck da nicht so ganz in der Materie. Anscheinend gelten die zehn Zyklen für den Zen+ irgendwas. Wenn man nicht gerade Zocker oder Simulant ist, hat man nicht selten auch heute einen Core Duo oder AthlonXP oder so, weswegen man vermutlich mit Windows 11 auch diesen Anforderungsstunt gepullt hat.

Das ist wohl auch, warum die Rechner mit der Zeit immer lahmer werden. Also die Geräte altern schon. Aber dann hast du da auch Entwickler, die gar nicht mehr mitschneiden, wie schlecht ihr Algorithmus läuft, weil DIV auf ihrem neuesten iCore Hufflepuff 9000 nur noch drei Zyklen braucht.

Vielleicht meintest du aber, es gäbe da noch lohnendere Ziele, von wegen: „Berechnungen sind kostenlos, die Datenschubsereien sind das eigentliche Übel“ und so? Würde ich verstehen.

Wenn man allerdings schon weiß, wie's effizienter läuft, sollte man's natürlich auch umsetzen. Im schlimmsten Fall läuft's dann auch auf dem Zen++ schneller.
>>
Nr. 50863
>>50671
>Mit Modulen lässt sich da einiges leichter machen (manche Probleme würden damit zu einem Einzeiler werden), aber die Herausforderung ist ja, es ohne Module zu machen.
Die Idee an Project Euler ist doch, durch Einsichten in die mathematischen Hintergründe Lösungen zu finden, die schnell genug laufen. Nicht die Implementierung "zu Fuß". Dafür ist Python sowieso die falsche Sprache.

>Dazu versuche ich, den Code so "allgemein" zu schreiben, dass der für andere Eingaben auch funktioniert
Hmm. Ok. Es ist kein Schaden, zu abstrahieren und Teil-Lösungen so zu implementieren, dass sie weiterverwendet werden können. Primzahlen sind ein Thema. Aber Problemeigenschaften sollten zur effizienten Problemlösung eingesetzt werden. Macht man das nicht, wird es teuer, weil man viele Zigaretten rauchen muss, bis es durchgelaufen ist.

Ich versuche mal, meine Idee zu Problem 11 auszuformulieren.

Mit einer Zeile folgendes tun:

Z[1], Z[2], Z[3], Z[4],
* Z[0], Z[1], Z[2], Z[3], ...
====================================================
Y:= Z[0]*Z[1], [Z1]*Z[2], Z[2]*Z[3], Z[3]*Z[4], ...

und dann


Y[2], Y[3], ...
* Y[0], Y[1], ...
=====================================================
X:= Y[0]*Y[1], Y[1]*Y[2]
= Z[0]*Z[1]*Z[2]*Z[3], Z[1]*Z[2]*Z[3]*Z[4], ...

was natürlich schamlos ausnutzt, dass 4 eine Zweier-Potenz ist.

Verallgemeinerung ist möglich: Für die Produkte aus 5 Faktoren müsste man z.B. mit einer Index-Verschiebung von 4 nochmal Z an X dran-multiplizieren. Für 6er Produkt Y dran-multiplizieren, um 4 verschoben.
Aber ohne Numpy und für beliebige Anzahl von Faktoren ist mir das ehrlich gesagt zu mühsam. VIEL zu mühsam.
Darüber mögen andere hirnen, ich trinke lieber in bester Knaller-Manier mein Bier.

Außerdem kann man natürlich noch kritisieren, dass ich Eigenschaften des Operators ausnutze, z.B. die Arität 2, das Assoziativgesetz, etc.

>Wenn die Eingabe erst bearbeitet werden muss, zählt es nicht!
Du hast die Eingabe auch bearbeitet? In der Eingabe steht nirgends "Zeile1 =".

Wäre sowas wie

f = open("input.csv", 'r')
grid = [list(map(int, x.split(' '))) for x in f.readlines()])

ein Abfall von der "reinen Lehre"?

>>50831
>Oho, was da wohl noch alles kommen mag? Zur Zeit wäre das wohl wie mit Kanonen auf Spatzen zu schießen.
Irgendwann später braucht man alle Primzahlen bis zu $GroßeZahl. Betonung auf ALLE. Und so große, dass bei mir damals das in Python implementierte Sieb des Erathostenes nicht mehr in den Hauptspeicher meines Laptops passte, weil ich ein ganzes Wort für eine Boolesche Tabellenzelle verbrauchte. Ich löste das durch Eratosthenes in C, mit einem einzelnen Bit als Zelle.

>Kannst du zu der Magie von dict() elaborieren?
Glaube ich zur dynamischen Programmierung genutzt zu haben, besonders für Primfaktorzerlegungen. kgV und ggT bleiben interessant.
Python ist nicht schnell, aber seine Dictionaries sind es schon.
Natürlich nur sinnvoll unter der Randbediungung, dass die Liste der benötigten Primfaktorzerlegungen hinreichend dünn besetzt ist.

Das nicht ganz-so-tolle Multiset-Äquivalent in Python heißt übrigens Counter. Sowas wie "die 3 zweimal" kann man dadrin ganz gut ablegen.

Problem 50 konnte ich allein durch Nutzung des in Python eingebauten Sets statt einer Liste um einen Faktor von ca. 600 beschleunigen.

Faustregel (1):
Es ist in Python eingebaut -> Es ist schnell.

Faustregel (2):
Es kommt aus NumPy -> Es hat kein Aliasing-Problem, weil in Fortran VERBOTEN -> Es ist noch schneller.

>>50833
> Wenn man nicht gerade Zocker oder Simulant ist, hat man nicht selten auch heute einen Core Duo oder AthlonXP oder so,
Und da dachte ich, ich wäre mit meinem Whiskey-Lake Klappcomputer schlecht ausgestattet...

>weswegen man vermutlich mit Windows 11 auch diesen Anforderungsstunt gepullt hat.
Erzähle mir von es. Werden auf der Weide deshalb Windows 10 nutzen, bis Rockwell Windows 11 VERLANGT, Windows 10-Unterstützung endet, oder die Geräte auseinanderfallen.

Zurück zu div und Stringcast:
Orinzipiell hast du recht, mir sollten die Kosten von Textumwandlung bewusst sein. Ein australischer Ultrachad-Tutor hat mir vor 15 Jahren wegen unnötiger Stringcasterei mal ein Testat verweigert, das hätte mir Lehre genug sein sollen.

Dann hatte ich vor 4 Jahren ein Weiden-Problem, als Azubis mit einem SAMD-21-Board und Arduino-Bibliothek Analog-Eingänge sampelten und jedes Sample als Text über die die serielle Ausgabe schickten. Blöderweise hat das das Programm um ungefähr den Faktor 10 verlangsamt. Die ausgegebenen Kurven sahen qualitativ durchaus richtig aus, das Under-Sampling war so gut gewählt, dass Ausschläge an den richtigen Stellen lagen. Aber alles Wesentliche konnte aber zwischen 2 samples passieren oder einen 1-Sample-langen Spike auslösen. Die falsche Zeit-Skalierung wurde mit
>wir haben uns halt um eine 10er-Potenz vertan
abgetan.

Zu faul, deren Programm zu lesen, setzte mich also hin und laß und zeitstempelte erstmal die Ausgabe mit Termios in C so Echtzeit wie möglich, und stellte fest, dass zwischen zwei Samples 10x zu viel Zeit lag. Das Problem war dann leicht zu finden. Ich hoffe, die Azubis haben daraus so viel gelernt wie ich. Oder mehr, weil ich ja immernoch sage fick es, die Hartwaren-Ingenieure regeln das, elementare Rechenoperationen sind nicht mein Thema.
>>
Nr. 50865 Kontra
>>50831
>ist das eine Frage, weil du's nicht genau weißt?
eben dieses :3
t. Nicht-Programmierer und Mathe immer zwischen 4 und 5
>>
Nr. 50877
1 kB, 1 Datei
>>50865
Ist ja nicht schlecht, was du geschrieben hast. Vielleicht hast du ja trotz schlechter Noten sowas wie mathematische Intuition. :3

>>50340
>aber dem war nicht so
Dachte ich auch und die Aufgabe ist einfach genug. Mein Taschenrechner hat sogar Tasten Σx und Σx². Damit wäre die Aufgabe eine Sekundensache, wenn da nicht gerade das Eintippen aller Zahlen von 1 bis 100 wäre. Geht es auch ohne Eintipporgie?

Das Problem könnte man kurz so notieren:
(Σx)² - Σ(x²)
Der Minuend wäre also kein Problem, denn für Σx haben wir schon die Gaußsche Summenformel >>50257 kennengelernt. Für den Subtrahenten kannte ich noch keine Summenformel, aber — wie sich herausstellt — gibt es die.

Erstmal musste ich dafür herausfinden, wie die Reihe 1² + 2² + 3² usw. genannt wird. Da es eine Summe von Quadraten ist, liegt Quadratsumme ja nahe. Dazu findet man Einiges zu Statistik (mithin der Grund, warum mein Taschenrechner solche Tasten besitzt. Quadratsummen spielen in der Statistik eine wesentliche Rolle.), aber die Zahlentheorie ist für unsere Aufgabe ergiebiger, denn da gibt es allgemeiner Erkenntnisse zu Quadratzahlen.

Die Summe der ersten n Quadratzahlen nennt sich nämlich Pyramidenzahl (in einer Pyramide hat die n-te Ebene genau Kugeln, s. Bild) und dazu gibt es eine Formel. Der Rest der Übung ist dann nur noch beide Formeln auszurechnen bzw. in eine einzige, neue umzuformen, wie z.B.:

(n^4 - n^2)/4 + (n^3 - n)/6

Das in Python zu implementieren ist natürlich arschlos einfach, also machen wir es in Assembler. Dann sieht man, dass das praktisch auch nur wie in den Taschenrechner eintippen ist ;)

Wenn du in deinen Taschenrecher Zahlen eingibst und die dann auf dem Bildschirm erscheinen, muss er sie ja irgendwo gespeichert haben (also sogar vor der ersten Rechenoperation). Dieses Irgendwo ist ein Register und ein Taschenrechner hat davon einige, genauso wie dein Prozessor. Nur damit klar ist, was hier rax, rbx, rcx usw. bedeuten.


mov rax,100 ; n in Register rax laden
mov r8,rax ; n für den zweiten Term aufheben
mul rax ; rax <- n * n
mov rbx,rax ; rbx <- n^2
mul rax ; rax <- n * n * n * n
sub rax,rbx ; rax <- rax - rbx
mov rcx,4 ; Dividend laden
div rcx ; dividieren (Ergebnis -> RAX, Modulo -> RDX)
mov rcx,rax ; sichern, damit wir rax benutzen können...

mov rax,rbx ; ...denn mul erwartet das so; rax <- n^2
mul r8 ; rax <- n^2 * n
sub rax,r8 ; rax <- n^3 - n
mov rbx,6 ; diesmal nimmt rbx den Dividenden auf
div rbx ; rax <- rax / rbx; rdx <- rax % rbx
add rax,rcx ; Ergebnis vom ersten Term


Auch wenn du den Kode nicht an der Formel oben nachvollziehst, solltest du leicht die vier Grundrechenarten ADD, SUB, MUL und DIV erkennen. Außerdem gibt es noch mit MOV praktisch das Äquivalent zum Gleichheitszeichen in anderen Programmiersprachen.


$ fasm p6.asm && ./p6
flat assembler version 1.7
3 passes, 324 bytes.
25164150



Der angehängte Quelltext ist noch etwas länger, weil wir bis jetzt nur das Ergebnis im Register rax zu liegen haben. Um es auszugeben, muss es noch in eine Dezimalzahl (0x7B -> 0x01 0x02 0x03) umgewandelt werden und als ASCII (0x31 0x32 0x33, also alle Bytes +0x30) in einen Puffer abgelegt werden, damit der Kernel das auf dem Bildschirm ausgeben kann. Ein Paradebeispiel dafür, was print in Python alles für uns tut.
>>
Nr. 51361
520 kB, 498 × 360, 0:11
>>50449
Ist das das Problem, wofür >>50653 die Bitvektoren bemüht hat? Ich habe einen Mega-Speicherbedarf erwartet, gerade mit Püthon, wo, wie man sieht, ein Wahrheitswert ganze 28 Byte Byte belegt.

>>> from sys import getsizeof as sizeof # Gibe Größe in Byte
>>> sizeof(True)
28
>>> sizeof([True])
64
>>> sizeof([True] * 2)
72

Wenn man den Wert in eine Liste packt, wird der Speicherbedarf sogar nochmal mehr als verdoppelt. Allerdings scheint für einen Wert mehr dann nur noch acht Byte mehr benötigt zu werden.

>>> sizeof([True] * 200000)
1600056

Wenn ich zweihunderttausend Zahlen sieben möchte, brauche ich dann etwa 1,6 Megabyte Speicher. Das scheint doch ganz vertretbar.

from time import time

def primzahl(n):
p = [False] * n

for i in range(2, n):
if not p[i]:
yield i
for j in range(i, n, i):
p[j] = True

t0 = time()
P = primzahl(200000)
print(list(P)[10001-1]) # -1 wegen nullbasierter Indizierung
print(time() - t0)

Ich habe also den Primzahl-Generator aus >>50561 so umgeschrieben, damit er eine Liste aus Wahrheitswerten p benutzt. Ich vermute mal, wegen list(P) werden tatsächlich alle Primzahlen bis 200'000 gefunden.

104743
0.04080820083618164

Durch das Sieben läuft's dennoch erstaunlich schnell.
>>
Nr. 51365
>>51361
>Wenn ich zweihunderttausend Zahlen sieben möchte, brauche ich dann etwa 1,6 Megabyte Speicher. Das scheint doch ganz vertretbar.
Habe recherchiert, warum genau ich das damals gemacht habe.
Schau dir mal Problem 41 an. Gesucht ist größte n-stellige Primzahl, in der jede Ziffer genau einmal vorkommt. Dann mach die grobe Abschätzung: es gibt n Ziffern. Maximale 9-stellige Zahl ist 999999999. Bis dahin bräuchte Eratosthenes 8GB, und so viel steckte damals nicht in meinem Computer.

Man findet eine bessere Abschätzung, deutlich besser. Die ist aber nicht sooo einfach zu finden, und mein Kommentar dazu labert irgendwas von Quersumme, die beim Vorkommen bestimmter Ziffern einen bestimmten Wert annehmen muss. Kann man glauben, weil das richtige Ergebnis dabei rauskommt...
>>
Nr. 51418
>>51365
>irgendwas von Quersumme
Ich will nicht vorgreifen, aber war der Plan in etwa so?

1. Die maximal n! Kombinationen aus 1..n erzeugen,
2. die dann absteigend nach Größe sortieren (oder gleich in der richtigen Reihenfolge erzeugen).
3. Dann mit Teilbarkeitsregeln und teilen durch kleine Primzahlen (bis maximal √10^n) die Kombinationen aussieben, also der Zusammengesetztheit überführen.

Dann sollten recht schnell nur noch wenige Kandidaten übrig bleiben. Möglicherweise kann man das mit der Dichte für pandigitale Zahlen (9!/10^9 ≈ 0,00036) und der geschätzten Primzahldichte (1/ln 10^9 ≈ 0,04825) schonmal abwägen. Das werde ich sehen, wenn (falls) ich bei dem Problem ankomme. Bei meiner Geschwindigkeit ist das frühestens in drei Jahren.
>>
Nr. 51436
>>51418
Keine Ahnung, ob man es so machen kann. Hört sich aufwändig an. Mein Ansatz war nicht halb so clever. Leider sehr, sehr führender Hinweis: Es gibt einen Teilbarkeitstest für Teilbarkeit durch eine gewisse Ganzzahl, mit dem man man n-Pandigitalen für gewisse n ausschließen kann.
>>
Nr. 51446
1 kB, 1 Datei
>>51436
Ich sehe schon. Mein Ansatz ist aber genau andersherum. Ich habe ja gleich zu Anfang nur pandigitale Zahlen und ich muss die zusammengesetzten darunter ausschließen.

>>50492
Du musst nicht die ganze Zahl in eine Zeile quetschen. Lass das doch Püthon übernehmen:

N = '''
731...
...450
'''.replace('\n','')


Meine Lösung ist zuerst mal genauso wie deine.

def v1(n, l):
m = 0

for i in range(len(n)-l+1):
r = 1
for x in n[i:i+l]:
r *= int(x)
if r > m:
m = r
p = i

return p, int(n[p:p+l]), m

print('Position: %d, Ziffernfolge: %d, Produkt: %d' % v1(N, 13))

Schau dir mal die innere Schleife an. Die ist für die Optimierung besonders interessant, weil sie in deinem Kode am häufigsten ausgeführt wird. Hier solltest du nicht in jeder Iteration i + j berechnen, sondern dir ein Scheibchen von n geben lassen. Damit läuft das Ganze immerhin nochmal doppelt so schnell.

Eine andere Lösung aus dem Zwischennetz. Also nicht meine, nur angepasst.

def _querprod(n):
e = 1

while n:
e *= n % 10
n //= 10

return e

def v2(n, l):
m = 0

a = map(int, re.findall(re.compile(f'(?=([1-9]{{{l}}}))'), n))
for i in a:
r = _querprod(i)
if r > m:
m = r
z = i

return n.find(str(z)), z, m

Bei der Zeichenfolge {{{l}}} denkt man mit Bilderbretterfahrung natürlich unwillkürlich an
> De Joodn
Hier geht es allerdings um die sogenannten f-Strings. Mit dem f vor dem String wird das {l} durch den Wert von l ersetzt (z. B. 4 oder 13). Die doppelten geschweiften Klammern werden durch einfache ersetzt. Nach den Ersetzungen bleibt ein gültiger regulärer Ausdruck. Wenn du wissen willst, wie das genau funktioniert, such mal in der Python-Doku für das re-Modul nach lookahead assertion. Jedenfalls hält a danach alle möglichen 13-stelligen Zahlen ohne eine Null, für die man dann das größte Querprodukt sucht.

Das hat mich dann auf die Idee gebracht, die große Zahl an den Nullen zu zerteilen und die Berechnungen nur für Teile durchzuführen, die lang genug sind. Gerade wenn man 13 aufeinanderfolgende Ziffern untersucht, fällt da ja einiges weg. Das brachte mir die bisher schnellste Lösung.

Für 10000 Wiederholungen
Dauer(v1(13)) = 18.012172414993984
Dauer(v2(13)) = 5.416081340998062
Dauer(v3(13)) = 5.063234209999791


Die Lösung mit den regulären Ausdrücken (v2) ist also überraschenderweise mehr als doppelt so schnell und meine Lösung ohne regA (v3) bringt nur noch einen geringen Gewinn. Das gibt einen zu denken, wie mächtig Pythons (kompilierte) reguläre Ausdrücke sind! Die Zeiten sind hier höher, als in >>50492, weil ich hier wieder timeit benutze, das den Versuch zehntausendmal wiederholt. Bei einer durchschnittlichen Ausführungsdauer von ursprünglich 0,008 Sekunden jetzt eher 0,0001 :3 wird der Unterschied zwischen den Algorithmen dadurch deutlicher.

Nebenbei habe ich noch gelernt, dass JS viele Eigenschaften mit Püthon teilt (also auch so Dinge wie Generatoren und map() usw). Der kühle Einzeiler hier

f = n => [...n.matchAll(/(?=([1-9]{13}))/g)].reduce((a,c)=>(p=eval(c[1].split``.join`*`),p>a?p:a),0)

zeigt aber leider auch die ganze Beschissenheit der Sprache. Weil es ohne externe Bibos kein prod() gibt, wird da ein String zusammengefriemelt und mit dem pöhsen eval() interpretiert. Will man das in seiner JS-Konsole ausführen, fliegt einem mitunter ein blocked by CSP um die Ohren, weil der Kode im Webseiten-Kontext läuft m(

Der Kode im ZIP ist noch ein bisschen mehr ausgearbeitet mit den drei verschiedenen Formatierungsmöchlichkeiten, die Püthon bietet, mit Zeichenkettenarithmetik und gibt eine hübsche ASCII-Tabelle aus. Bei Fragen, hier im Faden die Fragen fragen :3
>>
Nr. 51712
11 kB, 350 × 315
>>50602
Protipp, wenn Ernst die Lösung selbst erarbeiten möchte: Beim „kleinen“ Triplett (3, 4, 5), das als Beispiel gegeben ist, ist 3 + 4 + 5 = 12. Stell dich doof! Wenn du nur die 12 hast, wie würdest du auf die 3, 4 und 5 kommen?

Es ist jedenfalls eine geniale Aufgabe und ohne muh Primzahlen. Kann man so weit optimieren, dass eine Million Lösungen in unter einer Sekunden gefunden werden (sagt timeit). Das geht auch für andere Zahlen als die 1000 (allerdings findet man dann nicht immer eine gültige Lösung). Dabei wird keine höhere Mathematik eingesetzt! Es läuft alles nach dem Schema „Einsetzen, ausmultiplizieren und nach xy umstellen“.

Du kannst einen Trick direkt in deinem Kode ausprobieren. Du iterierst ja über a und b. Das c ergibt sich dann aus den anderen Größen, ist also abhängig von a und b. Wenn du jetzt eine von den ersten beiden Variablen von der jeweils anderen abhängig machst, brauchst du nur über die eine iterieren und kannst dir die andere Schleife sparen. Dafür nimmst du die zwei Gleichungen aus der Aufgabe. Ich nenne Sie mal Ⅰ und Ⅱ:

Ⅰ: a² + b² = c² (Pythagoras)
Ⅱ: a + b + c = u (Umfang)

Du musst also nur z.B. Ⅱ nach c = u - a - b umstellen und in Ⅰ einsetzen, dann ausmultiplizieren und nach b umstellen. Dann solltest du auf b(a) = u ÷ 2 ⋅ (u-2a) ÷ (u-a) kommen (oder auf pythonisch b = u / 2 * (u - 2 * a) / (u - a)). Das packst du in deine innere Schleife, löschst die äußere. Schon bist du schneller.

Okeh, wenn ich dir jetzt meine Lösung zeige, werde ich ein bisschen erklären müssen. Die Anforderungen sind aber dennoch eher mäßig. Wie gesagt: „Einsetzen, ausmultiplizieren, umstellen“. Mehr nicht.

from math import isqrt

def p9(u):
uh = u >> 1
p = isqrt(uh); q = 0
while p > q:
q = uh / p - p
if q.is_integer():
return 2 * p * q * (p*p*p*p - q*q*q*q)
p -= 1

print(p9(12), p9(1000))#;print(p9(randint(1,8192))

Die ersten beiden Zeilen sind etwas magere Optimierungen, die ich trotzdem mal gezeigt haben möchte:

- 1) Mit u >> 1 teile ich durch zwei, was zumindest früher(tm) schneller war als einfach zu teilen.
- 2) Bei Compilern kann man angeblich auch nicht mehr optimieren, indem man Zwischenergebnisse speichert, wie hier mit uh geschehen. Bei Python scheint sich das zu lohnen, allerdings nicht so sehr.
- 3) Wie mir scheint, ist isqrt nix anderes als int(sqrt(x)), zumindest wenn ich auf die Ausführungszeiten gucke.
- 4) Der Wert von q ist hier noch egal. Die Variable muss nur für das while darunter schon definiert sein.


Jetzt brauchen wir die Formeln von Euklid, mit denen man aus zwei ganzen Zahlen p und q pythagoräische Zahlentripletten erzeugt.

a = p² - q²
b = 2pq
c = p² + q²

Mit der richtigen Kombination aus p und q erzeugen wir ein Triplett, das genau den Umfang von u = 1000 hat (Gleichung Ⅱ).

Wie bei deinem Kode haben wir dasselbe Problem: Zwei scheinbar voneinander unabhängige Variablen (p und q) müssen durchprobieren werden. Verändere ich jetzt p oder q? Wie muss ich vorgehen, um möglichst schnell zu kommen? Zum Glück können wir mit den beiden Gleichungen Ⅰ und Ⅱ und den Euklidischen Formeln wieder eine Variable als abhängig von der anderen definieren. Euklidische Formeln in Ⅱ einsetzen, ausmultiplizieren und nach q umgestellen: q(p) = u ÷ 2p - p. Damit haben wir nebenbei q auch abhängig von u gemacht. Alle q, die wir mit dieser Formel finden, sind bereits so gewählt, dass Ⅱ erfüllt ist. Jetzt brauchen wir nur noch ein ganzzahliges q(p) zu finden, für das der Euklid nämlich nur definiert ist.

Wir brauchen also nur noch eine Schleife (für p). Aber auch hier können wir Iterationen sparen. Schau nochmal auf die gefundene Formel für q(p). Bei sehr großen p wird q(p) negativ. Spätestens dann sollte unsere Schleife enden. Um herauszufinden, bei welchen p das q(p) negativ wird, setzen wir einfach q(p) = 0 und stellen diese neue Formel nach p um. Also 0 = u ÷ (2p) - p nach p umstellen. Dann solltest du auf p = √(u/2) kommen.


Wenn wir auf den ersten Euklid (a = p² - q²) schauen, sieht man, dass a negativ wird, wenn q > p ist. Also fangen wir am besten nicht „unten“ (mit p = 2) an, sondern arbeiten uns von „oben“ herab. Deswegen steht p in der ersten Iteration auf der Nullstelle von q(p), die wir uns gerade errechnet haben. Von da aus wird er dann immer weiter dekrementiert.

Wir wissen dann aber auch, dass p > q für unsere ganze Schleife gelten sollte und wir aufhören können, wenn das nicht mehr stimmt. Wenn du dir p und q in der Schleife ausgeben lässt, wirst du sehen, dass sie aufaneinder zu wachsen (weil q über u an p gebunden ist).

Der letzte Trick ist beim Rückgabewert und auch hier muss man wieder einsetzen und ausmultiplizieren (nicht mal umstellen): Euklidische Formeln in a ⋅ b ⋅ c eingesetzt ((p²-q²)² ⋅ (2pq)² ⋅ (p²+q²)²) und gekürzt (2pq(p⁴-q⁴)).
>>
Nr. 51757
35 kB, 200 × 208
51 kB, 1400 × 600
>>50604
Wir haben schon in >>51361 für Problem 7 Primzahlen bis 200'000 gesiebt. Jetzt einfach denselben Generator für 2 Mio. erzeugen und dann print(sum(P)) und fertig!

Das ist also auch noch nicht die Aufgabe, für die wir Bitvektoren brauchen werden. Nur, wann ist es soweit, dass unser Programm nicht mehr in den Speicher passt?

Mit sys.getsizeof können wir schon einzelne Variablen untersuchen. Um das Programm insgesamt einzuschätzen, suchen wir den maximalen Speicherverbrauch. Leider unterscheiden sich die Befehle da nach Betriebssystem:

# Linux
from resource import getrusage, RUSAGE_SELF
# hier Algorithmus einfügen
print(getrusage(RUSAGE_SELF).ru_maxrss)

# Windows
import psutil
# Arbeit, Arbeit...
print(psutil.Process().memory_info().peak_wset)

Gegebenfalls muss man erstmal pip install psutil bemühen. Dann hat man aber auch ein Modul, dessen Funktionsumfang weit über das hinausgeht, was wir hier brauchen.

Wenn man schon dabei ist, kann man sich auch den memory_profile dazu installieren. Dann schreibst du from memory_profiler import profile zu deinen Importen, packst deinen Algorithmus in eine Funktion und schreibst @profile in die Zeile über das def. Nach dem Ausführen bekommst du dann eine zeilenweise Übersicht über den Speicherbedarf.

Line # Mem usage Increment Line Contents
================================================
2 13.8 MiB 13.8 MiB @profile
3 def SumOfPrimes(MaxNum):
4 13.8 MiB 0.0 MiB Sieb = []
5
6 91.3 MiB 0.0 MiB for i in range(0, MaxNum+1):
7 91.3 MiB 77.5 MiB Sieb.append(i)
8
9 91.3 MiB 0.0 MiB Removers = [0, 1]
10 580.6 MiB 0.0 MiB for Prime in Sieb:
11 580.6 MiB 0.0 MiB if Prime!=0 and Prime!=1:
12 580.6 MiB 0.0 MiB Maex = int(MaxNum/Prime)
13 580.6 MiB 394.6 MiB for i in range(Prime, Maex+1):
14 580.6 MiB 94.6 MiB Removers.append(i*Prime)
15
16 291.6 MiB -289.0 MiB Removers = list(set(Removers))
17 305.5 MiB -7707477.4 MiB for i in sorted(Removers, reverse=True):
18 305.5 MiB -7707491.3 MiB del Sieb[i]
19 292.1 MiB -13.4 MiB return sum(Sieb)

Die Ausführung wird dadurch natürlich verlangsamt, also musst du die Laufzeit separat testen.

Dein Programm ist hierfür ein sehr dankbares Beispiel, weil du Listen dynamisch anfragst und andernorts Einträge wieder löschst. Damit wächst und schrumpft der Speicher, den dein Programm braucht, immer wieder.

Beim del gibt es allerdings ein Problem, denn die angezeigte Speicherfreigabe (rund 7,7 TiB) in Zeile 17 und 18 ist Unsinn. Dein Programm war während der Ausführung tatsächlich nie größer als die angegeben 580 MiB.

Leistungsmessung ist anscheinend nicht immer einfach. Die 13,8 MiB vom Anfang sind übrigens der Grundbedarf, den Python und die Module haben. Ich habe dasselbe mal mit print('Krtek') versucht und es waren auch 13,8 MiB.

Mit dem Paket memory_profiler kommt außerdem ein Programm namens mprof (oder python3-mprof, je nachdem, wer das paketiert hat). Damit sagt man dann

mprof run SumOfPrimes.py
mprof plot
# `pip install matplotlib`, falls plot "No module named 'pylab'" sagt

Dann bekombt man seinen Speicherbedarf grafisch aufbereitet (so wie bsp.png).

Kühlerweise hat man dann Speicher und Ausführungszeit gegenübergestellt. Auch wenn die Programme insgesamt langsamer laufen, sieht das nach einem guten Anhaltspunkt aus, um die Komplexität seines Algorithmus überwachen.

Das nützt uns freilich nicht viel, wenn wir tatsächlich zu C oder einer anderen Sprache wechseln sollten. Zumindest unter Linux kann man versuchen, in der Sprache auf die getrusage-API zuzugreifen oder man nutzt einfach GNU time (ggf. installieren).

\time -f '%M' python SumOfPrimes.py

Das \ vor dem time ist wichtig, weil du sonst die eingebaute Funktion deiner Muschel aufrufst und die ist bei weitem nicht so mächtig. Interessant ist auch, \time -v, das dir allerhand weitere Informationen gibt.

Unter Windows bekommt man die Information vermutlich mit resmon.exe oder perfmon.exe, aber damit habe ich mich noch nicht anfreunden können. Ich fand immer den Prozesserforscher (procexp.exe) von Sysinternals kühler. Bei dem klickt man auf einen Prozess doppelt, wählt den Reiter "Performance", bei "Physical Memory" schaut man nach "Peak Working Set".

Wieder etwas dazugelernt. Dann kann Problem 41 bald kommen :^)
>>
Nr. 52272
814 kB, 3759 × 2976
>>50863
>weil man viele Zigaretten rauchen muss, bis es durchgelaufen ist
Mit anderen Worten: Je schlechter der Kot, desto häufiger sind die Raucherpausen. Wozu will man da noch guten Kode schreiben ;)

>>50660
Dieses Problem bringt einfach keinen Gewinn. Die größte Einsparung, die du in deinem Programm machen kannst, ist es, die Berechnungen zu halbieren, indem du nicht nach links und rechts usw. prüfst, sondern nur nach rechts, weil du ohnehin über die gesamte Matrix läufst und Multiplikation assoziativ ist. Das wurde ja von >>50666 schon angesprochen und mehr scheint dieses Problem nicht zu bieten.


from time import time

t0 = time()
D20 = """
08 02..
...
..67 48
"""

def p11(M, n):
'Suche in Datenmatrix M nach dem größten Produkt aus n Faktoren'

M = M.strip().split('\n')
d = len(M) # Dimension der Matrix, Annahme: quadratische Matrix
e = 0 # Endergebnis

# (1): Eingabe nach Ganzzahlmatrix umwandeln
for i in range(d):
M[i] = M[i].split(' ')
for j in range(d):
M[i][j] = int(M[i][j])

# (2): solange wir den Rand nicht berühren in alle Richtungen suchen
for i in range(d - n + 1):
for j in range(d - n + 1):
w0 = M[i][j]
# Jedes Tupel steht für eine Suchrichtung, wobei wir uns die Suche
# nach links, oben usw. sparen, um Doppelberechnungen zu meiden.
for di, dj in [(0, 1), (1, 0), (1, 1)]:
w = w0
for k in range(1, n):
w *= M[i + k*di][j + k*dj]
if w > e:
e = w
# Speziell für die zweite Diagonale muss die Startposition
# um (n - 1) nach unten verlegt werden
w = 1
for k in range(n):
w *= M[i + n - 1 - k][j + k]
if w > e:
e = w
# in den letzten n - 1 Spalten nur noch senkrecht prüfen
for j in range(n - 1):
w = 1
for k in range(n):
w *= M[i + k][j + d - n + 1]
if w > e:
e = w
# in den letzten n - 1 Zeilen nur noch waagerecht prüfen
for i in range(n - 1):
for j in range(d - n + 1):
w = 1
for k in range(n):
w *= M[i + d - n + 1][j + k]
if w > e:
e = w

return e

print(p11(D20, 4), time() - t0)

Im Kode wurden Schleifen abgerollt und Dereferenzierungen sollten gespart werden. Aber das ist Kleinkram.

>>50863
>Ich versuche mal, meine Idee zu Problem 11 auszuformulieren.
Das war auch meine Überlegung, die Daten erst in eine für die Berechnung günstige Form zu bringen, so dass beim Berechnen höchstens ein Zähler hochgezählt werden muss und die Index-Berechnungen alle entfallen. Für die 3x3-Matrix wäre das:

gerade transponiert diagonal gegendiagonal
08 02 22 08 49 81 22 08
49 49 99 02 49 49 02 99 02 49
81 49 31 22 99 31 08 49 31 22 49 81
49 49 99 49
81 31

Dann läuft man da nur noch zeilenweise drüber (für Zeilen, die lang genug sind). Habe ich sein lassen, weil es letztlich die Index-Berechnungen nur verschiebt.