Concurrency/DRY/jQuery/UX/and more…

Project Euler problem 51~

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The smallest prime that is part of an eight prime value family");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(test_each_6_digits_prime_to_find_first_match);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// base on the question, 5-d number with 2-replacement part produces 7 primes
 16:         /// so its worth to try 6-d number with 3-replacement part to see if it produces 8 primes
 17:         /// i guess it does!
 18:         /// 1. generate a seive prime map up to 1 mil
 19:         /// 2. for each 6-digit prime number, see if it has any repeating number of 0,1,2
 20:         ///    (the reason for this is because we need at least 8 produced primes, so the number has to start with
 21:         ///     at least one of 1, 2 or 3)
 22:         /// 3. if 2. holds true, it would fill array (pos) with the index of repeating numbers,
 23:         ///    replacing each number with 1~10 and see if the count goes to 8
 24:         /// 4. return the 1st answer
 25:         /// </summary>
 26:         /// <returns></returns>
 27:         static int test_each_6_digits_prime_to_find_first_match()
 28:         {
 29:             var bound = 1000000;
 30:             var primes = GetPrimes(bound);
 31:             var len = 6;
 32:             var target = 8;
 33:             var master = new int[len];
 34:             var worker = new int[len];
 35:             var pos = new int[len];
 36:             for (int i = 100001; i < bound; i += 2)
 37:             {
 38:                 if (primes[i] == false)
 39:                 {
 40:                     num_to_int_array(i, master, len);
 41:                     if (look_for_same_digits(0, master, len, pos)
 42:                         || look_for_same_digits(1, master, len, pos)
 43:                         || look_for_same_digits(2, master, len, pos))
 44:                     {
 45:                         copy_int_arrays(master, worker, len);
 46:                         if (test_all_digits(worker, primes, len, pos, target))
 47:                             return i;
 48:                     }
 49:                 }
 50:             }
 51:             return 0;
 52:         }
 53: 
 54:         static bool test_all_digits(int[] worker, bool[] primes, int len, int[] pos, int target)
 55:         {
 56:             var count1 = 0;
 57:             var count2 = 0;
 58:             int num, i, j;
 59:             var limit = 10 - target;
 60:             for (i = 0; i < 10; i++)
 61:             {
 62:                 for (j = 0; j < 3; j++)
 63:                 {
 64:                     worker[pos[j]] = i;
 65:                 }
 66:                 if (worker[0] == 0)
 67:                     continue;
 68: 
 69:                 num = int_array_to_num(worker, len);
 70: 
 71:                 if (primes[num] == false)
 72:                     count1++;
 73:                 else
 74:                     count2++;
 75: 
 76:                 if (count2 > limit)
 77:                     break;
 78:             }
 79:             if (count1 == target)
 80:                 return true;
 81:             return false;
 82:         }
 83: 
 84:         static bool look_for_same_digits(int d, int[] array, int len, int[] pos)
 85:         {
 86:             var pos_count = 0;
 87:             while (len != 0)
 88:             {
 89:                 if (array[--len] == d)
 90:                     pos[pos_count++] = len;
 91:             }
 92:             if (pos_count == 3)
 93:                 return true;
 94:             else
 95:                 return false;
 96:         }
 97: 
 98:         static void num_to_int_array(int n, int[] array, int len)
 99:         {
100:             while (n != 0)
101:             {
102:                 n = Math.DivRem(n, 10, out array[--len]);
103:             }
104:         }
105: 
106:         static int int_array_to_num(int[] array, int len)
107:         {
108:             var tens = 1;
109:             var n = 0;
110:             while (len != 0)
111:             {
112:                 n += (array[--len] * tens);
113:                 tens *= 10;
114:             }
115:             return n;
116:         }
117: 
118:         static void copy_int_arrays(int[] master, int[] clone, int len)
119:         {
120:             while (len != 0)
121:             {
122:                 clone[--len] = master[len];
123:             }
124:         }
125: 
126:         static bool[] GetPrimes(int max)
127:         {
128:             var bound = (int)Math.Sqrt(max);
129:             bool[] primes = new bool[max];
130:             primes[0] = true;
131:             primes[1] = true;
132:             int s, m;
133:             for (s = 2; s <= bound; s++)
134:             {
135:                 if (primes[s] == false)
136:                 {
137:                     for (m = s * s; m < max; m += s)
138:                     {
139:                         primes[m] = true;
140:                     }
141:                 }
142:             }
143:             return primes;
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:             var 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