Project Euler 81,82,83

http://projecteuler.net/index.php?section=problems&id=81
http://projecteuler.net/index.php?section=problems&id=82
http://projecteuler.net/index.php?section=problems&id=83


3題とも同じアルゴリズムで計算できる。違うのは初期のマスと最小を取るマス。Problem 82は初期は左1列で、右1列の最小を取る。

import Data.Map (fromList, lookup, insert, (!))
import Data.List (sortBy)

split [] = [[]]
split (c:cs) | c == ','  = []:(split cs)
             | otherwise = (c:s):ss where s:ss = split cs
matrix :: [Char] -> [[Int]]
matrix s = map (map read) (map split (lines s))

dirs = [ (1, 0), (0, 1), (0, -1), (-1, 0) ]

solve mat k = if k /= 82 then m!(n,n)
                   else foldl1 min [ m!(n,y) | y <- [1..n] ] where
        (m, ps) = update (fromList (init k)) (init k)
        a = fromList (zip [(x,y) | y <- [1..n], x <- [1..n] ] (concat mat))
        n = length mat
        dir = take (k - 79) dirs
        init k = if k /= 82 then [((1,1),a!(1,1))]
                 else sortBy (\a b -> compare (snd a) (snd b))
                            [ ((1,y),a!(1,y)) | y <- [1..n] ]
        update m [] = (m,[])
        update m (p:ps) = update m1 ps1 where
                (m1, ps1) = f m (map (step (fst p)) dir) ps (m!(fst p))
        f m [] ps v0 = (m, ps)
        f m (pt:pts) ps v0 | is_OB pt  = f m pts ps v0
                           | otherwise = case Data.Map.lookup pt m of
                    Just v1 -> f m pts ps v0
                    Nothing -> f (insert pt v m) pts (ins [] ps (pt,v)) v0
                                            where v = v0 + (a!pt)
        ins q1 [] (pt,v) = q1 ++ [(pt,v)]
        ins q1 (q:q2) (pt,v) | v < snd q = q1 ++ ((pt,v):q:q2)
                             | otherwise = ins (q1 ++ [q]) q2 (pt,v)
        step (x,y) (dx,dy) = (x + dx, y + dy)
        is_OB (x,y) = x < 1 || n < x || y < 1 || n < y

main = do
    cs <- readFile "matrix.txt"
    print (map (solve (matrix cs)) [81..83])