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 / 215 * 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.

Be Sociable, Share!