Geheime Ruine – Panda-Updater aktivieren

Ich wurde bereits mehrfach gefragt, ob ich bei der Einrichtung des Panda-Zonen-Updaters helfen könnte.

Daher hier mal eine kurze Zusammenfassung:

  1. Über das Externe-Seiten-Büchler in DV die Geheime Ruine auswählen und dort unter Addons den Addon Manager für den jeweiligen Browser gemäß Kurzanleitung installieren.
  2. Zurück auf DV ein paar mal die Seite neu laden, bis oben Links in der Ecke neben oder unter dem Buch von DV eine ähnliche Box mit einem Ring auftaucht.
  3. Fahrt mit der Maus über die Box und geht dann auf „Addons installieren und verwalten“
  4. Sucht in der Liste der Addons nach dem Eintrag „Panda-Zonenupdater“ und klickt direkt darunter auf installieren
  5. Das Fenster kann dann wieder geschlossen werden.
  6. Fahrt mit der Maus jetzt wieder auf das Rad oben links und wählt dieses mal den Punkt „Allgemeine Einstellungen“
  7. Ganz oben sollte ein Feld „Schlüssel registrieren“ sein, darunter der Eintrag „Kein Schlüssel registriert“.
  8. Klickt in diesem Fenster auf „Meinen Schlüssel registrieren“. Die Beschriftung über dem Button sollte sich ändern in „Aktuell registrierter Schlüssel:“ gefolgt von einer langen Zahlen-/Buchstaben-Kombination.

Ich hoffe das hilft erst einmal, ansonsten, leave a comment!

Projekt Euler in Haskell – Problem 19

Das Problem

Counting Sundays

You are given the following information, but you may prefer to do some research for yourself.

  • 1 Jan 1900 was a Monday.
  • Thirty days has September,
    April, June and November.
    All the rest have thirty-one,
    Saving February alone,
    Which has twenty-eight, rain or shine.
    And on leap years, twenty-nine.
  • A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

Lösungsansatz

Wir werden hier die Kalenderfunktionen aus der Standardbibliothek benutzen:

import Data.Time.Calendar
import Data.Time.Calendar.WeekDate

Wir erstellen jetzt damit eine Liste aller Sonntage die auf einen Monatsersten fallen innerhalb des gesuchten Zeitraumes:

sundays :: [Day]
sundays = [ fromGregorian y m 1 | y <- [1901..2000], m <- [1..12], d (toWeekDate $ fromGregorian y m 1) == 7 ]
  where
    d (_, _, w) = w

Als nächstes erfragen wir die Länge dieser Liste:

problem19 = length sundays

Das Programm

module Main where

import Data.Time.Calendar
import Data.Time.Calendar.WeekDate

main :: IO ()
main = putStrLn $ problem19

problem19 :: Int
problem19 = length sundays

sundays :: [Day]
sundays = [ fromGregorian y m 1 | y <- [1901..2000], m <- [1..12], d (toWeekDate $ fromGregorian y m 1) == 7 ]
  where
    d (_, _, w) = w

Projekt Euler in Haskell – Problem 10

Das Problem

Summation of primes

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

Find the sum of all the primes below two million.

Lösungsansatz

Die Geschichte ist mal wieder relativ simpel:

prob10 = sum $ takeWhile (< 2000000) primes

Hierzu bedienen wir uns wieder des Primzahlentests/Generators den wir bereits in Problemen 3 und 7 verwendet haben:

primes                  = filter isPrime possiblePrimes
isPrime n               = n == head (primeFactors n) -- pointfree (Control.Monad!): isPrime = ap (==) (head . primeFactors)
possiblePrimes          = 2:3:concat [ [6*pp-1, 6*pp+1] | pp <- [1..] ]
primeFactors            = pf 2
pf n m | n*n > m        = [m]
       | n*n == m       = [n,n]
       | m `mod` n == 0 = n:pf n (m `div` n)
       | otherwise      = pf (n+1) m

Hilferuf

Erneut bitte ich hier um Mithilfe… Data.Numbers.Primes aus dem Paket primes bietet eine Primzahlliste mit der die Lösung etwa 100 mal schneller gefunden wird. Diese Liste wird mit Hilfe eines “Wheel Sieves” erstellt, leider verstehe ich die Technik dahinter noch nicht. Ich würde mich über jede Hilfe freuen die hilft mir das zu verstehen, damit ich die betreffenden Probleme anpassen kann!

Projekt Euler in Haskell – Problem 9

Das Problem

Special Pythagorean triplet

A Pythagorean triplet is a set of three natural numbers, $a < b < c$, for which,

