https://wiki.haskell.org/api.php?action=feedcontributions&user=Drigz&feedformat=atomHaskellWiki - User contributions [en]2024-03-28T16:41:55ZUser contributionsMediaWiki 1.35.5https://wiki.haskell.org/index.php?title=Euler_problems/81_to_90&diff=15081Euler problems/81 to 902007-08-15T22:54:12Z<p>Drigz: </p>
<hr />
<div>[[Category:Programming exercise spoilers]]<br />
== [http://projecteuler.net/index.php?section=view&id=81 Problem 81] ==<br />
Find the minimal path sum from the top left to the bottom right by moving right and down.<br />
<br />
Solution:<br />
<haskell><br />
problem_81 = undefined<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=82 Problem 82] ==<br />
Find the minimal path sum from the left column to the right column.<br />
<br />
Solution:<br />
<haskell><br />
problem_82 = undefined<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=83 Problem 83] ==<br />
Find the minimal path sum from the top left to the bottom right by moving left, right, up, and down.<br />
<br />
Solution:<br />
<haskell><br />
problem_83 = undefined<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=84 Problem 84] ==<br />
In the game, Monopoly, find the three most popular squares when using two 4-sided dice.<br />
<br />
Solution:<br />
<haskell><br />
problem_84 = undefined<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=85 Problem 85] ==<br />
Investigating the number of rectangles in a rectangular grid.<br />
<br />
Solution:<br />
<haskell><br />
problem_85 = undefined<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=86 Problem 86] ==<br />
Exploring the shortest path from one corner of a cuboid to another.<br />
<br />
Solution:<br />
<haskell><br />
problem_86 = undefined<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=87 Problem 87] ==<br />
Investigating numbers that can be expressed as the sum of a prime square, cube, and fourth power?<br />
<br />
Solution:<br />
<haskell><br />
import List<br />
<br />
problem_87 = length expressible<br />
where limit = 50000000<br />
squares = takeWhile (<limit) (map (^2) primes)<br />
cubes = takeWhile (<limit) (map (^3) primes)<br />
fourths = takeWhile (<limit) (map (^4) primes)<br />
choices = [[s,c,f] | s <- squares, c <- cubes, f <- fourths]<br />
unique = map head . group . sort<br />
expressible = filter (<limit) . unique . map sum $ choices<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=88 Problem 88] ==<br />
Exploring minimal product-sum numbers for sets of different sizes.<br />
<br />
Solution:<br />
<haskell><br />
problem_88 = undefined<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=89 Problem 89] ==<br />
Develop a method to express Roman numerals in minimal form.<br />
<br />
Solution:<br />
<haskell><br />
problem_89 = undefined<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=90 Problem 90] ==<br />
An unexpected way of using two cubes to make a square.<br />
<br />
Solution:<br />
<haskell><br />
problem_90 = undefined<br />
</haskell><br />
<br />
[[Category:Tutorials]]<br />
[[Category:Code]]</div>Drigzhttps://wiki.haskell.org/index.php?title=Euler_problems/111_to_120&diff=15080Euler problems/111 to 1202007-08-15T22:22:47Z<p>Drigz: </p>
<hr />
<div>[[Category:Programming exercise spoilers]]<br />
== [http://projecteuler.net/index.php?section=view&id=111 Problem 111] ==<br />
Search for 10-digit primes containing the maximum number of repeated digits.<br />
<br />
Solution:<br />
<haskell><br />
problem_111 = undefined<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=112 Problem 112] ==<br />
Investigating the density of "bouncy" numbers.<br />
<br />
Solution:<br />
<haskell><br />
problem_112 = undefined<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=113 Problem 113] ==<br />
How many numbers below a googol (10100) are not "bouncy"?<br />
<br />
Solution:<br />
<haskell><br />
import Array<br />
<br />
mkArray b f = listArray b $ map f (range b)<br />
<br />
digits = 100<br />
<br />
inc = mkArray ((1, 0), (digits, 9)) ninc<br />
dec = mkArray ((1, 0), (digits, 9)) ndec<br />
<br />
ninc (1, _) = 1<br />
ninc (l, d) = sum [inc ! (l-1, i) | i <- [d..9]]<br />
<br />
ndec (1, _) = 1<br />
ndec (l, d) = sum [dec ! (l-1, i) | i <- [0..d]]<br />
<br />
problem_113 = sum [inc ! i | i <- range ((digits, 0), (digits, 9))]<br />
+ sum [dec ! i | i <- range ((1, 1), (digits, 9))]<br />
- digits*9 -- numbers like 11111 are counted in both inc and dec <br />
- 1 -- 0 is included in the increasing numbers<br />
</haskell><br />
Note: inc and dec contain the same data, but it seems clearer to duplicate them.<br />
<br />
== [http://projecteuler.net/index.php?section=view&id=114 Problem 114] ==<br />
Investigating the number of ways to fill a row with separated blocks that are at least three units long.<br />
<br />
Solution:<br />
<haskell><br />
problem_114 = undefined<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=115 Problem 115] ==<br />
Finding a generalisation for the number of ways to fill a row with separated blocks.<br />
<br />
Solution:<br />
<haskell><br />
problem_115 = undefined<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=116 Problem 116] ==<br />
Investigating the number of ways of replacing square tiles with one of three coloured tiles.<br />
<br />
Solution:<br />
<haskell><br />
problem_116 = undefined<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=117 Problem 117] ==<br />
Investigating the number of ways of tiling a row using different-sized tiles.<br />
<br />
Solution:<br />
<haskell><br />
problem_117 = undefined<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=118 Problem 118] ==<br />
Exploring the number of ways in which sets containing prime elements can be made.<br />
<br />
Solution:<br />
<haskell><br />
problem_118 = undefined<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=119 Problem 119] ==<br />
Investigating the numbers which are equal to sum of their digits raised to some power.<br />
<br />
Solution:<br />
<haskell><br />
problem_119 = undefined<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=120 Problem 120] ==<br />
Finding the maximum remainder when (a − 1)n + (a + 1)n is divided by a2.<br />
<br />
Solution:<br />
<haskell><br />
problem_120 = undefined<br />
</haskell><br />
<br />
[[Category:Tutorials]]<br />
[[Category:Code]]</div>Drigzhttps://wiki.haskell.org/index.php?title=Euler_problems/61_to_70&diff=15079Euler problems/61 to 702007-08-15T22:06:48Z<p>Drigz: </p>
<hr />
<div>[[Category:Programming exercise spoilers]]<br />
== [http://projecteuler.net/index.php?section=view&id=61 Problem 61] ==<br />
Find the sum of the only set of six 4-digit figurate numbers with a cyclic property.<br />
<br />
Solution:<br />
<haskell><br />
import Data.List<br />
<br />
triangle = [n*(n+1)`div`2 | n <- [1..]]<br />
square = [n^2 | n <- [1..]]<br />
pentagonal = [n*(3*n-1)`div`2 | n <- [1..]]<br />
hexagonal = [n*(2*n-1) | n <- [1..]]<br />
heptagonal = [n*(5*n-3)`div`2 | n <- [1..]]<br />
octagonal = [n*(3*n-2) | n <- [1..]]<br />
<br />
triangle4 = fourDigs triangle<br />
square4 = fourDigs square<br />
pentagonal4 = fourDigs pentagonal<br />
hexagonal4 = fourDigs hexagonal<br />
heptagonal4 = fourDigs heptagonal<br />
octagonal4 = fourDigs octagonal<br />
<br />
fourDigs = takeWhile (<10000) . dropWhile (<1000)<br />
<br />
solve = do<br />
(l1:l2:l3:l4:l5:l6:_) <- permute [triangle4, square4, pentagonal4, hexagonal4, heptagonal4, octagonal4]<br />
a <- l1<br />
let m = filter (g a) l2<br />
b <- m<br />
let n = filter (g b) l3<br />
c <- n<br />
let o = filter (g c) l4<br />
d <- o<br />
let p = filter (g d) l5<br />
e <- p<br />
let q = filter (g e) l6<br />
f <- q<br />
if g f a then return (sum [a,b,c,d,e,f]) else fail "burp"<br />
where<br />
g x y = x `mod` 100 == y `div` 100<br />
<br />
permute :: [a] -> [[a]]<br />
permute [] = [[]]<br />
permute list = concat $ map (\(x:xs) -> map (x:) (permute xs)) (take (length list) (unfoldr (\x -> Just (x, tail x ++ [head x])) list))<br />
<br />
problem_61 = head $ solve<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=62 Problem 62] ==<br />
Find the smallest cube for which exactly five permutations of its digits are cube.<br />
<br />
Solution:<br />
<haskell><br />
import Data.List<br />
<br />
cubes = [(x, show $ x^3) | x <- [1..100000]]<br />
<br />
problem_62 = f3 $ head $ head $ sortBy shf $ filter l5 $ groupBy g $ sortBy ss $ map sd cubes<br />
where<br />
sd (a, b) = (a, sort b)<br />
shf a b = compare (fst $ head a) (fst $ head b)<br />
ss a b = compare (snd a) (snd b)<br />
g a b = (snd a) == (snd b)<br />
l5 a = length a == 5<br />
f3 a = (fst a)^3<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=63 Problem 63] ==<br />
How many n-digit positive integers exist which are also an nth power?<br />
<br />
Solution:<br />
Since d<sup>n</sup> has at least n+1 digits for any d≥10, we need only consider 1 through 9. If d<sup>n</sup> has fewer than n digits, every higher power of d will also be too small since d < 10. We will also never have n+1 digits for our nth powers. All we have to do is check d<sup>n</sup> for each d in {1,...,9}, trying n=1,2,... and stopping when d<sup>n</sup> has fewer than n digits.<br />
<haskell><br />
problem_63 = length . concatMap (takeWhile (\(n,p) -> n == nDigits p))<br />
$ [powers d | d <- [1..9]]<br />
where powers d = [(n, d^n) | n <- [1..]]<br />
nDigits n = length (show n)<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=64 Problem 64] ==<br />
How many continued fractions for N ≤ 10000 have an odd period?<br />
<br />
Solution:<br />
<haskell><br />
problem_64 = undefined<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=65 Problem 65] ==<br />
Find the sum of digits in the numerator of the 100th convergent of the continued fraction for e.<br />
<br />
Solution:<br />
<haskell><br />
import Data.Ratio<br />
<br />
problem_65 = dsum . numerator . contFrac . take 100 $ e<br />
where dsum 0 = 0<br />
dsum n = let ( d, m ) = n `divMod` 10 in m + ( dsum d )<br />
contFrac = foldr1 (\x y -> x + 1/y)<br />
e = 2 : 1 : insOnes [2,4..]<br />
insOnes (x:xs) = x : 1 : 1 : insOnes xs<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=66 Problem 66] ==<br />
Investigate the Diophantine equation x<sup>2</sup> − Dy<sup>2</sup> = 1.<br />
<br />
Solution:<br />
<haskell><br />
problem_66 = undefined<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=67 Problem 67] ==<br />
Using an efficient algorithm find the maximal sum in the triangle?<br />
<br />
Solution:<br />
<haskell><br />
import System.Process<br />
import IO<br />
<br />
slurpURL url = do<br />
(_,out,_,_) <- runInteractiveCommand $ "curl " ++ url<br />
hGetContents out<br />
<br />
problem_67 = do<br />
src <- slurpURL "http://projecteuler.net/project/triangle.txt"<br />
print $ head $ foldr1 g $ parse src<br />
where<br />
parse :: String -> [[Int]]<br />
parse s = map ((map read).words) $ lines s<br />
f x y z = x + max y z<br />
g xs ys = zipWith3 f xs ys $ tail ys<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=68 Problem 68] ==<br />
What is the maximum 16-digit string for a "magic" 5-gon ring?<br />
<br />
Solution:<br />
<haskell><br />
problem_68 = undefined<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=69 Problem 69] ==<br />
Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.<br />
<br />
Solution:<br />
<haskell><br />
import Data.Ratio<br />
import Data.List<br />
<br />
primePowerFactors n = rle (takeFactors n primes)<br />
where rle = map (\xs -> (head xs, length xs)) . group<br />
takeFactors n (p:ps)<br />
| n == 1 = []<br />
| p * p > n = [n]<br />
| n `mod` p == 0 = p : takeFactors (n `div` p) (p:ps)<br />
| otherwise = takeFactors n ps<br />
<br />
eulerTotient n = product (map (\(p,i) -> p^(i-1) * (p-1)) factors)<br />
where factors = primePowerFactors n<br />
<br />
problem_69 = snd . maximum . map (\n -> (n % eulerTotient n, n)) $ [1..1000000]<br />
</haskell><br />
<br />
Note: credit for arithmetic functions is due to [http://www.polyomino.f2s.com/ David Amos].<br />
<br />
== [http://projecteuler.net/index.php?section=view&id=70 Problem 70] ==<br />
Investigate values of n for which φ(n) is a permutation of n.<br />
<br />
Solution:<br />
<haskell><br />
problem_70 = undefined<br />
</haskell><br />
<br />
[[Category:Tutorials]]<br />
[[Category:Code]]</div>Drigz