Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I'm trying to learn some Scala and decided to try to tackle some Project Euler problems.

For problem #48, coming from a Python background, my solution is the following one-liner:

print ( (1 to 1000).map(i => BigInt(i).pow(i)).sum % BigInt(10).pow(10) )

Is this idiomatic? Is there a simpler/more readable solution?

share|improve this question
add comment

2 Answers 2

up vote 2 down vote accepted

Your solution is totally valid. Instead of xs.map(f).sum it is possible to use xs.foldLeft(init)(f):

(1 to 1000).foldLeft(BigInt(0)) {
  (sum, n) => sum+BigInt(n).pow(n)
}
// or with /: synonym for foldLeft
(BigInt(0) /: (1 to 1000)) {
  (sum, n) => sum+BigInt(n).pow(n)
}
share|improve this answer
    
Thanks for you answer! Would using foldLeft be more efficient or is it just a matter of taste? Also, I didn't know at all the /: syntax for foldLeft. Seems a bit cryptic TBH... –  jjt Sep 28 '12 at 21:05
1  
foldLeft should be more efficient because it does both operations (map+sum) in a single step. Thus, there is no unnecessary creation of an intermediate collection (from map), which can be allayed with lazy collections (like .iterator of .view). But, foldLeft should be more efficient, even with lazy collections. –  sschaef Sep 28 '12 at 21:27
add comment

Your solution is clean but doesn't scale well. A well known optimization for a^k mod m is to perform all computations modulus m. If m is sufficiently small, we furthermore can switch to native types (this is not the case here !).

val n = 1000
val m = BigInt(10).pow(10)
(for (i <- 1 to n) yield BigInt(i).modPow(i,m)).sum % m

Rounded avarage timing results (Scala 2.9.1 with -optimize) :

n                     1000     | 10000
Initial solution       4.8 ms  |  6700 ms
Fold left              4.8 ms  |  6700 ms
My humble version      0.5 ms  |     5 ms
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.