{-
 - Copyright (c) 2011, Thomas Davie
 - All rights reserved.
 - 
 - Redistribution and use in source and binary forms, with or without
 - modification, are permitted provided that the following conditions are met:
 -    * Redistributions of source code must retain the above copyright
 -      notice, this list of conditions and the following disclaimer.
 -    * Redistributions in binary form must reproduce the above copyright
 -      notice, this list of conditions and the following disclaimer in the
 -      documentation and/or other materials provided with the distribution.
 -
 - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 - ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 - WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 - DISCLAIMED. IN NO EVENT SHALL THOMAS DAVIE BE LIABLE FOR ANY
 - DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 - (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 - LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 - ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 - (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 - SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 -}

module AV (av) where

import Data.List
import Control.Applicative
import Control.Arrow
import System

type Vote = [Candidate]
type Candidate = String
 
av :: [Vote] -> [[(Int, Candidate)]]
av votes =
  if maxMargin >= 0.5 then [result]
  else result : av (filter ((> 0) . length) . map eliminate $ votes)
  where
    maxMargin = fst $ head margins
    margins = map (margin &&& snd) result
    margin x = (fromIntegral (fst x)) / (fromIntegral (length votes))
    result = reverse . sort . map (length &&& head) . group . sort . map head $ votes
    min = last result
    mins = filter ((== fst min) . fst) result
    minNames = map snd mins
    eliminate = filter (not . (`elem` minNames))
 
main :: IO ()
main = do
  file <- head <$> getArgs
  contents <- readFile file
  putStrLn . unlines . map (unwords . (map show)) . av . map words . lines $ contents