Wenn ihr mal bissl was machen wollt, um euch geistig fitt zu halten oder wenn ihr einfach nur Spass an Mathe + Programmieren habt, dann kann ich euch die Seite hier wärmstens empfehlen: http://projecteuler.net (Außerdem will ich die Engländer in der Statistik überholen und deshalb müsst ihr mindestens eine Aufgabe lösen, was kein Problem sein sollte. ;-) )
Naja, das sind alles leichte Fingerüungen... Hier mal einige Lösungsvorschläge in Haskell: Aufgabe 1:
1 | series n = map (*n) [1..] |
2 | |
3 | merge (x:xs) (y:ys) | x < y = x : (merge xs (y:ys)) |
4 | merge (x:xs) (y:ys) | x > y = y : (merge (x:xs) ys) |
5 | merge (x:xs) (y:ys) | otherwise = x : (merge xs ys) |
6 | |
7 | numbers = takeWhile (<1000) $ merge (series 3) (series 5) |
8 | |
9 | result = foldr1 (+) numbers |
10 | |
11 | main = print result |
Aufgabe 2:
1 | fibonaccis = map fst $ iterate fib (1,2) where |
2 | fib (a,b) = (b,a+b) |
3 | |
4 | isEven n = n `mod` 2 == 0 |
5 | |
6 | numbers = takeWhile (<4000000) $ filter isEven fibonaccis |
7 | |
8 | result = foldr1 (+) numbers |
9 | |
10 | main = print result |
Aufgabe 16 ist auch so einfach:
1 | import Char (digitToInt) |
2 | |
3 | number = 2 ^ 1000 |
4 | |
5 | digits = map digitToInt $ (show number) |
6 | |
7 | result = foldr1 (+) digits |
8 | |
9 | main = print result |
Gut, ich geb zu, Haskell auf diese Aufgaben anzusetzen ist etwas gemein, da sehr mächtig... fieß grins
Naja, das die ersten beiden Aufgaben nicht sehr schwer sind, wird wohl niemanden überraschen. Wie schauts mit Aufgabe 27 aus?
Haskell ? You never cease to amaze me! Nie was davon gehört, ist aber recht interessant!
Ja, Haskell ist eine feine Sache. Bin aber etwas eingerostet. Aber egal, hier die Lösung zu Problem 67 in Haskell:
1 | parse = (map.map) read . map words . lines |
2 | |
3 | solve = maximum . foldl1 addRows where |
4 | addRows sum row = zipWith maxSum (expand sum) row |
5 | maxSum (left,right) x = (left+x) `max` (right+x) |
6 | expand row = zip (0:row) (row++[0]) |
7 | |
8 | main = do |
9 | content <- readFile "triangle.txt" |
10 | print $ solve $ parse content |
Wer schafft in seiner Lieblings-Sprache eine schönere Variante?
> Wie schauts mit Aufgabe 27 aus?
Ist auch nicht schwer bzw. reine Fleißarbeit. Man benötigt einen
schnellen Test auf Primzahlen und probiert die vier Millionen
Gleichungen durch.
Hmm, manche Aufgaben sind wirklich nur triviale Einzeiler, wie z.B. Aufgabe 48:
1 | main = print $ reverse $ take 10 $ reverse $ show $ sum $ map (\x->x^x) [1..1000] |
"You are not the lightest bulb in the box" würde der Engländer wohl zu dieser dummen Unterstellung sagen!
Also bis jetzt hab ich das Gefühl, das sich die meisten Aufgaben mit Java am einfachsten lösen lassen. Z.B. hat Java eine tolle Kalender-Klasse, mit der die Aufgabe mit den Sonntagen einfach zu lösen ist und Java hat die BigInteger-Klasse, mit der viele der Zahlenspielereien kein Problem mehr sind. Lässt sich eigentlich die Aufgabe 4 mit Haskell ohne große Umstände lösen? Also die Prüfung, ob es ein Palindrom ist, stell ich mir schwierig vor, falls es dafür keine eingebaute Funktion gibt.
> wow, haskell ist ja extrem kryptisch.
Ne, eigentlich überhaupt nicht. Es ist nur nicht die hunderste
"Erfindung" einer irgendwie gearteten C-Variante. Da es eine funktionale
Sprache ist, ist Haskells Stärke eben der Umgang mit Funktionen, Listen
und Pattern-Matching auf Argumente. Funktionen wie map, filter, fold,
zip in ihren verschiedenen Variationen lesen sich für ein
Haskell-Programmierer wie break, continue, while, return, switch etc.
für C-Programmierer.
Hier mal eine Erklärung der Lösung zur Aufgabe 48:
Grundsätzlich werden die Argumente zu Funktionen in Haskell ohne
Klammern geschrieben. In C ein1 | print("hallo welt")
|
wird in Haskell einfach zu
1 | print "hallo welt" |
Wenn eine Funktion mehrer Parameter hat, kommen keine Kommas dazwischen. Der $-Operator ruft Funktionen nacheinander auf, von rechts nach links. Anstatt
1 | c (b (a x) ) |
kann man
1 | c $ b $ a x |
schreiben. Ok, nun Schritt für Schritt:
1 | [1..1000] |
erzeugt eine Liste (lineare Liste) mit den Zahlen 1 bis 1000. Die Funktion "map" hat zwei Parameter. Der erste eine Funktion, der zweite eine Liste. Map ruft für jedes Element der Liste die Funktion auf und speichert das Ergebnis in einer neuen Liste. Mit
1 | \foo -> .... |
erzeugt man eine "anonyme Funktion" (Lambda). Also
1 | \x -> x^x |
ist eine Funktion, die ein Argument erhält und als Ergebnis eben x^x zurück gibt. Kombiniert:
1 | map (\x->x^x) [1..1000] |
macht aus einer Liste [1,2,3,4,...] eine Liste [1,4,27,256,...]. Weiter: Die Funktion sum addiert alle Elemente einer Liste zusammen. Die Funktion show macht aus einer Zahl ein String. Ein String ist eine Liste aus Zeichen. Die Funktion reverse dreht eine Liste um, in diesem Fall wird der String also rückwärts. Die Funktion take nimmt eine bestimmte Anzahl von Elementen einer Liste vom Anfang, also take 10 nimmt die ersten 10 Zeichen des Strings (in Wirklichkeit die letzten 10, weil wir den String ja gespiegelt haben). Der nächste Schritt ist diese 10 Zeichen wieder umzudrehen. Dann bleibt noch print übrig. Das war's. Überhaupt nicht kryptisch.
>Kann das mal jemand in Brainf*ck programmieren ?
Ja ich find auch das sich die Gelangweilten hier mal lieber Freunde
suchen sollten.
> Lässt sich eigentlich die Aufgabe 4 mit Haskell ohne große > Umstände lösen? Ja. > Also die Prüfung, ob es ein Palindrom ist, stell ich mir > schwierig vor, falls es dafür keine eingebaute Funktion gibt. Gibt keine eingebaute Funktion dafür, ist aber trivial. Komplette Lösung Aufgabe 4:
1 | isPalindrom n = n == (read $ reverse $ show n) |
2 | |
3 | main = print $ maximum $ filter isPalindrom $ [ x*y | x <- [100..999], y <- [x..999] ] |
Das Ergebnis ist übrigen 906609... ;-)
Zur Entspannung, hier eine Haskell-Lösung zu Aufgabe Nr. 8:
1 | import Char (isDigit, digitToInt) |
2 | import List (tails) |
3 | |
4 | parse = map digitToInt . filter isDigit |
5 | |
6 | tuples n = filter ((n==).length) . map (take n) . tails |
7 | |
8 | main = do |
9 | content <- readFile "digits.txt" |
10 | print $ maximum $ map product $ tuples 5 $ parse content |
Hast du schon die Aufgabe 15 gelöst? Die fand ich bis jetzt am anspruchsvollsten, weil die Lösung ohne bissl Optimierung extrem lange dauert.
Ja. Ich nehm Java, da Java so eine schöne BigInteger Klasse hat, mit der viele Probleme sehr einfach sind.
Problem 16 ist gut ;) >2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26. >What is the sum of the digits of the number 2^1000? Ich sage 1 ;) Gruß Hagen
> Hast du schon die Aufgabe 15 gelöst?
Ja. Es sind rund 137 Milliarden Möglichkeiten... Mit einem naiven Ansatz
kommt man nicht so weit:
1 | $ time ./euler-15 >/dev/null |
2 | |
3 | real 0m0.003s |
4 | user 0m0.000s |
5 | sys 0m0.003s |
Die Lösung hatte ich aber auch erst, als ich etwas auf Papier rumgemalt habe...
Ich hab die Aufgabe 15 erstmal brute force mäßig rekursiv programmiert. Also von einem Punkt aus gibts immer 2 Richtungen, nach unten und nach rechts. Nachdem nach 10min immer noch kein Ergebnis da war, hab ich mir die Zwischenergebnisse für die Punkte einfach in einem Feld abgespeichert. D.h. von jedem Punkt aus gibts ja immer eine feste Anzahl von Wegen, die sich nicht ändert. Wenn nun der Algorithmus merkt, das dieser Weg schonmal beschritten wurde, dann kann er einfach aus dem Feld die Zahl der Wege nehmen und den eigenen dazu addieren. Erstaunlich wie diese einfache Änderung die Lösung beschleunigt. Es dauert dann weniger als 1s. Die Aufgaben 18 und 67 sind ganz ähnlich. Wieviel Aufgaben hast du schon gelöst?
> D.h. von jedem Punkt aus gibts ja immer eine feste Anzahl > von Wegen, die sich nicht ändert. Ja. > Wenn nun der Algorithmus merkt, das dieser Weg schonmal > beschritten wurde, dann kann er einfach aus dem Feld > die Zahl der Wege nehmen und den eigenen dazu addieren. Ja, Du bist der endgültigen Lösung schon sehr nahe... Mal Dir mal ein 4er Quadrat auf Papier und dann schreibe an jeden Gittepunkt die Anzahl der Möglichkeiten diesen Punkt zu erreichen. Der Startpunkt hat nur eine Möglichkeit. Zwischen den Gitterpunkten malst Du Pfeile, wie Du laufen darfst. Dann kannst Du das Papier mal 45° nach rechts drehen. Es steht dann auf dem Ziel-Eck. Wenn Du es immer noch nicht siehst, kannst Du links und rechts "Füße" aus Möglichkeiten und Pfeilen nach dem vorherigen Schema dazu malen, damit das Quadrat zu einem rechtwinklen Dreieck wird das auf der Hypotenuse steht. Dann schaust Du Dir das Dreieck genau an...
Ach so, falls Du noch nicht registriert bist, es lohnt sich. Diskussionforen zu den einzelen Aufgaben (nur die gelösten) und zu manchen Aufgaben nähere Informationen und Ausblicke.
Meine Lösung war schon schnell genug. Alles was unter 1s fertig ist, da lohnt sich das optimieren nicht mehr. Ich hab mitlerweile 24 Aufgaben fertig und bin grad dabei Level 1 zu erreichen. :-)
Hmm, also meine alte Behauptung dass das alles leichte Fingerübungen sind, nehm ich mal zurück... Inzwischen habe ich 85 Aufgaben gelöst und mir fehlen noch 15 Aufgaben bis zum Level 3...
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.