$$a^2 + b^2 = c^2$$

For example, $3^2 + 4^2 = 9 + 16 = 25 = 5^2$.

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

Lösungsansatz

Hier haben wir wieder einmal ein Problem, welches ich „eben schnell“ bruteforcen möchte.

Das ist möglich in einer einzigen Listcomprehension:

triples = [ (a, b, 1000-b-a) | a <- [1..1000], b <- [a..1000], a*a+b*b == (1000-b-a)*(1000-b-a) ]

Diese Liste enthält sämtliche pythagoräischen Tripple für die gilt $a+b+c=1000$ und da wir bereits aus der Aufgabenstellung heraus wissen, dass es davon nur eines gibt, bekommen wir auf folgende Art das Produkt dieser Zahlen:

problem9 = (\ (a, b, c) -> a*b*c) $ head triples

Farbiger GHCi-Prompt mit λ und geladenen Modulen in getrennten Zeilen

Ich habe gerade auf Coderwall einen Beitrag zum Thema verfasst, da er dort allerdings auf englisch ist, möchte ich eine deutsche Übersetzung meinen Lesern nicht vorenthalten:

Wenn man sich den GHCi-Prompt anderer Entwickler ansieht, findet man oft einen sehr einfachen wie den folgenden:

λ>

Der ist sehr einfach zu erreichen indem man das folgende Schnipsel in seine ~/.ghci schreibt:

:set prompt "\ESC[34mλ> \ESC[m"

