HaskellでAOJの問題を解いた(ITP1_8)
AOJ の Introduction to Programming を解いたときのメモです。
前回: HaskellでAOJの問題を解いた(ITP1_7)
今回解いた問題
8_A Toggling Cases
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_8_A
import qualified Data.Char as Char (isUpper, isLower, toUpper, toLower) main = putStrLn . toggleCases =<< getLine toggleCases :: String -> String toggleCases [] = [] toggleCases (x:xs) | Char.isLower x = Char.toUpper x : toggleCases xs | Char.isUpper x = Char.toLower x : toggleCases xs | otherwise = x : toggleCases xs
与えられた文字列の小文字と大文字を入れ替えるだけの問題です。
文字判定と変換はすべて Data.Char
モジュールがやってくれます。今回入力を別の型に変換する必要がなかったので =<<
を使って toggleCases
関数に渡すようにしました。 main がワンライナーで書けるとスマートに解けた気がして嬉しいですね。
8_B Sum of Numbers
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_8_B
import Control.Applicative ((<$>)) import qualified Control.Monad as Monad (when) import qualified Data.Char as Char (digitToInt) main = do s <- getLine Monad.when (read s /= 0) $ do print $ sum $ Char.digitToInt <$> s main
与えられた数の各桁の和を計算する問題です(H本でも見たことある気がする)。
入力された文字列のすべての文字に digitToInt で Int 型に変換してそれを sum で集計するだけです(特に難しいことはなかった...)。
8_C Counting Characters
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_8_C
import Control.Applicative ((<$>)) import qualified Control.Monad as Monad (forM_) import qualified Data.Char as Char (toLower) import qualified Data.List as List (sort, group) import qualified Data.Map as Map (Map, fromList, lookup) type AlphabetCountMap = Map.Map Char Int main = do s <- getContents let acl = alphabetCounts $ groupAlphabet s Monad.forM_ ['a'..'z'] $ \c -> do putStrLn $ case Map.lookup c acl of Nothing -> c : " : 0" Just n -> c : " : " ++ show n groupAlphabet :: String -> [String] groupAlphabet s = List.group . List.sort $ filter (\x -> x `elem` ['a'..'z']) $ Char.toLower <$> s alphabetCounts :: [String] -> AlphabetCountMap alphabetCounts cs = Map.fromList $ [(head c, length c) | c <- cs]
与えられた文字列に含まれる各アルファベットの数をカウントして出力する問題です。
やりたいことは単純そうなのですが実装をどうしようか結構悩んで、愚直にやるなら文字列を一から走査して各アルファベットの数を State モナドで保持しておく...みたいなことを考えましたが、やりたいことの割に複雑な処理になりそうだったので止めました(主にモナド変換子あたり)。
最終的に次のような実装に落ち着きました。
- 入力された文字列を、同じ文字同士が隣り合うように並べ替えて、グルーピングする
- 1 のリストを、アルファベットとその数のタプルでリスト化する
- 2 のリストを走査して各アルファベットの数を出力する
アルファベットの数を保持するのに今回は Data.Map
を組み込んでみました。今までは型シノニムを定義するだけで特に走査関数を用意するようなことをしてなかったのですが、 Data.Map の lookup
関数便利ですね。速度のことは特に考えてないです。
8_D Ring
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_8_D
import qualified Data.List as List (elemIndices) main = do s <- getLine p <- getLine putStrLn $ if elemFromRing (List.elemIndices (head p) s) s p then "Yes" else "No" elemFromRing :: [Int] -> String -> String -> Bool elemFromRing [] _ _ = False elemFromRing (x:xs) s p | pickFromRing [x..(x + length p - 1)] s == p = True | otherwise = elemFromRing xs s p pickFromRing :: [Int] -> String -> String pickFromRing [] _ = [] pickFromRing (n:ns) xs = xs !! (n `mod` length xs) : pickFromRing ns xs
リング状の文字列(以下 S )を受け取って、そこから任意の文字列(以下 P )が作れるかどうかを判定する問題です。 P が、時計回りに連続した文字を取ってきて作れるかどうかというところが肝なので解き方を考えるのに結構苦労しました。
解き方は次のような流れでやりました。
- P の先頭が、 S のどの位置に現れるのかを調べる
- 1で調べた位置をもとに、そこから P が作れるか調べる
- 作れたならそこで終わり、そうでなければ次の位置に進む
(流れだけ書いてみると意外と単純だった...?)
ポイントとしては、「リング状」の文字列から探すというのをどう実現するかというところ。今回は pickFromRing
関数で、P の先頭が出現する位置から P の長さをリストで引数として与えていますが ( [x..(x + length p - 1)]
の部分)、このリストの各要素(位置)をもとに S から文字を取ってくるときに、各要素に対して n `mod` ( S の長さ)
で余数を計算してその数で文字を取り出すようにしています。こうすることで下の例のように、 S の長さを超えた位置でも、余数を使うことで位置を折り返して取得することができます。
*Main> let s="vanceknowledgetoad" *Main> length s 18 *Main> pickFromRing [16..22] s "advance"
まとめ
Haskell で AOJ を解くのもだいぶ慣れてきて少しは Haskell と仲良くなれた感じがしてきたので、そろそろ次のステップに進もうと思います。具体的には JSON Web API でも作ってみようかなあと。なので AOJ 編はこの辺りで一旦終わりにします。それでは。