ScalaでProject Euler（79）

Problem 49

この問題はどうやっても解けると思いますが、なるべく速そうな方法を考えます。
まず0〜9で4要素の重複組合せを生成します。例えば[1, 4, 7, 8]です。順番を入れ替えて生成される4桁の数はこれで代表されます。そして、ここから順列を生成します。例えば、[1, 1, 2, 3]なら、

[1, 1, 2, 3], [1, 1, 3, 2], [1, 2, 1, 3], [1, 2, 3, 1],
[1, 3, 1, 2], [1, 3, 2, 1], [2, 1, 1, 3], [2, 1, 3, 1],
[2, 3, 1, 1], [3, 1, 1, 2], [3, 1, 2, 1], [3, 2, 1, 1]

重複を避けるためにふつうの順列生成から少し変えています。nextsという関数が少し違います。[1, 1, 2, 3]なら

[(1, [1, 2, 3]), (2, [1, 1, 3]), (3, [1, 1, 2])]

が生成されて、今選んだ要素が第1項、再帰的に生成されるための種が第2項です。
そして、このように生成されたリストの中から、頭が0または最後が偶数または5のものは排除します。ここで数に直します。[1, 4, 7, 8]なら、

[1487, 1847, 4187, 4781, 4817, 4871, 7481, 7841, 8147, 8417, 8471, 8741]

ここからペアを生成します。例えば、1487と1847です。これを等差数列の初項と第2項とみなして第3項を求めます。2207ですね。これが上のリストにあれば、3項とも素数かどうか調べます。

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

def is_prime(n :Int) =
    Iterator.from(2).takeWhile(p => p * p <= n).forall(n % _ != 0)

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)
}

def nexts[T](a :List[T], prev :Option[T]) :List[(T,List[T])] = (a, prev) match {
    case (Nil, _) => Nil
    case (h :: t, Some(p)) if h == p =>
        for((n, b) <- nexts(t, prev)) yield (n, h :: b)
    case (h :: t, _) => (h, t) ::
        (for((n, b) <- nexts(t, Some(h))) yield (n, h :: b))
}

def permutations[T](a :List[T]) :List[List[T]] =
    if(a == Nil)
        List(Nil)
    else
        for((h, b) <- nexts(a, None); t <- permutations(b))
            yield h :: t

def solve(a :List[Int]) = {
    val s = permutations(a).
            filter(b => b.head != 0 && b.last % 2 == 1 && b.last != 5).
            map(number)
    
    for(b <- s.tails.take(s.size - 1);
        n1 = b.head;
        n2 <- b.tail;
        n3 = n2 * 2 - n1;
        if b.tail.contains(n3) && List(n1, n2, n3).forall(is_prime))
            yield (n1, n2, n3)
}

val N = 4
for(a <- repeated_combination(List.range(0, 10), 4); b <- solve(a))