module Exercise02 where

import Data.List (sort, elemIndices,  minimumBy, genericIndex, sortOn, tails, foldl1')
import Data.Ord (comparing)
import System.Environment (getArgs)

{-H2.1a)-}
twoThirdsAverage :: [Int] -> Int
twoThirdsAverage xs = 2 * sum xs `div` (3 * length xs)

allMinimumBy :: (a -> Int) -> [a] -> [a]
allMinimumBy _ [e] = [e]
allMinimumBy key (x:xs)
    | key x == key (head tailMinimumBy) = x : tailMinimumBy
    | key x  < key (head tailMinimumBy) = [x]
    | otherwise                         = tailMinimumBy
    where tailMinimumBy = allMinimumBy key xs

twoThirdsAverageWinners :: [(String, Int)] -> [String]
twoThirdsAverageWinners gs = map fst (allMinimumBy (abs . (-) avg . snd) gs)
    where avg = twoThirdsAverage (map snd gs)

{-H2.1b)-}
firstUniqueOn :: (a -> Int) -> [a] -> Maybe a
firstUniqueOn _ [] = Nothing
firstUniqueOn _ [x] = Just x
firstUniqueOn key (x:xs)
    | key x /= key (head xs)    = Just x
    | otherwise                 = firstUniqueOn key (dropWhile ((==) (key x) . key) xs)

lowestUniqueBidder :: [(String, Int)] -> String
lowestUniqueBidder bs = maybe "Nobody" fst (firstUniqueOn snd (sortOn snd bs))


{-H2-}

-- returns the shortest list in a list of lists
shortest :: [[Int]] -> [Int]
shortest = minimumBy (comparing length)

-- returns the set of all players in a tournament
players :: [[Int]] -> [Int]
players tournament = [1..length tournament]

-- returns the dominion of player i
dominion :: [[Int]] -> Int -> [Int]
dominion tournament i = tournament !! (i - 1)

{-H2.2a)-}
dominators :: [[Int]] -> Int -> [Int]
dominators tournament i = [p | (p, pDominion) <- zip [1..] tournament, i `elem` pDominion]

dominators2 :: [[Int]] -> Int -> [Int]
dominators2 tournament i = map fst $ filter (elem i . snd) (zip [1..] tournament)

{-H2.2b)-}

isSortedSubsetOf :: (Ord a) => [a] -> [a] -> Bool
isSortedSubsetOf [] _ = True
isSortedSubsetOf _ [] = False
isSortedSubsetOf (x:xs) (y:ys) = case compare x y of
    LT -> False
    GT -> isSortedSubsetOf (x:xs) ys
    EQ -> isSortedSubsetOf xs ys

covers :: [[Int]] -> Int -> Int-> Bool
covers tournament i j = isSortedSubsetOf (dominion tournament j) (dominion tournament i)

{-2.2c)-}
intersectSorted :: Ord a => [a] -> [a] -> [a]
intersectSorted [] _ = []
intersectSorted _ [] = []
intersectSorted (x:xs) (y:ys) = case compare x y of
    LT -> intersectSorted xs (y:ys)
    GT -> intersectSorted (x:xs) ys
    EQ -> x : intersectSorted xs ys

dominant :: [[Int]] -> [Int] -> Bool
dominant _ [] = False
dominant tournament ps = length (foldl1' intersectSorted (map (dominion tournament) ps)) == (length tournament - length ps)

{-WETT-}
 
{-H2.2d)-}
copeland :: [[Int]] -> [Int]
copeland tournament = maximum dominionSizes `elemIndices` dominionSizes
    where dominionSizes = minBound : map length tournament

-- Note: copeland [] = [0] which is OK, since it doesn't need to work for the empty tournament [].
-- Why the minBound? I need a value less than zero, otherwise the one player tournament [[]] would
-- map to [0, 0]. Of course -1 would work, but that is two tokens.

{-H2.2e)-}
uncoveredSet :: [[Int]] -> [Int]
uncoveredSet tournament = filter noCovers ps
    where
        cov = covers tournament
        ps = players tournament
        noCovers j = filter (`cov` j) ps == [j]

