Euler problems/81 to 90

import Data.List (unfoldr)
 
columns s = 
    unfoldr f s
    where
    f [] = Nothing
    f xs = Just $ (\(a,b) -> (read a, drop 1 b)) $ break (==',') xs
 
firstLine ls = scanl1 (+) ls
 
nextLine pl [] = pl
nextLine pl (n:nl) = 
    nextLine p' nl
    where
    p' = nextCell (head pl) pl n
    nextCell _ [] [] = []
    nextCell pc (p:pl) (n:nl) = 
        pc' : nextCell pc' pl nl
        where pc' = n + min p pc
 
minSum (p:nl) = 
    last $ nextLine p' nl
    where
    p' = firstLine p
 
problem_81 c = minSum $ map columns $ lines c
main=do
    f<-readFile "matrix.txt"
    print$problem_81 f

import Data.List
import qualified Data.Map as M
import Data.Array
 
minPathSum xs t= 
    stepPath M.empty $ M.singleton t $ arr ! t
    where 
    len = genericLength $ head xs
    ys = concat $ transpose xs
    arr = listArray ((1, 1), (len, len)) ys
    nil = ((0,0),0)
    stepPath ds as 
        |fs2 p1==len =snd p1 
        |fs2 p2==len =snd p2 
        |fs2 p3==len =snd p3 
        |otherwise=stepPath ds' as3
        where
        fs2=fst.fst
        ((i, j), cost) = 
            minimumBy (\(_,a) (_,b) -> compare a b) $ M.assocs as
        tas = M.delete (i,j) as
        (p1, as1) = if i == len then (nil, tas) else check (i+1, j) tas
        (p2, as2) = if j == len then (nil, as1) else check (i, j+1) as1
        (p3, as3) = if j == 1   then (nil, as2) else check (i, j-1) as2
        check pos zs =
            if pos `M.member` tas || pos `M.member` ds 
            then (nil, zs)
            else (entry, uncurry M.insert entry $ zs)
            where
            entry = (pos, cost + arr ! pos)  
        ds' = M.insert (i, j) cost ds
 
main=do
    let parse = map (read . ("["++) . (++"]")) . words
    a<-readFile "matrix.txt"
    let s=parse a
    let m=minimum[p|a<-[1..80],let p=minPathSum s (1,a)]
    appendFile "p82.log"$show m
 
problem_82 = main

import Array (Array, listArray, bounds, inRange, assocs, (!))
import qualified Data.Map as M 
    (fromList, Map, foldWithKey, 
    lookup, null, delete, insert, empty, update)
import Data.List (unfoldr)
import Control.Monad.State (State, execState, get, put)
import Data.Maybe (fromJust, fromMaybe)
 
type Weight  = Integer
 
data Distance = D Weight | Infinity
    deriving (Show)
 
instance Eq Distance where
    (==) Infinity Infinity = True
    (==) (D a) (D b) = a == b
    (==) _ _ = False
 
instance Ord Distance where
    compare Infinity Infinity = EQ
    compare Infinity (D _) = GT
    compare (D _) Infinity = LT
    compare (D a) (D b) = compare a b
 
data (Eq n, Num w) => Arc n w = A {node :: n, weight :: w}
    deriving (Show)
 
type Index   = (Int, Int)
type NodeMap = M.Map Index Distance
type Matrix  = Array Index Weight
type Path    = Arc Index Weight
type PathMap  = M.Map Index [Path]
 
data Queues = Q {input :: NodeMap, output :: NodeMap, pathMap :: PathMap}
    deriving (Show)
 
listToMatrix :: [[Weight]] -> Matrix
listToMatrix xs = listArray ((1,1),(cols,rows)) $ concat $ xs
    where
        cols = length $ head xs
        rows = length xs
 
directions :: [Index]
directions = [(0,-1), (0,1), (-1,0), (1,0)]
 
add :: (Num a) => (a, a) -> (a, a) -> (a, a)
add (a,b) (a', b') = (a+a',b+b')
 
arcs :: Matrix -> Index -> [Path]
arcs a idx = do
    d <- directions
    let n = add idx d
    if (inRange (bounds a) n) then
        return $ A n (a ! n)
        else
            fail "out of bounds"
 
paths :: Matrix -> PathMap
paths a = M.fromList $ map (\(idx,_) -> (idx, arcs a idx)) $ assocs a
 
