Project Euler

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]

... Engländer in der Statistik überholen  ...

Nationalist?

"You are not the lightest bulb in the box" würde der Engländer wohl zu 
dieser dummen Unterstellung sagen!

"brightest" natürlich ;-)

wow, haskell ist ja extrem kryptisch.

Kann das mal jemand in Brainf*ck programmieren ?

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 ein

1

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.

> 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...