Personal tools

Euler problems/101 to 110

From HaskellWiki

< Euler problems(Difference between revisions)
Jump to: navigation, search
(Removing category tags. See Talk:Euler_problems)
Line 27: Line 27:
   
 
Solution:
 
Solution:
  +
  +
Very nice problem. I didnt realize you could deal with the precision problem.
  +
Therefore I used this identity to speed up the fibonacci calculation:
  +
f_(2*n+k)
  +
= f_k*(f_(n+1))^2
  +
+ 2*f_(k-1)*f_(n+1)*f_n
  +
+ f_(k-2)*(f_n)^2
  +
 
<haskell>
 
<haskell>
problem_104 = undefined
+
import Data.List
  +
import Data.Char
  +
  +
fibos = rec 0 1
  +
where
  +
rec a b = a:rec b (a+b)
  +
  +
fibo_2nk n k =
  +
let
  +
fk = fibo k
  +
fkm1 = fibo (k-1)
  +
fkm2 = fibo (k-2)
  +
fnp1sq = fnp1^2
  +
fnp1 = fibo (n+1)
  +
fn = fibo n
  +
fnsq = fn^2
  +
in
  +
fk*fnp1sq + 2*fkm1*fnp1*fn + fkm2*fnsq
  +
  +
fibo x =
  +
let
  +
threshold = 30000
  +
n = div x 3
  +
k = n+mod x 3
  +
in
  +
if x < threshold
  +
then fibos !! x
  +
else fibo_2nk n k
  +
  +
findCandidates = rec 0 1 0
  +
where
  +
m = 10^9
  +
rec a b n =
  +
let
  +
continue = rec b (mod (a+b) m) (n+1)
  +
isBackPan a = (sort $ show a) == "123456789"
  +
in
  +
if isBackPan a
  +
then n:continue
  +
else continue
  +
search =
  +
let
  +
isFrontPan x = (sort $ take 9 $ show x) == "123456789"
  +
in
  +
map fst
  +
$ take 1
  +
$ dropWhile (not.snd)
  +
$ zip findCandidates
  +
$ map (isFrontPan.fibo) findCandidates
  +
  +
problem_104 = search
 
</haskell>
 
</haskell>
+
It took 8 sec on a 2.2Ghz machine.
 
== [http://projecteuler.net/index.php?section=view&id=105 Problem 105] ==
 
== [http://projecteuler.net/index.php?section=view&id=105 Problem 105] ==
 
Find the sum of the special sum sets in the file.
 
Find the sum of the special sum sets in the file.

Revision as of 16:40, 30 November 2007

Contents

1 Problem 101

Investigate the optimum polynomial function to model the first k terms of a given sequence.

Solution:

problem_101 = undefined

2 Problem 102

For how many triangles in the text file does the interior contain the origin?

Solution:

problem_102 = undefined

3 Problem 103

Investigating sets with a special subset sum property.

Solution:

problem_103 = undefined

4 Problem 104

Finding Fibonacci numbers for which the first and last nine digits are pandigital.

Solution:

Very nice problem. I didnt realize you could deal with the precision problem. Therefore I used this identity to speed up the fibonacci calculation: f_(2*n+k) = f_k*(f_(n+1))^2 + 2*f_(k-1)*f_(n+1)*f_n + f_(k-2)*(f_n)^2

import Data.List
import Data.Char
 
fibos = rec 0 1
    where
        rec a b = a:rec b (a+b)
 
fibo_2nk n k = 
    let
        fk = fibo k
        fkm1 = fibo (k-1)
        fkm2 = fibo (k-2)
        fnp1sq = fnp1^2
        fnp1 = fibo (n+1)
        fn = fibo n
        fnsq = fn^2
    in
        fk*fnp1sq + 2*fkm1*fnp1*fn + fkm2*fnsq
 
fibo x = 
    let
        threshold = 30000
        n = div x 3
        k = n+mod x 3
    in
        if x < threshold 
        then fibos !! x
        else fibo_2nk n k
 
findCandidates = rec 0 1 0
    where
        m = 10^9
        rec a b n  =
            let
                continue = rec b (mod (a+b) m) (n+1)
                isBackPan a = (sort $ show a) == "123456789"
            in
                if isBackPan a 
                then n:continue
                else continue
search = 
    let
        isFrontPan x = (sort $ take 9 $ show x) == "123456789"
    in
        map fst
            $ take 1
            $ dropWhile (not.snd)            
            $ zip findCandidates
            $ map (isFrontPan.fibo) findCandidates
 
problem_104 = search

It took 8 sec on a 2.2Ghz machine.

5 Problem 105

Find the sum of the special sum sets in the file.

Solution:

problem_105 = undefined

6 Problem 106

Find the minimum number of comparisons needed to identify special sum sets.

Solution:

problem_106 = undefined

7 Problem 107

Determining the most efficient way to connect the network.

Solution:

problem_107 = undefined

8 Problem 108

Solving the Diophantine equation 1/x + 1/y = 1/n.

Solution:

problem_108 = undefined

9 Problem 109

How many distinct ways can a player checkout in the game of darts with a score of less than 100?

Solution:

problem_109 = undefined

10 Problem 110

Find an efficient algorithm to analyse the number of solutions of the equation 1/x + 1/y = 1/n.

Solution:

problem_110 = undefined