/projectEuler

Solutions to some Project Euler problems

Primary LanguageHaskellMIT LicenseMIT

After losing most of my original solutions I decided to github if I solve anything. Gives me an incentive to keep my code clean.

Content:

7. 10001st prime.

Problem | Solution

Haskell's show-off example: "Sieve of Eratosthenes"

time cabal run 7 10001
Preprocessing executable '7' for projecteuler-0.1.0.0...
104743

real    0m5.074s
user    0m4.543s
sys     0m0.503s

49. Prime permutations.

Problem | Solution

This one is written in Go because I am learning go now.

For each prime between 1000 and 10000 generate all permutations, and then keep permutations that are primes only. Then for all candidate set choose 3 and check whether smallest + largest = 2 * middle.

time go run 49.go
296962999629

real    0m0.414s
user    0m0.367s
sys     0m0.107s

49 Prime permutations (Haskell).

Problem | Solution

Just to compare it to haskell solution, I am including a 2-liner.

time cabal run 49
Preprocessing executable '49' for projecteuler-0.1.0.0...
Running 49...
296962999629

real    0m1.703s
user    0m1.433s
sys     0m0.290s

50. Consecutive prime sum.

Problem | Solution

Very first and naive implementation gave me the right answer, but the time needs to be improved.

time cabal run 50 1000000
Preprocessing executable '50' for projecteuler-0.1.0.0...
997651

real    2m54.542s
user    2m54.157s
sys     0m0.350s

79. Passcode derivation.

Problem | Solution

Solution to 79'th problem without the assumption of non-repeats. Algorithm: with each successful attempt generate all shortest passwords for each shortest password generated so far.

time cabal run 79 ./data/keylog.txt
Preprocessing executable '79' for projecteuler-0.1.0.0...
73162890

real    0m1.245s
user    0m0.910s
sys     0m0.320s

88. Product-sum numbers.

Problem | Solution

Brute forces decomposition via factorisation and backtracking.

time cabal run 88
Preprocessing executable '88' for projecteuler-0.1.0.0...
7587457

real    0m8.768s
user    0m8.363s
sys     0m0.390s

96. Su Doku.

Problem | Solution

Backtracking depth-first algorithm. At each step pick a square with least number of guesses.

time cabal run 96 ./data/p096_sudoku.txt
Preprocessing executable '96' for projecteuler-0.1.0.0...
24702

real    0m2.429s
user    0m2.090s
sys     0m0.323s