ScalaでProject Euler（70）

Problem 40

この問題はIteratorを使うと簡単ですね。Streamだとメモリを使ってしまうはずです。

def digits(n :Int) :List[Int] =
    if(n == 0) Nil else n % 10 :: digits(n / 10)

def f(k :Int) = {
    val it = Iterator.from(1).flatMap(n => digits(n).reverse.toIterator)
    it.slice(k - 1, k).next
}

val N = 7
val ds = Iterator.iterate(1)(_ * 10).take(N)
println (ds.map(f).reduceLeft(_ *_))

もちろんdを最初から辿らずに求めることもできます。

def d(k :Int) = {
    def f(count :Int, ini :Int, w :Int, n :Int) :Int =
        if(k - count <= w * n) {
            val q = (k - count) / w
            val r = (k - count) % w
            digits(q + ini).reverse(r)
        }
        else
            f(count + w * n, ini * 10, w + 1, n * 10)
    
    f(1, 1, 1, 9)
}