Project Euler problem 28~

`1: class Program`

2: {3: static void Main(string[] args)4: {`5: Console.WriteLine("The sum of the numbers on the diagonals in a 1001 by 1001 spiral:");`

6:7: TestBenchSetup();8: TestBenchLoader(traverse_matrix_in_spiral_fashion);9: TestBenchLoader(arithmetic_calculate_corners_for_each_rim_with_formula);10:`11: Console.WriteLine("Press any key to exit");`

12: Console.ReadKey();13: }14:`15: /// <summary>`

`16: /// 1. basically traverse the matrix starting from top right corner`

`17: /// in counter-clockwise spiral fahsaion and populate the value for each`

`18: /// cell advanced.`

`19: /// 2. starting value is n*n, which n is the width and height of the matrix`

`20: /// 3. after matrix is populated with n*n, n*n-1, n*n-2,...,1. another loop is called`

`21: /// to get the cells lie within the diagonal line`

`22: /// 4. the top right corner value is always n*n in the domain of this problem`

`23: /// </summary>`

`24: /// <returns></returns>`

25: static int traverse_matrix_in_spiral_fashion()26: {27: var len = 1001;28: var map = new int[len, len];29: var num = len * len;30: var row = 0;31: var col = len - 1;`32: var direction = 0; //0:left 1:down 2:right 3:up`

33: while (true)34: {`35: if (num <= 1)`

`36: break;`

37:`38: switch (direction)`

39: {`40: case 0:`

`41: if (col > 0 && map[row, col - 1] == 0)`

42: map[row, col--] = num--;`43: else`

44: direction = 1;`45: break;`

`46: case 1:`

`47: if (row < len - 1 && map[row + 1, col] == 0)`

48: map[row++, col] = num--;`49: else`

50: direction = 2;`51: break;`

`52: case 2:`

`53: if (col < len - 1 && map[row, col + 1] == 0)`

54: map[row, col++] = num--;`55: else`

56: direction = 3;`57: break;`

`58: case 3:`

`59: if (row > 0 && map[row - 1, col] == 0)`

60: map[row--, col] = num--;`61: else`

62: direction = 0;`63: break;`

64: }65: }66: var sum = 1;67: for (int i = 0; i < len; i++)68: {69: sum += map[i, i];70: sum += map[i, len - 1 - i];71: }`72: return sum;`

73: }74:`75: /// <summary>`

`76: /// 1. since the top right corner is n*n`

`77: /// 2. and top left corner is top right corner minus the len plus 1`

`78: /// 3. so it becomes (NE = north-east corner, and so on...)`

`79: /// NE: n^2, NW: n^2-n+1, SW: n^2-2n+2, SE: n^2-3n+3`

`80: /// 4. so formula can be formed: n^2-cn+c, where c is corner(starting with NE=0, NW=1,...)`

`81: /// 5. thinking the matrix is composed of matrices, the question's sample matrix is`

`82: /// composed of matrix with len=5 and len=3;`

`83: /// 6. so starting with len=n, the next inner matrix will have len-2, so on...`

`84: /// 7. by calculating the corners of each matrix, and sum them up, we get the answer to this`

`85: /// problem!`

`86: /// </summary>`

`87: /// <returns></returns>`

88: static int arithmetic_calculate_corners_for_each_rim_with_formula()89: {90: var len = 1001;91: var sum = 1;92: var corner = 0;93: Func<int, int, int> formula = (n, c) => n * n - c * n + c;94: for (int i = 3; i <= len; i += 2)95: {96: corner = 0;`97: sum += formula(i, corner++); // NE corner`

`98: sum += formula(i, corner++); // NW`

`99: sum += formula(i, corner++); // SW`

`100: sum += formula(i, corner++); // SE`

101: }`102: return sum;`

103: }104:105: static Stopwatch stopwatch = new Stopwatch();106: static void TestBenchSetup()107: {`108: // Uses the second Core or Processor for the Test`

`109: Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);`

`110: // Prevents "Normal" processes from interrupting Threads`

111: Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;`112: // Prevents "Normal" Threads from interrupting this thread`

113: Thread.CurrentThread.Priority = ThreadPriority.Highest;114: }`115: // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx`

116: static void TestBenchLoader(Func<int> test_method)117: {118: stopwatch.Reset();119: stopwatch.Start();120: var result = 0;`121: long avg_tick = 0;`

`122: long avg_ms = 0;`

123: while (stopwatch.ElapsedMilliseconds < 1200) // A Warmup of 1000-1500 ms`124: // stabilizes the CPU cache and pipeline.`

125: {`126: result = test_method(); // Warmup`

127: }128: stopwatch.Stop();129: for (int repeat = 0; repeat < 20; ++repeat)130: {131: stopwatch.Reset();132: stopwatch.Start();133: result = test_method();134: stopwatch.Stop();135: avg_tick += stopwatch.ElapsedTicks;136: avg_ms += stopwatch.ElapsedMilliseconds;137: }138: avg_tick = avg_tick / 20;139: avg_ms = avg_ms / 20;140: Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",141: test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));142: }143: }

Advertisements