GameDev/Optimization/C#/Algorithm/and more…

Project Euler problem 106~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The number of subset pairs that needed to be tested for equality: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(using_check_condition_method_from_problem_105_with_modification);
  9:             TestBenchLoader(awesome_mathematical_analysis_with_DyckPath);
 10: 
 11:             Console.WriteLine("press any key to exit");
 12:             Console.ReadKey();
 13:         }
 14: 
 15:         /// <summary>
 16:         /// since the problem stated that condition ii is already satisifed, and the set contains
 17:         /// n strictly increasing elements.
 18:         /// to check condition i, only two set with equal number of elements would need to be checked
 19:         /// however, since the set is already in sorted order, the set which the ordinal element is always bigger than 
 20:         /// the other set can be omitted. The rest of the pairs are the one that need to be compare and checked
 21:         /// </summary>
 22:         static int using_check_condition_method_from_problem_105_with_modification()
 23:         {
 24:             var n = 12;
 25:             var mask = new int[n];
 26:             var map = new int[(int)Math.Pow(2, n), n];
 27:             var pos = n - 1;
 28:             var row = 0;
 29:             var col = 0;
 30: 
 31:             while (pos >= 0)
 32:             {
 33:                 if (mask[pos] == 0)
 34:                 {
 35:                     mask[pos] = 1;
 36:                     pos = n - 1;
 37: 
 38:                     for (int i = 0; i < n; i++)
 39:                     {
 40:                         if (mask[i] == 1)
 41:                         {
 42:                             map[row, i] = 1;
 43:                         }
 44:                     }
 45:                     row++;
 46:                 }
 47:                 else
 48:                 {
 49:                     mask[pos] = 0;
 50:                     pos--;
 51:                 }
 52:             }
 53: 
 54:             row = 0;
 55:             col = 0;
 56:             var cur = 0;
 57:             var bound = (int)Math.Pow(2, n) - 1;
 58:             var half = n / 2;
 59:             var result = 0;
 60:             var src_set = new int[n];
 61:             var dest_set = new int[n];
 62:             for (cur = 0; cur < bound; cur++)
 63:             {
 64:                 var cur_count = 0;
 65: 
 66:                 // reset the set that holds current start set
 67:                 src_set[0] = 0; src_set[1] = 0; src_set[2] = 0;
 68:                 src_set[3] = 0; src_set[4] = 0; src_set[5] = 0;
 69: 
 70:                 // copy the current start set col index
 71:                 for (col = 0; col < n; col++)
 72:                 {
 73:                     if (map[cur, col] == 1)
 74:                     {
 75:                         src_set[cur_count] = col;
 76:                         cur_count++;
 77:                     }
 78:                 }
 79: 
 80:                 // no point to continue if current start set size is greater than half of the whole set
 81:                 if (cur_count > half)
 82:                     continue;
 83: 
 84:                 for (row = cur + 1; row < bound; row++)
 85:                 {
 86:                     var count = 0;
 87:                     var disjoint = true;
 88:                     var possible = false;
 89:                     // reset the set that holds current destination set
 90:                     dest_set[0] = 0; dest_set[1] = 0; dest_set[2] = 0;
 91:                     dest_set[3] = 0; dest_set[4] = 0; dest_set[5] = 0;
 92: 
 93:                     for (col = 0; col < n; col++)
 94:                     {
 95:                         if (map[row, col] == 1)
 96:                         {
 97:                             if (map[cur, col] == 1 || count > cur_count)
 98:                             {
 99:                                 disjoint = false;
100:                                 break;
101:                             }
102:                             dest_set[count] = col;
103:                             // if there are any element in dest set that are bigger than src set
104:                             // which means dest set is not strickly smaller than src set and comparsion is needed
105:                             if (dest_set[count] > src_set[count])
106:                             {
107:                                 possible = true;
108:                             }
109:                             count++;
110:                         }
111:                     }
112:                     if (disjoint == true && possible == true && count > 1 && count == cur_count)
113:                     {
114:                         result++;
115:                     }
116:                 }
117:             }
118:             return result;
119:         }
120: 
121:         /// <summary>
122:         /// saw this awesome way of solving this problem using dyck path
123:         /// </summary>
124:         static int awesome_mathematical_analysis_with_DyckPath()
125:         {
126:             Func<int, int, int> C = (left, right) =>
127:                 {
128:                     if (right > left)
129:                         return 0;
130:                     var sum = 1;
131:                     for (int i = 1; i <= right; i++)
132:                     {
133:                         sum = sum * (left - right + i) / i;
134:                     }
135:                     return sum;
136:                 };
137: 
138:             int n = 12, result = 0;
139:             for (int a = 1; a <= n / 2; ++a)
140:             {
141:                 result += C(n, a * 2) * (C(a * 2, a) / 2 - C(2 * a, a) / (a + 1));
142:             }
143:             return result;
144:         }
145: 
146:         static Stopwatch stopwatch = new Stopwatch();
147:         static void TestBenchSetup()
148:         {
149:             // Uses the second Core or Processor for the Test
150:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
151:             // Prevents "Normal" processes from interrupting Threads
152:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
153:             // Prevents "Normal" Threads from interrupting this thread
154:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
155:         }
156:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
157:         static void TestBenchLoader(Func<int> test_method)
158:         {
159:             stopwatch.Reset();
160:             stopwatch.Start();
161:             long result = 0;
162:             long avg_tick = 0;
163:             long avg_ms = 0;
164:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms
165:             // stabilizes the CPU cache and pipeline.
166:             {
167:                 result = test_method(); // Warmup
168:             }
169:             stopwatch.Stop();
170:             for (int repeat = 0; repeat < 20; ++repeat)
171:             {
172:                 stopwatch.Reset();
173:                 stopwatch.Start();
174:                 result = test_method();
175:                 stopwatch.Stop();
176:                 avg_tick += stopwatch.ElapsedTicks;
177:                 avg_ms += stopwatch.ElapsedMilliseconds;
178:             }
179:             avg_tick = avg_tick / 20;
180:             avg_ms = avg_ms / 20;
181:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
182:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
183:         }
184:     }

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