ScalaでProject Euler（53）

Scala

Problem 30

重複組合せを使えばかなり速くなります。重複組合せを生成して、その各要素の5乗和の各桁をソートして元のリストと同じになればOkです。例えば、

List(0, 1, 3, 4, 6) -> 04 + 14 + 34 + 44 + 64 = 1634

  • > List(0, 1, 6, 3, 4) -> List(0, 1, 3, 4, 6)

と元に戻ってきます。ここで、自然数をリストにするとき5桁で足りない分は0で埋める必要があります。
重複組合せはIteratorを使えば簡単に生成できます。
下のコードは8乗までですが、適切にLongを使うと11乗でも1秒程度でした。

import scala.testing.Benchmark

def pow(n :Int, e :Int) = (1 to e).foldLeft(1)((x, y) => x * n)

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

def repeated_combination[T](a :List[T], n :Int) :Iterator[List[T]] =
    (a, n) match {
        case (_, 0) => Iterator(Nil)
        case (Nil, _) => Iterator()
        case _ => repeated_combination(a, n - 1).map(a.head :: _) ++
                                        repeated_combination(a.tail, n)
}

val E = 5

def calc_upper() =
    Iterator.from(1).filter(e => e * pow(9, E) < pow(10, e)).next

def solve() = {
    val pows = Array.range(0, 10).map(pow(_, E))
    val e = calc_upper
    
    def is_valid(a :List[Int]) =
        a == digits(a.map(pows(_)).sum, e).sort(_ < _)
    
    val it = repeated_combination(List.range(0, 10), e)
    println (it.filter(is_valid).map(_.map(pows(_)).sum).sum - 1)
}

object Test extends Benchmark {
    def run() = solve
}

println (Test.runBenchmark(10))