ScalaでProject Euler（67）

Problem 38

積が合わせると9桁になるので、例えば被乗数が1〜4だとすると、桁数の分配は2,2,2,3になります。この分配の計算は次のように簡単に行えます。

9 / 4 = 2 -> 9 - 2 = 7 -> 7 / 3 = 2 -> 7 - 2 = 5 -> 5 / 2 = 2 -> 5 - 2 -> 3 -> 3 / 1 = 3

そうすると、乗数の範囲が決まります。被乗数に対しそれぞれ、

1 : 10 / 1 〜 100 / 1
2 : 10 / 2 〜 100 / 2
3 : 10 / 3 〜 100 / 3
4 : 100 / 4 〜 1000 / 4

この交わりの25 〜 33の範囲で調べればよいことになります。本当はもう少し絞り込めますが手抜きします。
あとは積が1〜9まで使われているか調べるだけです。

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

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

def number(ds :List[Int]) = ds.foldLeft(0)(_ * 10 + _)

def is_pandigital(ds :List[Int]) =
    ds.foldLeft(0)((x, y) => x | (1 << y)) == 1022

def intersect(a :(Int,Int), b :(Int,Int)) = (a, b) match {
    case ((f1, s1), (f2, s2)) => (f1.max(f2), s1.min(s2))
}

def calc_range(n :Int) = {
    def f(m :Int, d :Int) :List[Int] =
        if(d == 0) Nil else m / d :: f(m - m / d, d - 1)
    
    f(9, n).zip(List.range(1, n + 1)).
                map(x => (pow(10, x._1 - 1) / x._2, pow(10, x._1) / x._2)).
                reduceLeft(intersect)
}

def gen_products() =
    for(n <- Iterator.range(2, 10);
        (b, e) = calc_range(n);
        m <- Iterator.range(b, e + 1))
            yield Iterator.range(1, n + 1).map(m *)

def digits2(it :Iterator[Int]) =
    it.flatMap(n => digits(n).toList.reverse).toList

val it = for(ds <- gen_products().map(digits2)
             if is_pandigital(ds))
                yield number(ds)

println (it.max)