{-H2.2f)-}
-- For any tournament T and any players a, b in T: let |a| and |b| be the sizes
-- of the dominionSizes of a and b, respectively and let TC_T be the top cycle in T. Then:
--                  a in TC_T AND |b| >= |a| ==> b in TC_T
-- I have a truly marvelous demonstration of this proposition which this comment is too small to contain.
-- It is, however, included at docs/proofs.pdf

topCycle :: [[Int]] -> [Int]
topCycle tournament = last $ filter (dominant tournament) $ tails $ sortOn (length . dominion tournament) $ players tournament

-- O(e^n) naive solution
-- topCycle tournament = shortest $ filter (dominant tournament) $ subsequences $ players tournament

-- slightly longer solution
-- topCycle tournament = fromJust $ find (dominant tournament) $ inits $ sortOn f $ players tournament
--     where dom = dominion tournament
--           f = Down . length . dom

{-TTEW-}

add :: Int -> Int -> Int
add a = genericIndex $ enumFrom a

splitOn :: (a -> Bool) -> [a] -> [[a]]
splitOn _ [] = [[]]
splitOn pred (x:xs)
    | pred x    = [] : splitOn pred xs
    | otherwise = let (r:rs) = splitOn pred xs in (x : r) : rs

tournamentFromCsv :: String -> [[Int]]
tournamentFromCsv csv = map (map read . filter (/= "") . splitOn (',' == )) $ lines csv

tournamentFromFile :: String -> IO [[Int]]
tournamentFromFile fName = readFile fName >>= \s -> return $ tournamentFromCsv (s ++ "\n")

main :: IO ()
main = do
    args <- getArgs
    x <- tournamentFromFile $ head args
    print "start running"
    print $ topCycle x
    print "done"

t1 :: [[Int]]
t1 = [[2,4],[3,4],[1,4],[]]

t2 :: [[Int]]
t2 = [[2,3],[3],[]]

t3 :: [[Int]]
t3 = [[3,4,5],[1],[2],[2,3,5],[2]]

t4 :: [[Int]]
t4 = [[3, 6, 7, 8], [1, 3, 4, 6, 9], [5, 6, 8, 9, 10], [1, 3, 5, 7, 9], [1, 2, 6, 7, 8, 9], [4, 10], [2, 3, 6], [2, 4, 6, 7, 9], [1, 6, 7], [1, 2, 4, 5, 7, 8, 9]]

tt6 :: IO [[Int]]
tt6 = tournamentFromFile "digraphs/9/1024.csv"

ex10 :: [[Int]]
ex10 = [[2,3,4,5,6,8,9],[3,5,6],[5,8],[2,3,5,6,7,8,9,10],[],[3,5,8],[1,2,3,5,6,8,9],[2,5],[2,3,5,6,8],[1,2,3,5,6,7,8,9]]
co10 :: [Int]
co10 = [4, 10]
uc10 :: [Int]
uc10 = [1, 4, 10]
tc10 :: [Int]
tc10 = [1, 4, 7, 10]

ex20 :: [[Int]]
ex20 = [[2,3,4,5,6,7,8,9,10,11,12,13,15,16,18,19,20],[3,4,5,8,10,13,15,19],[4,5,12,13,15,19,20],[6,10,13,15,19],[4,9,10,13,15,19,20],[2,3,5,9,13,15,19],[2,3,4,5,6,8,9,10,11,12,13,15,19],[3,4,5,6,9,11,13,15,19],[2,3,4,10,11,13,15,19,20],[3,6,8,11,13,15,19],[2,3,4,5,6,13,15,19],[2,4,5,6,8,9,10,11,13,15,19],[19],[1,2,3,4,5,6,7,8,9,10,11,12,13,15,17,19,20],[13,19],[2,3,4,5,6,7,8,9,10,11,12,13,14,15,18,19,20],[1,2,3,4,5,6,7,8,9,10,11,12,13,15,16,18,19,20],[2,3,4,5,6,7,8,9,10,11,12,13,14,15,19,20],[],[2,4,6,7,8,10,11,12,13,15,19]]
co20 :: [Int]
co20 = [17]
uc20 :: [Int]
uc20 = [14,16,17]
tc20 :: [Int]
tc20 = [1,14,16,17,18]

