HTML/Hacks/C#/and more…

Project Euler problem 86~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The least value of M such that the number of solutions first exceeds one million: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(using_memoization_with_pythagorean_triple);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// basically for width(a), depth(b), and height(c)
 16:         /// counter(a+1) = all the combo when a = a+1 + previously calculated counter(a), thats why previous and current is used
 17:         /// Still, finding all the combo for a+1 is going to take a long time. so the generate_triplets() is used to limit
 18:         /// the search range
 19:         /// http://mathschallenge.net/index.php?section=problems&show=true&titleid=spider_fly_distance&full=true#solution
 20:         /// </summary>
 21:         static int using_memoization_with_pythagorean_triple()
 22:         {
 23:             var map = generate_triplets(5000);
 24:             var a = 0;
 25:             var b = 0;
 26:             var c = 0;
 27:             var bound = 0;
 28:             var counter = 0;
 29:             var previous = 0;
 30:             var current = 0;
 31:             while (counter < 1000000)
 32:             {
 33:                 a++;
 34:                 current = 0;
 35:                 if (map.ContainsKey(a) == true)
 36:                 {
 37:                     bound = a * 2;
 38:                     foreach (var num in map[a])
 39:                     {
 40:                         if (num <= bound) // counts how many ways that (b+c) = num can be formed
 41:                         {
 42:                             if (num > a)
 43:                             {
 44:                                 b = a;
 45:                                 c = num - a;
 46:                             }
 47:                             else
 48:                             {
 49:                                 b = num - 1;
 50:                                 c = 1;
 51:                             }
 52:                             while (b >= c)
 53:                             {
 54:                                 b--;
 55:                                 c++;
 56:                                 current++;
 57:                             }
 58:                         }
 59:                     }
 60:                 }
 61:                 counter = current + previous;
 62:                 previous = counter;
 63:             }
 64:             return a;
 65:         }
 66: 
 67:         static Dictionary<int, List<int>> generate_triplets(int max)
 68:         {
 69:             var map = new Dictionary<int, List<int>>();
 70:             Action<int, int, int> trans = null;
 71:             trans = (a, b, c) =>
 72:             {
 73:                 if (a <= max)
 74:                 {
 75:                     var m_a = a;
 76:                     var m_b = b;
 77:                     while (m_a <= max) // so here the multiples of the prime triplets are also included
 78:                     {
 79:                         if (map.ContainsKey(m_a) == false) // so depth can be either a or b
 80:                             map[m_a] = new List<int>();
 81:                         if (map.ContainsKey(m_b) == false) // so width can be either a or b
 82:                             map[m_b] = new List<int>();
 83:                         map[m_a].Add(m_b);
 84:                         map[m_b].Add(m_a);
 85:                         m_a += a;
 86:                         m_b += b;
 87:                     }
 88:                     trans(a - 2 * b + 2 * c, 2 * a - b + 2 * c, 2 * a - 2 * b + 3 * c);
 89:                     trans(a + 2 * b + 2 * c, 2 * a + b + 2 * c, 2 * a + 2 * b + 3 * c);
 90:                     trans(-a + 2 * b + 2 * c, -2 * a + b + 2 * c, -2 * a + 2 * b + 3 * c);
 91:                 }
 92:             };
 93:             trans(3, 4, 5);
 94:             return map;
 95:         }
 96: 
 97:         static Stopwatch stopwatch = new Stopwatch();
 98:         static void TestBenchSetup()
 99:         {
100:             // Uses the second Core or Processor for the Test
101:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
102:             // Prevents "Normal" processes from interrupting Threads
103:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
104:             // Prevents "Normal" Threads from interrupting this thread
105:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
106:         }
107:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
108:         static void TestBenchLoader(Func<int> test_method)
109:         {
110:             stopwatch.Reset();
111:             stopwatch.Start();
112:             var result = 0;
113:             long avg_tick = 0;
114:             long avg_ms = 0;
115:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
116:             // stabilizes the CPU cache and pipeline.
117:             {
118:                 result = test_method(); // Warmup
119:             }
120:             stopwatch.Stop();
121:             for (int repeat = 0; repeat < 20; ++repeat)
122:             {
123:                 stopwatch.Reset();
124:                 stopwatch.Start();
125:                 result = test_method();
126:                 stopwatch.Stop();
127:                 avg_tick += stopwatch.ElapsedTicks;
128:                 avg_ms += stopwatch.ElapsedMilliseconds;
129:             }
130:             avg_tick = avg_tick / 20;
131:             avg_ms = avg_ms / 20;
132:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
133:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
134:         }
135:     }

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