StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>For Haskell I like</p> <pre><code>let s n = sum [0,n..999] in s 3 + s 5 - s 15 </code></pre> <p>or</p> <pre><code>sum $ filter ((>1).(gcd 15)) [0..999] </code></pre> <p>For fun the Rube-Goldberg version:</p> <pre><code>import Data.Bits sum $ zipWith (*) [1..999] $ zipWith (.|.) (cycle [0,0,1]) (cycle [0,0,0,0,1]) </code></pre> <hr> <p>Okay, explanation time. </p> <p>The first version defines a little function s that sums up all multiples of n up to 999. If we sum all multiples of 3 and all multiples of 5, we included all multiples of 15 twice (once in every list), hence we need to subtract them one time.</p> <p>The second version uses the fact that 3 and 5 are primes. If a number contains one or both of the factors 3 and 5, the gcd of this number and 15 will be 3, 5 or 15, so in every case the gcd will be bigger than one. For other numbers without a common factor with 15 the gcd becomes 1. This is a nice trick to test both conditions in one step. But be careful, it won't work for arbitrary numbers, e.g. when we had 4 and 9, the test <code>gdc x 36 > 1</code> won't work, as <code>gcd 6 36 == 6</code>, but neither <code>mod 6 4 == 0</code> nor <code>mod 6 9 == 0</code>.</p> <p>The third version is quite funny. <code>cycle</code> repeats a list over and over. <code>cycle [0,0,1]</code> codes the "divisibility pattern" for 3, and <code>cycle [0,0,0,0,1]</code> does the same for 5. Then we "or" both lists together using <code>zipWith</code>, which gives us <code>[0,0,1,0,1,1,0,0,1,1,0,1...]</code>. Now we use <code>zipWith</code> again to multiply this with the actual numbers, resulting in <code>[0,0,3,0,5,6,0,0,9,10,0,12...]</code>. Then we just add it up.</p> <p>Knowing different ways to do the same thing might be wasteful for other languages, but for Haskell it is essential. You need to spot patterns, pick up tricks and idioms, and play around a lot in order to gain the mental flexibility to use this language effectively. Challenges like the project Euler problems are a good opportunity to do so. </p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload