- How do you start development of a game?
- Splitting into files – how much splitting?
- New to creating AI – where to start?
- UI design examples?
- How to build and fight simultaneously in Starcraft 2
- .NET Framework – Any way to get Dictionary<> to be a little faster?
- Divide grid (2D array) into random shaped parts?
- Find the Longest Path
- P versus NP
- A Classic of Soviet Engineering – The Typhoon-class sub
- Ask HN: If P = NP, what does it mean?
- Ask HN: Why did Twitter succeed?
- Who Needs University? The Best Nettuts+ Screencast Training Courses
- Something You May Not Know About the Switch Statement in C/C++
- Improving Your Audio: Hardware Edition
- PicFx – Windows Phone Picture Effects Application – Part 1
- Simple TriggerAction for docking using GridSplitters
- How to Post Code To Your Blog and other Religious Arguments
- Everybody thinks about garbage collection the wrong way

`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