ex30 :: [[Int]]
ex30 = [[2,3,5,6,7,8,10,11,12,13,14,15,17,18,19,20,21,22,23,24,25,26,27,28,29,30],[18,23,29],[2,7,8,10,11,14,18,19,20,21,22,23,25,26,27,28,29],[1,2,3,6,7,8,10,11,12,13,14,15,17,18,19,20,21,22,23,24,25,26,27,28,29,30],[2,3,4,6,7,8,9,10,11,12,13,14,15,17,18,19,20,21,22,23,24,25,26,27,28,29,30],[2,3,7,8,10,11,13,14,15,17,18,19,20,22,23,24,25,26,27,28,29,30],[2,8,10,11,14,17,18,20,22,23,24,25,26,27,28,29],[2,10,11,14,18,19,20,23,25,26,27,28],[1,2,3,4,6,7,8,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30],[2,18,23,28],[2,10,18,23,28],[2,3,6,7,8,10,11,13,14,15,17,18,19,20,21,22,23,24,25,26,27,28,29],[2,3,7,8,10,11,14,17,18,19,20,21,22,23,24,25,26,27,28,29,30],[2,10,11,18,19,20,23,25,26,27,28,29],[2,3,7,8,10,11,13,14,17,18,19,20,22,23,25,26,27,28,29],[1,2,3,4,5,6,7,8,10,11,12,13,14,15,17,18,19,20,21,22,23,24,25,26,27,28,29,30],[2,3,8,10,11,14,18,19,20,23,25,26,27,28,29],[23],[2,7,10,11,18,23,25,28],[2,10,11,18,19,22,23,25,26,27,28,29],[2,6,7,8,10,11,14,15,17,18,19,20,22,23,24,25,26,27,28,29,30],[2,8,10,11,14,17,18,19,23,24,25,26,27,28,29,30],[],[2,3,8,10,11,14,15,17,18,19,20,23,25,26,27,28,29],[2,10,11,18,23,28],[2,10,11,18,19,23,25,27,28],[2,10,11,18,19,23,25,28],[2,18,23],[8,10,11,18,19,23,25,26,27,28],[2,3,7,8,10,11,12,14,15,17,18,19,20,23,24,25,26,27,28,29]]
co30 :: [Int]
co30 = [9,16]
uc30 :: [Int]
uc30 = [5,9,16]
tc30 :: [Int]
tc30 = [1,4,5,9,16]

