Problem 107

http://projecteuler.net/index.php?section=problems&id=107

どうみても最小木問題です。本当に(ry

というわけで、今回はライブラリを使ってみた。
なんと、最小木を求める関数があるという充実ぶり。

import Data.List
import Data.Array
import Data.Graph.Inductive

mkEdge' xs = map triple.filter((0/=).snd).assocs.listArray ((1,1),(m,n)).concat$xs
    where m = length.head$xs
          n = length xs
          triple (x,y) = (fst x, snd x ,y)

mkNetwork :: [[Int]]->Gr () Int
mkNetwork =mkGraph (zip [1..40] (repeat ())).mkEdge'

getNet :: IO [[Int]]
getNet = do f <- readFile "network.txt"
            return.map (read.("["++).(++"]").map g).lines $ f
    where g x | x == '-' = '0'
              | x /= '-' =  x

getNodes'' (LP xs) = [x|x<-xs]

main = do net <-getNet
          let mst = msTree.mkNetwork$net
              m = sum.map snd.nub.concat.map getNodes''$mst
              n = sum.concat$net
          print $ div n 2 - m

とりあえず、このGraph.Inductiveの使い方を理解するのに時間がかかった。
帰納的にグラフを定義するというのはプログラミングでは新鮮。
関数型言語は帰納的定義が多いから、まぁ普通なのか？

getNode''がきにくわないが、よしとしよう。