ScalaでProject Euler（64）

Problem 35

長さ1からはじめて、N/2までのパターンを列挙します。

1 : [ 0 ]

次に長さ2ですが、0に長さ2をあてはめます。[ 0, 0 ]は特別として、0が続いてそこから0以外が続く、というのは[ 0, 1 ]のみです。[ 0, 2 ]のような抜けがあるというのは無しです。

2 : [ 0, 0 ], [ 0, 1 ]

3も同じで、

3 : [ 0, 0, 0 ], [ 0, 0, 1 ], [ 0, 1, 1 ], [ 0, 1, 2 ], [ 0, 2, 1 ]

4もまずは1に長さ4をあてはめるパターンがあって、[ 0, 0, 0, 0 ], ... , [ 0, 3, 2, 1 ]です。それと長さ2に2つずつあてはめる方法もあります。[ 0, 0 ]は[ 0, 1, 0, 1 ]しかありません。[ 0, 1 ]も[ 0, 1, 0, 2 ]のみです。

4 : [ 0, 0, 0, 0 ], ... , [ 0, 3, 2, 1 ], [ 0, 1, 0, 1 ], [ 0, 1, 0, 2 ]

前回の手順で縮約してみるとわかりやすいかもしれません。
このように、再帰的に各長さのパターンが全て求められます。
これに分配した長さを、今度は[ 0, 1, 2, ... ]ではなく[ 1, 3, 7, 9 ]であてはめます。

次のコードはひどいので見ないでください。相当苦労しています。N = 6までは確認しました。

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

def number(a :List[Int]) = a.foldLeft(0)(_ * 10 + _)
def pow(n :Int, e :Int) = Iterator.range(0, e).foldLeft(1)((x, y) => x * n)

// aより大きい長さlen以下のリストを生成する
def gen_greater(a :List[Int], ds :List[Int], len :Int) = {
    // eq : aとここまで等しいか first : 最小の数字が続いているか
    def gen(b :List[Int], res :Int, eq :Boolean, first :Boolean)
                                            :Iterator[List[Int]] = {
        val ds2 = (if(b == Nil)
                        if(first) ds else ds.tail
                   else if(eq)
                        ds.filter(b.head <=)
                   else
                        ds.tail).toIterator
        val it = (b, res, first) match {
            case (_, 0, _) => Iterator()
            case (Nil, _, _) =>
                    for(d <- ds2; c <- gen(Nil, res - 1, false, d == ds.head))
                        yield d :: c
            case (h :: t, _, _) =>
                    for(d <- ds2; c <- gen(t, res - 1,
                                        eq && d == h, d == ds.head))
                        yield d :: c
        }
        if(eq || first) it else Iterator(Nil) ++ it
    }
    
    val tail = if(a == Nil) Nil else a.tail
    gen(tail, len - 1, a != Nil, true).map(ds.head :: _)
}

def is_less_jump(a :List[Int]) = {
    val b = a.foldLeft(0)((x, y) => x | (1 << y))
    (b & (b + 1)) == 0
}

def count_freq(a :List[Int]) = {
    val b = new Array[Int](a.max + 1)
    for(i <- a)
        b(i) += 1
    b.toList
}

def repeat(d :Int, n :Int) =
    Iterator.range(0, n).foldLeft(Nil :List[Int])((x, y) => d :: x)

def divide(freq :List[Int], n :Int) :Iterator[List[Int]] = freq match {
    case Nil => Iterator()
    case h :: Nil if n % h == 0 && n / h >= 2 => Iterator(List(n / h))
    case h :: Nil => Iterator()
    case h :: t => for(m <- Iterator.range(2, n / h + 1);
                        a <- divide(t, n - h * m))
                            yield m :: a
}

//def extend(a :List[Int], len :Int) :Iterator[List[Int]] = {
//  val freq = count_freq(a)
//  val ds = List.range(0, len - a.size + 1)
//  for(ns <- divide(freq, len);
//      bs <- extend_core(Nil, ds, ns))
//      yield bs.map(b => a.foldLeft(List[Int]())(_ ++ b(_))).filter(is_less_jump)
//}
def extend(a :List[Int], len :Int) :Iterator[List[Int]] = {
    val freq = count_freq(a)
    val ds = List.range(0, len - a.size + 1)
    val bs = extend_core(Nil, ds, a.max + 1, len)
    bs.map(b => a.foldLeft(List[Int]())(_ ++ b(_))).filter(is_less_jump)
}

def extend_core(b :List[Int], ds :List[Int], n :Int,
                            res_len :Int) :Iterator[List[List[Int]]] =
    if(n == 1)
        gen_greater(b, ds, res_len).map(x => List(x))
    else
        for(m <- Iterator.range(2, res_len - 2 * n + 3);
            c <- gen_greater(b, ds, m);
            cs <- extend_core(c, ds, n - 1, res_len - m))
                yield c :: cs

// 最後用
def extend2(a :List[Int], ds :List[Int], ns :List[Int]) :Iterator[List[Int]] = {
    val freq = count_freq(a)
    val bs = extend_core2(Nil, ds, ns)
    bs.map(b => a.foldLeft(List[Int]())(_ ++ b(_)))
}

def extend_core2(b :List[Int], ds :List[Int], ns :List[Int])
                                :Iterator[List[List[Int]]] = ns match {
    case Nil => Iterator(Nil)
    case (n :: t) =>
        for(c <- gen_greater(b, ds, n).filter(c => c.size == n);
            cs <- extend_core2(c, ds, t))
                yield c :: cs
}

def gen_min_rotate(N :Int) :Iterator[Int] = {
    val M = N / 2
    val a = new Array[List[List[Int]]](M + 1)
    a(1) = List(List(0))
    for(i <- Iterator.range(2, M + 1)) {
        a(i) = Iterator.range(1, i / 2 + 1).
                    map(k => a(k).map(b => extend(b, i))).
                    reduceLeft(_ ++ _).reduceLeft(_ ++ _).toList
        a(i) = a(i) ++ List(repeat(0, i))
        a(i) = a(i).filter(x => x.size == i)
    }
    
    val it = for(d <- Iterator(1, 3, 7, 9); n <- Iterator.range(2, N + 1))
                yield (pow(10, n) - 1) / 9 * d
    
    for(n <- Iterator.range(2, N + 1);
                    ds <- List(1, 3, 7, 9).tails.take(4);
                    i <- Iterator.range(1, n / 2 + 1);
                    b <- a(i);
                    freq = count_freq(b);
                    ns <- divide(freq, n);
                    c <- extend2(b, ds, ns))
            println (number(c), n, ds, i, b, freq, ns)
    
    val it2 = for(n <- Iterator.range(2, N + 1);
                    ds <- List(1, 3, 7, 9).tails.take(4);
                    i <- Iterator.range(1, n / 2 + 1);
                    b <- a(i);
                    freq = count_freq(b);
                    ns <- divide(freq, n);
                    c <- extend2(b, ds, ns))
            yield number(c)
    
    it ++ it2
}

def is_min_rotate(a :List[Int]) = {
    val front = number(a)
    val it = Iterator.iterate(a)(rotate).slice(1, a.size).map(number)
    it.forall(front <=)
}
def rotate(a :List[Int]) = a.tail ++ List(a.head)

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

val N = 6
val a = gen_min_rotate(N)
println (a.sum)