Saturday’s problem

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
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