ScalaでProject Euler（94）

Problem 61

これはグラフにすると比較的考えやすいです。例にあるように8128は三角数ですが、81という点と28という点が線で結ばれていて重みが3と考えます。ネットワークですね。4桁の3〜8角数を全て求めてネットワークを作ります。

そうしたときに、ある点から2の重み乗をビットごとのORを取りながらネットワークを辿って行きます。重複無しに3〜8の全てのフラグが立った0X1F8になって、しかも元の点に戻っていたらそれが解です。

import scala.collection.mutable.Map

type Net = Map[Int,List[(Int,Int)]]

def add_edge(g :Net, v1 :Int, v2 :Int, w :Int) =
    if(g.contains(v1))
        g(v1) = (v2, w) :: g(v1)
    else
        g(v1) = List((v2, w))

def polygonal(p :Int)(n :Int) =
    n * ((p - 2) * n - p + 4) / 2

def make_graph() = {
    val g = Map[Int,List[(Int,Int)]]()
    for(p <- 3 to 8;
        f = polygonal(p :Int)_;
        n <- Iterator.from(1).map(f).dropWhile(1000 >).takeWhile(10000 >);
        upper = n / 100;
        lower = n % 100)
            add_edge(g, upper, lower, p)
    g
}

def find_loop(g :Net, v0 :Int) :List[Int] = {
    def step(v :Int, flag :Int) :List[List[Int]] =
        if(flag == 0x1F8)
            if(v == v0) List(Nil) else Nil
        else if(!g.contains(v))
            Nil
        else
            for((n, p) <- g(v)
                if (flag & (1 << p)) == 0;
                vs <- step(n, flag | (1 << p)))
                    yield n :: vs
    
    step(v0, 0).map(vs => vs.sum * 101)
}

val g = make_graph()
println (g.keys.flatMap(v0 => find_loop(g, v0)))