Difference between revisions of "Euler problems/101 to 110"
Line 1:  Line 1:  
−  == [http://projecteuler.net/index.php?section= 
+  == [http://projecteuler.net/index.php?section=problems&id=101 Problem 101] == 
Investigate the optimum polynomial function to model the first k terms of a given sequence. 
Investigate the optimum polynomial function to model the first k terms of a given sequence. 

Line 7:  Line 7:  
</haskell> 
</haskell> 

−  == [http://projecteuler.net/index.php?section= 
+  == [http://projecteuler.net/index.php?section=problems&id=102 Problem 102] == 
For how many triangles in the text file does the interior contain the origin? 
For how many triangles in the text file does the interior contain the origin? 

Line 32:  Line 32:  
</haskell> 
</haskell> 

−  == [http://projecteuler.net/index.php?section= 
+  == [http://projecteuler.net/index.php?section=problems&id=103 Problem 103] == 
Investigating sets with a special subset sum property. 
Investigating sets with a special subset sum property. 

Line 42:  Line 42:  
</haskell> 
</haskell> 

−  == [http://projecteuler.net/index.php?section= 
+  == [http://projecteuler.net/index.php?section=problems&id=104 Problem 104] == 
Finding Fibonacci numbers for which the first and last nine digits are pandigital. 
Finding Fibonacci numbers for which the first and last nine digits are pandigital. 

Line 111:  Line 111:  
The lesson I learned fom this challenge, is: know mathematical identities and exploit them. They allow you take short cuts. 
The lesson I learned fom this challenge, is: know mathematical identities and exploit them. They allow you take short cuts. 

Normally you compute all previous fibonacci numbers to compute a random fibonacci number. Which has linear costs. The aforementioned identity builds the number not from its two predecessors but from 4 much smaller ones. This makes the algorithm logarithmic in its complexity. It really shines if you want to compute a random very large fibonacci number. f.i. the 10mio.th fibonacci number which is over 2mio characters long, took 20sec to compute on my 2.2ghz laptop. 
Normally you compute all previous fibonacci numbers to compute a random fibonacci number. Which has linear costs. The aforementioned identity builds the number not from its two predecessors but from 4 much smaller ones. This makes the algorithm logarithmic in its complexity. It really shines if you want to compute a random very large fibonacci number. f.i. the 10mio.th fibonacci number which is over 2mio characters long, took 20sec to compute on my 2.2ghz laptop. 

−  == [http://projecteuler.net/index.php?section= 
+  == [http://projecteuler.net/index.php?section=problems&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. 

Solution: 
Solution: 

<haskell> 
<haskell> 

−  import List 
+  import Data.List 
+  import Control.Monad 

import Text.Regex 
import Text.Regex 

−  ghc M p105.hs 

+  
−  digitstwo n k 

+  solNum=map solve [7..12] 

−  k==0=[] 

+  solve n = twoSetsOf [0..n1] =<< [2..div n 2] 

−  otherwise= y:digitstwo x (k1) 

+  twoSetsOf xs n = do 

+  firstSet < setsOf n xs 

+  let rest = dropWhile (/= head firstSet) xs \\ firstSet 

+  secondSet < setsOf n rest 

+  let f = firstSet >>= enumFromTo 1 

+  s = secondSet >>= enumFromTo 1 

+  guard $ not $ null (f \\ s)  null (s \\ f) 

+  [(firstSet,secondSet)] 

+  
+  setsOf 0 _ = [[]] 

+  setsOf (n+1) xs = concat [map (y:) (setsOf n ys)  (y:ys) < tails xs] 

+  comp lst a b= 

+  a1/=b1 

where 
where 

−  +  a1=sum$map (lst!!) a 

−  +  b1=sum$map (lst!!) b 

−  +  notEqu lst = 

−  +  all id[comp slst a b(a,b)<solNum!!s] 

−  let a=digitstwo n len, 

−  sum a<=mlen, 

−  let t=zip lst a, 

−  let sl=delzero t 

−  ] 

where 
where 

−  +  s=length lst7 

−  +  slst=sort lst 

−  delzero x=[a(a,b)<x,b/=0] 

−  notEqu lst su= 

−  length sm ==(length.nub) sm 

−  where 

−  sm=[sum aa<su] 

moreElem lst = 
moreElem lst = 

−  +  all id maE 

where 
where 

le=length lst 
le=length lst 

Line 144:  Line 156:  
] 
] 

maE=[a<b(a,b)<zip maxElem minElem] 
maE=[a<b(a,b)<zip maxElem minElem] 

−  +  stoInt s=map read (splitRegex (mkRegex ",") s) :: [Integer] 

−  +  check x=moreElem x && notEqu x 

−  +  main = do 

−  +  f < readFile "sets.txt" 

−  +  let sets = map stoInt$ lines f 

−  +  let ssets = filter check sets 

−  +  print $ sum $ concat ssets 

−  notEqu a $subset a 

−  ] 

−  print $sum$concat sm 

</haskell> 
</haskell> 

−  == [http://projecteuler.net/index.php?section= 
+  == [http://projecteuler.net/index.php?section=problems&id=106 Problem 106] == 
Find the minimum number of comparisons needed to identify special sum sets. 
Find the minimum number of comparisons needed to identify special sum sets. 

Line 174:  Line 186:  
</haskell> 
</haskell> 

−  == [http://projecteuler.net/index.php?section= 
+  == [http://projecteuler.net/index.php?section=problems&id=107 Problem 107] == 
Determining the most efficient way to connect the network. 
Determining the most efficient way to connect the network. 

Line 182:  Line 194:  
</haskell> 
</haskell> 

−  == [http://projecteuler.net/index.php?section= 
+  == [http://projecteuler.net/index.php?section=problems&id=108 Problem 108] == 
Solving the Diophantine equation 1/x + 1/y = 1/n. 
Solving the Diophantine equation 1/x + 1/y = 1/n. 

Line 197:  Line 209:  
</haskell> 
</haskell> 

−  == [http://projecteuler.net/index.php?section= 
+  == [http://projecteuler.net/index.php?section=problems&id=109 Problem 109] == 
How many distinct ways can a player checkout in the game of darts with a score of less than 100? 
How many distinct ways can a player checkout in the game of darts with a score of less than 100? 

Line 205:  Line 217:  
</haskell> 
</haskell> 

−  == [http://projecteuler.net/index.php?section= 
+  == [http://projecteuler.net/index.php?section=problems&id=110 Problem 110] == 
Find an efficient algorithm to analyse the number of solutions of the equation 1/x + 1/y = 1/n. 
Find an efficient algorithm to analyse the number of solutions of the equation 1/x + 1/y = 1/n. 

Revision as of 13:37, 26 January 2008
Contents
Problem 101
Investigate the optimum polynomial function to model the first k terms of a given sequence.
Solution:
problem_101 = undefined
Problem 102
For how many triangles in the text file does the interior contain the origin?
Solution:
import Text.Regex
ghc M p102.hs
isOrig (x1:y1:x2:y2:x3:y3:[])=
t1*t2>=0 && t3*t4>=0 && t5*t6>=0
where
x4=0
y4=0
t1=(y2y1)*(x4x1)+(x1x2)*(y4y1)
t2=(y2y1)*(x3x1)+(x1x2)*(y3y1)
t3=(y3y1)*(x4x1)+(x1x3)*(y4y1)
t4=(y3y1)*(x2x1)+(x1x3)*(y2y1)
t5=(y3y2)*(x4x2)+(x2x3)*(y4y2)
t6=(y3y2)*(x1x2)+(x2x3)*(y1y2)
buildTriangle s = map read (splitRegex (mkRegex ",") s) :: [Integer]
problem_102=do
x<readFile "triangles.txt"
let y=map buildTriangle$lines x
print $length$ filter isOrig y
Problem 103
Investigating sets with a special subset sum property.
Solution:
six=[11,18,19,20,22,25]
seven=[mid+alet mid=six!!3,a<0:six]
problem_103=foldl (++) "" $map show seven
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_(k1)*f_(n+1)*f_n + f_(k2)*(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
fkm1 = fibo (k1)
fkm2 = fibo (k2)
fk = fkm1 + fkm2
fnp1 = fibo (n+1)
fnp1sq = fnp1^2
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.
The lesson I learned fom this challenge, is: know mathematical identities and exploit them. They allow you take short cuts. Normally you compute all previous fibonacci numbers to compute a random fibonacci number. Which has linear costs. The aforementioned identity builds the number not from its two predecessors but from 4 much smaller ones. This makes the algorithm logarithmic in its complexity. It really shines if you want to compute a random very large fibonacci number. f.i. the 10mio.th fibonacci number which is over 2mio characters long, took 20sec to compute on my 2.2ghz laptop.
Problem 105
Find the sum of the special sum sets in the file.
Solution:
import Data.List
import Control.Monad
import Text.Regex
solNum=map solve [7..12]
solve n = twoSetsOf [0..n1] =<< [2..div n 2]
twoSetsOf xs n = do
firstSet < setsOf n xs
let rest = dropWhile (/= head firstSet) xs \\ firstSet
secondSet < setsOf n rest
let f = firstSet >>= enumFromTo 1
s = secondSet >>= enumFromTo 1
guard $ not $ null (f \\ s)  null (s \\ f)
[(firstSet,secondSet)]
setsOf 0 _ = [[]]
setsOf (n+1) xs = concat [map (y:) (setsOf n ys)  (y:ys) < tails xs]
comp lst a b=
a1/=b1
where
a1=sum$map (lst!!) a
b1=sum$map (lst!!) b
notEqu lst =
all id[comp slst a b(a,b)<solNum!!s]
where
s=length lst7
slst=sort lst
moreElem lst =
all id maE
where
le=length lst
sortLst=sort lst
maxElem =
(1):[sum $drop (lea) sortLst
a<[0..le]
]
minElem =
[sum $take a sortLst
a<[0..le]
]
maE=[a<b(a,b)<zip maxElem minElem]
stoInt s=map read (splitRegex (mkRegex ",") s) :: [Integer]
check x=moreElem x && notEqu x
main = do
f < readFile "sets.txt"
let sets = map stoInt$ lines f
let ssets = filter check sets
print $ sum $ concat ssets
Problem 106
Find the minimum number of comparisons needed to identify special sum sets.
Solution:
binomial x y =div (prodxy (y+1) x) (prodxy 1 (xy))
prodxy x y=product[x..y]
 http://mathworld.wolfram.com/DyckPath.html
catalan n=flip div (n+1) $binomial (2*n) n
calc n=
sum[e*(cd)
a<[1..di2],
let mu2=a*2,
let c=flip div 2 $ binomial mu2 a,
let d=catalan a,
let e=binomial n mu2]
where
di2=div n 2
problem_106 = calc 12
Problem 107
Determining the most efficient way to connect the network.
Solution:
problem_107 = undefined
Problem 108
Solving the Diophantine equation 1/x + 1/y = 1/n.
Solution:
import List
primes=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73]
series _ 1 =[[0]]
series xs n =[x:psx<xs,ps<series [0..x] (n1) ]
distinct=product. map (+1)
sumpri x=product $map (\(x,y)>x^y)$zip primes x
prob x y =head$sort[(sumpri m ,m)m<series [1..3] x,(>y)$distinct$map (*2) m]
problem_108=prob 7 2000
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
Problem 110
Find an efficient algorithm to analyse the number of solutions of the equation 1/x + 1/y = 1/n.
Solution:
 prob in problem_108
problem_110 = prob 13 (8*10^6)