mikrocontroller.net

Forum: Offtopic Project Euler


Autor: Bri (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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. 
;-) )

Autor: Unbekannter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Naja, das sind alles leichte Fingerüungen...

Hier mal einige Lösungsvorschläge in Haskell:


Aufgabe 1:
series n = map (*n) [1..]

merge (x:xs) (y:ys) | x < y     = x : (merge xs (y:ys))
merge (x:xs) (y:ys) | x > y     = y : (merge (x:xs) ys)
merge (x:xs) (y:ys) | otherwise = x : (merge xs ys)

numbers = takeWhile (<1000) $ merge (series 3) (series 5)

result = foldr1 (+) numbers

main = print result


Aufgabe 2:
fibonaccis = map fst $ iterate fib (1,2) where
        fib (a,b) = (b,a+b)

isEven n = n `mod` 2 == 0

numbers = takeWhile (<4000000) $ filter isEven fibonaccis

result = foldr1 (+) numbers

main = print result


Aufgabe 16 ist auch so einfach:
import Char (digitToInt)

number = 2 ^ 1000

digits = map digitToInt $ (show number)

result = foldr1 (+) digits

main = print result


Gut, ich geb zu, Haskell auf diese Aufgaben anzusetzen ist etwas gemein, 
da sehr mächtig... fieß grins

Autor: Bri (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Naja, das die ersten beiden Aufgaben nicht sehr schwer sind, wird wohl 
niemanden überraschen. Wie schauts mit Aufgabe 27 aus?

Autor: Dr. G. Reed (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Haskell ?

You never cease to amaze me!

Nie was davon gehört, ist aber recht interessant!

Autor: Unbekannter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ja, Haskell ist eine feine Sache. Bin aber etwas eingerostet. Aber egal, 
hier die Lösung zu Problem 67 in Haskell:

parse = (map.map) read . map words . lines

solve = maximum . foldl1 addRows where
        addRows sum row = zipWith maxSum (expand sum) row
        maxSum (left,right) x = (left+x) `max` (right+x)
        expand row = zip (0:row) (row++[0])

main = do
        content <- readFile "triangle.txt"
        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.

Autor: Unbekannter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hmm, manche Aufgaben sind wirklich nur triviale Einzeiler, wie z.B. 
Aufgabe 48:

main = print $ reverse $ take 10 $ reverse $ show $ sum $ map (\x->x^x) [1..1000]

Autor: Siggi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
... Engländer in der Statistik überholen  ...

Nationalist?

Autor: Bri (Gast)
Datum:

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

Autor: Bri (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
"brightest" natürlich ;-)

Autor: Lupin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
wow, haskell ist ja extrem kryptisch.

Autor: Dr. G. Reed (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Kann das mal jemand in Brainf*ck programmieren ?

Autor: Bri (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Unbekannter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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
print("hallo welt")
 wird in Haskell einfach zu
print "hallo welt"
 Wenn eine Funktion mehrer Parameter hat, kommen keine Kommas 
dazwischen.

Der $-Operator ruft Funktionen nacheinander auf, von rechts nach links. 
Anstatt
c (b (a x) )
 kann man
c $ b $ a x
 schreiben.

Ok, nun Schritt für Schritt:
[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
\foo -> ....
 erzeugt man eine "anonyme Funktion" (Lambda). Also
\x -> x^x
 ist eine Funktion, die ein Argument erhält und als Ergebnis eben x^x 
zurück gibt.

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

Autor: Katzeklo (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Kann das mal jemand in Brainf*ck programmieren ?

Ja ich find auch das sich die Gelangweilten hier mal lieber Freunde 
suchen sollten.

Autor: Unbekannter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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:


isPalindrom n = n == (read $ reverse $ show n)

main = print $ maximum $ filter isPalindrom $ [ x*y | x <- [100..999], y <- [x..999] ]


Das Ergebnis ist übrigen 906609... ;-)

Autor: Unbekannter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Zur Entspannung, hier eine Haskell-Lösung zu Aufgabe Nr. 8:

import Char (isDigit, digitToInt)
import List (tails)

parse = map digitToInt . filter isDigit

tuples n = filter ((n==).length) . map (take n) . tails

main = do
        content <- readFile "digits.txt"
        print $ maximum $ map product $ tuples 5 $ parse content

Autor: Bri (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Marius S. (lupin) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Löst hier auch jemand mit "normalen" programmiersprachen?

Autor: Bri (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ja. Ich nehm Java, da Java so eine schöne BigInteger Klasse hat, mit der 
viele Probleme sehr einfach sind.

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Unbekannter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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:

$ time ./euler-15 >/dev/null

real    0m0.003s
user    0m0.000s
sys     0m0.003s

Die Lösung hatte ich aber auch erst, als ich etwas auf Papier rumgemalt 
habe...

Autor: Bri (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Unbekannter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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...

Autor: Unbekannter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Bri (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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. :-)

Autor: Unbekannter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail, Yahoo oder Facebook? Keine Anmeldung erforderlich!
Mit Google-Account einloggen | Mit Facebook-Account einloggen
Noch kein Account? Hier anmelden.