お布団宇宙ねこ

にゃーん

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. 1 のリストを、アルファベットとその数のタプルでリスト化する
  3. 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 が、時計回りに連続した文字を取ってきて作れるかどうかというところが肝なので解き方を考えるのに結構苦労しました。

解き方は次のような流れでやりました。

  1. P の先頭が、 S のどの位置に現れるのかを調べる
  2. 1で調べた位置をもとに、そこから P が作れるか調べる
  3. 作れたならそこで終わり、そうでなければ次の位置に進む

(流れだけ書いてみると意外と単純だった...?)

ポイントとしては、「リング状」の文字列から探すというのをどう実現するかというところ。今回は 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 編はこの辺りで一旦終わりにします。それでは。

github.com