GameDev/.NET/Algorithm/C++/and more…

Project Euler problem 82~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The minimal path sum, in matrix.txt: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(using_dynamic_programming);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// the idea is that when moving from one cell to another cell to the right(col+1), if that another cell
 16:         /// is the start of the minimum path from col+1 to end of the matrix wall(it can be any cell alone the wall),
 17:         /// then the path from the cell to end of the wall is the minimum path.
 18:         /// if this is done interatively, then eventually the the minimum path from start of the matrix wall to end of
 19:         /// matrix wall can be calculated. really similar to problem 18 and 81.
 20:         /// </summary>
 21:         static int using_dynamic_programming()
 22:         {
 23:             var len = 80;
 24:             var cache = new int[len, len];
 25:             var map = new int[len, len];
 26:             var row = 0;
 27:             var col = 0;
 28:             foreach (var line in File.ReadAllLines("matrix.txt"))
 29:             {
 30:                 col = 0;
 31:                 foreach (var num in line.Split(new char[] { ',' }))
 32:                 {
 33:                     map[row, col++] = Convert.ToInt32(num);
 34:                 }
 35:                 row++;
 36:             }
 37:             var tmp = new int[len];
 38:             var min = 0;
 39:             for (col = len - 2; col >= 0; col--)
 40:             {
 41:                 for (row = 0; row < len; row++)
 42:                 {
 43:                     min = map[row, col + 1];  // since the travel path can be vertical, the following two for loops calculates
 44:                     var accum = 0;            // vertical travel costs
 45:                     for (int i = row - 1; i >= 0; i--)
 46:                     {
 47:                         accum += map[i, col];
 48:                         min = Math.Min(min, accum + map[i, col + 1]);
 49:                     }
 50:                     accum = 0; // accumulate the vertical travel cost
 51:                     for (int i = row + 1; i < len; i++)
 52:                     {
 53:                         accum += map[i, col];
 54:                         min = Math.Min(min, accum + map[i, col + 1]);
 55:                     }
 56:                     tmp[row] = min + map[row, col]; // cant just update the cell with min value yet, since the original still needed
 57:                 }                                   // by others
 58:                 for (int i = 0; i < len; i++)
 59:                 {
 60:                     map[i, col] = tmp[i];  // now the cell value can be safely updated with min cost
 61:                 }
 62:             }
 63:             min = int.MaxValue;
 64:             for (int i = 0; i < len; i++) // so col[0..len-1] would contain the minimum cost of col[i] to some cell at end of the matrix 
 65:             {
 66:                 if (min > map[i, 0])
 67:                     min = map[i, 0];
 68:             }
 69:             return min;
 70:         }
 71: 
 72:         static Stopwatch stopwatch = new Stopwatch();
 73:         static void TestBenchSetup()
 74:         {
 75:             // Uses the second Core or Processor for the Test
 76:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
 77:             // Prevents "Normal" processes from interrupting Threads
 78:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
 79:             // Prevents "Normal" Threads from interrupting this thread
 80:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
 81:         }
 82:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
 83:         static void TestBenchLoader(Func<int> test_method)
 84:         {
 85:             stopwatch.Reset();
 86:             stopwatch.Start();
 87:             long result = 0;
 88:             long avg_tick = 0;
 89:             long avg_ms = 0;
 90:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms
 91:             // stabilizes the CPU cache and pipeline.
 92:             {
 93:                 result = test_method(); // Warmup
 94:             }
 95:             stopwatch.Stop();
 96:             for (int repeat = 0; repeat < 20; ++repeat)
 97:             {
 98:                 stopwatch.Reset();
 99:                 stopwatch.Start();
100:                 result = test_method();
101:                 stopwatch.Stop();
102:                 avg_tick += stopwatch.ElapsedTicks;
103:                 avg_ms += stopwatch.ElapsedMilliseconds;
104:             }
105:             avg_tick = avg_tick / 20;
106:             avg_ms = avg_ms / 20;
107:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
108:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
109:         }
110:     }

c++

Advertisements
This entry was posted in Programming. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s