ScalaでProject Euler（96）

アップミスで順番が逆になってしまいました。

Problem 62

3乗して同じ桁になる数を用意して並び替えると同じになる数ごとに分類します。同じ数は、降順にでも並び替えればいいですね。8なら3乗して512を並び替えて521です。並び替えて同じになる数が5つあれば解です。

この分類という処理は非常によく使うので、ジェネリクスで書いてみました。

def map_cons[K,V](m :Map[K,List[V]], key :K, value :V) =
    if(m.contains(key))
        m(key) = value :: m(key)
    else
        m(key) = List(value)

def classify[K,V](a :Traversable[V], f :V => K) :Map[K,List[V]] = {
    val m = Map[K,List[V]]()
    for(v <- a)
        map_cons(m, f(v), v)
    m
}

Listなどと関数を入力すると分類したMapを返します。例えば、書名のリストと書名からジャンルを返す関数を入力すると、ジャンル→書名のリストというMapを返します。
上のmap_consという関数はもっとよく使う関数です。C++のSTLならこんな関数は必要ないです。

m[key].push_back(value)

import scala.collection.mutable.Map
import scala.math.pow

def map_cons[K,V](m :Map[K,List[V]], key :K, value :V) =
    if(m.contains(key))
        m(key) = value :: m(key)
    else
        m(key) = List(value)

def classify[K,V](a :Traversable[V], f :V => K) :Map[K,List[V]] = {
    val m = Map[K,List[V]]()
    for(v <- a)
        map_cons(m, f(v), v)
    m
}

// 3124 -> [ 4, 2, 1, 3 ]
def digits(n :Long) :List[Int] =
    if(n == 0) Nil else (n % 10).toInt :: digits(n / 10)

// [ 4, 2, 1, 3 ] -> 4213
def number(a :List[Int]) :Long =
    a.foldLeft(0L)((x, y) => x * 10 + y)

// 3124 -> 1234
def ascending_number(n :Long) :Long =
    number(digits(n).sorted)

def cube_ranges() :Iterator[(Int,Int)] = {
    // (1, 3, 10) -> (3, 5, 100)
    def next(x :(Int,Int,Long)) :(Int,Int,Long) = {
        val (b, e, n) = x
        val new_n = n * 10
        val new_e = (pow(new_n.toDouble, 1 / 3.) - 0.5).toInt + 1
        (e, new_e, new_n)
    }
    
    Iterator.iterate((1, 3, 10L))(next).map(x => (x._1, x._2))
}

def solutions(r :(Int,Int)) :List[Long] = {
    val (b, e) = r
    val m = classify((b to e - 1).map(n => n.toLong * n * n), ascending_number)
    for((key, nums) <- m.toList if nums.size == N)
        yield nums.min
}

val N = 5
println (cube_ranges().map(solutions).filter(Nil !=).next.min)