Project Euler Problem 1 Revisited
Part 1,2
I posted my original solution on Reddit. I received positive feedback and not so positive feedback. The best solution I seen so far is.
1 | 3 * 333 * 334 / 2 + 5 * 199 * 200 / 2 – 15 * 66 * 67 / 2 |
Yes, elegant indeed. Special thanks goes out to Xavier for this one. Below is his explanation of the solution above.
Well, you don’t need Scala or any other programming language, good old math can do it for you 
solution
= sum of multiples of 3 < 1000
+ sum of multiples of 5 < 1000
- sum of multiples of 15 < 1000 (because multiples of 15 are added twice)
sum of n first numbers = n*(n+1)/2
sum of n first multiples of x = x*n*(n+1)/2
there are 333 multiples of 3 < 1000 (last one is 333 * 3 = 999)
there are 199 multiples of 5 < 1000 (last one is 199 * 5 = 995)
there are 66 multiples of 15 < 1000 (last one is 66 * 15 = 990)
I know that many people with coding skills will try to brute-force every project-euler problems… but some of those problems actually don’t need to be brute-forced.
The one liner that most people eventually come up with will be something like:
1 | (1 until 1000).filter(x => x%3==0 || x%5==0).sum |
or
1 | 1 until 1000 filter { x => x % 3 == 0 || x % 5 == 0 } sum |
Kim, a commenter from my first post provided the second one. Thanks!
Below is another revision of the code I came up with. This one is taking input from the command line and using a parallel collection to solve this problem. It runs very fast compared to a large ceiling (i.e. 1,000,000).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | object Euler001a { def main(args: Array[String]) { def check (i: Long, factors: List[Long]) : Boolean = { var divisible = false factors.foreach(factor => { if(i%factor == 0) { divisible = true } }) return divisible } val argList = args.toList val ceiling = args(0).toLong val factors = argList.slice(1,argList.length).map(s => s.toLong) val answer:Long = (1L until ceiling).par.filter(i => check(i, factors)).sum println(answer) } } |
The solution I listed above is very verbose. However, I did this for a reason. Most will consider this a Java-Scala hybrid. To me its still Scala; just more readable for new users. I came up with this solution to allow for additional factors. If you wanted to find the sum of the factors 3,5, and 7 for numbers under 1000, you can run the following command.
scala Euler001a 1000 3 5 7
Colin Dellow came up with this. Its very similar to my solution but more concise.
1 2 | def reduce(i: Int) = if(i % 3 == 0 || i % 5 == 0) i else 0 (0 /: (0 until 1000)) { _ + reduce(_) } |
I really appreciate the feedback good and bad. I feel I found a couple of people that care about Scala as much as I do. A good community will always help when learning anything. I have an Actor example I will post next; closing out the series on problem 1.
dbcfd 2:34 pm on December 15, 2011 Permalink |
Not sure if you’ll post this on reddit, but you’ll want to check out List head/tail. That will eliminate your usage of args(0) and argList.slice. ceiling is equivalent to argList.head, while factors becomes argList.tail.map(s=> s.toLong)
Eliot 4:09 pm on December 15, 2011 Permalink |
Yes, I posted it on Reddit. You are completely right. Lines 15 – 17 can be:
val ceiling = args.head.toLong
val factors = args.tail.map(s => s.toLong).toList
That is one less val and a great example of using head and tail. Thanks for pointing me in the right direction.:)