blah~

Project Euler problem 53~

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The values of  ^(n)C_(r), for 1 ≤ n  ≤ 100, are greater than one-million:");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(turn_every_number_into_prime_factors_for_easy_calculation);
  9:             TestBenchLoader(using_pascal_triangle_to_calculate_binomial_coefficients);
 10: 
 11:             Console.WriteLine("Press any key to exit");
 12:             Console.ReadKey();
 13:         }
 14: 
 15:         /// <summary>
 16:         /// test all the possible combination of n and r, then calling the factorial method to see if 
 17:         /// the sum is greater than 1mil.
 18:         /// n)C_(r) = 	
 19:         ///    n!
 20:         /// --------   (binomial coefficients)
 21:         /// r!(n−r)!
 22:         /// so end = the greater of r or (n-r) to be used to cancel out from n! so n*(n-1)*(n-2)....end
 23:         /// f = the lesser of r or (n-r), and it is the divisor
 24:         /// </summary>
 25:         /// <returns></returns>
 26:         static int turn_every_number_into_prime_factors_for_easy_calculation()
 27:         {
 28:             int n, r;
 29:             var count = 0;
 30:             var end = 0;
 31:             var f = 0;
 32:             var map = prime_factors_map();
 33:             var max = 101;
 34:             var factors = new int[max];
 35:             for (n = 23; n <= 100; n++)
 36:             {
 37:                 for (r = 1; r <= n; r++)
 38:                 {
 39:                     end = n - r > r ? n - r : r;
 40:                     f = n - r > r ? r : n - r;
 41:                     if (factorial(n, end + 1, f, map, factors, max))
 42:                         count++;
 43:                 }
 44:             }
 45:             return count;
 46:         }
 47: 
 48:         /// <summary>
 49:         /// turns out pascal triangle is awesome at solving this problem(from q's post)
 50:         /// see detail: http://mathforum.org/dr/math/faq/faq.pascal.triangle.html
 51:         /// </summary>
 52:         static int using_pascal_triangle_to_calculate_binomial_coefficients()
 53:         {
 54:             var bound = 101;
 55:             var pascal = new int[bound][];
 56:             int i, col, row, value;
 57:             var limit = 1000000;
 58:             var count = 0;
 59:             // 1. populate edges
 60:             for (i = 0; i < bound; i++)
 61:             {
 62:                 pascal[i] = new int[i + 1];
 63:                 pascal[i][0] = 1;
 64:                 pascal[i][i] = 1;
 65:             }
 66:             // 2. starting at 3rd row(1,x,1), and populate x value from x upper left and upper neighbor
 67:             //    and if x value is greater than 1mil, add 1 to count. the max value is kept at 1 mil + 1
 68:             for (row = 2; row < bound; row++)
 69:             {
 70:                 for (col = 1; col < row; col++)
 71:                 {
 72:                     value = pascal[row - 1][col - 1] + pascal[row - 1][col];
 73:                     pascal[row][col] = value > limit ? limit + 1 : value;
 74:                     if (value > limit)
 75:                         count++;
 76:                 }
 77:             }
 78:             return count;
 79:         }
 80: 
 81:         /// <summary>
 82:         /// basically turning every number into prime factors, and then cancel out all the divisor's factors from dividend's
 83:         /// factors, then calculate product of all the remaining factors and return false if it is less than 1 mil, true
 84:         /// otherwise
 85:         /// </summary>
 86:         static bool factorial(int start, int end, int div, List<List<int>> map, int[] factors, int max)
 87:         {
 88:             var i = 0;
 89:             var sum = 1;
 90:             for (i = 2; i < max; i++) //reset
 91:             {
 92:                 factors[i] = 0;
 93:             }
 94:             for (i = end; i <= start; i++) //add all the prime factors from dividend
 95:             {
 96:                 foreach (var factor in map[i])
 97:                 {
 98:                     factors[factor]++;
 99:                 }
100:             }
101:             for (i = 2; i <= div; i++) // substract all the prime factors from dividend
102:             {
103:                 foreach (var factor in map[i])
104:                 {
105:                     factors[factor]--;
106:                 }
107:             }
108:             for (i = 2; i < max; i++) // multiply all the remaining prime factors
109:             {
110:                 while (factors[i] > 0)
111:                 {
112:                     sum *= i;
113:                     factors[i]--;
114:                     if (sum > 1000000)
115:                         return true;
116:                 }
117:             }
118:             return sum > 1000000;
119:         }
120: 
121:         /// <summary>
122:         /// generate all the prime factors for number from 0 to 100
123:         /// </summary>
124:         static List<List<int>> prime_factors_map()
125:         {
126:             var len = 101;
127:             var map = new List<List<int>>();
128:             map.Add(new List<int>() { 0 });
129:             map.Add(new List<int>() { 1 });
130:             var primes = generate_primes(100);
131:             var num = 0;
132:             for (int i = 2; i < len; i++)
133:             {
134:                 var list = new List<int>();
135:                 num = i;
136:                 foreach (var prime in primes)
137:                 {
138:                     while (num % prime == 0)
139:                     {
140:                         list.Add(prime);
141:                         num /= prime;
142:                     }
143:                     if (num == 1)
144:                         break;
145:                 }
146:                 map.Add(list);
147:             }
148:             return map;
149:         }
150: 
151:         /// <summary>
152:         /// generate all the primes from 1 to max
153:         /// </summary>
154:         static List<int> generate_primes(int max)
155:         {
156:             var bound = (int)Math.Sqrt(max);
157:             bool[] primes = new bool[max];
158:             primes[0] = true;
159:             primes[1] = true;
160:             int s, m;
161:             for (s = 2; s <= bound; s++)
162:             {
163:                 if (primes[s] == false)
164:                 {
165:                     for (m = s * s; m < max; m += s)
166:                     {
167:                         primes[m] = true;
168:                     }
169:                 }
170:             }
171:             var result = new List<int>();
172:             for (s = 2; s < max; s++)
173:             {
174:                 if (primes[s] == false)
175:                     result.Add(s);
176:             }
177:             return result;
178:         }
179: 
180:         static Stopwatch stopwatch = new Stopwatch();
181:         static void TestBenchSetup()
182:         {
183:             // Uses the second Core or Processor for the Test
184:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
185:             // Prevents "Normal" processes from interrupting Threads
186:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
187:             // Prevents "Normal" Threads from interrupting this thread
188:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
189:         }
190:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
191:         static void TestBenchLoader(Func<int> test_method)
192:         {
193:             stopwatch.Reset();
194:             stopwatch.Start();
195:             var result = 0;
196:             long avg_tick = 0;
197:             long avg_ms = 0;
198:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
199:             // stabilizes the CPU cache and pipeline.
200:             {
201:                 result = test_method(); // Warmup
202:             }
203:             stopwatch.Stop();
204:             for (int repeat = 0; repeat < 20; ++repeat)
205:             {
206:                 stopwatch.Reset();
207:                 stopwatch.Start();
208:                 result = test_method();
209:                 stopwatch.Stop();
210:                 avg_tick += stopwatch.ElapsedTicks;
211:                 avg_ms += stopwatch.ElapsedMilliseconds;
212:             }
213:             avg_tick = avg_tick / 20;
214:             avg_ms = avg_ms / 20;
215:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
216:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
217:         }
218:     }

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