using System.Diagnostics;

namespace MTGOImporter
{
    internal class Program
    {
        private string[] _allCards = new string[]
        {
            "Plains",
            "Mountain",
            "Island",
            "Swamp",
            "Forest",
            "Up the Beanstalk",
            "Lórien Revealed",
            "Fire/Ice",
            "Fireblast",
            "Fireball"
        };

        static void Main(string[] args)
        {
            var closestCard1 = FindClosestCard("Fire // Ice");
            Debug.Assert(closestCard1 == "Fire/Ice");

            var closestCard2 = FindClosestCard("L356ie Revealed");
            Debug.Assert(closestCard2 == "Lórien Revealed");

            var closestCard3 = FindClosestCard("Plains");
            Debug.Assert(closestCard3 == "Plains");

            var closestCard4 = FindClosestCard("Forest");
            Debug.Assert(closestCard4 == "Forest");
        }

        private static string FindClosestCard(string input)
        {
            string[] cardList = { "Plains", "Mountain", "Island", "Swamp", "Forest", "Up the Beanstalk", "Lórien Revealed", "Fire/Ice", "Fireblast", "Fireball" };
            string closestCard = string.Empty;
            int closestDistance = int.MaxValue;

            foreach (string card in cardList)
            {
                int distance = ComputeLevenshteinDistance(card, input);

                if (distance < closestDistance)
                {
                    closestDistance = distance;
                    closestCard = card;
                }
            }

            return closestCard;
        }

        private static int ComputeLevenshteinDistance(string s, string t)
        {
            int[,] distance = new int[s.Length + 1, t.Length + 1];

            for (int i = 0; i <= s.Length; i++)
            {
                distance[i, 0] = i;
            }
            for (int j = 0; j <= t.Length; j++)
            {
                distance[0, j] = j;
            }

            for (int j = 1; j <= t.Length; j++)
            {
                for (int i = 1; i <= s.Length; i++)
                {
                    if (s[i - 1] == t[j - 1])
                    {
                        distance[i, j] = distance[i - 1, j - 1];
                    }
                    else
                    {
                        distance[i, j] = Math.Min(distance[i - 1, j] + 1, Math.Min(distance[i, j - 1] + 1, distance[i - 1, j - 1] + 1));
                    }
                }
            }

            return distance[s.Length, t.Length];
        }
    }
}