- Got to see this: Stackoverflow, HTML by Regex, topmost answer
- UPS was founded by 2 teenagers, 1 Bicycle, and $100 borrowed from a friend
- Did Americans in 1776 have British accents?
- Youtube comments susceptible to XSS
- 10 Signs of Crappy PHP Software
- Basics of probability and statistics
- Ask HN: How obsessive are you with your code?
- So that’s how they do it!
- What a Difference 8 Years Makes (In Code), K Scott Allen
- One small silver lining of moving Boeing headquarters to Chicago

`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 formed41: {`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 included78: {79: if (map.ContainsKey(m_a) == false) // so depth can be either a or b80: map[m_a] = new List<int>();81: if (map.ContainsKey(m_b) == false) // so width can be either a or b82: 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