Codeforces

2012年2月16日 (木)

Codeforces 35

最近、「Project Euler」を休んで、「Codeforces」の過去問を Haskell で解いて遊んでます。
ずっと「モナド」とか「IO アクション」から逃げてたんですけど、「Codeforces」では「入力」と「出力」が決まってるので「IO」の練習になるかな…と思いまして。

今回、この問題を解いてみました。
一般的な手続型言語では配列にデータを入れておいて、後はスワップを繰り返せばいいのでしょうけど、Haskell だとリストや配列のスワップはコストが高いよな…と思って、次のようなコードを書きました。

test :: String -> [String] -> Int
test "1" xs = loop 1 0 0 xs
test "2" xs = loop 0 1 0 xs
test "3" xs = loop 0 0 1 xs

loop :: Int -> Int -> Int -> [String] -> Int
loop 1 _ _ [] = 1
loop _ 1 _ [] = 2
loop _ _ 1 [] = 3
loop a b c (x1 : x2 : xs)
  | (x1, x2) == ("1", "2") || (x1, x2) == ("2", "1") = loop b a c xs
  | (x1, x2) == ("1", "3") || (x1, x2) == ("3", "1") = loop c b a xs
  | (x1, x2) == ("2", "3") || (x1, x2) == ("3", "2") = loop a c b xs

main :: IO ()
main = do input <- readFile "input.txt"
          let ([i], xs) = splitAt 1 $ words input
          writeFile "output.txt" $ show $ test i xs

一応、結果は「Accepted」でしたが、力技で解いた感があってあまり美しいと言えません。

 

今後の参考にと、他の人の解放を見ていたら、次のようなコードを見つけました。私とはちょっと発想が違っています。

import IO

gao :: [Int] -> Int
gao [a] = a
gao (a:b:c:d) = gao $ (if a == b then c else if a == c then b else a):d

main = do
        hi <- openFile "input.txt" ReadMode
        ho <- openFile "output.txt" WriteMode
        hGetContents hi >>= hPutStr ho . show . gao . map read . words
        hClose ho

このコードを参考に(パクッて?)、自分の好きなスタイルでコードを書いてみました。 (私は "if 〜 then 〜 else 〜 " があまり好きではありません。特に参考にしたコードのように if が連なっていると、直感的に分りにくい気がします)

test :: String -> [String] -> String
test i (a : b : xs)
  | i == a    = test b xs
  | i == b    = test a xs
  | otherwise = test i xs
test i [] = i

main :: IO ()
main = do input <- readFile "input.txt"
          let (i : xs) = words input
          writeFile "output.txt" $ test i xs

最初に自分で書いたコードより、こちらのコードのほうがずっと良い気がします。

Date: 2012-02-16 11:48:22 JST

HTML generated by org-mode 6.33x in emacs 23

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