ScalaでProject Euler（117）

Problem 79

3桁のキーの前後の数字を関係付けます。例えば319なら、3 → 1、1 → 9という辺をグラフに加えます。そうしたときに、グラフの辺の始点側になっていない点が一つあります。これが元の数の最も右の数字です。そして、この数字を終点とする辺をすべて取り除きます。この処理を繰り返し行うと元の数が出てきます。

import scala.collection.mutable.Map
import scala.collection.mutable.Set

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

def make_graph(a :List[List[Int]]) = {
    val m = Map[Int,Set[Int]]()
    for(ds <- a; (d2, d1) <- ds.zip(ds.tail))
        if(m.contains(d1))
            m(d1).add(d2)
        else
            m(d1) = Set(d2)
    m
}

def next_digit(x :(Int,Map[Int,Set[Int]],Set[Int])) = {
    val (_, g, ds) = x
    if(ds.isEmpty)
        (-1, g, ds)
    else {
        val d_right = ds.filter(d => !g.contains(d)).head
        for(y <- g.toList) {
            val (d, v) = y
            if(v.contains(d_right)) {
                v -= d_right
                if(v.isEmpty)
                    g -= d
            }
        }
        ds -= d_right
        println (d_right)
        println (g)
        println (ds)
        (d_right, g, ds)
    }
}

val source = io.Source.fromFile("keylog.txt")
val a = source.getLines.map(s => digits(s.toInt)).toList
val ds = Set[Int]()
for(b <- a; n <- b) ds += n
println (ds)
val g = make_graph(a)
println (g)
val g_digits = (Iterator.iterate((0, g, ds))(next_digit).
                takeWhile(_._1 != -1).map(_._1).drop(1).toList)
println (g_digits.toList.reverse.reduceLeft((x, y) => x * 10 + y))