Projekt Euler: Problem 11

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
bremer
User
Beiträge: 109
Registriert: Sonntag 25. Mai 2008, 00:13

Problem 11
22 February 2002

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 any direction (up, down, left, right, or diagonally) in the 20×20 grid?

Code: Alles auswählen

with open("grid.txt") as file:
    grid = file.read().split()
matrix, products = [], []

for i in range(20):
    submatrix = []
    for j in range(20):
        submatrix.append(grid.pop())
    submatrix = [int(substring) for substring in submatrix]
    matrix.append(submatrix)

print("horizontal:")
for i in range(20):
    for j in range(17):
        new_product = matrix[i][j] * matrix[i][j+1] * matrix[i][j+2] \
            * matrix[i][j+3]
        print(matrix[i][j], matrix[i][j+1], matrix[i][j+2], \
            matrix[i][j+3], "-->", new_product)
        products.append(new_product)

print("vertical:")
for i in range(17):
    for j in range(20):
        new_product = matrix[i][j] * matrix[i+1][j] * matrix[i+2][j] \
            * matrix[i+3][j]
        products.append(new_product)
        print(matrix[i][j], matrix[i+1][j], matrix[i+2][j], \
            matrix[i+3][j])

print("diagonal:")
for i in range(17):
    for j in range(17):
        new_product = matrix[i][j] * matrix[i+1][j+1] * matrix[i+2][j+2] \
            * matrix[i+3][j+3]
        print(matrix[i][j], matrix[i+1][j+1], matrix[i+2][j+2], \
            matrix[i+3][j+3], "-->", new_product)
        products.append(new_product)

print("largest value:", max(products))
Ergebnis ist, dass der Ausschnitt "97, 88, 91, 66" das größte Produkt ergibt, nämlich 51267216.

Laut projecteuler.net ist diese Antwort aber leider falsch.

Ideen?
kripsy
User
Beiträge: 1
Registriert: Sonntag 20. September 2009, 17:22

Kann es sein, dass du nur Diagonalen von links oben nach rechts unten anschaust?
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

bremer hat geschrieben:Ideen?
Es gibt nicht nur eine Diagonale ... :wink:
bremer
User
Beiträge: 109
Registriert: Sonntag 25. Mai 2008, 00:13

Ach, ich habe steigenden Diagonalen übersehen.
BlackJack

Mein C64 bekommt mit BASIC nach einer Minute und 38 Sekunden das richtige Ergebnis heraus. :-)

Code: Alles auswählen

   10 rem -----------------------------
   20 rem project euler (projecteuler.net)
   30 rem problem 11
   40 rem
   50 rem takes about 00:01:38.
   60 rem
   70 ti$="000000":n=20:dim m(n,n):mx=0
   80 rem
   90 print "reading data..."
  100 for i=1 to n:for j=1 to n:read m(i,j):next:next
  110 rem
  120 rem main loop
  130 rem
  140 read n$:if n$="" then 210
  150 print "searching ";n$;
  160 read x1,x2,ya,xm,ym
  170 for x=x1 to n-x2:print ".";:for y=1 to n-ya
  180 t=1:for z=1 to 4:t=t*m(y+z*ym,x+z*xm):next:if t>mx then mx=t
  190 next:next:print:goto 140
  200 rem
  210 t$=ti$:print "result:";mx;" (";mid$(t$,3,2);":";right$(t$,2);")":end
  220 rem
  230 rem 20x20 data grid
  240 rem
  250 data 08,02,22,97,38,15,00,40,00,75,04,05,07,78,52,12,50,77,91,08
  260 data 49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,04,56,62,00
  270 data 81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,03,49,13,36,65
  280 data 52,70,95,23,04,60,11,42,69,24,68,56,01,32,56,71,37,02,36,91
  290 data 22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80
  300 data 24,47,32,60,99,03,45,02,44,75,33,53,78,36,84,20,35,17,12,50
  310 data 32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70
  320 data 67,26,20,68,02,62,12,20,95,63,94,39,63,08,40,91,66,49,94,21
  330 data 24,55,58,05,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72
  340 data 21,36,23,09,75,00,76,44,20,45,35,14,00,61,33,97,34,31,33,95
  350 data 78,17,53,28,22,75,31,67,15,94,03,80,04,62,16,14,09,53,56,92
  360 data 16,39,05,42,96,35,31,47,55,58,88,24,00,17,54,24,36,29,85,57
  370 data 86,56,00,48,35,71,89,07,05,44,44,37,44,60,21,58,51,54,17,58
  380 data 19,80,81,68,05,94,47,69,28,73,92,13,86,52,17,77,04,89,55,40
  390 data 04,52,08,83,97,35,99,16,07,97,57,32,16,26,26,79,33,27,98,66
  400 data 88,36,68,87,57,62,20,72,03,46,33,67,46,55,12,32,63,93,53,69
  410 data 04,42,16,73,38,25,39,11,24,94,72,18,08,46,29,32,40,62,76,36
  420 data 20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,04,36,16
  430 data 20,73,35,29,78,31,90,01,74,31,49,71,48,86,81,16,23,57,05,54
  440 data 01,70,54,71,83,51,54,69,16,92,33,48,61,43,52,01,89,19,67,48
  450 rem
  460 rem iteration parameters
  470 rem
  480 data "horizontal",1,4,0,1,0
  490 data "vertical",1,0,4,0,1
  500 data "diagonal 1",1,4,4,1,1
  510 data "diagonal 2",4,0,4,-1,1
  520 data "":rem <- end marker
bremer
User
Beiträge: 109
Registriert: Sonntag 25. Mai 2008, 00:13

