HaskellでAOJの問題を解いた(ITP1_6)
AOJ の Introduction to Programming を解いたときのメモです。
前回: HaskellでAOJの問題を解いた(ITP1_5)
今回解いた問題
- ITP1_6
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 では、行列の転置を使うことでもう少しスマートに書くことができました。