Tagged: Project Euler Toggle Comment Threads | Keyboard Shortcuts

  • Eliot 1:18 pm on December 19, 2011 Permalink | Reply
    Tags: Project Euler,   

    Project Euler Problem 2 

    I will provide a solution for problem 2 in Scala.  I think I will mark each solution moving forward as being just a solution.  I have received feedback that someone can find this and learn bad style or not learn the language properly.  I don’t want that to happen and you have been warned.  The problem details are:

    Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

    1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

    By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

    For this problem I was able to pick up the concept of using a Stream.  Its similar to a list, Daily Scala has a great explanation of the difference.

    A Scala List basically consists of the head element and the rest of the list. A Scala Stream is the head of the stream and a function that can construct the rest of the Stream. It is a bit more than this because each element is evaluated only once and stored in memory for future evaluations. That should be more clear after some examples.

    And now to the solution.

    1
    2
    3
    4
    5
    6
    
    object Euler002 {
      def main(args: Array[String]) {
       def fib(a:Int=1, b:Int=2):Stream[Int] = Stream.cons(a, fib(b, a+b))
       println(fib().filter(_%2==0).takeWhile(_<4000000).sum)
      }
    }

    My solution is pretty straightforward.  I define a fib method that take two arguments with default values.  It returns a Stream of Integers.  The method definition constructs a Stream making a recursive call to itself.  This will happen until we get to 4 million for everyone even number.  The use of the filter method takes care of this checking to see if the number is divisible by 2.  We stop at 4 million because of the takewhile method.

     

     
  • Eliot 1:14 pm on December 15, 2011 Permalink | Reply
    Tags: Project Euler,   

    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.

     
    • dbcfd 2:34 pm on December 15, 2011 Permalink | Reply

      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 | Reply

      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.:)

  • Eliot 2:32 am on December 14, 2011 Permalink | Reply
    Tags: Project Euler,   

    Project Euler Problem 1 

    Part 1,2

    Project Euler problem 1 wants a person to find the sum of all numbers less than 1000 that are divisible by 3 and 5.  I was able solve this problem pretty easily in Scala.  My solution is very similar to how I would solve the problem in Java.  Quickly glancing at the code, you can see there is less of it.  Keywords in Java like Public and static aren’t in here.  It may not see like much, but it adds up.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    
    object Euler001 {
      def main(args: Array[String]) {
        var a = 0
        var sum = 0
     
        while(a < 1000) {
          if(a%3 == 0 || a%5 == 0) sum = sum + a
     
          a = a + 1
        }
     
        println(sum)
      }
    }

    Using a while loop solved the problem.  I have more variations of the solution I will post later.  If you are trying to learn a new programming language, projects like Euler is a great way to do this.  For now just trust me, I will write a follow up article on why.

     
    • Colin Dellow 1:24 pm on December 14, 2011 Permalink | Reply

      Pfft, that’s far too readable.

      def reduce(i: Int) = if(i % 3 == 0 || i % 5 == 0) i else 0
      (0 /: (0 until 1000)) { _ + reduce(_) }

      Much better! ;)

    • Xavier 1:36 pm on December 14, 2011 Permalink | Reply

      Pfff, that’s far too brutal:

      3 * 333 * 334 / 2 + 5 * 199 * 200 / 2 – 15 * 66 * 67 / 2 is much better! =)

      • Eliot 5:00 pm on December 14, 2011 Permalink | Reply

        I never thought about it that way. How did you come up with that approach?

        • Xavier 6:57 am on December 15, 2011 Permalink | Reply

          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.

          • Eliot 1:23 pm on December 15, 2011 Permalink

            Very good point brute force is not needed for this one. Thanks for the explanation.

          • Didier 11:09 am on January 11, 2013 Permalink

            ok for good old math but where your magical numbers 333, 199, 66 are coming from. is there a mathematical formula to calculate how many multiples of x there are between a and b ??

    • Colin Dellow 1:41 pm on December 14, 2011 Permalink | Reply

      To explain my solution, I recast your imperative solution in a functional form. The two mutable variables you used — sum and a — were replaced with a foldLeft and a sequence.

      What was a comes from (0 until 1000) — a Seq[Int] that includes the numbers 0 <= i accumulator + reduce(current) }

      Which says: Initialize accumulator to 0. Iterate over the numbers for 0 until 1000, updating accumulator as needed.

      You can then use Scala’s magic _ syntax sugar to make it more concise. Whenever you’re defining a function whose parameters are known (in this case, the accumulator = accumulator + reduce(current) is actually a function whose type is defined by the foldLeft function), if you use each parameter exactly once, each subsequent use of _ refers to the next parameter.

      So, you could rewrite as:

      (0 until 1000).foldLeft(0) { _ + reduce(_) }

    • Kim 2:07 pm on December 14, 2011 Permalink | Reply

      noobs…;)

      1 to 1000 filter { x => x % 3 == 0 || x % 5 == 0 } sum

    • ohboy 2:47 pm on December 14, 2011 Permalink | Reply

      Please take some time to learn the language before posting these kinds of “solutions”. What you’ve done was just translate a Java solution and say it’s Scala, very very bad coding style. Kim’s solution is how you should be thinking about this in Scala.

    • ohboy 3:46 pm on December 14, 2011 Permalink | Reply

      To elaborate on what is condireded “bad style” in your code:

      mutable variables: Scala promotes functional style coding, where everything is immutable
      loop over a range/collection: again functional style transformations are preferred, look at reduce, fold, map, filter, sum, etc.

      (and lose those semicolons, they’re evil :)

      • Eliot 6:21 pm on December 14, 2011 Permalink | Reply

        I removed the semi-colons. Thank you for your insight. I appreciate your opinion. I feel that posting Java-Scala hybrid solutions help people understand the new concepts in Scala. I never stated use this code in production, or this is “good style.” I stated this is a solution I came up with.

    • Chinmay 8:45 pm on April 30, 2013 Permalink | Reply

      println((1 until x).filter(a => a % 3 == 0 || a % 5 == 0).foldLeft(0)(_+_))

c
compose new post
j
next post/next comment
k
previous post/previous comment
r
reply
e
edit
o
show/hide comments
t
go to top
l
go to login
h
show/hide help
shift + esc
cancel