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''がきにくわないが、よしとしよう。

Problem 104

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

単純な解法

import Data.List
fib = 0:1:zipWith (+) fib (tail fib)
fibMod = map (flip mod (10^9))$0:1:zipWith (+) fibMod (tail fibMod)
main = print.findIndex pandigit.zip fibMod $fib
    where pandigit (x,y) = "123456789"==(sort.show) x 
                           && "123456789"== (sort.take 9.show) y

あまり速くないが、他の方法を思いつかない。

Problem 105

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

ちょっと考えたら、シンプルな解法に気がついた。

import Data.List
monotone xs = all (f.sort$xs) [1..length xs `div` 2]
    where f ys n = (sum.take (n+1)) ys > (sum.take n.reverse) ys

subsetSumNeq xs = all (f xs) [1..length xs `div` 2]
    where f ys n = all (null.tail).group.sort.map sum. comb ys $ n

specialSum xs = monotone xs &&  subsetSumNeq xs

main = do f <- readFile "sets.txt"
          let sets = map (read.("["++).(++"]")).lines $ f
          print.sum.map sum.filter specialSum $ sets

comb _ 0 = [[]]
comb [] _ = []
comb (x:xs) (n+1) = map (x:) (comb xs n) ++ comb xs (n+1)

Problem 106

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

とりあえず問題文を理解するのにすごい時間がかかった。
なんで、n=4で25になるのか分からなかった。
とりあえず原因は
問題文がどこまでリストの要素が昇順である仮定をつかっているのか
明記してなかった点にあると思う。
（と、問題文のせいにしてみる。）

import Data.List

needTest (x,y) = (or $ zipWith (>) x y)&&(or $ zipWith (<) x y)
divid (x:xs) = [(x:ys,xs\\ys)|ys<-comb xs (length xs `div` 2)]

tests m = [filter needTest$divid xs|n<-[4,6..m`div`2*2],xs<-comb [1..m] n]

main = print.sum.map length.tests$12

comb _ 0 = [[]]
comb [] _ = []
comb (x:xs) (n+1) = map (x:) (comb xs n) ++ comb xs (n+1)

考えたアルゴリズム
偶数個の要素をとってくる
二分割をいろいろ考える
testが必要なものだけ取り出す
以上

効率は悪い。しかし、高々１２。tractableです。