Internet restoration: ETA 5/16/10, Operation Compcrapstic in action

Project Euler problem 60~

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The lowest sum for a set of five primes for which any two primes concatenate to produce another prime: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(using_martrix_to_narrow_down_scope_and_probing_for_primes_chain);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         static readonly int max = 100000000;
 15:         static readonly bool[] master_primes = generate_primes(max);
 16: 
 17:         /// <summary>
 18:         /// firstly i picked a arbitrary range of primes from 2 to 10000(glad it worked out)
 19:         /// then i created a matrix to find all the pairs of primes can be concat both way
 20:         /// then the probe recursive method is used to find if the prime_chain of length 5 exist
 21:         /// the first chain found should be the answer (and it is!)
 22:         /// sigh, the first solution to break 1-second calculation time (~3s on my pc)
 23:         /// prolly a lot of optimization can be done, but im done with this question for now, theres
 24:         /// way too many other things to do or prepare 😦
 25:         /// </summary>
 26:         /// <returns></returns>
 27:         static int using_martrix_to_narrow_down_scope_and_probing_for_primes_chain()
 28:         {
 29:             var primes = master_primes;
 30:             var size = (int)Math.Sqrt(max);
 31:             var matrix = new int[size, size];
 32:             int row, col;
 33:             for (row = 2; row < size; row++)
 34:             {
 35:                 for (col = 2; col < size; col++)
 36:                 {
 37:                     if (primes[row] == false && primes[col] == false && matrix[row, col] == 0)
 38:                     {
 39:                         if (concat_both_way(row, col, primes))
 40:                         {
 41:                             matrix[row, col] = 1;
 42:                             matrix[col, row] = 1;
 43:                         }
 44:                         else
 45:                         {
 46:                             matrix[row, col] = -1;
 47:                             matrix[col, row] = -1;
 48:                         }
 49:                     }
 50:                 }
 51:             }
 52:             var count = 5;
 53:             var accum = new int[count];
 54:             for (row = 3; row < size; row++)
 55:             {
 56:                 for (col = 3; col < size; col++)
 57:                 {
 58:                     if (matrix[row, col] == 1)
 59:                     {
 60:                         accum[5 - count] = row;
 61:                         if (probe(col, matrix, size, count - 1, accum))
 62:                             return accum.Sum();
 63:                     }
 64:                 }
 65:             }
 66:             return 0;
 67:         }
 68: 
 69:         /// <summary>
 70:         /// basically a recursive method that walk the matrix map for possible combination of prime numbers
 71:         /// and keeps drilling down to see if evetually we would have 5 primes that satisified the condition
 72:         /// specified by this problem
 73:         /// how it workrs:
 74:         /// 1. scanning the row givien by the row variable, 
 75:         /// 2. find the cell that has the following: 1 as value, produces primes by concat with all the number in accum array
 76:         /// 3. if 2. is true, add the column number to accum array, 
 77:         /// 4. if the count variable contain one:
 78:         ///    a. true: that means we found all the primes we need, return true.(the accum array now contains all the answer)
 79:         ///    b. false: that means we still need to find more primes,
 80:         ///                 call itself with the column number as row number, and reduce the count by 1.
 81:         /// 5. if the for loop is finished(if we ever get to this point), return false.
 82:         /// </summary>
 83:         /// <param name="row">the row that we want to sweep</param>
 84:         /// <param name="matrix">the map that contains all the possible primes combination</param>
 85:         /// <param name="size">the size(side length) of the matrix</param>
 86:         /// <param name="count">how many more primes to find</param>
 87:         /// <param name="accum">the array contains so far the primes found</param>
 88:         /// <returns>true if we reached the answer(all 5 primes found)</returns>
 89:         static bool probe(int row, int[,] matrix, int size, int count, int[] accum)
 90:         {
 91:             for (int col = 3; col < size; col++)
 92:             {
 93:                 if (matrix[row, col] == 1 && isGood(accum, matrix, accum.Length - count, col))
 94:                 {
 95:                     accum[accum.Length - count] = col;
 96:                     if (count == 1)
 97:                         return true;
 98: 
 99:                     return probe(col, matrix, size, count - 1, accum);
100:                 }
101:             }
102:             return false;
103:         }
104: 
105:         /// <summary>
106:         /// basically checks to see if all the number in accum array can form primes
107:         /// by concact with "num" in the array with any other in array
108:         /// </summary>
109:         /// <param name="accum">array contain numbers</param>
110:         /// <param name="matrix">prime pair matrix</param>
111:         /// <param name="count">current "length" of the array</param>
112:         /// <param name="num">the number to be check against</param>
113:         /// <returns></returns>
114:         static bool isGood(int[] accum, int[,] matrix, int count, int num)
115:         {
116:             for (int i = 0; i < count; i++)
117:             {
118:                 if (matrix[num, accum[i]] != 1)
119:                     return false;
120:             }
121:             return true;
122:         }
123: 
124:         /// <summary>
125:         /// baically checks if both n1-n2 and n2-n1 produce prime
126:         /// </summary>
127:         static bool concat_both_way(int n1, int n2, bool[] primes)
128:         {
129:             var num = 0;
130: 
131:             // tail
132:             num = n1 * (int)Math.Pow(10, (int)Math.Log10(n2) + 1) + n2;
133:             if (primes[num] == true)
134:                 return false;
135: 
136:             // head
137:             num = n2 * (int)Math.Pow(10, (int)Math.Log10(n1) + 1) + n1;
138:             if (primes[num] == true)
139:                 return false;
140: 
141:             return true;
142:         }
143: 
144:         static bool[] generate_primes(int max)
145:         {
146:             var bound = (int)Math.Sqrt(max);
147:             var primes = new bool[max];
148:             primes[0] = true;
149:             primes[1] = true;
150:             int s, m;
151:             for (s = 2; s <= bound; s++)
152:             {
153:                 if (primes[s] == false)
154:                 {
155:                     for (m = s * s; m < max; m += s)
156:                     {
157:                         primes[m] = true;
158:                     }
159:                 }
160:             }
161:             return primes;
162:         }
163: 
164:         static Stopwatch stopwatch = new Stopwatch();
165:         static void TestBenchSetup()
166:         {
167:             // Uses the second Core or Processor for the Test
168:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
169:             // Prevents "Normal" processes from interrupting Threads
170:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
171:             // Prevents "Normal" Threads from interrupting this thread
172:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
173:         }
174:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
175:         static void TestBenchLoader(Func<int> test_method)
176:         {
177:             stopwatch.Reset();
178:             stopwatch.Start();
179:             var result = 0;
180:             long avg_tick = 0;
181:             long avg_ms = 0;
182:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms
183:             // stabilizes the CPU cache and pipeline.
184:             {
185:                 result = test_method(); // Warmup
186:             }
187:             stopwatch.Stop();
188:             for (int repeat = 0; repeat < 20; ++repeat)
189:             {
190:                 stopwatch.Reset();
191:                 stopwatch.Start();
192:                 result = test_method();
193:                 stopwatch.Stop();
194:                 avg_tick += stopwatch.ElapsedTicks;
195:                 avg_ms += stopwatch.ElapsedMilliseconds;
196:             }
197:             avg_tick = avg_tick / 20;
198:             avg_ms = avg_ms / 20;
199:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
200:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
201:         }
202:     }

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