euler-83.cs

/* Problem 82: Path Sum, 3 ways
 In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in bold red and is equal to 2297.
 Find the minimal path sum, in matrix.txt (right click and "Save Link/Target As..."), a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right by moving left, right, up, and down.
 */

public static void Main(string[] args)
{
	long answer = 0;								// standard variables
	Action<string> wl = Console.WriteLine;			// shortcut for printing to console
	Stopwatch sw = new Stopwatch(); sw.Start();		// for timing

	int iterations = 0;
	String[] numberRows = System.IO.File.ReadAllLines(@"E:\InputFiles\p081_matrix.txt");
	int l = numberRows.Length;
	// create matrix
	int[][] m = new int[l][];
	for (int i = 0; i < l; i++)
	{	// fill each line with a converted string->int array
		m[i] = Array.ConvertAll(numberRows[i].Split(','), a => Convert.ToInt32(a));
	}

	// start testdata
	//m = new int[5][] {
	//	new int[5]{131,673,234,103,18 },
	//	new int[5]{201,96,342,965,150 },
	//	new int[5]{630,803,746,422,111 },
	//	new int[5]{537,699,497,121,956 },
	//	new int[5]{805,732,524,37,331 }
	//};
	//l = 5;
	// end testdata

	int[][] d = new int[l][];	// distance matrix
	for (int i = 0; i < l; i++) { d[i] = new int[l]; } // initialize distance matrix
	wl("Starting matrix with " + l * l + " nodes");

	// Classic Dijkstra

	// Queue holds points that need to be examined
	// The tuple holds the x and y coordinate in the matrix
	Queue<Tuple<int, int>> q = new Queue<Tuple<int, int>>();

	// initialize
	d[0][0] = m[0][0];
	q.Enqueue(new Tuple<int, int>(0, 1));	// starting node
	q.Enqueue(new Tuple<int, int>(1, 0));	// starting node

	bool found = false;
	while (!found)
	{
		// exit (error) condition, empty queue but no result
		if (q.Count == 0) { found = true; wl("Exit: empty queue!"); break; }

		// dequeue current node
		var curTuple = q.Dequeue();
		int x = curTuple.Item1, y = curTuple.Item2;
		// get neighbours minPathWeight
		int upper = x > 0 && d[x - 1][y] !=0 ? d[x - 1][y] : Int32.MaxValue;
		int bottom = x < l - 2 && d[x + 1][y] !=0 ? d[x + 1][y] : Int32.MaxValue;
		int left = y > 0 && d[x][y - 1]!=0 ? d[x][y - 1] : Int32.MaxValue;
		int right = y < l - 1 && d[x][y + 1]!=0 ? d[x][y + 1] : Int32.MaxValue;

		// process node
		int minPathToThisNode = m[x][y] + Math.Min(Math.Min(upper, bottom), Math.Min(left, right));
		if (d[x][y] == 0 || d[x][y] > minPathToThisNode)
		{
			d[x][y] = minPathToThisNode;
			// enqueue all neighbours (if exists)
			if (x > 0) { q.Enqueue(new Tuple<int, int>(x - 1, y)); }
			if (x < l - 1) { q.Enqueue(new Tuple<int, int>(x + 1, y)); }
			if (y > 0) { q.Enqueue(new Tuple<int, int>(x, y-1)); }
			if (y < l-1) { q.Enqueue(new Tuple<int, int>(x, y + 1)); }
		}
		iterations++;

		//// print current calculated minimum paths
		//wl("== Iteration " + iterations);
		//for (int i = 0; i < l; i++) { wl(String.Join(",", d[i])); }
		//wl("-");
	}
	answer = d[l-1][l-1]; wl("End matrix in " + iterations + " iterations");

	sw.Stop();
	// Answer Euler 83: 425185 runs in 8 ms, with 105939 steps
	wl("Answer: " + answer); wl("Runtime in miliseconds: " + sw.ElapsedMilliseconds); Console.ReadKey();
}