nodes :: Matrix -> NodeMap
nodes a = 
    M.fromList $ (\((i,_):xs) -> (i, D (a ! (1,1))):xs) $ 
    map (\(idx,_) -> (idx, Infinity)) $ assocs a
 
extractMin :: NodeMap -> (NodeMap, (Index, Distance))
extractMin m = (M.delete (fst minNode) m, minNode)
    where
        minNode = M.foldWithKey mini ((0,0), Infinity) m
        mini i' v' (i,v)
            | v' < v    = (i', v')
            | otherwise = (i,v)
 
dijkstra :: State Queues ()
dijkstra = do
    Q i o am <- get
    let (i', n) = extractMin i
    let o' = M.insert (fst n) (snd n) o
    let i'' = updateNodes n am i'
    put $ Q i'' o' am
    if M.null i'' then return () else dijkstra
 
updateNodes :: (Index, Distance) -> PathMap -> NodeMap -> NodeMap
updateNodes (i, D d) am nm = foldr f nm ds
    where
        ds = fromJust $ M.lookup i am
        f :: Path -> NodeMap -> NodeMap
        f (A i' w) m = fromMaybe m val
            where
                val = do
                    v <- M.lookup i' m
                    if (D $ d+w) < v then
                        return $ M.update (const $ Just $ D (d+w)) i' m
                        else return m
 
shortestPaths :: Matrix -> NodeMap
shortestPaths xs = output $ dijkstra `execState` (Q n M.empty a)
    where
        n = nodes xs
        a = paths xs
 
problem_83 :: [[Weight]] -> Weight
problem_83 xs = jd $ M.lookup idx $ shortestPaths matrix
    where
        matrix = listToMatrix xs
        idx = snd $ bounds matrix
        jd (Just (D d)) = d
main=do
    f<-readFile "matrix.txt"
    let m=map sToInt $lines f
    print $problem_83 m
split :: Char -> String -> [String]
split = unfoldr . split'
 
split' :: Char -> String -> Maybe (String, String)
split' c l
    | null l = Nothing
    | otherwise = Just (h, drop 1 t)
    where (h, t) = span (/=c) l
sToInt x=map ((+0).read) $split ',' x

problem_84 = undefined

import List
problem_85 = snd$head$sort 
    [(k,a*b)|
    a<-[1..100],
    b<-[1..100],
    let k=abs (a*(a+1)*(b+1)*b-8000000)
    ]

problem_86 = undefined

import List
merge xs@(x:xt) ys@(y:yt) = case compare x y of
    LT -> x : (merge xt ys)
    EQ -> x : (merge xt yt)
    GT -> y : (merge xs yt)
 
diff  xs@(x:xt) ys@(y:yt) = case compare x y of
    LT -> x : (diff xt ys)
    EQ -> diff xt yt
    GT -> diff xs yt
 
primes, nonprimes :: [Int]
primes    = [2,3,5] ++ (diff [7,9..] nonprimes) 
nonprimes = foldr1 f . map g $ tail primes
    where f (x:xt) ys = x : (merge xt ys)
          g p = [ n*p | n <- [p,p+2..]]
groups=1000000
problem_87 50 total=total 
problem_87 n total= 
    problem_87 (n+1) (total+length expressible)
    where 
    limit =groups+n*groups
    max   =n*groups 
    squares = takeWhile (<limit) (map (^2) primes)
    cubes   = takeWhile (<limit) (map (^3) primes)
    fourths = takeWhile (<limit) (map (^4) primes)
    choices = [sm| 
        s <- squares, 
        c <- cubes, 
        f <- fourths,
        let sm=s+c+f,
        sm>max,
        sm<=limit
        ]
    unique  = map head . group . sort
    expressible = unique  choices
main=appendFile "p87.log"$show$problem_87 0 0

problem_88 = undefined

replace ([], _) zs = zs
replace _ [] = []
replace (xs, ys) zzs@(z:zs)
    | xs == lns = ys ++ rns
    | otherwise = z : replace (xs, ys) zs
    where
    (lns, rns) = splitAt (length xs) zzs
 
problem_89 = 
    print . difference . words =<< readFile "roman.txt"
    where
    difference xs = sum (map length xs) - sum (map (length . reduce) xs)
    reduce xs = foldl (flip replace) xs [("DCCCC","CM"), ("CCCC","CD"), 
                                         ("LXXXX","XC"), ("XXXX","XL"), 
                                         ("VIIII","IX"), ("IIII","IV")]

problem_90 = undefined