Skip to content

Instantly share code, notes, and snippets.

/euler-83.cs Secret

Created Dec 30, 2014
Embed
What would you like to do?
/* 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();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment