ScalaでProject Euler（111）

Scala

Problem 74

大きさ100000の0に初期化した配列を用意します。
例えば、69を考えます。このインデックスの配列の要素を-1とします。69の次は363600です。ここは-2とします。次の1454は-3とします。このように進んでいくと、1454がやってきます。ここは0でなく負になっているのでループを1周したということがわかります。ここは、-6をつけるのではなく前の-3との差3に付け直します。そして帰ります。このときにループであることを長さととも返します。帰りに要素が正ならループが一回りしたことになりそのあとはループでない部分ということになるので、そこの長さは手前の長さより1長いということになります。

 -1 ->   -2   ->  -3  ->  -4 ->   -5   ->  -6
 69 -> 363600 -> 1454 -> 169 -> 363601 -> 1454
0,5 <-  0,4   <- 1,3  <- 1,3 <-  1,3   <-  
val N = 1e6.toInt

object Chain {
    private val a = new Array[Int](N)
    private val factorials = List.iterate((1, 0), 10)(
                        x => (x._1 * (x._2 + 1), x._2 + 1)).map(_._1)
    
    private def digits(n :Int) :List[Int] =
        if(n == 0) Nil else n % 10 :: digits(n / 10)
    
    def length(n :Int) :Int = {
        def next(n :Int, p :Int = 0) :Int =
            digits(n).foldLeft(0)((x, y) => x + factorials(y))
        
        def f(n :Int, p :Int) :(Int,Int) = {
            if(n < N) {
                if(a(n) == 0) {
                    val m = next(n)
                    a(n) = -p
                    val (prev_s, prev_len) = f(m, p + 1)
                    val s = if(a(n) > 0) 0 else prev_s
                    val len = if(prev_s == 0) prev_len + 1 else prev_len
                    a(n) = len
                    (s, len)
                }
                else if(a(n) < 0) {     // visited
                    a(n) = a(n) + p     // length of loop
                    (1, a(n))
                }
                else
                    (0, a(n))
            }
            else {
                val m = next(n)
                val (s, prev_len) = f(m, p + 1)
                val len = if(s == 0) prev_len + 1 else prev_len
                (s, len)
            }
        }
        
        f(n, 1)._2
    }
}

val M = 60
println (Iterator.range(1, N).count(n => Chain.length(n) == M))