ScalaでProject Euler(9)

Problem 4

この問題は、回文数を大きいほうから順に生成して3桁同士の積になっているかを調べる方法と、3桁同士の積を大きいほうから順に生成して回文数かどうか調べる方法の2通りがあります。今回は前者、次回は後者を考えます。


まず、回文数を生成します。回文数は、再帰的に生成することもできますが、わかりやすいのは999から1ずつ小さくして、例えば321ならそれをひっくり返して123にしてそれを結合して321123とします。

def reverse(n :Int, m :Int = 0) :Int =
    if(n == 0)
        m
    else
        reverse(n / 10, m * 10 + n % 10)

def palindrome(N :Int) = {
    val m = pow(10, N)
    for(n <- (m - 1) to (m / 10) by -1)
        yield n * m + reverse(n)
}

for式

println (for(i <- List(1, 2, 3)) yield i * 2)
List(2, 4, 6)

yieldのあとに書かれたものがListになります。他の言語で言う内包表記みたいなものですね。
forの中のコレクションで戻り値の型が変わります。

println (for(i <- 1 to 3) yield i * 2)
Vector(2, 4, 6)

回文数を生成した後は3桁の掛け算になっているかの判定です。これは大きな数になれば素因数分解して約数を列挙したほうが速いのでしょうが、ここでは999から順番に割っていけばよいでしょう。1ずつ除数を小さくしていき、商が除数以上になれば掛け算になっていないということになります。
以上をまとめると、

def pow(n :Int, e :Int) :Int =
    if(e == 0) 1 else n * pow(n, e - 1)

def reverse(n :Int, m :Int = 0) :Int =
    if(n == 0) m else reverse(n / 10, m * 10 + n % 10)

def palindrome(N :Int) =
    for(n <- (M - 1) to (M / 10) by -1)
        yield n * M + reverse(n)

def is_product(n :Int) = {
    def f(d :Int) :Boolean =
        if(d * d < n)
            false
        else if(n % d == 0)
            true
        else
            f(d - 1)
    
    f(M - 1)
}

val N = 3
val M = pow(10, N)
println (palindrome(N).filter(is_product).head)