santaTravels.cs

	public static class TravelingSalesman
	{
		private static readonly Dictionary<string, Dictionary<string, int>> _connections =
			new Dictionary<string, Dictionary<string, int>>(); 

		public static void PopulateConnections()
		{
			if (_connections.Any())
				return;

			var input = File.ReadAllLines("Input/TravelingSalesman.txt");

			foreach (var s in input)
			{
				var line = s.Split(new [] {' '}, StringSplitOptions.RemoveEmptyEntries);

				var from = line[0];
				var to = line[2];
				var cost = int.Parse(line[4]);

				if (!_connections.ContainsKey(from))
					_connections.Add(from, new Dictionary<string, int>());

				_connections[from].Add(to, cost);

				if (!_connections.ContainsKey(to))
					_connections.Add(to, new Dictionary<string, int>());

				_connections[to].Add(from, cost);
			}
		}
		public static IEnumerable<T[]> Permutations<T>(T[] values, int fromInd = 0)
		{
			if (fromInd + 1 == values.Length)
				yield return values;
			else
			{
				foreach (var v in Permutations(values, fromInd + 1))
					yield return v;

				for (var i = fromInd + 1; i < values.Length; i++)
				{
					SwapValues(values, fromInd, i);
					foreach (var v in Permutations(values, fromInd + 1))
						yield return v;
					SwapValues(values, fromInd, i);
				}
			}
		}

		private static void SwapValues<T>(T[] values, int pos1, int pos2)
		{
			if (pos1 != pos2)
			{
				T tmp = values[pos1];
				values[pos1] = values[pos2];
				values[pos2] = tmp;
			}
		}

		public static int CalculateLowestTravelCost()
		{
			int currentLowest = int.MaxValue;

			foreach (var p in Permutations(_connections.Keys.ToArray()))
			{
				string previous = null;
				var totalCost = 0;

				foreach (var c in p)
				{
					if (previous != null)
						totalCost += _connections[previous][c];

					previous = c;
				}

				currentLowest = Math.Min(totalCost, currentLowest);
			}

			return currentLowest;
		}

		public static int CalculateLargestTravelCost()
		{
			int currentMostExpensive = int.MinValue;

			foreach (var p in Permutations(_connections.Keys.ToArray()))
			{
				string previous = null;
				var totalCost = 0;

				foreach (var c in p)
				{
					if (previous != null)
						totalCost += _connections[previous][c];

					previous = c;
				}

				currentMostExpensive = Math.Max(totalCost, currentMostExpensive);
			}

			return currentMostExpensive;
		}
	}