Connecting...

W1siziisimnvbxbpbgvkx3rozw1lx2fzc2v0cy9zawduawz5lxrly2hub2xvz3kvanbnl2jhbm5lci1kzwzhdwx0lmpwzyjdxq

Project Euler with retrospect on my Scala journey by Marko Švaljek

W1siziisijiwmtgvmdyvmjevmtavmtmvmjavmjm0l3blegvscy1wag90by00nje3nzuuanblzyjdlfsiccisinrodw1iiiwiotawedkwmfx1mdazzsjdxq

Today's #ThursdayThoughts is from Marko Švaljek with his article on 'Project Euler with retrospect on my Scala journey'. Happy reading! 

 

'After starting to ride on the rollercoaster of scala and zalando for the past year and some months I started noticing that it has been a while since I did my last blog post. Precisely it has been a year since my last blog entry. What's the reason for that?

Well I could beat around the bush but the reality is that over the past year I was pretty much learning the basics that every scala programmer should know by having this guy reviewing my pull requests: johofer. And since my learning were pretty much "basic" all the time there just wasn't anything that I found interesting enough to post here. Not to mention that whatever I would write there are tons of better materials out there, writing about programming language and programming, in general, is a niche I never really covered on my blog. But, let's go back to my scala journey.

Now, a lot of times you hear various success stories about learning scala in a couple of weeks and similar and I agree it's totally easy language to start. But working alongside a guy that has many years of experience you suddenly notice that this language is "difficult" to master. One good news is I'm not getting my soul crushed for a while now when I make a pull request at work. Also having a kid further reduces the amount of time I'm able to invest in the blog. But on the other hand you learn how to be more efficient with time and enjoy little things.

Lately, I started a habit of solving programming puzzlers as often as I could, it's incredible how even when solving very small and contained puzzles I still learn a lot about the scala. One of the nicer databases with interesting programming / mathematical puzzles is Project Euler. It has been around for quite some time, but why not cover it here? I'll start with something very very simple and might include it in the following posts too. The thing is that you can always pimp this up, even the simplest algorithm you can take up to the level of a microservice so there's plenty that can be shown.

 

Assignment 2

Here you can lookup the problem 2. First thing that comes to my mind is, this looks like a perfect fit for streams, you have the starting condition and from then on you can construct as many elements as you like. Basically, after doing some filtering it's very easy to satisfy all the conditions of the assignment.

 

My solution

After some hacking and making all the classical coding trial and error stuff, some of which I'm even afraid to admit here here is my initial solution:

object Euler2 extends App {

  def fibs(a: Int, b:Int): Stream[Int] = 
    b #:: fibs(b, a + b)

  val res = fibs(1, 1).
    filter(_ % 2 == 0).
      takeWhile(_ < 4000000).sum

  println(res)
}

 

Research what others did in order to learn more

One of the first solutions I bumped into is from Shadaj. The first thing I notice in this solution is that Shadaj is actually using takeWhile before the filtering, now it makes me wonder if there is any difference between the two, especially in execution time. After some mini testing it looks like filter before takeWhile is around 4% faster. It would be very interesting to check why, but then again this might be subject to some other post.

There is also a very nice overview of many solutions to the Euler project done by Pavel Fatin. I'll focus on what I can learn from the second one. At first I was impressed by the fact that the stream is constructed by using scanLeft this is way more elegant than what I did, basically scanLeft returns a new sequence whereas reduce returns single value. This I'll totally remember for the future. Also by seeing the comment on the assert statement that it takes only 1 ms I wanted to compare the speed against the common solution, it looks like it's way slower, on my computer and my solution it takes ~50 ms where as the scanLeft approach takes ~300 ms, now this seems a bit bad, at first I just tried removing lazy from the stream, but this one also didn't help. Also very interesting to explore what actually happens here.

Then I bumped into the following solution from samskivert. Let's try this one out. This one was very close to the initial one and I could not find any statistical difference. What I did notice is that the code seems a bit complicated, there are 2 if statements in one method and that seems a bit unreadable. But also a nice solution to the problem.

 

Conclusions

Solving programming "puzzles" was always a thing I really liked to do, back in the day when I was starting out in the high school, I got thrown into competitive programming and I really liked what it did to my way of thinking. One year and some months into Scala I'm still able to remember the imperative thinking way I had and to be honest it scares me how much my way of thinking was changed. Not so long (assuming I didn't work with java8) I would just bash something like this up:
 
object Euler2_imperative extends App {
  
  var a = 0
  var b = 1
  var sum = 0

  while (a + b < 4000000) {
    if ((a + b) % 2 == 0) {
      sum += a + b
    }
    val t = b
    b = a + b
    a = t
  }

  println(sum)
}


It still doesn't stop to amaze me how much more expressiveness you get when you start thinking functionally, but also the language that you use helps a lot. Personally, I think I'm just barely starting to scratch the surface of the functional bug, but let's see how far it will take me.'

 

This article was written by Marko Švaljek and originally posted on msvaljek.blogspot.com