ScalaでProject Euler（103）

まず外の5つを決めます。その和をs_ext、内側の和をs_intとします。

s_ext + s_int = 55

です。1列の和をs_lineとします。全ての列の和を取ると、内側は2回ずつカウントするので、

5s_line = s_ext + 2s_int
s_int = 5(s_line - 11)

s_intは5の倍数、s_extも5の倍数です。そうなるように外側を選びます。外側のトップだけ最小のものを選んで残りは順列を出します。内側はトップだけ決めれば、あとは先ほどの式でs_lineが決まっているので、残りの内側は自動的に決まります。

この問題は組みにくいですね。Arrayを使ってごまかしています。

// List(1, 2, 3) -> (1, List(2, 3)), (2, List(3)), (3, List())
def removes[T](a :List[T]) :Iterator[(T,List[T])] = a match {
    case Nil => Iterator()
    case h :: t => Iterator((h, t)) ++ removes(t)
}

// List(1, 2, 3, 4), List(2, 3) -> List(1, 4)
def sub[T](a :List[T], b :List[T]) :List[T] = (a, b) match {
    case (Nil, b) => Nil
    case (a, Nil) => a
    case (h1 :: t1, h2 :: t2) if h1 == h2 => sub(t1, t2)
    case (h1 :: t1, h2 :: t2) => h1 :: sub(t1, b)
}

// 1, 2, 3 -> 123
def number(it :Iterator[Int]) :Long =
    it.foldLeft(0L)((x, y) => x * 10 + y)

// 123 -> 1, 2, 3
def digits(n :Int) :Iterator[Int] =
    if(n == 0) Iterator() else digits(n / 10) ++ Iterator(n % 10)

def solutions(N :Int) :Iterator[Long] = {
    val M = N * 2
    val a = new Array[Int](M)
    
    def select_ext_numbers(ns :List[Int]) :Iterator[Long] =
        for(ext_ns <- ns.combinations(N) if ext_ns.sum % N == 0;
            s = (M + 1) * 2 - ext_ns.sum / N;
            ext_ns2 <- ext_ns.tail.permutations.map(ext_ns.head :: _);
            flag = ext_ns2.zipWithIndex.foldLeft(0)(set_flag);
            n <- select_int_top(sub(ns, ext_ns2), flag, s))
                yield n
    
    def select_int_top(int_ns :List[Int], flag0 :Int, s :Int) :Iterator[Long] =
        for(n <- int_ns.toIterator if (flag0 & (1 << n)) == 0;
            flag = set_flag(flag0, (n, N)) if is_satisfied(N + 1, flag, s))
                yield array_to_number(a)
    
    def is_satisfied(pos :Int, flag0 :Int, s :Int) :Boolean =
        if(pos == M)
            true
        else {
            val n = s - a(pos-N-1) - a(pos-1)
            (flag0 & (1 << n)) == 0 && 1 <= n && n < M &&
                is_satisfied(pos + 1, set_flag(flag0, (n, pos)), s)
        }
    
    def set_flag(f :Int, x :(Int,Int)) = {
        val (n, pos) = x
        a(pos) = n
        f | (1 << n)
    }
    
    def array_to_number(a :Array[Int]) :Long = {
        val it = for(k <- Iterator.range(0, N);
                     n <- Iterator(a(k), a(k+N), a((k+1)%N+N));
                     d <- digits(n))
                        yield d
        number(it)
    }
    
    select_ext_numbers(List.range(1, M + 1))
}

val N = 5
val L = 1e16.toLong
println (solutions(N).filter(L >).max)