HaskellでAOJの問題を解いた(ITP1_3~4)

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

github.com

今回解いた問題

• ITP1_3
  • 3_A: Print Many Hello World
  • 3_B: Print Test Cases
  • 3_C: Swapping Two Numbers
  • 3_D: How Many Divisors?
• ITP1_4
  • 4_A: A / B Problem
  • 4_B: Circle
  • 4_C: Simple Calculator
  • 4_D: Min, Max and Sum

3_A: Print Many Hello World

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

こちら に書きました。

3_B: Print Test Cases

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

import qualified Control.Monad as Monad

main = loopPutCase 1

loopPutCase :: Int -> IO ()
loopPutCase i = do
    x <- getLine
    Monad.when (read x /= 0) $ do
        putStrLn $ "Case " ++ show i ++ ": " ++ x
        loopPutCase $ i + 1

複数の入力データが与えられる問題が初登場しました。

はじめは Writer や State モナドを使ってカウントの状態を管理しないといけないのでは?と考えて色々試行錯誤をしてみましたが、最終的に引数にカウントを取る関数を再帰させる形に落ち着きました。

3_C: Swapping Two Numbers

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

import Control.Applicative
import qualified Control.Monad as Monad

main = loopPutNumbers

loopPutNumbers :: IO ()
loopPutNumbers = do
    [x,y] <- map (read :: String -> Int) . words <$> getLine
    Monad.when (x /= 0 || y /= 0) $ do
        putStrLn $ if (x < y)
                    then unwords $ show <$> [x,y]
                    else unwords $ show <$> [y,x]
        loopPutNumbers

リストもモナドなので <$> が適用できます。とは言っても getLine で受け取っている IO () も中身は String で同じリストモナドなので今更なのですが。
今回は show <$> [x,y] と書きましたが、IO () に普通の関数を適用したい場合は <$> を使えばよさそうですが、リストの場合は map show とも置き換えられるので好みの問題かもしれません。

3_D: How Many Divisors?

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

import Control.Applicative

main = do
    [a,b,c] <- map (read :: String -> Int) . words <$> getLine
    print $ length $ findDivisors a b c

findDivisors :: Int -> Int -> Int -> [Int]
findDivisors a b c = [n | n <- [a..b], c `mod` n == 0]

問題文から即座に集合の問題だと判断し、リスト内包表記で解いてみました。このような数学らしい問題を解くのに便利な構文があるのも Haskell の強みですね。

4_A: A / B Problem

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

import Control.Applicative
import Data.Fixed

main = do
    [a,b] <- map (read :: String -> Int) . words <$> getLine
    putStrLn $
        show (a `div` b) ++ " " ++
        show (a `mod` b) ++ " " ++
        show ((realToFrac a) / (realToFrac b) :: Fixed E9)

簡単な除算と剰余演算かと思っていましたが、浮動小数点数の扱いだけは少し悩みました。

/ 演算子を使えば除算はできますが、それだけでは期待する結果になりません。例えば、 3 / 2 には 1.50000 という結果が期待されるのですが、実際にはこうならず 1.5 が返ってきます。

この問題を解決するために Data.Fixed というモジュールを使います。このモジュールが提供している型コンストラクタ Fixed を使うことで任意の精度の小数を扱えるようになります。今回は問題文より0.00001以下の誤差が認められているので桁数としては E9 で十分そうです( 10^-9 = .000000001 )。 Fixed 型コンストラクタを使うためには Fractional 型クラスのインスタンスである必要があるので Int を realToFrac で変換しています。

https://hackage.haskell.org/package/base-4.9.0.0/docs/src/Data.Fixed.html#line-199

4_B: Circle

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

import Control.Applicative
import Data.Fixed

main = do
    r <- (read :: String -> Double) <$> getLine
    putStrLn $ unwords $ show . toFixedE9 <$> [(pi*r^2), (2*pi*r)]

toFixedE9 :: Double -> Fixed E9
toFixedE9 r = realToFrac r :: Fixed E9

Aと同じく浮動小数点数を扱う必要があるので Data.Fixed を使っています。変換処理の記述が長くなって読みづらくなりそうだったので関数に切り出しました。

4_C: Simple Calculator

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

import Control.Applicative
import qualified Control.Monad as Monad

main = calculator

calculator :: IO ()
calculator = do
    [a, op, b] <- words <$> getLine
    Monad.when (op /= "?") $ do
        print $ calculate (read a) op (read b)
        calculator

calculate :: Int -> String -> Int -> Int
calculate a op b = interpret op
    where interpret "+" = a + b
          interpret "-" = a - b
          interpret "*" = a * b
          interpret "/" = a `div` b

引数で与えられた演算子の文字列をパターンマッチで評価している部分は、

calculate a "+" b = a + b
calculate a "-" b = a - b
...  

と書いてもよかったのですが、 where キーワードで一時関数を作ってそこでパターンマッチさせるようにしました。個人的にパターンマッチさせたい値が1つだけの場合や、パターンマッチによる分岐が多い場合は、 where キーワードを使った方が見やすい気がします。

4_D: Min, Max and Sum

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

import Control.Applicative
import qualified Control.Monad as Monad

main = do
    getLine
    xs <- map (read :: String -> Int) . words <$> getLine
    putStrLn $ unwords $ show <$> Monad.sequence [minimum, maximum, sum] xs

同じ値に対して複数の関数を適用したいときは sequence が便利です。似たような関数に sequenceA というのがありますが、モナドを取るかアプリカティブファンクターを取るかの違いしかなく、今回はリストを取るのでどちらでもよさそうです。

参考文献

• Converting numbers - HaskellWiki
• Data.Fixed
• Haskell における数値間の変換（Int・Integer・Float・Double・Rational ） - sirocco の書いてもすぐに忘れるメモ
• Haskellで任意精度小数を扱う - think and error
• sequence - Prelude