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((/=).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”がきにくわないが、よしとしよう。