Problem 1 [Algorithm]: Multiples of 3 and 5

[samdebacker]

If we list all the natural numbers below 10 that are multiples of 3 or 5 we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.

[samdebacker]

The very simple solution, just use the Scala collections API to create a Range, filter and sum.
See my simple case.

[jamiephillips0000]

Hi guys
I used the same approach as Sam except I used (1 to 1000) instead of (1 until 1000).
Using (1 to 1000) fails the test but (1 until 1000) works (Works means it passes the test)
i had a look and the reason is here >> http://tutorials.jenkov.com/scala/for.html

to vs. until

You can use either the keyword to or until when creating a Range object. The difference is, that to includes the last value in the range, whereas until leaves it out. Here are two examples:

for(i <- 1 to 10) {
println("i is " + i);
}

for(i <- 1 until 10) {
println("i is " + i);
}
The first loop iterates 10 times, from 1 to 10 including 10.

The second loop iterates 9 times, from 1 to 9, excluding the upper boundary value 10.

[eloots]

Just added a version using Set. This is what I demonstrated as an alternative during the hacking session on Monday. Not claiming to be efficient. Just to show an alternative way to solve this problem

[oleastre]

Added my math based solutions.
The first version is purely mathematical and does not teach anything about scala.
The second one is more fun: it showcases implicit classes.

[samdebacker]

So next I present you a tail recursive with accumulator solution.

An often used technique in Functional Programming is to write it as a recursive function. In a tail-recursive function, the very last expression/statement that gets executed is the recursive call. After that the function just returns. Such a tail recursive function can and will be optimised by the compiler, effectively generating byte code of a while-loop. In Scala we add the @tailrec annotation as a warranty that the function is tail recursive. (Just like we add an @OverRide annotation in Java to indicate that a method overrides an inherited method on purpose.)

The sum parameter accumulates the result built during the recursion and is returned at the very end. We call this an accumulator.

[tdeconin]

I pushed a solution using foldLeft with pattern matching guards

[samdebacker]

👍 for @tdeconin, my favourite so far, a lot going on here though:

• fold(Left)-ing to do the tail recursion with accumulator
• using a partial function with case matching with a condition on one of the cases
• over a Stream
• using exists

and an overal complexity of O(n)

[tdeconin]

Cheers @samdebacker !

One thing I was wondering about my solution: does the scala runtime materialise an actual sequence in memory of 1000 elements? In theory this is not needed, since we only iterate over the elements and the result is a number.

[mverbist]

my favourite remains the simple one from Sam (I had the same, in fact).
It's the most readible, and understandable, for anyone who comes after us.

(1 until 1000).filter(l => l % 3 == 0 || l % 5 == 0).sum

[octonato]

It's without doubt the most efficient and comprehensive solution. And I think everybody (I hope) can agree with that.

I see the other implementations are more exploratory of Scala features and functional concepts. I think it's a good idea to explore other implementations because others can always learn a little bit more of Scala.

However, as mentioned before, we must not forget that the goal of this initiative is to teach/learn Scala from each other. Therefore, whenever someone comes with an alternative, less obvious, implementation, it's better go give a short explanation of the concepts.

[octonato]

@tdeconin

The Scala runtime will not hold everything in memory because you are using a Stream. Each iteration will produce one new item until you reach the stop condition.

Items that are behind the Stream cursor are eligible for GC.

However, it'll produce items that are not multiples of 3 or 5. But those items will be discarded.

[tdeconin]

@rcavalcanti Thanks for clarifying. I wasn't sure about the behaviour of takeWhile. I tested it with 10 billion elements in the stream and memory consumption remained pretty much constant :)

[samdebacker]

I'm not very sure of your point @rcavalcanti, in the Stream ScalaDoc I read:
"The Stream class also employs memoization such that previously computed values are converted from Stream elements to concrete values of type A."
So every computed element in the Stream is kept in memory!! So the items behind the cursor are NOT GCed, until the complete Stream is GCed.

Towards performance the Stream seems absolutely worst (3ms) compared to the others in the µs range. But I liked the Stream because it feels 'reactive event-based elastic ... ' I had a Stream solution as well, a bit different, but I didn't posted it (yet) because of the memoization. The takeWhile and filter on a Stream return new Streams and hence you avoid 'materialising' the Stream and keep the nice readability of the very first solution posted here. On the other hand, a Range (1 until 1000) is materialised into an IndexedSequence by the filter method.

Integers.positiveIntegers.takeWhile(_ < 1000).filter(l => l % 3 == 0 || l % 5 == 0).sum

[tdeconin]

@samdebacker I came across this blog post regarding Streams. It explains the memoization does not always take place: http://blog.dmitryleskov.com/programming/scala/stream-hygiene-i-avoiding-memory-leaks/

[ghost]

👍 for @tdeconin as well

[eloots]

for @tdeconin https://github.com/tdeconin as well

On 29-nov.-2014, at 22:05, Luc Duponcheel [email protected] wrote:

for @tdeconin https://github.com/tdeconin as well

—
Reply to this email directly or view it on GitHub #5 (comment).