09

03

[Haskell] クロッシング問題を解きました

2013.09.03(20:35)

結城浩 @hyuki さんのツイートで知った
クロッシング問題
http://www.hyuki.com/codeiq/#c12
を解いてCodeIQへ投稿しました。アルゴリズムを改良してゆくステップが楽しめました。時間制限も絶妙でした。今日、 @hyuki さんから採点が届き、正解だったので、私の解答を公開します。

Haskellで、マージソートを使った、O(n log n)のアルゴリズムを書きました。
私の環境ではIntでは桁が足りず、Integerで数えました。

私のノートブックで
ghciで
(21.36 secs, 4447749184 bytes)
ghc -O2 -o crossing.exe crossing.hs
crossing.exe
24689222839
2.9671697s
という速度になりました。

24689222839,2
ENV: Haskell

-- | CodeIQの問題に挑戦しよう! 結城浩
-- | http://www.hyuki.com/codeiq/
-- | 問題12. Crossing(クロッシング)
-- | http://www.hyuki.com/codeiq/#c12

{-# OPTIONS -Wall -Werror #-}

import Data.Time
{--------------------------------------------------
import Test.HUnit
c2 :: Integer->Integer
c2 n = (n*(n-1)) `div` 2

-- | ユニットテスト
myTests :: Test
myTests = test [
  cross [2,1] ~?= 1,
  cross [3,2,1] ~?= (2+1),
  cross [2,1,3] ~?= 1,
  cross [3,1,2] ~?= 2,
  cross [4,3,2,1] ~?= (3+2+1),
  cross [2,1,3,5,4] ~?= 2,
  cross [3,1,4,5,9,2,6,8,7] ~?= 9,

  cross [1..100] ~?= 0,
  cross ([51..100]++[1..50]) ~?= (50*50),
  cross (reverse [1..100]) ~?= (c2 100),
  cross (101:[1..100]) ~?= 100,
  cross (reverse [1..1000]) ~?= (c2 1000),
  cross (10001:[1..10000]) ~?= 10000,
  -- cross (100001:[1..100000]) ~?= 100000,
  True ~?= True] 

--------------------------------------------}

-- | 1つのリストを中央値より大きい値と中央値以下の値に分け、
-- | あわせてクロスした回数を数えて返す
cross3 :: Int->Int->[Int]->([Int],[Int],Integer,Integer)
cross3 _ _ [] = ([],[],0,0)
cross3 from to (x:xs) = 
  if (mid < x) then (    smaller,(x:larger),(len+1),result)
               else ((x:smaller),larger,    len,    (result+len))
  where mid = (from + to) `div` 2
        (smaller,larger,len,result) = cross3 from to xs

-- | 再帰のたびに(from == to)をやらないでいいように関数を分ける。
cross2 :: Int->Int->[Int]->([Int],[Int],Integer)
cross2 from to xs = if (from == to) then ([],[],0)
                                    else (s,l,r) 
                                         where (s,l,_,r) = cross3 from to xs

-- | 1つのリストを前半分と後ろ半分に分け、クロスした回数に、左の再帰分と右の再帰分を足す。
cross1 :: Int->Int->[Int]->Integer
cross1 _ _ [] = 0
cross1 from to xs = (r1+r2+r3)
                     where (smaller,larger,r1) = cross2 from to xs
                           r2 = cross1 from ((from+to)`div`2) smaller
                           r3 = cross1 (((from+to)`div`2)+1) to larger

-- | 前準備。問題より値の範囲は1から(length xs)まで。
cross :: [Int]->Integer
cross [] = 0
cross xs = cross1 1 (length xs) $ reverse xs

-- | メイン
main :: IO ()
main = do
  -- _ <- runTestTT myTests
  x <- getCurrentTime
  -- | 時間計測ここから ---------------------------------
  let fileName = "crossing.txt"
  -- let fileName = "sample.txt"
  contents <- readFile fileName
  let nums = map (\s -> read s :: Int) $ lines contents
  print $ cross nums
  -- | 時間計測ここまで ---------------------------------
  y <- getCurrentTime
  print $ diffUTCTime y x
  return ()
 
プロフィール

島敏博

Shima Toshihiro 島敏博
信州アルプスハイランド在住。HaskellとElixirが好き。組み込みソフトウェアアーキテクト、C++プログラマ、山歩き、美術館巡り、和食食べ歩き、日本赤十字社救急法指導員、インデックス投資、クラシック音楽、SESSAME会員、状態マシン設計、モデル駆動開発、ソフトウェアプロダクトライン、Rubyist、実践ビジネス英語

■ ツイッター
http://twitter.com/saltheads
■ Facebook
http://www.facebook.com/saltheads
■ Qiita
http://qiita.com/saltheads

印刷する場合は、ブラウザの印刷メニューではなく、このページの上から3cmくらいの青いところにある、「印刷」を押してみてください。少しうまく印刷できます。まだ完全ではないのですが、これで勘弁してください。


カテゴリ
最新記事
月別アーカイブ
最新コメント
検索フォーム
リンク
sessame
RSSリンクの表示