Comments on Scala Blog: Fun with Project Euler and Scala

For problem 5, an efficient algorithm using Euler&...

2011-06-10T03:37:05.755-07:00

For problem 5, an efficient algorithm using Euler's method to find GCD:

def gcd(a:Long,b:Long):Long={
val r=a%b
if(r==0)b else gcd(b,r)
}

(1l to 20l) reduce {(a,v)=>a*v/gcd(a,v)}

2011-06-04T10:29:26.279-07:00

This comment has been removed by the author.

Hello, We are delighted to inform you that Codefe...

2011-01-22T10:35:32.238-08:00

Hello,

We are delighted to inform you that Codefest'11, the annual International online coding festival of Computer Engineering Society, IT-BHU, has been unveiled. CodeFest is a unique fest wherein concepts of mathematics, logic, artificial intelligence, algorithms, language syntax, etc. are required to be deployed in programming; these concepts manifest themselves in solving problems effectively and efficiently!

CodeFest was started last year. CodeFest'10 was a phenomenal success with participation from all over the globe. CodeFest'11 is geared up with some new and pepped up events, while maintaining the integrity of its standards.This year CodeFest has associated with Technex'11, the annual all India Technical Festival of IT-BHU, to expand its horizons.

Here is a brief description of the constituent online events:

* Mathmania: A mathematical puzzle contest that puts mathematical and computational skills to test.
* Manthan: An algorithm intensive programming contest that would require coders to tailor existing standard algorithms.
* Perplexed: A programming contest, aimed to test the knowledge of C, wherein codes will be rewarded against syntactic constraints.
* Ratespiel: A technical contest covering different areas of Computer Science.
* Virtual Combat: An educational game wherein teams of programmed robotic tanks will fight the battles for glory. Codes Do Fight! Watch this out.

Visit our website for more details.

Few exciting statistics about Codefest'10:

* 2354 registrations (including 128 professionals) from 680 different institutions, across 59 countries
* Some participants were among the winners of Google Code Jam, Top Coder SRMs and ACM ICPC
* Total prize money was a whopping amount of 260,000 INR!
* Codefest '10 was the largest online coding festival of the Indian subcontinent in 2010 in terms of prize money!
* Codefest'10 was the second largest online coding festival of the Indian subcontinent in 2010, next to Bitwise
* Gained recognition from several international organizations including Codechef, Adobe, British Telecom, TCS and IEEE

The Codefest'11 team has set out to unleash a yet another coding extravaganza. We hope that your participation would raise the level of competition in Codefest'11. Feel free to contact us at codefest@itbhu.ac.in or reach us personally at:

* Mohit Bansal mohit.bansal.cse06@itbhu.ac.in
* Saket Saurabh saket.saurabh.cse07@itbhu.ac.in

We wish you all the best for Codefest'11 and for your future endeavours.

Happy coding, and be free!

Regards,
Team Codefest
Visit us at http://itbhu.ac.in/codefest
Mail us at codefest@itbhu.ac.in
Check out our page at http://facebook.com/codefest
Follow us at http://twitter.com/c0defest/
Read our blog at http://itbhu.ac.in/codefest/blog

Do Watch The Virtual Combat Promotional Video:
http://www.youtube.com/watch?v=v1rY3tyTj50

Awesome post, although I still prefer to use C#

2010-12-26T07:59:11.871-08:00

Awesome post, although I still prefer to use C#

I had fun with my solution to problem 6. By using...

2008-10-17T07:37:00.000-07:00

I had fun with my solution to problem 6. By using implicits I made sum and square functions that work with either lists of numbers or single numbers, so they can be applied in either order:

implicit def int2list(i: Int) = List(i)
implicit def list2int(l: List[Int]) = l(0)

def sum(xs: List[Int]) = xs.foldLeft(0)(_+_)
def square(xs: List[Int]) = xs.map(x => x*x)

val xs = (1 to 100).toList
println((sum(square(xs)) - square(sum(xs))).abs)

Here's my solution to problem 5. I don't ...

2008-10-01T12:54:00.000-07:00

Here's my solution to problem 5. I don't know if it gives correct results for all numbers, but it appears to work until the result exceeds the capacity of Int.

(1 to 20).foldLeft(1){ (product,n) =>
val r_raw = product % n
val r = if (r_raw == 0) n else r_raw
product * (if (n % r == 0) (n / r) else n)
}

