Re: [Haskell-beginners] Project Euler #01 on HackerRank, Performance issue‏

27 Jan 2015

      The key to solving any Euler problem is to realize that you want an
analytic solution whenever possible. In this case, if you try to construct
and sum lists, you're going to hit the time boundaries every time. On the
other hand, you can do some basic algebra and come up with a fully analytic
solution that will run in constant (well, nearly, it depends on the number
of bits in the upper bound) time.

So for the problem at hand, you've already realized that you can compute 3
separate sums and combine them into your answer. When you want to sum
numbers from 1 to n, there's an analytic formula for the summation: n*(n+1)
/ 2. So rewrite your sums as summations from 1 to some number, insert the
analytic formula and algebraically reduce the resulting equation to a
couple of simple terms that are easy to compute. If you've never done this,
let me know, and I'll walk you through the steps more slowly.

Thanks,
Arjun

On Tue, Jan 27, 2015 at 8:09 PM, Animesh Saxena 
wrote:
...
why not just use infinite series. mathematically...
series 1 = Mutiples of 3
series 2 = Multiples of 5
Apply filter and sum to get the answer
-Animesh
On Jan 27, 2015, at 04:43 PM, Jean Lopes  wrote:
Your solution runs really quick! I'll study it. Thank you
2015-01-27 22:25 GMT-02:00 Lyndon Maydwell :
...
Ah sorry, I didn't notice that you were doing that. The effectiveness of
the trick really only comes into play though if you use an analytic
solution for finding the sum of the multiples of 3, etc.
I haven't tested this code in a while, but here's what I wrote some time
ago:
sum2 :: Integer -> Integer -> Integer -> Integer
sum2 a b ceiling = aX + bX - abX
where
aX  = sum1 a ceiling
bX  = sum1 b ceiling
abX = sum1 (a * b) ceiling
sum1 :: Integer -> Integer -> Integer
sum1 x ceiling = sum1' (even times) times x
where
times = ceiling `div` x
sum1' :: Bool -> Integer -> Integer -> Integer
sum1' True times x = area
where
area = (times + 1) * (times * x) `div` 2
sum1' False times x = max + area'
where
max   = times * x
area' = sum1' True (times - 1) x
Please excuse the poor Haskell style as it is quite possibly the first
Haskell program I ever wrote.
On Wed, Jan 28, 2015 at 11:15 AM, Jean Lopes  wrote:
...
Thats actually what I did...
2015-01-27 22:11 GMT-02:00 Lyndon Maydwell :
I remember that when I had a look at Euler 1 I found that there's a fun
...
solution that should run in "constant" time.
You can find the sum of the multiples of 3, add the multiples of 5, and
then subtract the multiples of 3*5.
Is that the kind of thing you're looking for?
- Lyndon
On Wed, Jan 28, 2015 at 10:57 AM, Jean Lopes 
wrote:
...
I'm not really good at math, maybe I am missing something obvious ?
Maybe some pointers as of where to start studying math in order to
avoid this brute force attempts, at least to help in this particular problem
2015-01-27 21:38 GMT-02:00 Brandon Allbery :
...
On Tue, Jan 27, 2015 at 6:29 PM, Jean Lopes 
wrote:
> The problem to be solved:
> https://www.hackerrank.com/contests/projecteuler/challenges/euler001
It's worth remembering that the Euler problems are all about math
understanding; often they are designed such that brute force solutions will
time out or otherwise fail.
--
brandon s allbery kf8nh                               sine nomine
associates
allbery.b@gmail.com
ballbery@sinenomine.net
unix, openafs, kerberos, infrastructure, xmonad
http://sinenomine.net
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners

Re: [Haskell-beginners] Project Euler #01 on HackerRank, Performance issue‏

Arjun Comar