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 / 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 | 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)(_+_))

  • Eliot 1:01 pm on December 7, 2011 Permalink | Reply
    Tags: Project Euler,   

    Project Euler and Scala 

    What the heck is Project Euler?

    A summary from the website is below:

    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.

    Leonard Euler

    So you need use programming skills along with Mathematical insight to solve these problems.  That is what I need to learn my new interest Scala.

    The picture above is Leonhard Euler.  The project was named after him.  I am not sure completely sure why, but I know he was a Swiss Mathematican and Physicist.

    What the heck is Scala?

    Scala is a general purpose programming language designed to express common programming patterns in a concise, elegant, and type-safe way. It smoothly integrates features of object-oriented and functional languages, enabling Java and other programmers to be more productive. Code sizes are typically reduced by a factor of two to three when compared to an equivalent Java application.

    Scala Programming

    To me, Scala is an object oriented programming (OOP) and functional programming (FP) language.  Its a best of breeds in my opinion.  I can leverage what I learned in OOP while easing into FP.

    So what are you going to do with this?

    I am going to solve problems from Project Euler and I am going to use Scala to do it.  I am sure my solutions will be crude but at least I am learning something.  Also, I am hope my readers with offer insights for improvements.  Yes, I am talking to you out there reading this.:)

    Additional Resources

    http://www.scala-lang.org – The homepage for the Scala programming language.

     

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