Wobei das \ESC[34m der ANSI-Code für einen blauen Vordergrund ist und das \ESC[m diese Attribute wieder entfernt.

Aber ich weiß auch immer gerne, welche Module in den GHCi geladen sind und welche davon interpretiert und welche kompiliert, also erweiterte ich den oben gezeigten Prompt:

:set prompt "\ESC[1;34m%s\n\ESC[0;34mλ> \ESC[m"

\ESC[1;34m%s\n erzeugt hier die erste Zeile, welche die geladenen Module in einem satten Blau zeigt, wohingegen \ESC[0;34mλ> \ESC[m den Prompt wie oben gezeigt setzt, nur dass ich das „satte“ Blau explizit als ein „normales“ Blau haben möchte.

Mit dem neuen Prompt hat man jetzt alles was wichtig ist… Da sind die Farben um schnell den letzten Prompt zu finden, das coole λ das jeder „echte“ Haskell-Programmierer haben muss und man sieht zu jeder Zeit welche Module gerade geladen sind (und weil diese Zeile auch farbig ist, hilft sie ebenfalls den letzten Prompt wieder zu finden).

Mehr zu ANSI-Escape-Sequenzen (engl.)

Projekt Euler in Haskell – Problem 8

Das Problem

Largest product in a series

Find the greatest product of five consecutive digits in the 1000-digit number.

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

Lösung im IO-Monad

Na, dann wollen wir mal…

Meine erste Überlegung war, die Zahl als Integer direkt im Quelltext abzulegen und dann eine digits-Funktion zu schreiben. Diese hätte darauf aufgebaut, die Zahl in einen String einzulesen und dann jedes Zeichen wieder einen Int umzuwandeln. Also statt Integer nach String umzuwandeln, habe ich mich dazu entschlossen, die Zahl direkt als String anzugeben:

theNumber = "<die Zahl>"

Auf der anderen Seite wollte ich mich schon immer ein wenig mit IO beschäftigen und habe deswegen die Zahl einfach in eine Textdatei geschrieben und als prob8.txt abgespeichert, in mein Programm kommt sie wie folgt:

readNumber = readFile "prob8.txt" >>= return

Und um zu verhindern, dass uns irgendwelche Newlines am Ende der Textdatei stören, machen wir folgendes:

readNumber = readFile "prob8.txt" >>= return . head . lines

Das wandeln wir dann jetzt in eine Liste von Ints um:

import Data.Char
digits = readNumber >>= return . (map digitToInt)

Also haben wir jetzt in intify eine Liste mit unseren 1000 Stellen.

Nun brauchen wir eine Liste mit jeweils 5 aufeinanderfolgenden Stellen:

import Data.List
consecutive = do
  theDigits <- digits
  return $ map (take 5) (tails theDigits)

Mithilfe des Bind-Operators (>>=) lässt sich dieser Abschnitt ähnlich umschreiben wie auch die oberen beiden, auch wenn ich hier deutlich länger gebraucht habe, um herauszufinden, dass ich zweimal ein return benötige:

consecutiv = digits >>= return . tails >>= return . map (take 5)

Hiervon jeweils das Produkt und am Ende davon das größte:

products = consecutiv >>= return . map product
problem8 = products >>= return . maximum

Und hier noch einmal die Zusammenfassung (heute sogar mit Typ!):

problem8 :: IO Int
problem8 = products >>= return . maximum

readNumber :: IO String
readNumber = readFile "prob8.txt" >>= return . head . lines

digits :: IO [Int]
digits = readNumber >>= return . (map digitToInt)

consecutiv :: IO [[Int]]
consecutiv = digits >>= return . tails >>= return . map (take 5)

products :: IO [Int]
products = consecutiv >>= return . map product
$ time ./prob8
40824
./prob8  0.00s user 0.00s system 85% cpu 0.004 total

Ohne Fischgräten (Bind, >>=)!

Habe gerade mal hlint drüber laufen lassen, und der machte ein paar schöne Vorschläge, so dass der Code nun so aussieht:

module Main where

import           Control.Monad (liftM)
import           Data.Char     (digitToInt)
import           Data.List     (tails)

main :: IO ()
main = problem8 >>= print

problem8 :: IO Int
problem8 = liftM maximum products

readNumber :: IO String
readNumber = liftM (head . lines) (readFile "prob8.txt")

digits :: IO [Int]
digits = liftM (map digitToInt) readNumber

consecutiv :: IO [[Int]]
consecutiv = liftM (map (take 5) . tails) digits

products :: IO [Int]
products = liftM (map product) consecutiv

Aber einen Performancegewinn bringt das nicht. Es ist so lediglich etwas lesbarer, zumindest empfinde ich das so.

Projekt Euler in Haskell – Problem 7

10001st prime

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?

Wir suchen also die 10001ste Primzahl.

Es bleibt uns hier wohl kaum etwas anderes über, als uns eine Liste zu erstellen, die die Primzahlen enthält und hier auf Element 10000 zuzugreifen.

primes = [ x | x <- [1..], isPrime x ]

Diese Variante überprüft jede natürliche Zahl auf ihre primalität und fügt sie ggf der Liste hinzu.

Allerdings wissen wir auch, dass jede Primzahl größer $3$ darstellbar ist als $6k+1$ oder $6k-1$, wir erstellen uns also zuerst eine Liste möglicher Primzahlen:

possiblePrimes = 2:3:concat [ [6*pp-1, 6*pp+1] | pp <- [1..] ]

Im nächsten Schritt befüllen wir damit unsere Liste primes:

primes = filter isPrime possiblePrimes

Jetzt fehlt nur noch isPrime:

Prim ist jede Zahl, die bei der Primfaktorenzerlegung höchstens einen Faktor hat, nämlich sich selbst:

isPrime n = length (primeFactors n) == 1

primeFactors = pf 2
  where
    pf n m | n*n > m        = [m]
           | n*n == m       = [n,n]
           | m `mod` n == 0 = n:pf n (m `div` n)
           | otherwise      = pf (n+1) m

Wobei ich hier primeFactors aus Problem 3 – Largest prime factor übernommen habe. Problem dabei ist allerdings, dass jedes Element der Liste für length einmal komplett berechnet werden muss um die tatsächliche Länge der Liste zu ermitteln.

Als einen weiteren Ansatz hatte ich dann diesen hier:

isPrime n = onlyOneElementIn (primeFactors n)
  where
    onlyOneElementIn (_:xs) | null xs   = True
                            | otherwise = False

Sieht nicht nur doof aus, es ist auch so… Da ja primeFactors ohnehin eine geordnete Liste ausspuckt, kann ich doch auch gleich folgendes sagen:

isPrime n = n == head (primeFactors n)

und gieße mir das ganze zusammen in eine Funktion:

problem7 = primes!!10000 -- Index startet bei 0!
  where
    primes                  = filter isPrime possiblePrimes
    isPrime n               = n == head (primeFactors n) -- pointfree (Control.Monad!): isPrime = ap (==) (head . primeFactors)
    possiblePrimes          = 2:3:concat [ [6*pp-1, 6*pp+1] | pp <- [1..] ]
    primeFactors            = pf 2
    pf n m | n*n > m        = [m]
           | n*n == m       = [n,n]
           | m `mod` n == 0 = n:pf n (m `div` n)
           | otherwise      = pf (n+1) m

Diese Variante dauert zwar extrem lange, aber sie funktioniert und ist von mir selbst. Den WheelSieve Ansatz den Data.Numbers.Primes.primes geht kann ich leider nicht wirklich nachvollziehen, aber damit habe ich das Ergebniss in weniger als einer halben Sekunde…

Vielleicht ist ja jemand hier, der mir das erklären würde, dann kann ich den Code hier gerne anpassen!

Projekt Euler in Haskell – Problem 6

Und ein weiteres schönes Problem:

Sum square difference

The sum of the squares of the first ten natural numbers is,

\[ 1^2 + 2^2 + \cdots + 10^2 = 385 \]

The square of the sum of the first ten natural numbers is,

\[ (1 + 2 + \cdots + 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.

Also gefragt ist das folgende:

\[ \left( \sum_{i=1}^{100} i \right)^2 - \left( \sum_{i=1}^{100} i^2 \right) \]

Was man auch ausdrücken kann wie folgt:

\[ \begin{align*}
& \left( \frac{n^2 + n}2 \right)^2 - \left( \frac{n \left( n+1 \right)\left( 2n+1 \right)}6 \right) && \text{mit $n=100$} \\
& \left( \frac{100^2 + 100}2 \right)^2 - \left( \frac{100 \left( 100+1 \right)\left(2\times100+1\right)}6 \right)
\end{align*} \]

Aber wir nehmen die allgemein Form und mischen sie wie folgt zusammen:

problem6 = squareOfSums 100 - sumOfSquares 100
  where
    squareOfSums n = ((n*n+n) `div` 2)^2
    sumOfSquares n = (n*(n+1)*(2*n+1)) `div` 6

Projekt Euler in Haskell – Problem 5

Smallest multiple

\(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\)?

Also, wo mit geht es los? Mit der Überlegung!

Wir wollen also \(kgV(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20)\) berechnen. In Haskell heißt die Funktion dafür lcm und ist leider nur zweistellig. Wir müssen also ein lcmList entwerfen, welches eine Liste annimmt und das auf einfache lcm Aufrufe runterbricht.

Dafür muss mann wissen, dass

\[ \begin{align*}
& kgV(1,2,3,4) \\
\equiv & kgV\left(1,kgV\left(2,3,4\right)\right) \\
\equiv & kgV\left(1,kgV\left(2,kgV\left(3,4\right)\right)\right)
\end{align*} \]

Das sieht doch verdächtig nach einer gefalteten Liste aus!

Also falten wir mal drauf los:

lcmList = foldr1 lcm

Und der lcmList werfen wir nun alle Zahlen von \(1\) bis \(20\) zum „Fraß“ vor (ehrlich gesagt ist die \(1\) sowas von unnötig und wird keinerlei Auswirkungen auf das Ergebniss haben):

problem5 = lcmList [2..20]

Projekt Euler in Haskell – Problem 4

Und wieder ein schnelles und kleines Problem aus der Project Euler Welt:

Largest palindrome product

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

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

Auf die Schnelle fallen mir 2 Möglichkeiten ein, ich werde aber nur eine vertiefen:

  1. Erzeugen aller möglichen Ergebnisse wenn man zwei dreistellige Zahlen miteinander multipliziert.
  2. Erzeugen der Palindrome von oben beginnend und dann prüfen ob sie sich durch die Multiplikation zweier dreistelliger Zahlen erzeugen lässt.

Ich habe mich für Variante 1) entschieden, weil sie sich mit deutlich weniger Code einrichten lässt.

Aber schauen wir uns zuerst einmal das ganze an. Wie überprüfen wir ob es sich bei einer Zahl um ein Palindrom handelt?

Mir fielen auch hier zwei Wege ein, entweder wir zerlegen die Zahl in eine Liste von Ints, also aus 1234 wird dann [1,2,3,4] und vergleichen sie mit der umgedrehten Liste. Eine entsprechende Funktion müssten wir aber erst schreiben, also wandeln wir unsere Zahl mit show in einen String um:

isPalindrome n = show n == reverse (show n)

Und weil ich gerade auf das Tool pointfree gestoßen wurde, hier die pointfree-Variante:

isPalindrome' = liftM2 (==) show (reverse . show)

Ich verzichte hier allerdings auf Pointfree-Style, weil ich auf imports verzichten möchte und liftM2 befindet sich in Control.Monad. Davon abgesehen ist die Pointfull-Variante deutlich lesbarer.

Die Liste der Palindrome erzeugen wir relativ einfach mit der folgenden Funktion:

palindromes = [ n * m | n <- [100..999], m <- [100..999], isPalindrome (n*m) ]

Aber das dauert unnötig lange. Immerhin wissen wir, dass \(m \times n \equiv n \times m\), wir brauchen also \(m\) höchstens so groß werden lassen wie \(n\):

palindromes' = [ n * m | n <- [100..999], m <- [100..n], isPalindrome (n*m) ]

Und aus dieser Liste brauchen wir das Maximum:

problem4 = maximum palindromes'