Much as I hate the phrase “The Tournament is wide Open” (which ranks right up there with “DLF maximum” and “Citi moment of success” in terms of irritability and frequency), especially when I have to hear it from the likes of Ravi Shastry during one of those fugly presentation ceremonies, am enough intrigued by it to see if one can apply one’s haskellfu to throw more light on the alleged width of the tournament’s opening.
In short, I want a (haskell) program that takes as input:
- points table and
- future matches
- A team name
and can answer the following question :
under what conditions can the team reach the last four?
Assuming that at the end of each match the net run rate(NRR) will be incremented by 0.5 for the winner and decremented by 0.5 for the loser and that a match could also result in a draw (thanks to the the rain),in which case the teams share a point each (and with no change in the NRRs), the tree of possibilities will have a small matter of 322 nodes (considering there are 22 more matches to go , as I type this). And 320 is just 348,67,84,401 ! I know for sure I would not be able to write the program in java/C++ as easily as I can do it in Haskell.
So, Here I go,
module Main where import System.IO import Data.Tree import System.Environment import qualified Data.Map as M import qualified Data.List as L
A match is a record of two fields teamA , teamB and points won by teamA and points won by teamB
data Match = Match (String,Int) (String, Int)
deriving Show
Each team has a unique identifier to represent it, a collection of points and net-run rate
The teams can be compared on the basis of their points. If the points are identical, then their net-run rates are identified
data Team = Team{teamName:: String,
teamScore :: Int,
teamNetRunRate :: Float
}
deriving (Eq,Show)
compTeams (Team _ t1 n1) (Team _ t2 n2)
= if (t1 > t2) then GT
else if (t1 < t2) then LT
else if (n1 > n2) then GT
else if (n1 < n2) then LT
else EQ
instance Ord Team where
compare = compTeams
we can also add three functions to the team that lets us add a win, lose and a draw
addWin (Team t1 s r) = Team t1 (s + 2) (r + 0.5) addLoss (Team t1 s r) = Team t1 s (r - 0.5) addDraw (Team t1 s r) = Team t1 (s+1) r
A tournament can be defined as a list of matches that were already played and a list of planned clashes between teams.
However, I will also need a map between String and a team in order to use just the strings
data Tournament = Tourney { teamMap :: M.Map String Team,
played :: [Match],
toPlay :: [(String,String)]
}
deriving Show
Thus, this tournament presents a snapshot of the tournament at any given instant.
Given these, identifying the top 4 is trivial
topFour :: Tournament -> [Team] topFour t = drop 4 (L.sort $ M.elems $ teamMap t)
To conduct a match, we need to take a potential clash out of the “toPlay” list, convert it into a Match and add it to
the played list and then update the teamMap with appropriate points depending on who won the particular match.
In order to do so, we need a new data type to indicate the result of a match
data MatchRes = AWon | BWon | Draw
As mentioned earlier, conducting a match is akin to taking a given tournament and a result and getting a new snapshot of the tournament.
conductMatch :: Tournament -> MatchRes -> Tournament
conductMatch t@(Tourney _ _ []) _ = t -- should it be an error
conductMatch t@(Tourney teams pld topl) mres
= Tourney (updateTeams teams newMatch) (newMatch:pld) (tail topl)
where newMatch = clashResToMatch (head topl) mres
The two functions used above are defined below:
clashResToMatch (s1,s2) AWon = Match (s1,2) (s2, 0) clashResToMatch (s1,s2) BWon = Match (s1,0) (s2, 2) clashResToMatch (s1, s2) _ = Match (s1, 1) (s2, 1) updateTeams tMap (Match (t1,p1) (t2,p2)) = addPointsToTeam t2 p2 (addPointsToTeam t1 p1 tMap) addPointsToTeam t1 0 tMap = M.update (\x -> Just $ addLoss x) t1 tMap addPointsToTeam t1 1 tMap = M.update (\x -> Just $ addDraw x) t1 tMap addPointsToTeam t1 2 tMap = M.update (\x -> Just $ addWin x) t1 tMap addPointsToTeam _ _ _ = error "Invalid points in addPointsToTeam"
Now in order to generate all the combinations, we need a function “explode”, that takes a tournament and gives a list of tournaments such that
in each of these we have one possible result.
explode (Tourney _ _ []) = [] explode t = map (conductMatch t) [AWon, BWon, Draw]
Once the “explode” is in place, creating a tournament “tree” which provides all the possible combinations is very simple:
tourneyTree t = Node t (map tourneyTree (explode t)) getLeaves (Node a []) = [a] getLeaves (Node a xs) = concatMap getLeaves xs
We are left with dealing with the input files and accessing the filter, which is pretty straight forward.
main = do args <- getArgs
case args of
(i1:i2:t:[]) -> do tourney <- readInput i1 i2
let lvs = filter (\x -> hasTeamInTopFour t x) (getLeaves $ tourneyTree tourney)
case lvs of
(hd:rst) -> do print hd
[] -> do print "No chance, dude"
_ -> do usage
usage = do print "Usage:"
print "TWOpen InputFile outputFile <Team Name>"
print "Team Name is one of : Delhi, Mumbai, Chennai, Kolkata, Hyd, Blore, Jaipur, Mohali"
hasTeamInTopFour tName t = tName `elem` (map teamName $ topFour t)
Here, readInput is an IO action that takes a couple of files and returns the tournament snapshot as depicted in the input.
It is trivial as am using the built-in “read” function.
readInput t1 t2 = do inpStr1 <- readFile t1
inpStr2 <- readFile t2
let tmMap = getteamMap $ getList1 $ lines inpStr1
let t2 = getList2 (lines inpStr2)
return $ Tourney tmMap [] t2
getteamMap ts = M.fromList $ zip (map teamName ts) ts
getList1 strs = map (getTeam . L.words) strs
getList2 strs = map (getClashes . L.words) strs
getTeam (t1:t2:t3:[]) = Team t1 (read t2) (read t3)
getTeam _ = error "Invalid team"
getClashes (t1:t2:[]) = (t1,t2)
getClashes _ = error " invalid clash"
Running the file with the following Points table (which is the latest not counting the ongoing Chennai Vs Mohali game) and trying out various
teams, we can see that even KKR still has an outside chance of reaching the game:
Delhi 10 0.158 Mumbai 7 0.516 Kolkata 3 -1.097 Chennai 9 1.36 Blore 8 -0.395 Mohali 8 -0.5 Hyd 10 0.152 Jaipur 11 0.05
and the following schedule:
Delhi Mumbai Hyd Mohali Chennai Jaipur Kolkata Delhi Blore Mumbai Hyd Jaipur Blore Kolkata Mohali Mumbai Hyd Delhi Mumbai Jaipur Chennai Blore Mohali Delhi Chennai Mumbai Hyd Kolkata Jaipur Delhi Mohali Hyd Chennai Kolkata Delhi Blore Chennai Mohali Jaipur Kolkata Hyd Blore Mumbai Delhi
and checking out the options for Kolkata, the program runs for about 2 full minutes and presents a scenario under which the beleagured team can reach the semis. Possibly there are others as well!
If the future matches go as below
Match ("Mumbai",2) ("Delhi",0),
Match ("Hyd",2) ("Blore",0),
Match ("Jaipur",0) ("Kolkata",2),
Match ("Chennai",2) ("Mohali",0),
Match ("Delhi",0) ("Blore",2),
Match ("Chennai",0) ("Kolkata",2),
Match ("Mohali",2) ("Hyd",0),
Match ("Jaipur",2) ("Delhi",0),
Match ("Hyd",0) ("Kolkata",2),
Match ("Chennai",2) ("Mumbai",0),
Match ("Mohali",2) ("Delhi",0),
Match ("Chennai",2) ("Blore",0),
Match ("Mumbai",2) ("Jaipur",0),
Match ("Hyd",2) ("Delhi",0),
Match ("Mohali",2) ("Mumbai",0),
Match ("Blore",0) ("Kolkata",2),
Match ("Hyd",2) ("Jaipur",0),
Match ("Blore",2) ("Mumbai",0),
Match ("Kolkata",2) ("Delhi",0),
Match ("Chennai",2) ("Jaipur",0),
Match ("Hyd",2) ("Mohali",0),
Match ("Delhi",2) ("Mumbai",0)
the final points table would look like:
Hyd -> points = 18, NetRunRate = 1.152 Chennai -> points = 17, NetRunRate = 2.8600001 Mohali -> points = 14, NetRunRate = 0.0 Kolkata -> points = 13, NetRunRate = 1.403 Jaipur -> points = 13, NetRunRate = -1.45 Blore -> points = 12, NetRunRate = -0.895 Delhi -> points = 12, NetRunRate = -2.342 Mumbai -> points = 11, NetRunRate = -0.48400003
So you see, The tournament is indeed wide open!
