I’ve wanted to take a crack at Project Euler for some time now. If you’re not\u00a0familiar, it’s basically a list of mathematical problems. From the site:<\/p>\n
Project Euler is a series of challenging mathematical\/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.<\/p>\n
The motivation for starting Project Euler, and its continuation, is to provide a platform for the inquiring mind to delve into unfamiliar areas and learn new concepts in a fun and recreational context.<\/p><\/blockquote>\n
And they keep score<\/a>! In\u00a0addition, I’ve also been looking for an excuse to learn F#. In truth, I’ve wanted to get down and dirty with some functional language, to learn the principles and hopefully become a better programmer. I chose F#\u00a0because\u00a0it’s part of Visual Studio (starting with 2010), and I’m already handy with .NET, so in theory that will lower the barrier to entry just a little bit. At the very least, it allows me to dodge the hassle of installing another interpreter or\u00a0environment\u00a0on my system.<\/p>\n
Blogging It<\/h2>\n
As I continue though Project Euler, I’ll be posting my solutions here on my site under http:\/\/factormystic.net\/projects\/code<\/a>, and you can also check my progress by looking at my Project Euler profile<\/a> and I look forward to your mocking laughter\u00a0gentle guidance as I fumble around in F#.<\/p>\n
On to Problem 1<\/h2>\n
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
\nFind the sum of all the multiples of 3 or 5 below 1000.<\/p><\/blockquote>\nStraightforward enough, and easy to form a mental model around the problem. But how to implement this in F#? For a quick language primer, I skimmed An Introduction to Functional Programming for .NET Developers<\/a> and noticed a few things I might need:<\/p>\n
\n
- An add function
\nlet add x y = x + y
\n<\/span><\/li>\n- Sequence syntax and list comprehension
\nlet numbers = {0..10}
\n<\/span><\/li>\n- Modulo and ternary operators
\nstring result = x % 2 == 0 ? “yes” : “no”;<\/span><\/li>\n<\/ul>\nThe Thinking<\/h2>\n
The thinking is this: sequences could be used to build a list of integers 1 to 1000; I could use modulo to get multiples of 3 and 5 (think <\/a>FizzBuzz<\/a>), and somehow use that add function to get the sum. Reading the documentation for sequence expressions<\/a> turned out to be quite rewarding (!), as you can embed a filter on a sequence when you\u00a0declare\u00a0it:<\/p>\n
[sourcecode]let multiples = seq { for i in 1 .. 1000 do if i % 3 = 0 || i % 5 = 0 then yield i }[\/sourcecode]<\/p>\n
Yield is already a familiar concept from C#, from using Enumerables. In fact, from the documentation:<\/p>\n
Sequences are represented by the\u00a0seq<‘T>\u00a0type, which is an alias for IEnumerable<T>. Therefore, any .NET Framework type that implements\u00a0System.IEnumerable can be used as a sequence. The\u00a0Seq module provides support for manipulations involving sequences.<\/p><\/blockquote>\n
Thus our F# is roughly analogous to something like
\n[sourcecode]public static IEnumerable GiveMults()
\n{
\nforeach (int i in Enumerable.Range(1, 1000))
\nif (i % 3 == 0 || i % 5 == 0)
\nyield return i;
\n}[\/sourcecode]<\/p>\nNow that we have our sequence of natural numbers, let’s figure out how to sum them up. I have the add function I grabbed from the article, and while poking around with the Seq module, I noticed a reduce function, which can apply an accumulator. That would give us<\/p>\n
[sourcecode]
\nlet multiples = seq { for i in 1 .. 1000 do if i % 3 = 0 || i % 5 = 0 then yield i }
\nlet add x y = x + y
\nlet result= Seq.reduce add multiples
\nprintfn “%A” result
\n[\/sourcecode]
\n(Side note: printfn<\/a> is how we can write to stdout, much like Console.Writeline. The “%A” stuff works like string.Format parameters- %A indicates “Formats any value, printed with the default layout settings.” In the case of a sequence, that means printing the first few values)<\/p>\n…and that code does indeed sum the multiples, as you would expect. But there is a better way. After all, we should expect something as simple as adding up a list to be built in already, and we do have our Seq module functions available.<\/p>\n
Indeed, there is a Seq.sum function that does exactly what we’re seeking to do, sum a sequence. Rewritten, we have:
\n[sourcecode]
\nlet result\u00a0= seq { for i in 1 .. 1000 do if i % 3 = 0 || i % 5 = 0 then yield i }
\nlet total = Seq.sum result
\nprintfn “%A” total
\n[\/sourcecode]
\nAnd this prints an answer, but that answer is WRONG. See the bug? The original problem stated that we’re to “sum of all the multiples of 3 or 5 below<\/strong> 1000″, but the list comprehension syntax (1..1000) is inclusive<\/strong>. Thus, our answer includes 1000, which is evenly divisible by 5, and is summed into the final total. The fix is simple, just write 1..999:<\/p>\nMy Solution<\/h2>\n
[sourcecode]
\nlet multiples = seq { for i in 1 .. 999 do if i % 3 = 0 || i % 5 = 0 then yield i }
\nlet result = Seq.sum multiples
\nprintfn “%A” result
\n[\/sourcecode]<\/p>\nBingo.
\nProject Euler Problem 1: Answered<\/strong><\/p>\nFurther Reading<\/h2>\n
\n
- An Introduction to Functional Programming for .NET Developers<\/a><\/li>\n
- Sequences<\/a><\/li>\n
- Core.Printf Module<\/a><\/li>\n<\/ul>\n
A Post Script<\/h2>\n
For the code golf crew:
\n[sourcecode]printfn “%A” (Seq.sum (seq { for i in 1 .. 999 do if i % 3 = 0 || i % 5 = 0 then yield i }))[\/sourcecode]<\/p>\n","protected":false},"excerpt":{"rendered":"About Project Euler I’ve wanted to take a crack at Project Euler for some time now. If you’re not\u00a0familiar, it’s basically a list of mathematical problems. From the site: Project Euler is a series of challenging mathematical\/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[26,25],"tags":[],"class_list":["post-214","post","type-post","status-publish","format-standard","hentry","category-f-sharp","category-project-euler"],"_links":{"self":[{"href":"https:\/\/factormystic.net\/blog\/wp-json\/wp\/v2\/posts\/214","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/factormystic.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/factormystic.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/factormystic.net\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/factormystic.net\/blog\/wp-json\/wp\/v2\/comments?post=214"}],"version-history":[{"count":29,"href":"https:\/\/factormystic.net\/blog\/wp-json\/wp\/v2\/posts\/214\/revisions"}],"predecessor-version":[{"id":262,"href":"https:\/\/factormystic.net\/blog\/wp-json\/wp\/v2\/posts\/214\/revisions\/262"}],"wp:attachment":[{"href":"https:\/\/factormystic.net\/blog\/wp-json\/wp\/v2\/media?parent=214"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/factormystic.net\/blog\/wp-json\/wp\/v2\/categories?post=214"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/factormystic.net\/blog\/wp-json\/wp\/v2\/tags?post=214"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}