using System;

using System.Linq;

using System.Text;

using System.Collections.Generic;

​

    public class Program

    {

        public static void Main(string[] args)

        {

            var parser = new Parser();

            var games = new Games();

​

            WriteUsage();

            Console.WriteLine("Input game results in separate lines, Enter empty line when done: ");

​

            var sInputLine = Console.ReadLine();

            while (!string.IsNullOrWhiteSpace(sInputLine))

            {

                Player winner;

                Player loser;

                if (parser.TryParse(sInputLine, out winner, out loser))

                {

                    games.RecordGame(winner, loser);

                }

                else

                {

                    Console.WriteLine("Invalid input, Ignored.");

                    Console.WriteLine("Keep entering game results in the valid format.");

                    WriteUsage();

                }

                sInputLine = Console.ReadLine();

            }

​

            Console.WriteLine("Results:");

​

            try

            {

                var players = games.GetPlayersRanking().ToArray();

​

                var sb = new StringBuilder();

                foreach (var player in players)

                {

                    sb.AppendFormat("{0} -> ", player.Name);

                }

​

                Console.WriteLine(sb.ToString().Substring(0, sb.Length - 4));

            }

            catch (Exception ex)

            {

                Console.WriteLine(ex.Message);

            }

        }

​

        private static void WriteUsage()

        {

            Console.WriteLine("Supported input formats are:");

            Console.WriteLine("<player1> won against <player2>");

            Console.WriteLine("<player1> lost to <player2>");

        }

    }

​

​

    internal class Games

    {

        private readonly Dictionary<Player, List<Player>> playersAdjList = new Dictionary<Player, List<Player>>();

​

        /// <summary>

        /// This method tries to build a graph, where each node represents a player and each directed edge represents a win of source node against target node

        /// The graph is represented by the Dictionary, which has Player as the Key, and it's adjacency list as Value

        /// </summary>

        public void RecordGame(Player winner, Player loser)

        {

            if (!playersAdjList.ContainsKey(winner))

            {

                playersAdjList.Add(winner, new List<Player>());

            }

​

            if (!playersAdjList.ContainsKey(loser))

            {

                playersAdjList.Add(loser, new List<Player>());

            }

​

            if (!playersAdjList[winner].Contains(loser))

            {

                playersAdjList[winner].Add(loser);

            }

        }

​

        /// <summary>

        /// This method finds a hamiltonian path for the players directed graph. 

        /// A path is build placing one player at a time, a player Pi is placed in the list just before the first player found in teh list who has lost from Pi. 

        /// If no such player is found in the list (that means no one in the list has lost to Pi), then Pi is added to the end of the list.

        /// </summary>

        /// <returns></returns>

        public IEnumerable<Player> GetPlayersRanking()

        {

            if (!AreAllResultsRecorded())

            {

                throw new InsufficientInputException();

            }

​

            var list = new LinkedList<Player>();

            foreach (var keyValuePair in playersAdjList)

            {

                var currentNode = list.First;

​

                var newPlayer = keyValuePair.Key;

                var newPlayerAdjList = keyValuePair.Value;

​

                while (currentNode != null)

                {

                    if (newPlayerAdjList.Contains(currentNode.Value))

                    {

                        list.AddBefore(currentNode, newPlayer);

                        break;

                    }

                    currentNode = currentNode.Next;

                }

​

                if (currentNode == null)

                {

                    list.AddLast(newPlayer);

                }

            }

​

            return list;

        }

​

        /// <summary>

        /// This method checks if the graph is complete

        /// In a complete graph, number of edges should be equal to nC2 for n nodes.

        /// </summary>

        /// <returns></returns>

        private bool AreAllResultsRecorded()

        {

            var totalMatchCount = 0;

​

            foreach (var keyValuePair in playersAdjList)

            {

                totalMatchCount += keyValuePair.Value.Count;

            }

​

            var playersCount = playersAdjList.Keys.Count;

​

            return totalMatchCount == playersCount * (playersCount - 1) / 2;

        }

    }

​

    internal class InsufficientInputException : Exception

    {

        public InsufficientInputException(): base("Insufficient games data to determine ranking.")

        {

        }

    }

​

    internal class Parser

    {

        private readonly List<IExpressionParser> expressionParsers;

​

        public Parser()

        {

            expressionParsers = new List<IExpressionParser>

            {

                new LostToExpressionParser(),

                new WonAgainstExpressionParser()

            };

        }

​

        public bool TryParse(string expression, out Player winner, out Player loser)

        {

            winner = null;

            loser = null;

​

            foreach (var parser in expressionParsers)

            {

                if (parser.TryParse(expression, out winner, out loser))

                {

                    return true;

                }

            }

            return false;

        }

    }

​

    interface IExpressionParser

    {

        bool TryParse(string expression, out Player winner, out Player Loser);

    }

​

    abstract class SimpleExpressionParser : IExpressionParser

    {

        private readonly string[] conditionWords;

​

        protected SimpleExpressionParser(params string[] args)

        {

            if (args == null || args.Length == 0)

            {

                throw new ArgumentException("Parser requires at least one word representing the condition");

            }

​

            conditionWords = args;

        }

​

        public abstract bool TryParse(string expression, out Player winner, out Player loser);

​

        protected bool TryParseTokens(string expression, out string firstToken, out string lastToken)

        {

            firstToken = null;

            lastToken = null;

​

            if (string.IsNullOrWhiteSpace(expression))

            {

                return false;

            }

​

            var tokens = expression.ToLower().Split(null);

​

            if (tokens.Length != conditionWords.Length + 2)

            {

                return false;

            }

​

            var i = 1;

            foreach (var conditionWord in conditionWords)

            {

                if (tokens[i] != conditionWord)

                {

                    return false;

                }

                i++;

            }

​

            firstToken = tokens[0];

            lastToken = tokens[tokens.Length - 1];

            return true;

        }

    }

​

    class LostToExpressionParser : SimpleExpressionParser

    {

        public LostToExpressionParser() : base("lost", "to")

        {

        }

​

        public override bool TryParse(string expression, out Player winner, out Player loser)

        {

            winner = null;

            loser = null;

​

            string firstPlayer;

            string secondPlayer;

​

            if (TryParseTokens(expression, out firstPlayer, out secondPlayer))

            {

                winner = Player.GetPlayer(secondPlayer);

                loser = Player.GetPlayer(firstPlayer);

                return true;

            }

​

            return false;

        }

    }

​

    class WonAgainstExpressionParser : SimpleExpressionParser

    {

        public WonAgainstExpressionParser():base("won", "against")

        {

        }

​

        public override bool TryParse(string expression, out Player winner, out Player loser)

        {

            winner = null;

            loser = null;

​

            string firstPlayer;

            string secondPlayer;

​

​

            if (TryParseTokens(expression, out firstPlayer, out secondPlayer))

            {

                winner = Player.GetPlayer(firstPlayer);

                loser = Player.GetPlayer(secondPlayer);

                return true;

            }

​

            return false;

        }

    }

​

    internal class Player

    {

        private static readonly Dictionary<string, Player> Players = new Dictionary<string, Player>(); 

        public string Name { get; private set; }

​

        private Player()

        {

        }

​

        public static Player GetPlayer(string name)

        {

            name = name.Trim().ToLower();

​

            if (string.IsNullOrWhiteSpace(name))

            {

                throw new ArgumentException("Name cannot be empty");

            }

​

            if (!Players.ContainsKey(name))

            {

                Players.Add(name, new Player {Name = name});

            }

            return Players[name];

        }

    }