読者です 読者をやめる 読者になる 読者になる

アヤチノオト

覚書のこと

チケットゴブル問題に挑戦したけど評価3だった

ダブリのいちばん多いチケットを取り除き、ダブリがなくなるまで繰り返す。

module Main where


import Control.Applicative ((<$>), (<*>))
import Data.List ((\\))
import System.Environment (getArgs)
import Debug.Trace


type Date = Integer
type Ticket = (String, Date, Date)


-- |
-- main
-- >>> :main
-- 4 Austria Canada Denmark Egypt
main :: IO ()
main = do
  args <- getArgs
  if null args then
      readFile "five.txt" >>= putStrLn . solve
  else
      readFile (head args) >>= putStrLn . solve
  where
    solve = (++) <$> (++" ") . show . length <*> unwords  <$> unconflictedCountries
    unconflictedCountries = map getCountry . resolveConflict . toTickets . nonEnptyLines
    nonEnptyLines = filter (/="") . lines
    toTickets = map readTicket
    getCountry (c, _, _)= c

-- |
-- readTicket
-- >>> readTicket "Afghanistan 4/17-4/18"
-- ("Afghanistan",417,418)
readTicket :: String -> Ticket
readTicket s = (country, start, end)
    where
      (country, ds) = break (==' ') s
      (start', end') = break (=='-') ds
      start = readDate start'
      end = readDate (tail end')

-- |
-- readDate
-- Converts String to Date that indicated with Int that less than 1231 more than 101.
-- Two lower digits indicates day, and two upper digits indicates month.
-- >>> readDate "1/13"
-- 113
-- >>> readDate "12/1"
-- 1201
readDate :: String -> Date
readDate dateString = a' * 100 + b'
    where
      a' = read a
      b' = read (tail b)
      (a, b) = break (=='/') dateString

-- |
-- conclictedTo
-- Whether the two tickets are conflicted.
-- >>> conflicted ("America", 113, 115) ("India", 110, 113)
-- True
-- >>> conflicted ("India", 110, 113) ("America", 113, 115)
-- True
-- >>> conflicted ("America", 113, 122) ("India", 115, 120)
-- True
-- >>> conflicted ("America", 113, 115) ("India", 116, 120)
-- False
-- >>> conflicted ("America", 121, 135) ("India", 116, 120)
-- False
isConflictedTo :: Ticket -> Ticket -> Bool
isConflictedTo (_, s1, e1) (_, s2, e2) = s1 == s2 ||
                                     (s1 < s2 && e1 >= s2) ||
                                     (s1 > s2 && s1 <= e2)

-- |
-- countConflicted
-- Conts the number of conflicted tickets.
-- >>> let tickets = [("America", 113, 115), ("India", 110, 112), ("Germany", 112, 113)]
-- >>> countConflicted tickets ("America", 113, 115)
-- 2
-- >>> countConflicted tickets ("Germany", 112, 113)
-- 3
countConflicted :: [Ticket] -> Ticket -> Int
countConflicted [] _ = error "There is no tickets"
countConflicted tickets t = length . filter (isConflictedTo t) $ tickets

-- |
-- resolveConflict
-- Removes all tickets that conflicted to other.
-- >>> let tickets1 = [("America", 100, 105), ("India", 106, 112), ("Germany", 113, 114)]
-- >>> resolveConflict tickets1
-- [("America",100,105),("India",106,112),("Germany",113,114)]
-- >>> let tickets2 = ("Japan", 103, 116):tickets1
-- >>> resolveConflict tickets2
-- [("America",100,105),("India",106,112),("Germany",113,114)]
resolveConflict :: [Ticket] -> [Ticket]
resolveConflict tickets
    | all ((==1) . countConflicted tickets) tickets = tickets
    | otherwise = resolveConflict (tickets \\ [snd mostConflictedTicket])
    where
      mostConflictedTicket =
          let t = foldr1 (\t1 t2-> if fst t1 >= fst t2 then t1 else t2) ticketC
          in trace (show t) t
      ticketC = map (\t -> (countConflicted tickets t, t)) tickets