Nun Problem 21.
Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.
Mein Code:

Code: Alles auswählen

def d(n):
    divisors = [1]
    for i in range(2, n):
        if not (n % i):
            divisors.append(i)
    return sum(divisors)

amicables = []
for a in range(1, 10000):
    b = d(a)
    if b < 10000 and a == d(b):
        amicables.append(a)
print(sum(amicables))
Für die "range" 200 bis 300 funktioniert es. In diesem Fall (10000) ergibt sich 40285. Die Antwort ist aber nicht korrekt. Habe ich die Aufgabe falsch gelesen? Ich berechne die Summe aller "einvernehmlichen" Zahlen unter 10000.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

bremer hat geschrieben:
..., where a ≠ b, ...
:wink:

Im übrigen kannst du die Laufzeit erheblich verbessern, indem du ausnutzt, dass beim Auffinden eines Teilers per Probedivision automatisch zwei Teiler gefunden wurden.
BlackJack

Selbst mit der von numerix vorgeschlagenen Optimierung braucht mein C64 mit folgendem BASIC-Programm 3 Stunden und 40 Minuten. :shock:

Code: Alles auswählen

   10 rem ---------------------------
   20 rem project euler (projecteuler.net)
   30 rem problem 21: evaluate the sum
   40 rem of all the amicable numbers
   50 rem under 10000.
   60 rem
   70 rem takes about 3h 40m.
   80 rem
   90 ti$="000000":m=10000-1
  100 rem
  110 rem sum amicable numbers.
  120 rem
  130 r=0:for a=1 to m
  140 n=a:gosub 240:b=d
  150 if b>m or a=b then next
  160 n=b:gosub 240:if a=d then r=r+a
  170 next
  180 print r;"(";ti$;")"
  190 end
  200 rem ---------------------------
  210 rem sum divisors of n.
  220 rem result in d.
  230 rem
  240 d=1:for i=2 to sqr(n)+1
  250 if int(n/i)*i=n then d=d+i+n/i
  260 next:return
Ich habe auch schon eine Alternative im Kopf, aber die geht nicht mit dem C64 → zu wenig Speicher. Zumindest wenn ich bei BASIC bleiben möchte. Auf'm C128 müsste es gehen…
Benutzeravatar
Hyperion
Moderator
Beiträge: 7478
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

BlackJack hat geschrieben:Selbst mit der von numerix vorgeschlagenen Optimierung braucht mein C64 mit folgendem BASIC-Programm 3 Stunden und 40 Minuten. :shock:
PAL oder NTSC? :-D

Immerhin kann der Brotkasten das :-)
BlackJack

@Hyperion: PAL natürlich. Könnte ich ein NTSC-Modell überhaupt hier in Deutschland verwenden? Und da Prozessortakt und Bilderzeugung von den 50Hz vom Wechselstrom abhängen, dürfte ein NTSC-Modell hier am Netz doch auch nicht schneller sein, oder? Ich sehe da potentiell nur Probleme mit dem Bild. Die verschiedenen Hacks den Prozessor höher zu takten oder durch einen höher getakteten zu ersetzen, haben immer relativ viel Aufwand getrieben, dass der Takt für den VIC sich *nicht* ändert. Wenn man beim C128 in den 2 Mhz-Modus schaltet ohne den VIC zu "deaktivieren", zeigt der jedenfalls nur flimmernden Müll an.
Benutzeravatar
Hyperion
Moderator
Beiträge: 7478
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

BlackJack hat geschrieben:@Hyperion: PAL natürlich. Könnte ich ein NTSC-Modell überhaupt hier in Deutschland verwenden?
Naja, wenn Dein Fernseher NTSC "kann", dann sollte es doch gehen, oder? Ich habe aber auch nur PAL Versionen...
Und da Prozessortakt und Bilderzeugung von den 50Hz vom Wechselstrom abhängen, dürfte ein NTSC-Modell hier am Netz doch auch nicht schneller sein, oder?
Da muss ich doch gleich mal recherchieren. Ich hatte so im Kopf, als sei das NTSC-Modell einen Ticken schneller, da es nur einen Taktgeber gab, von dem sowohl der VIC als auch die CPU direkt oder indirekt abhängig waren. Aber jetzt hast Du mich da schon verunsichert.
Benutzeravatar
Hyperion
Moderator
Beiträge: 7478
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

So, auch wenn's extrem off topic wird:

Ganz unten werden phi0 und phi2 erklärt. Daraus schließe ich, dass der CPU Takt direkt vom Bildprozessor abhängt.
http://www.c64-wiki.de/index.php/Hardwa ... au_des_C64

Hier steht das, was ich oben angenommen hatte:
http://www.8bit-museum.de/docs/comm3.htm

Nun bleibt die Frage, ob das wirklich verläßlich ist...
BlackJack

@Hyperion: Die Takterzeugung für Prozessor und Bildgenerator hängen auf jeden Fall zusammen. Da beide über den gleichen Bus auf den Speicher zugreifen, müssen die auch "synchron" laufen. Wie gesagt, die diversen "Turbokarten" für den C64 haben da immer recht viel Aufwand treiben müssen.

Die Frage ist also ob man das NTSC-Gerät mit unserem Netzstrom betreiben kann.

Die Alternative ging übrigens doch auf dem C64, also bin ich jetzt auf 15½ Minuten runter. :-) Die Idee war, nicht die Zahlen in Faktoren zu zerlegen, sondern die d(n) aus den Faktoren aufzubauen. Wenn man dafür explizit Integer-Zahlen verwendet, reicht auch auf dem C64 der BASIC-Speicher aus.
Antworten