Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Project Euler #01 on HackerRank, Performance issue?
(Jean Lopes)
2. Re: Project Euler #01 on HackerRank, Performance issue?
(Lyndon Maydwell)
3. Re: Project Euler #01 on HackerRank, Performance issue?
(Jean Lopes)
----------------------------------------------------------------------
Message: 1
Date: Tue, 27 Jan 2015 22:15:03 -0200
From: Jean Lopes <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Project Euler #01 on HackerRank,
Performance issue?
Message-ID:
<CAKeoKsgMgD=pkeojvmrg4ofjdols_i4acf-wexerhgqm_fx...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Thats actually what I did...
2015-01-27 22:11 GMT-02:00 Lyndon Maydwell <[email protected]>:
> 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 <[email protected]> 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 <[email protected]>:
>>
>>> On Tue, Jan 27, 2015 at 6:29 PM, Jean Lopes <[email protected]> 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
>>> [email protected]
>>> [email protected]
>>> unix, openafs, kerberos, infrastructure, xmonad
>>> http://sinenomine.net
>>>
>>> _______________________________________________
>>> Beginners mailing list
>>> [email protected]
>>> http://www.haskell.org/mailman/listinfo/beginners
>>>
>>>
>>
>> _______________________________________________
>> Beginners mailing list
>> [email protected]
>> http://www.haskell.org/mailman/listinfo/beginners
>>
>>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20150127/0785ab10/attachment-0001.html>
------------------------------
Message: 2
Date: Wed, 28 Jan 2015 11:25:57 +1100
From: Lyndon Maydwell <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Project Euler #01 on HackerRank,
Performance issue?
Message-ID:
<CAM5QZtydaLgrZgy2_=omzVq2vK1RnNMVAWq=x3hxn1rzpz_...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
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 <[email protected]> wrote:
> Thats actually what I did...
>
> 2015-01-27 22:11 GMT-02:00 Lyndon Maydwell <[email protected]>:
>
> 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 <[email protected]> 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 <[email protected]>:
>>>
>>>> On Tue, Jan 27, 2015 at 6:29 PM, Jean Lopes <[email protected]> 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
>>>> [email protected]
>>>> [email protected]
>>>> unix, openafs, kerberos, infrastructure, xmonad
>>>> http://sinenomine.net
>>>>
>>>> _______________________________________________
>>>> Beginners mailing list
>>>> [email protected]
>>>> http://www.haskell.org/mailman/listinfo/beginners
>>>>
>>>>
>>>
>>> _______________________________________________
>>> Beginners mailing list
>>> [email protected]
>>> http://www.haskell.org/mailman/listinfo/beginners
>>>
>>>
>>
>> _______________________________________________
>> Beginners mailing list
>> [email protected]
>> http://www.haskell.org/mailman/listinfo/beginners
>>
>>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20150128/7fa3d352/attachment-0001.html>
------------------------------
Message: 3
Date: Tue, 27 Jan 2015 22:43:22 -0200
From: Jean Lopes <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Project Euler #01 on HackerRank,
Performance issue?
Message-ID:
<CAKeoKsj3sfOD5sz7aBsXXYVKgZSvGq-DP=us2jxvxembguz...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Your solution runs really quick! I'll study it. Thank you
2015-01-27 22:25 GMT-02:00 Lyndon Maydwell <[email protected]>:
> 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 <[email protected]> wrote:
>
>> Thats actually what I did...
>>
>> 2015-01-27 22:11 GMT-02:00 Lyndon Maydwell <[email protected]>:
>>
>> 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 <[email protected]> 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 <[email protected]>:
>>>>
>>>>> On Tue, Jan 27, 2015 at 6:29 PM, Jean Lopes <[email protected]>
>>>>> 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
>>>>> [email protected]
>>>>> [email protected]
>>>>> unix, openafs, kerberos, infrastructure, xmonad
>>>>> http://sinenomine.net
>>>>>
>>>>> _______________________________________________
>>>>> Beginners mailing list
>>>>> [email protected]
>>>>> http://www.haskell.org/mailman/listinfo/beginners
>>>>>
>>>>>
>>>>
>>>> _______________________________________________
>>>> Beginners mailing list
>>>> [email protected]
>>>> http://www.haskell.org/mailman/listinfo/beginners
>>>>
>>>>
>>>
>>> _______________________________________________
>>> Beginners mailing list
>>> [email protected]
>>> http://www.haskell.org/mailman/listinfo/beginners
>>>
>>>
>>
>> _______________________________________________
>> Beginners mailing list
>> [email protected]
>> http://www.haskell.org/mailman/listinfo/beginners
>>
>>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20150127/d25c4eb6/attachment.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 79, Issue 33
*****************************************
