お布団宇宙ねこ

にゃーん

HaskellでAOJの問題を解いた(ITP1_6)

AOJ の Introduction to Programming を解いたときのメモです。

前回: HaskellでAOJの問題を解いた(ITP1_5)

今回解いた問題

6_A Reversing Numbers

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_6_A

import Control.Applicative

main = do
    getLine
    xs <- map (read :: String -> Int) . words <$> getLine
    putStrLn $ unwords $ show <$> reverse xs

入力として受け取った数列を逆順に出力するだけだったので、 reverse 関数を使って簡単に解けました。 [5,4,3,2,1] のようなリストを "5 4 3 2 1" のように出力するのに各要素に show を適用してから unwords で連結すると上手くいきます。

6_B Finding Missing Cards

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_6_B

import Control.Applicative
import qualified Control.Monad as Monad

type Card = (String, Int)

main = do
    n <- read <$> getLine
    hc <- map (toCard . words) <$> Monad.replicateM n getLine
    mapM_ (putStrLn . fromCard) $ missingCards hc

toCard :: [String] -> Card
toCard [p,r] = (p, read r)

fromCard :: Card -> String
fromCard (p,r) = p ++ " " ++ (show r)

missingCards :: [Card] -> [Card]
missingCards hc = [ (p,r) | p <- ["S","H","C","D"], r <- [1..13], not $ (p,r) `elem` hc ]

すべての要素から入力として与えられた要素を除いた要素のみを出力すればよい、と考えると、リスト内包表記を使うことでスマートに書けました。カードを表現する型がタプルのままだと分かりづらいと思い type を使って別の名前を付けています。

6_C Official House

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_6_C

import Control.Applicative ((<$>))
import qualified Control.Monad as Monad (forM_)
import qualified Control.Monad.Trans as Trans (lift)
import qualified Control.Monad.State as State (execStateT, modify)
import qualified Data.List.Split as Split (chunksOf)

type Room = (Int, Int, Int, Int)

main = do
    n <- getLine
    rs <- putRooms (read n)
    let rs' = Split.chunksOf limitRoom $ zipWith (++) (repeat " ") (show . getValue <$> rs)
    Monad.forM_ [1..(limitBuilding*limitFloor)] $ \bf -> do
        putStrLn $ concat $ rs' !! (bf-1)
        if ((bf `mod` limitFloor == 0) && bf /= (limitBuilding*limitFloor))
            then putStrLn "####################"
            else return ()

putRooms :: Int -> IO [Room]
putRooms n = (`State.execStateT` officialHouse) $ do
    Monad.forM_ [1..n] $ \_ -> do
        room <- Trans.lift $ toRoom . map (read :: String -> Int) . words <$> getLine
        State.modify (`updateRoom` room)

limitBuilding = 4
limitFloor    = 3
limitRoom     = 10

officialHouse :: [Room]
officialHouse = [ (b,f,r,0) | b <- [1..limitBuilding],
                              f <- [1..limitFloor],
                              r <- [1..limitRoom] ]

toRoom :: [Int] -> Room
toRoom [b,f,r,v] = (b,f,r,v)

getValue :: Room -> Int
getValue (_, _, _, v) = v

updateRoom :: [Room] -> Room -> [Room]
updateRoom [] _ = []
updateRoom (room1@(b1,f1,r1,v1):rs) room2@(b2,f2,r2,v2)
    | (b1,f1,r1) == (b2,f2,r2) = (b1,f1,r1,(v1 + v2)) : rs
    | otherwise                = room1 : updateRoom rs room2

officialHouse ですべての部屋の情報を作成し、入力として入居・退去の情報を受け取る度に State モナドを使って部屋情報を更新するようにしています。 putRooms 関数では State モナドと IO モナドを同時に扱う必要があったのでモナド変換子を使っています。 State モナドを使わなくても解けた気がしますが、勉強のために今回は使った感じです。

それとこの問題から、モジュールは使う関数のみをインポートするようにしました。

6_D Matrix Vector Multiplication

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_6_D

import Control.Applicative ((<$>))
import qualified Control.Monad as Monad (forM, replicateM)

type Vector = [Int]
type Row = [Int]
type Matrix = [Row]

main = do
    [n,m] <- getLine'
    a <- Monad.replicateM n getLine'
    b <- toVector <$> Monad.replicateM m getLine'
    mapM_ print $ vectorAndMatrixProduct a b

getLine' :: IO [Int]
getLine' = map (read :: String -> Int) . words <$> getLine

toVector :: [[Int]] -> Vector
toVector = concat

vectorAndMatrixProduct :: Matrix -> Vector -> Vector
vectorAndMatrixProduct xs ys = toVector $ do
    Monad.forM [0..(length xs - 1)] $ \i -> dotProduct (xs !! i) ys

dotProduct :: Row -> Vector -> Row
dotProduct xs ys = return $ sum $ zipWith (*) xs ys

行列( Matrix )は二重のリストとして、ベクトル( Vector )はリストとして表現しました。ベクトルと行列の積は、 forM を使って行列の二重リストから行番号ごとにリストを取得し、ベクトルのリストと sum $ zipWith (*) で計算するようにしています。

この問題の応用である 7_D Matrix Multiplication では、行列の転置を使うことでもう少しスマートに書くことができました。

参考文献

github.com