HaskellでAOJの問題を解いた(ITP1_7)
AOJ の Introduction to Programming を解いたときのメモです。
前回: HaskellでAOJの問題を解いた(ITP1_6)
今回解いた問題
7_A Grading
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_7_A
import Control.Applicative ((<$>)) import qualified Control.Monad as Monad (when) main = loopGrading loopGrading :: IO () loopGrading = do result <- map (read :: String -> Int) . words <$> getLine Monad.when (any (/= (-1)) result) $ do putStrLn $ grading result loopGrading grading :: [Int] -> String grading [m,f,r] | m == (-1) || f == (-1) = "F" | total >= 80 = "A" | total >= 65 = "B" | total >= 50 || r >= 50 = "C" | total >= 30 = "D" | otherwise = "F" where total = m + f
試験の点数によってAやBなどの成績をつけるありふれた問題です。ガードと where 節を使うと綺麗に書ける気がします。
7_B How many ways?
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_7_B
import Control.Applicative ((<$>)) import qualified Control.Monad as Monad (when) main = do nx <- getLine' $ map read . words Monad.when (any (/= 0) nx) $ do print $ length $ combination nx main getLine' :: (String -> a) -> IO a getLine' f = f <$> getLine combination :: [Int] -> [[Int]] combination [n,x] = [[a,b,c] | a <- [1..n], b <- [a..n], c <- [b..n], a + b + c == x, a /= b, a/= c, b /= c]
組み合わせの問題もリスト内包表記で表現することができます。重複無しにするためには b と c の始めの要素を1つ前の変数の要素から始めることと、それぞれの変数の要素が一致しないように述語を入れることで実現できます。
また今回は getLine で入力を受け取る部分を String -> a
の関数を受け取る関数にしてみました。こう書くことで型推論によって (read :: String -> Int)
みたいなことをいちいち書かなくても済む...ような気がします(型推論がどこまで面倒を見てくれるのかよくわかっていない)。
7_C Spreadsheet
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_7_C
import Control.Applicative ((<$>)) import qualified Control.Monad as Monad (forM, replicateM) type Row = [Int] type Spreadsheet = [Row] main = do [r,c] <- getLine' xs <- Monad.replicateM r $ getLine' mapM_ (putStrLn . printFormat) =<< newSpreadsheet (c+1) xs getLine' :: IO [Int] getLine' = map read . words <$> getLine printFormat :: Row -> String printFormat xs = unwords $ show <$> xs newSpreadsheet :: Int -> Spreadsheet -> IO Spreadsheet newSpreadsheet n xs = do let xs' = zipWith (++) xs $ rowSums xs return $ xs' ++ columnSums n xs' rowSums :: Spreadsheet -> Spreadsheet rowSums = map $ (:[]) . sum columnSums :: (Monad m) =>Int -> Spreadsheet -> m Row columnSums n xs = Monad.forM [0..(n-1)] $ \i -> return $ sum $ map (!! i) xs
入力として与えられるエクセル表のような数列に、各行の最後の列としてその行の合計値を、各行の最後の行としてその列の合計値を追加した表を出力するという問題でした。
rowSums で各行の行の合計値を計算した後に columnSums で各列の列の合計値を計算するようにしています。本当はモナド必要ないのに繰り返しを forM を使って計算させるの違和感しかないので、何か別の良い方法ないですかね...。畳み込みは今回だと与えられたリストに対して処理を行うわけではないため適切ではないと思い使いませんでした。
7_D Matrix Multiplication
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_7_D
import Control.Applicative ((<$>), (<*>)) import qualified Control.Monad as Monad (replicateM) import qualified Data.List as List (transpose) import qualified Data.List.Split as Split (chunksOf) type Row = [Int] type Matrix = [Row] main = do [n,m,l] <- getLine' a <- Monad.replicateM n getLine' b <- Monad.replicateM m getLine' let result = toMatrix l $ dotProduct <$> a <*> List.transpose b mapM_ (putStrLn . printFormat) result getLine' :: IO [Int] getLine' = map (read :: String -> Int) . words <$> getLine printFormat :: Row -> String printFormat xs = unwords $ show <$> xs toMatrix :: Int -> [Int] -> Matrix toMatrix n xs = Split.chunksOf n xs dotProduct :: Row -> Row -> Int dotProduct xs ys = sum $ zipWith (*) xs ys
6_D Matrix Vector Multiplication では行列と列ベクトルの積を計算する問題でしたが、今回は行列同士の積を計算する問題です。行列Aと行列Bの積は、行列Aの行と、行列Bの転置行列の列の内積で計算することができます。行列の転置には transpose という便利な関数が Data.List モジュールにあるためそれを使いました。
どうして転置行列を使うことで行列の積が計算できるのかは別途証明する必要がありそうです...。(その辺りの文献が見当たらなかったので)