Its Friday~

Project Euler problem 85~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The area of the grid with the nearest solution: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(brute_force_with_limited_range_using_formula);
  9: 
 10:             Console.WriteLine("press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// x(number of triangles) = 1/4 m n (m+1) (n+1) where m and n are rows and columns
 16:         /// so roughly m^2 n^2 = 8mil that gives m*n around 2828ish so set range for m and n to be (1..to 100)
 17:         /// and it works!
 18:         /// http://www.mathhelpforum.com/math-help/other-topics/132725-number-squares-rectangles-grid.html
 19:         /// </summary>
 20:         static int brute_force_with_limited_range_using_formula()
 21:         {
 22:             var target = 2000000;
 23:             var delta = target;
 24:             var m1 = 0;
 25:             var n1 = 0;
 26:             for (int m = 100; m >= 1; m--)
 27:             {
 28:                 for (int n = 1; n < m; n++)
 29:                 {
 30:                     var sum = m * n * (m + 1) * (n + 1) / 4;
 31:                     var diff = Math.Abs(sum - target);
 32:                     if (delta > diff)
 33:                     {
 34:                         delta = diff;
 35:                         m1 = m;
 36:                         n1 = n;
 37:                     }
 38:                 }
 39:             }
 40:             return m1 * n1;
 41:         }
 42: 
 43:         static Stopwatch stopwatch = new Stopwatch();
 44:         static void TestBenchSetup()
 45:         {
 46:             // Uses the second Core or Processor for the Test
 47:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
 48:             // Prevents "Normal" processes from interrupting Threads
 49:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
 50:             // Prevents "Normal" Threads from interrupting this thread
 51:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
 52:         }
 53:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
 54:         static void TestBenchLoader(Func<int> test_method)
 55:         {
 56:             stopwatch.Reset();
 57:             stopwatch.Start();
 58:             long result = 0;
 59:             long avg_tick = 0;
 60:             long avg_ms = 0;
 61:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms
 62:             // stabilizes the CPU cache and pipeline.
 63:             {
 64:                 result = test_method(); // Warmup
 65:             }
 66:             stopwatch.Stop();
 67:             for (int repeat = 0; repeat < 20; ++repeat)
 68:             {
 69:                 stopwatch.Reset();
 70:                 stopwatch.Start();
 71:                 result = test_method();
 72:                 stopwatch.Stop();
 73:                 avg_tick += stopwatch.ElapsedTicks;
 74:                 avg_ms += stopwatch.ElapsedMilliseconds;
 75:             }
 76:             avg_tick = avg_tick / 20;
 77:             avg_ms = avg_ms / 20;
 78:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
 79:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
 80:         }
 81:     }

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