ex35 :: [[Int]]
ex35 = [[2,3,4,5,6,7,9,12,13,14,18,19,20,21,22,23,24,25,26,27,29,30,31,34,35],[3,4,5,6,7,9,14,18,19,20,21,22,23,24,25,26,27,29,30,31,34,35],[4,5,6,12,14,18,19,20,21,22,23,24,25,26,27,29,30,31,34,35],[5,6,12,14,18,19,20,21,22,23,24,25,26,27,29,30,31,34,35],[29],[5,14,18,21,22,23,24,26,27,29,31,35],[3,4,5,6,9,12,14,18,19,20,21,22,23,24,25,26,27,29,30,31,35],[1,2,3,4,5,6,7,9,10,12,14,18,19,20,21,22,23,24,25,26,27,29,30,31,34,35],[3,4,5,6,14,18,19,21,22,23,24,25,26,27,29,30,35],[1,2,3,4,5,6,7,9,11,12,14,18,19,20,21,22,23,24,25,26,27,29,30,31,34,35],[1,2,3,4,5,6,7,8,9,12,14,18,19,20,21,22,23,24,25,26,27,29,30,31,34,35],[2,5,6,9,13,14,18,19,20,21,22,23,24,25,26,27,29,30,31,34,35],[2,3,4,5,6,7,8,9,10,11,14,18,19,20,21,22,23,24,25,26,27,29,30,31,34,35],[5,18,27,35],[1,2,3,4,5,6,7,8,9,10,11,12,13,14,17,18,19,20,21,22,23,24,25,26,27,29,30,31,32,33,34,35],[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,17,18,19,20,21,22,23,24,25,26,27,29,30,31,33,34,35],[1,2,3,4,5,6,7,8,9,10,11,12,13,14,18,19,20,21,22,23,24,25,26,27,28,29,30,31,34,35],[5],[5,6,14,18,21,22,23,26,27,29,31,35],[5,6,9,14,18,19,21,23,26,27,29,30,31,34,35],[5,14,18,23,27,31],[5,14,18,20,21,23,27,29,30,31,35],[5,14,18,27,35],[5,14,18,19,20,21,22,23,27,29,31,35],[5,6,14,18,19,20,21,22,23,24,26,27,29,30,31,35],[5,14,18,21,22,23,24,27,29,30,31,34,35],[5,18,29,31],[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,18,19,20,21,22,23,24,25,26,27,29,30,31,34,35],[14,18,21,23],[5,6,14,18,19,21,23,24,27,29,31,35],[5,9,14,18,23,29],[1,2,3,4,5,6,7,8,9,10,11,12,13,14,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,34,35],[1,2,3,4,5,6,7,8,9,10,11,12,13,14,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,34,35],[5,6,7,9,14,18,19,21,22,23,24,25,27,29,30,31,35],[5,18,21,27,29,31]]
co35 :: [Int]
co35 = [15,16,32,33]
uc35 :: [Int]
uc35 = [15,16,28,32,33]
tc35 :: [Int]
tc35 = [15,16,17,28,32,33]