My solution to Problem 7:
var ps:Stream[Int...

2008-06-19T01:16:00.000-07:00

My solution to Problem 7:
var ps:Stream[Int] = Stream.cons(2,
　　　　　　　　　　　　Stream.from(3).filter{ n =>
　　　　　　　　　　　　　　ps.takeWhile(p => p*p <= n).forall(n%_ !=0)
　　　　　　　　　　　})
ps(10000)
And there has some codes for Project Euler:
http://eastsun.javaeye.com/category/34059

2008-06-19T01:11:00.000-07:00

This comment has been removed by the author.

Ugh that looks horrible. See the formatted code he...

2008-04-23T19:42:00.000-07:00

Ugh that looks horrible. See the formatted code here:
http://codepad.org/5RvHTTXB

I know I'm a little late to the conversation. But ...

2008-04-23T19:19:00.000-07:00

I know I'm a little late to the conversation. But I just wanted to present another take on the Sieve of Eratosthenes. Really its just a Scala translation of the Haskell algorithm posted here: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

Caveat: I'm a Scala noob so this may not be idiomic Scala.

/**
* Returns an infinite stream of prime numbers.
* The algortihm is ported from the Haskell algorithm discussed in
* the "Genuine Sieve of Eratosthenes" by Melissa E. O'Neill
* fond here: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
*/
def primes : Stream[Int] =
{
def sieve(nums : Stream[Int], table : Map[Int, List[Int]])
: Stream[Int] =
{
val curr = nums.head
table.get(curr) match
{
case None => Stream.cons(curr
, sieve(nums.tail
, table.update(curr * curr, List(curr))))
case Some(v) => sieve(nums.tail
, v.foldLeft (table - curr)(reinsert (curr) _ ))
}
}

def reinsert(curr : Int) (table : Map[Int, List[Int]], prime : Int)
: Map[Int, List[Int]] =
{
val newVal = prime + curr
table.get(newVal) match
{
case None => table.update(newVal, List(prime))
case Some(v) => table.update(newVal, prime::v)
}
}
sieve(naturals tail, Map.empty)
}

Thanks for this post — I've enjoyed comparing my s...

2008-04-07T11:11:00.000-07:00

Thanks for this post — I've enjoyed comparing my solutions to yours.

I tried changing my solutions to use your implicit conversions, but hit the following problem getting my code to compile:

https://lampsvn.epfl.ch/trac/scala/ticket/733

As you can see, I thought it was a compiler bug, but Martin says the implicits ought be declared in such a way as to help the type inference a bit more. If I understand his suggestion correctly, it's better to write:

implicit def pimpMyIterableInt(it: Iterable[Int]):RichIterableInt = new RichIterableInt(it)
class RichIterableInt(it: Iterable[Int]) {
def sum = it.foldLeft(0)(_ + _)
}

and in fact this made my compile problems go away.

You are right I was not looking good enough.

2008-01-14T15:29:00.000-08:00

You are right I was not looking good enough.

evenly divisible is just divisible (i.e. producing...

2008-01-14T09:42:00.000-08:00

evenly divisible is just divisible (i.e. producing no remainder when divided). Are you sure you checked the number properly? It is divisible by 9 -- if you look at the calculation, the number three appears twice in the multiplication list.

is the answer of Problem 5: What is the smallest ...

2008-01-14T04:16:00.000-08:00

is the answer of Problem 5: What is the smallest number that is evenly divisible by all of the numbers from 1 to 20
really the right answer?
9 is a number between 1 and 20 and your answer is not even divisible by 9. I am not sure what evenly divisible means.

Ah, thanks. I guess that's good enough for the pur...

2008-01-07T05:30:00.000-08:00

Ah, thanks. I guess that's good enough for the purpose of answering the question.

Michel:

I too found that the Sieve of Erato...

2008-01-06T06:19:00.000-08:00

Michel:

I too found that the Sieve of Eratosthenes lost its usefulness after a while. Thankfully, Java's math library has a BigInteger class with a "nextProbablePrime" method. Converting between Java's BigInteger and Scala's BigInt is a bit of a pain, but you can do the following:

scala> lazy val primes: Stream[BigInt] = Stream.cons(BigInt(2), primes.map(b => new BigInt(b.bigInteger.nextProbablePrime)))
primes: Stream[BigInt] = Stream(2, ?)

scala> primes drop 10000
res1: Stream[BigInt] = Stream(104743, ?)

If you define some implicits than the definition for primes becomes a lot prettier.

scala> implicit def bigInt2BigInteger(b: BigInt) = b.bigInteger
bigInt2BigInteger: (BigInt)java.math.BigInteger

scala> implicit def bigInteger2BigInt(b: java.math.BigInteger) = new BigInt(b)
bigInteger2BigInt: (java.math.BigInteger)BigInt

scala> lazy val primes: Stream[BigInt] = Stream.cons(2, primes.map(_.nextProbablePrime))
primes: Stream[BigInt] = Stream(2, ?)

Hope this helps.

Great article! Haven't noticed Project Euler befor...

2008-01-06T03:32:00.000-08:00

Great article! Haven't noticed Project Euler before, and now I'm hooked. Having used functional languages for several years, your post serves as a nice introduction to Scala-isms.. I've been finding the syntax a bit unnatural, and having concrete examples to compare my solutions to, makes the learning process easier.

Any idea how to do problem 7 in Scala? In Haskell I can just use the Sieve of Eratosthenes and drop the first 10,000 prime numbers, but in Scala I ran out of heap space.

Actually even the takeWhile method is unnecessary....

2007-12-31T11:29:00.000-08:00

Actually even the takeWhile method is unnecessary.

def largestPrimeFactor(n: Long): Long = {
val p = Stream.from(2).
filter(n % _ == 0).head
if (p == n) n
else largestPrimeFactor(n / p)
}

println(largestPrimeFactor(317584931803L))

For problem 3, this one is very fast (75 ms on my ...

2007-12-31T10:37:00.000-08:00

For problem 3, this one is very fast (75 ms on my computer).

I started with something more complicated and realized that it was very slow for big numbers. The interesting thing is that I discovered a much simpler solution while trying to optimize.

def largestPrimeFactor(n: Long): Long = {
val p = Stream.from(2).
takeWhile(_ <= n).
filter((x) => n % x == 0).
head
if (p == n) n
else largestPrimeFactor(n / p)
}

println(largestPrimeFactor(317584931803L))

Oscar:

Thanks for catching the <= bug! I...

2007-12-30T15:43:00.000-08:00

Oscar:

Thanks for catching the <= bug! I've fixed it in the post.

And you're correct, Scala allows for both functional and imperative approaches. An even -more- imperative solution (no iterators, anonymous functions, filters, or folds) would be:

var sum = 0
var curr = 1
var prev = 0

while (curr <= 1000000) {
if (curr % 2 == 0)
sum += curr

val next = curr + prev
prev = curr
curr = next
}

Console.println(sum)

A more imperative solution to problem 2 for a gent...

2007-12-30T13:41:00.000-08:00

A more imperative solution to problem 2 for a gentle introduction to scala for java programmers ;)

Your solution feels more idiomatic scala though.

class FiboIter extends Iterator[Int] {
var pp = 0
var p = 1
val hasNext = true
def next = {
val curr = pp + p
pp = p
p = curr
curr
}
}
println(new FiboIter().
takeWhile(_ <= 1000000).
filter(_ % 2 == 0).
foldLeft(0)(_ + _))
}

By the way the problem stated "... which do not exceed one million...". So I think that the takeWhile function argument should take the <= operator not <. But in that case it didn't change the result.

Jörn:

I would use "to" instead of "until", ...

2007-12-30T09:44:00.000-08:00

Jörn:

I would use "to" instead of "until", since it's inclusive.

Once again, pimping my Iterable[Int] with a "sum" method:

implicit def iterableWithSum(it: Iterable[Int]) = new { def sum: BigInt = it.foldLeft(0)(_+_) }

Except this time the result is coerced to be a BigInt, so I can take advantage of the "pow" method on BigInt.

Then:

(1 to 100).sum.pow(2) - (1 to 100).map(n => n*n).sum

Daniel:

Yes, that does use fewer instructions. The asymptotic complexity is unchanged though.

Also:

It has been brought to my attention that my original solution to Problem 3 was buggy, as it assumed that each prime factor only occurred once in the factorization. I've updated the blog post with a bug fix.

scala> (1 until 1000).foldLeft(0)((old, next) =...

2007-12-29T11:40:00.000-08:00

scala> (1 until 1000).foldLeft(0)((old, next) => old + (if (next % 3 == 0 || next % 5 == 0) next else 0))
res5: Int = 233168

// Might run slightly faster as it only iterates through the array once

Great post and an interesting approach to learn Sc...

2007-12-29T10:48:00.000-08:00

Great post and an interesting approach to learn Scala.

My solution to problem 6 (What is the difference between the sum of the squares and the square of the sums?):

var sum = (1 until 101).foldLeft(0)(_ + _);
var squareSum = sum * sum

var sumSquare: Int = 0
(1 until 101).foreach(n => sumSquare += n*n)
println(squareSum - sumSquare)

The output is correct, but I'm sure the solution could be improved a lot. I'm curious to see yours.

Fantastic Blog!

2007-12-28T17:51:00.000-08:00

Fantastic Blog!

Comments on Scala Blog: Fun with Project Euler and Scala

For problem 5, an efficient algorithm using Euler&...

Hello, We are delighted to inform you that Codefe...

Awesome post, although I still prefer to use C#

I had fun with my solution to problem 6. By using...

Here's my solution to problem 5. I don't ...

My solution to Problem 7: var ps:Stream[Int...

Ugh that looks horrible. See the formatted code he...

I know I'm a little late to the conversation. But ...

Thanks for this post — I've enjoyed comparing my s...

You are right I was not looking good enough.

evenly divisible is just divisible (i.e. producing...

is the answer of Problem 5: What is the smallest ...

Ah, thanks. I guess that's good enough for the pur...

Michel:I too found that the Sieve of Erato...

Great article! Haven't noticed Project Euler befor...

Actually even the takeWhile method is unnecessary....

For problem 3, this one is very fast (75 ms on my ...

Oscar:Thanks for catching the <= bug! I...

A more imperative solution to problem 2 for a gent...

Jörn:I would use "to" instead of "until", ...

scala> (1 until 1000).foldLeft(0)((old, next) =...

Great post and an interesting approach to learn Sc...

Fantastic Blog!

My solution to Problem 7:
var ps:Stream[Int...

Michel:

I too found that the Sieve of Erato...

Oscar:

Thanks for catching the <= bug! I...

Jörn:

I would use "to" instead of "until", ...