# Project Euler #12 in Scala — Highly divisible triangular numbers

I generally work in Python for programming competitions, but I'm teaching myself Scala. As an exercise, I've attempted Project Euler problem #12 in Scala. I hope that somebody familiar with Scala can point out anything I'm doing which is not idiomatic in "functional style" Scala. My code produces the correct result, and is reasonably fast, so I'm mostly looking for coding style advice.

object HighlyDivisibleTriangularNumber {
val triangleCache = collection.mutable.Map[Int, Int]()
val triangle: Int => Int = {
case 1 => 1
case n => triangle(n - 1) + n
}
def cachedTriangle(n: Int) = triangleCache.getOrElseUpdate(n, triangle(n))

def nFactors(x: Int): Int = {
val maxFactor: Int = math.round(math.sqrt(x.floatValue).floatValue)
val smallFactors: Set[Int] = (1 to maxFactor).filter(f => x % f == 0).toSet
val allFactors: Set[Int] = smallFactors ++ smallFactors.map(f => x / f)
allFactors.size
}

def main(args: Array[String]): Unit = {
val triangleNumbers = Iterator.from(1).map(cachedTriangle)
val firstWith500Factors = triangleNumbers.dropWhile(nFactors(_) < 500).next
println(firstWith500Factors)
}
}


I realize that a mutable collection is not a great starting point for functional Scala, but struggled to implement a memoized version of triangle without the mutable map.

Your triangular number "cache" isn't an idiomatic technique in functional programming. Since triangular numbers constitute an infinite sequence, it would be more elegant to model them in Scala as an infinite lazy stream, especially since you only require sequential access. I would define it this way:

val triangleNumbers = Stream.from(1).scan(0)(_ + _)


Or, if you prefer to have the sequence start with 1 rather than 0:

val triangleNumbers = Stream.from(2).scan(1)(_ + _)


nFactors could be optimized a bit.

• I would call the parameter n, which has the connotation of being an integer, instead of x, which has the connotation of being floating point.
• The .floatValue casts are superfluous, and it is safe to round the square root down using .intValue rather than sometimes rounding up.
• Personally, I would prefer the name middleFactor instead of maxFactor.
• The lambda in .filter(f => x % f == 0) could be more idiomatically written as .filter(x % _ == 0).
• You don't need to use sets. Just a count of factors will do, along with a check of whether middleFactor is being double-counted.
def nFactors(n: Int): Int = {
val middleFactor = math.sqrt(n).intValue
val smallFactors = (1 to middleFactor).count(n % _ == 0)
2 * smallFactors - (if (middleFactor * middleFactor == n) 1 else 0)
}


In main, the .dropWhile(…).next would be more clearly written as .find(…).

def main(args: Array[String]): Unit = {
triangleNumbers.find(nFactors(_) > 500).foreach(println)
}

• Great review!! Thanks a lot. Now to read up on scan, find etc :) – bsa Oct 24 '16 at 10:32