ex50 :: [[Int]]
ex50 = [[2,5,7,10,11,12,13,14,17,18,19,20,21,22,23,24,26,27,29,30,31,32,33,34,35,36,37,38,39,41,42,44,49,50],[5,7,8,10,11,12,14,15,17,18,19,20,21,22,23,24,26,27,29,30,31,32,33,35,36,37,38,39,41,42,43,44,48,49,50],[1,2,5,6,7,8,10,11,12,13,14,15,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,41,42,43,44,45,46,48,49,50],[1,2,3,5,6,7,8,10,11,12,13,14,15,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,41,42,43,44,45,48,49,50],[7,11,36,37],[1,2,5,7,8,9,10,11,12,13,14,15,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50],[26,36],[1,5,7,10,11,12,14,18,19,20,21,22,23,24,26,27,29,30,31,32,33,35,36,37,38,39,41,42,44,49,50],[1,2,3,4,5,7,8,10,11,12,13,14,15,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50],[5,7,11,12,14,18,21,22,24,26,27,29,30,31,32,33,35,36,37,39,41,42,44,49,50],[7,27,36],[5,7,11,18,21,22,24,26,27,29,30,33,35,36,37,39,42,50],[2,5,7,8,10,11,12,14,17,18,19,20,21,22,23,24,26,27,29,30,31,32,33,34,35,36,37,38,39,41,42,43,44,49,50],[5,7,11,12,18,21,22,24,26,27,29,30,31,32,33,35,36,37,39,42,44,49,50],[1,5,7,8,10,11,12,13,14,17,18,19,20,21,22,23,24,25,26,27,29,30,31,32,33,34,35,36,37,38,39,41,42,43,44,45,49,50],[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,41,42,43,44,45,46,47,48,49,50],[5,7,8,10,11,12,14,18,19,21,22,23,24,26,27,29,30,31,32,33,34,35,36,37,39,41,42,44,49,50],[5,7,11,22,24,26,27,29,30,32,33,36,37,39,42,44,50],[5,7,10,11,12,14,18,21,22,24,26,27,29,30,31,32,33,34,35,36,37,38,39,41,42,44,49,50],[5,7,10,11,12,14,17,18,19,21,22,24,26,27,29,30,31,32,33,34,35,36,37,38,39,41,42,44,49,50],[5,7,11,18,22,24,26,27,29,30,33,36,37,39,44],[5,7,11,27,29,36],[5,7,10,11,12,14,18,19,20,21,22,24,26,27,29,30,31,32,33,35,36,37,38,39,41,42,44,49,50],[5,7,11,22,26,27,29,33,36,39,42,50],[1,2,5,7,8,10,11,12,13,14,17,18,19,20,21,22,23,24,26,27,29,30,31,32,33,34,35,36,37,38,39,41,42,43,44,48,49,50],[5,11,22,29,33,36,39],[5,7,26,29,33,36,37,44],[1,2,5,7,8,10,11,12,13,14,15,17,18,19,20,21,22,23,24,25,26,27,29,30,31,32,33,34,35,36,37,38,39,41,42,43,44,45,48,49,50],[5,7,11,36,42],[5,7,11,22,24,26,27,29,33,36],[5,7,11,12,18,21,22,24,26,27,29,30,32,33,35,36,37,38,39,41,42,44,49,50],[5,7,11,12,21,22,24,26,27,29,30,33,35,36,37,39,41,42,44,50],[5,7,11,22,29,36],[2,5,7,8,10,11,12,14,18,21,22,23,24,26,27,29,30,31,32,33,35,36,37,38,39,41,42,44,49,50],[5,7,11,18,21,22,24,26,27,29,30,33,36,37,39,41,42,44,50],[],[7,11,22,24,26,29,30,33,36,42],[5,7,10,11,12,14,17,18,21,22,24,26,27,29,30,32,33,35,36,37,39,41,42,44,49,50],[5,7,11,22,27,29,30,33,36,37],[1,2,3,4,5,7,8,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,41,42,43,44,45,47,48,49,50],[5,7,11,12,14,18,21,22,24,26,27,29,30,33,36,37,39,42,44,49],[5,7,11,21,22,26,27,30,33,36,39],[1,5,7,8,10,11,12,14,17,18,19,20,21,22,23,24,26,27,29,30,31,32,33,34,35,36,37,38,39,41,42,44,48,49,50],[5,7,11,12,22,24,26,29,30,33,36,37,39,42,49],[1,2,5,7,8,10,11,12,13,14,17,18,19,20,21,22,23,24,25,26,27,29,30,31,32,33,34,35,36,37,38,39,41,42,43,44,48,49,50],[1,2,4,5,7,8,10,11,12,13,14,15,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,47,48,49,50],[1,2,3,4,5,7,8,10,11,12,13,14,15,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,41,42,43,44,45,48,49,50],[1,5,7,8,10,11,12,13,14,15,17,18,19,20,21,22,23,24,26,27,29,30,31,32,33,34,35,36,37,38,39,41,42,44,49,50],[5,7,11,12,18,21,22,24,26,27,29,30,32,33,35,36,37,39,42,50],[5,7,11,21,22,26,27,29,30,33,36,37,39,41,42,44]]
co50 :: [Int]
co50 = [16]
uc50 :: [Int]
uc50 = [6,9,16,40]
tc50 :: [Int]
tc50 = [3,4,6,9,16,40,46,47]

onep :: [[Int]]
onep = [[]]
coOnep :: [Int]
coOnep = [1]
ucOnep :: [Int]
ucOnep = [1]
tcOnep :: [Int]
tcOnep = [1]

samples :: [([[Int]], [Int], [Int], [Int])]
samples = [(ex10, co10, uc10, tc10),
           (ex20, co20, uc20, tc20),
           (ex30, co30, uc30, tc30),
           (ex35, co35, uc35, tc35),
           (ex50, co50, uc50, tc50),
           (onep, coOnep, ucOnep, tcOnep)]

checkSample :: ([[Int]], [Int], [Int], [Int]) -> Bool
checkSample (samp, co, uc, tc) =
    sort (copeland samp) == co &&
    sort (uncoveredSet samp) == uc &&
    sort (topCycle samp) == tc

checkSamples :: [([[Int]], [Int], [Int], [Int])] -> [Int]
checkSamples samps = map (\(samp, _, _, _) -> length samp) (filter (not . checkSample) samps)

prop_providedSamples :: Bool
prop_providedSamples = null (checkSamples samples)