.Net/C#/C++/GameDev/Aglorithm/and more…

Project Euler problem 94~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The sum of the perimeters of all almost equilateral triangles: ");
  6: 
  7:             TestBenchLoader(multithreaded_brute_force_test_all_possible_bases);
  8:             TestBenchSetup();
  9:             TestBenchLoader(generate_pythagorean_triplets_to_construct_and_test_triangles);
 10: 
 11:             Console.WriteLine("Press any key to exit");
 12:             Console.ReadKey();
 13:         }
 14: 
 15:         /// <summary>
 16:         /// basically test all the base from 6 to 1billion/3 to see if a triangle can be formed that matched problem's criteria
 17:         /// this way is painfully slow. even the multithreaded version is extremely slow
 18:         /// </summary>
 19:         static long multithreaded_brute_force_test_all_possible_bases()
 20:         {
 21:             var THREAD_COUNT = Environment.ProcessorCount - 1;
 22:             var results = new long[THREAD_COUNT];
 23:             var wait_handles = Enumerable.Range(0, THREAD_COUNT).Select(w => new AutoResetEvent(false)).ToArray();
 24: 
 25:             for (int i = 0; i < THREAD_COUNT; i++)
 26:             {
 27:                 ThreadPool.QueueUserWorkItem(o =>
 28:                     {
 29:                         var nth = (int)o;
 30:                         var off_set = nth * 2;
 31:                         var steps = THREAD_COUNT * 2;
 32:                         var max = 1000000000 / 3;
 33:                         long a, b, h, hh, partial_result;
 34:                         for (a = 6 + off_set, partial_result = 0; a < max; a += steps)
 35:                         {
 36:                             b = a + 1;
 37:                             hh = b * b - a * a / 4;
 38:                             h = (long)Math.Sqrt(hh);
 39: 
 40:                             if (h * h == hh)
 41:                                 partial_result += (b + b + a);
 42: 
 43:                             b = a - 1;
 44:                             hh = b * b - a * a / 4;
 45:                             h = (long)Math.Sqrt(hh);
 46:                             if (h * h == hh)
 47:                                 partial_result += (b + b + a);
 48:                         }
 49:                         results[nth] = partial_result;
 50:                         wait_handles[nth].Set();
 51:                     }, i);
 52:             }
 53: 
 54:             long result = 0;
 55:             for (int i = 0; i < THREAD_COUNT; i++)
 56:             {
 57:                 wait_handles[i].WaitOne();
 58:                 result += results[i];
 59:             }
 60:             return result;
 61:         }
 62: 
 63:         /// <summary>
 64:         /// basically using the Parent/child relationships method to generate pythagorean triplets, which is a
 65:         /// right triangle, and two of the same triangle can be used to form a new triangle, which is to be tested to
 66:         /// see if it is an "almost equilateral triangle".
 67:         /// the key point is that, since the Parent/child relationships method would create 3 more triplets from a 
 68:         /// parent triplet. By only using the parent triplets can be used to form "almost equilateral triangle" to generate next set
 69:         /// of children triplets, it becomes a lot more manageable since the upper bound is 1 billion.
 70:         /// as for why this works, i am not sure o.0
 71:         /// </summary>
 72:         static long generate_pythagorean_triplets_to_construct_and_test_triangles()
 73:         {
 74:             long total = 0;
 75:             Action<int, int, int> trans = null;
 76:             trans = (a, b, c) =>
 77:             {
 78:                 var t_base = 0;
 79:                 var t_side = 0;
 80:                 var is_valid = false;
 81:                 // the following if-else(s) are used to find out which of a,b,c is the smallest(for base), 
 82:                 // and largest(for side)
 83:                 if (a <= b && a <= c)
 84:                 {
 85:                     t_base = 2 * a;
 86:                     if (b <= c)
 87:                     {
 88:                         // test the condition of "the third differs by no more than one unit"
 89:                         is_valid = (c == t_base + 1 || c == t_base - 1); 
 90:                         t_side = c;
 91:                     }
 92:                     else
 93:                     {
 94:                         is_valid = (b == t_base + 1 || b == t_base - 1);
 95:                         t_side = b;
 96:                     }
 97:                 }
 98:                 else if (b <= a && b <= c)
 99:                 {
100:                     t_base = 2 * b;
101:                     if (a <= c)
102:                     {
103:                         is_valid = (c == t_base + 1 || c == t_base - 1);
104:                         t_side = c;
105:                     }
106:                     else
107:                     {
108:                         is_valid = (a == t_base + 1 || a == t_base - 1);
109:                         t_side = a;
110:                     }
111:                 }
112:                 else
113:                 {
114:                     t_base = 2 * c;
115:                     if (a <= b)
116:                     {
117:                         is_valid = (b == t_base + 1 || b == t_base - 1);
118:                         t_side = b;
119:                     }
120:                     else
121:                     {
122:                         is_valid = (a == t_base + 1 || a == t_base - 1);
123:                         t_side = a;
124:                     }
125:                 }
126:                 if (is_valid == true)
127:                 {
128:                     var perimeter = t_side * 2 + t_base;
129:                     if (perimeter >= 1000000000) return;
130:                     total += perimeter;
131:                     trans(a - 2 * b + 2 * c, 2 * a - b + 2 * c, 2 * a - 2 * b + 3 * c);
132:                     trans(a + 2 * b + 2 * c, 2 * a + b + 2 * c, 2 * a + 2 * b + 3 * c);
133:                     trans(-a + 2 * b + 2 * c, -2 * a + b + 2 * c, -2 * a + 2 * b + 3 * c);
134:                 }
135:             };
136:             // call the function to kick start the process, using the first Pythagorean Triple as initial seed
137:             trans(3, 4, 5);
138:             // return the result
139:             return total;
140:         }
141: 
142:         static Stopwatch stopwatch = new Stopwatch();
143:         static void TestBenchSetup()
144:         {
145:             // Uses the second Core or Processor for the Test
146:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
147:             // Prevents "Normal" processes from interrupting Threads
148:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
149:             // Prevents "Normal" Threads from interrupting this thread
150:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
151:         }
152:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
153:         static void TestBenchLoader(Func<long> test_method)
154:         {
155:             stopwatch.Reset();
156:             stopwatch.Start();
157:             long result = 0;
158:             long avg_tick = 0;
159:             long avg_ms = 0;
160:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
161:             // stabilizes the CPU cache and pipeline.
162:             {
163:                 result = test_method(); // Warmup
164:             }
165:             stopwatch.Stop();
166:             for (int repeat = 0; repeat < 20; ++repeat)
167:             {
168:                 stopwatch.Reset();
169:                 stopwatch.Start();
170:                 result = test_method();
171:                 stopwatch.Stop();
172:                 avg_tick += stopwatch.ElapsedTicks;
173:                 avg_ms += stopwatch.ElapsedMilliseconds;
174:             }
175:             avg_tick = avg_tick / 20;
176:             avg_ms = avg_ms / 20;
177:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
178:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
179:         }
180:     }

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