3 ms·

An you explain me the difference between your solution 2 and 3?

dan-robertson 5y ago
As in: 1. sum [i | i <- [1..1000], i % 3 == 0 || i % 5 == 0] 2. sum [3,6..1000] + sum [5,10..1000] - sum [15,30..1000] 3. rsum 3 + rsum 5 - rsum 15 where rsum n = let (k,r) = 1000 `divMod` n in rsum' 0 (1000 - r) k rsum' f l n = (n*(f + l)) `div` 2
- jacquesm 5y ago
  1. is the best solution. That's because it is the only solution that encodes the problem in a way that it is still obvious what is being done. 2. and 3. are incomplete without a pile of documentation to explain why they do what they do and what you'd need to do to modify them in case the inputs change.
  - dan-robertson 5y ago
    The first runs in linear[1] time and the last in constant time. One can write it more readably: sum_arithmetic_progression first last length = -- to compute S = first + (first+k) + (first+2k) + … + (first+length*k = last) -- write it backwards and add corresponding terms: -- 2S = (first+last) + ((first+k)+(last-k)) + … + (last+first) -- = (first+last) + … + (first+last) -- \____ length times ___________/ (first + last) * length `div` 2 -- = sum [i | i<- [1..upperBound], i%n == 0] but fast sum_multiples n upperBound = sum_arithmetic_progression n last count where (count,r) = upperBound `divMod` n last = upperBound - r subsets [] = [[]] subsets (x:xs) = [set | sub <- subsets xs, set <- [x:sub,sub]] -- given some sets [A,B,…,C] and a function count_intersection which acts like the sum of some function on the elements in the intersection of a list of sets, compute the count of their union using the inclusion–exclusion principle. inclusion_exclusion count_intersection sets = sum [count_intersection sub * (if odd (length sub) then 1 else -1) | sub <- subsets sets, sub != []] answer = inclusion_exclusion sum_multiples' [3,5] where sum_multiples' factors = -- the sum of the numbers which are multiples of all the numbers in factors is the sum of the multiples of their lowest common multiple sum_multiples (foldr lcm 1 factors) 1000 The point of project Euler is not to make you write clean or clear code but rather to make you write code that exploits the mathematical structure of the problem to find the answer with less computation.
kadoban 5y ago
Solution 2 is still iterating, once by 3, then by 5 then by 15. Solution 3 uses the closed-form solutions the the question "what is the sum of the multiples of k between x and y". If you're not familiar with that last part, it's pretty easy to get there from the formula for the sum of numbers from 1 to n, ie n(n+1)/2 (which is itself ~easy to see by pairing up 1 and n, then 2 and (n-1) and etc.)

As in: 1. sum [i | i <- [1..1000], i % 3 == 0 || i % 5 == 0] 2. sum [3,6..1000] + sum [5,10..1000] - sum [15,30..1000] 3. rsum 3 + rsum 5 - rsum 15 where rsum n = let (k,r) = 1000 `divMod` n in rsum' 0 (1000 - r) k rsum' f l n = (n*(f + l)) `div` 2

jacquesm 5y ago
1. is the best solution. That's because it is the only solution that encodes the problem in a way that it is still obvious what is being done. 2. and 3. are incomplete without a pile of documentation to explain why they do what they do and what you'd need to do to modify them in case the inputs change.
- dan-robertson 5y ago
  The first runs in linear[1] time and the last in constant time. One can write it more readably: sum_arithmetic_progression first last length = -- to compute S = first + (first+k) + (first+2k) + … + (first+length*k = last) -- write it backwards and add corresponding terms: -- 2S = (first+last) + ((first+k)+(last-k)) + … + (last+first) -- = (first+last) + … + (first+last) -- \____ length times ___________/ (first + last) * length `div` 2 -- = sum [i | i<- [1..upperBound], i%n == 0] but fast sum_multiples n upperBound = sum_arithmetic_progression n last count where (count,r) = upperBound `divMod` n last = upperBound - r subsets [] = [[]] subsets (x:xs) = [set | sub <- subsets xs, set <- [x:sub,sub]] -- given some sets [A,B,…,C] and a function count_intersection which acts like the sum of some function on the elements in the intersection of a list of sets, compute the count of their union using the inclusion–exclusion principle. inclusion_exclusion count_intersection sets = sum [count_intersection sub * (if odd (length sub) then 1 else -1) | sub <- subsets sets, sub != []] answer = inclusion_exclusion sum_multiples' [3,5] where sum_multiples' factors = -- the sum of the numbers which are multiples of all the numbers in factors is the sum of the multiples of their lowest common multiple sum_multiples (foldr lcm 1 factors) 1000 The point of project Euler is not to make you write clean or clear code but rather to make you write code that exploits the mathematical structure of the problem to find the answer with less computation.

kadoban 5y ago

Solution 2 is still iterating, once by 3, then by 5 then by 15. Solution 3 uses the closed-form solutions the the question "what is the sum of the multiples of k between x and y". If you're not familiar with that last part, it's pretty easy to get there from the formula for the sum of numbers from 1 to n, ie n(n+1)/2 (which is itself ~easy to see by pairing up 1 and n, then 2 and (n-1) and etc.)