C#4.0/LINQ/NoSQL/and more…

Project Euler problem 32~

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The sum of all numbers that can be written as pandigital products:");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(using_knuth_permutation_algorithm_to_generate_candidates);
  9:             TestBenchLoader(brute_force_with_limited_range_for_candidates);
 10: 
 11:             Console.WriteLine("Press any key to exit");
 12:             Console.ReadKey();
 13:         }
 14: 
 15:         /// <summary>
 16:         /// from this we can know the there can be only two possible way of making a number that fit 
 17:         /// this problem's description:
 18:         ///     1. 1-d * 4-d = 4-d
 19:         ///     2. 2-d * 3-d = 4-d
 20:         /// </summary>
 21:         static void bound_checking()
 22:         {
 23:             Console.WriteLine(string.Format("{0} * {1} = {2}", 9, 9, 9 * 9));
 24:             Console.WriteLine(string.Format("{0} * {1} = {2}", 9, 99, 9 * 99));
 25:             Console.WriteLine(string.Format("{0} * {1} = {2}", 9, 999, 9 * 999));
 26:             Console.WriteLine(string.Format("{0} * {1} = {2}", 9, 9999, 9 * 9999));
 27:             Console.WriteLine(string.Format("{0} * {1} = {2}", 9, 99999, 9 * 99999));
 28:             Console.WriteLine();
 29: 
 30:             Console.WriteLine(string.Format("{0} * {1} = {2}", 99, 99, 99 * 99));
 31:             Console.WriteLine(string.Format("{0} * {1} = {2}", 999, 99, 999 * 99));
 32:             Console.WriteLine(string.Format("{0} * {1} = {2}", 111, 111, 111 * 111));
 33:         }
 34: 
 35:         /// <summary>
 36:         /// using the code problem 24, which generates lexicographis permutation of given
 37:         /// range, a very efficient algorithm.
 38:         /// since there are limited combination how a pandigital can be made (see bound_checking())
 39:         /// the structure of the multiplicand/multiplier/product can only be the following:
 40:         ///     1. (1 digit) * (4 digit) = (4 digit) (or 4-1)
 41:         ///     2. (2 digit) * (3 digit) = (4 digit) (Or 3-2)
 42:         /// so it is fairly easy to test for each number generate by the permutation algorithm
 43:         /// </summary>
 44:         /// <returns></returns>
 45:         static int using_knuth_permutation_algorithm_to_generate_candidates()
 46:         {
 47:             var a = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 48:             var j = 0;
 49:             var l = 0;
 50:             var tmp = 0;
 51:             var len = a.Length;
 52:             var z = 0;
 53:             var p = 0;
 54:             var num = 0;
 55:             var rem = 0;
 56:             var cont = true;
 57:             var index = 0;
 58:             var result = new HashSet<int>();
 59:             while (true)
 60:             {
 61:                 //step 1. Find the largest index j such that a[j] < a[j + 1].
 62:                 for (j = len - 2; j >= 0; j--)
 63:                 {
 64:                     if (a[j] < a[j + 1])
 65:                         break;
 66:                 }
 67: 
 68:                 if (j == -1)
 69:                     break; // no more permutation, since no such index exist
 70: 
 71:                 //step 2. Find the largest index l such that a[j] < a[l]
 72:                 for (l = len - 1; l >= 0; l--)
 73:                 {
 74:                     if (a[j] < a[l])
 75:                         break;
 76:                 }
 77: 
 78:                 //step 3. Swap a[j] with a[l].
 79:                 tmp = a[j];
 80:                 a[j] = a[l];
 81:                 a[l] = tmp;
 82: 
 83:                 //step 4. Reverse the sequence from a[j + 1] up to and including the final element a[n]
 84:                 z = len - 1;
 85:                 for (l = j + 1; l < len; l++)
 86:                 {
 87:                     if (l >= z)
 88:                         break;
 89: 
 90:                     tmp = a[l];
 91:                     a[l] = a[z];
 92:                     a[z] = tmp;
 93:                     z--;
 94:                 }
 95: 
 96:                 p = a[0] * (a[1] * 1000 + a[2] * 100 + a[3] * 10 + a[4]);
 97:                 if (p > 1000 && p < 10000)
 98:                 {
 99:                     num = p;
100:                     index = 8;
101:                     cont = true;
102:                     while (num > 0)
103:                     {
104:                         rem = num % 10;
105:                         num = num / 10;
106:                         if (rem != a[index--])
107:                         {
108:                             cont = false;
109:                             break;
110:                         }
111:                     }
112:                     if (cont)
113:                     {
114:                         //Console.WriteLine(a.Aggregate(string.Empty, (s, n) => s += n));
115:                         result.Add(p);
116:                         continue;
117:                     }
118:                 }
119:                 p = (a[0] * 10 + a[1]) * (a[2] * 100 + a[3] * 10 + a[4]);
120:                 if (p > 1000 && p < 10000)
121:                 {
122:                     num = p;
123:                     index = 8;
124:                     cont = true;
125:                     while (num > 0)
126:                     {
127:                         rem = num % 10;
128:                         num = num / 10;
129:                         if (rem != a[index--])
130:                         {
131:                             cont = false;
132:                             break;
133:                         }
134:                     }
135:                     if (cont)
136:                     {
137:                         //Console.WriteLine(a.Aggregate(string.Empty, (s, n) => s += n));
138:                         result.Add(p);
139:                         continue;
140:                     }
141:                 }
142: 
143:             }
144:             return result.Sum();
145:         }
146: 
147:         /// <summary>
148:         /// since both way of (1-4) and (2-3) generates a 4-digit product
149:         /// so set the range from 1000 to 9000 for z, and test (1-4) senarion where x(1-9) * y = z, which
150:         /// if z / x = y, in which x, y and z makes a 1-9 pandigital
151:         /// do the same for (2-3) scenario
152:         /// </summary>
153:         /// <returns></returns>
154:         static int brute_force_with_limited_range_for_candidates()
155:         {
156:             int a, b, c, i, num, rem;
157:             var n = new int[5, 10]; // uses to track duplicate digits
158:             var skip = false;
159:             var result = new HashSet<int>();
160:             for (c = 1000; c < 9999; c++)
161:             {
162:                 num = c;
163:                 skip = false;
164:                 while (num > 0)
165:                 {
166:                     rem = num % 10;
167:                     num = num / 10;
168:                     if (n[0, rem] != 0 || rem == 0)
169:                     {
170:                         skip = true;
171:                         break;
172:                     }
173:                     n[0, rem] = 1;
174:                 }
175:                 if (skip == false)
176:                 {
177:                     //1,4
178:                     for (a = 1; a <= 9; a++)
179:                     {
180:                         rem = c % a;
181:                         num = c / a;
182:                         if (rem == 0 && num > 1000 && n[0, a] == 0)
183:                         {
184:                             n[1, a] = 1;
185:                             //-----------------------------
186:                             skip = false;
187:                             while (num > 0)
188:                             {
189:                                 rem = num % 10;
190:                                 num = num / 10;
191:                                 if (n[0, rem] != 0 || n[1, rem] != 0 || n[2, rem] != 0 || rem == 0)
192:                                 {
193:                                     skip = true;
194:                                     break;
195:                                 }
196:                                 n[2, rem] = 1;
197:                             }
198:                             if (skip == false && result.Add(c))
199:                             {
200: 
201:                                 //Console.WriteLine(a + " * " + c / a + " = " + c);
202:                             }
203:                             for (i = 0; i < 10; i++)
204:                                 n[2, i] = 0;
205:                             //-----------------------------
206:                             n[1, a] = 0;
207:                         }
208:                     }
209:                     //2,3
210:                     for (a = 10; a <= 99; a++)
211:                     {
212:                         skip = false;
213:                         num = a;
214:                         while (num > 0)
215:                         {
216:                             rem = num % 10;
217:                             num = num / 10;
218:                             if (n[0, rem] != 0 || n[1, rem] != 0 || rem == 0)
219:                             {
220:                                 skip = true;
221:                                 break;
222:                             }
223:                             n[1, rem] = 1;
224:                         }
225:                         if (skip == false)
226:                         {
227:                             rem = c % a;
228:                             num = c / a;
229:                             if (rem == 0 && num > 100 && num < 1000)
230:                             {
231:                                 //-----------------------------
232:                                 skip = false;
233:                                 while (num > 0)
234:                                 {
235:                                     rem = num % 10;
236:                                     num = num / 10;
237:                                     if (n[0, rem] != 0 || n[1, rem] != 0 || n[2, rem] != 0 || rem == 0)
238:                                     {
239:                                         skip = true;
240:                                         break;
241:                                     }
242:                                     n[2, rem] = 1;
243:                                 }
244:                                 if (skip == false && result.Add(c))
245:                                 {
246:                                     //Console.WriteLine(a + " * " + c / a + " = " + c);
247:                                 }
248:                                 for (i = 0; i < 10; i++)
249:                                     n[2, i] = 0;
250:                                 //-----------------------------
251:                             }
252:                         }
253:                         for (i = 0; i < 10; i++)
254:                             n[1, i] = 0;
255:                     }
256:                 }
257:                 //reset number(level p)
258:                 for (i = 0; i < 10; i++)
259:                     n[0, i] = 0;
260:             }
261:             return result.Sum();
262:             //Console.WriteLine("Sum is: " + result.Aggregate((s, z) => s += z));
263:         }
264: 
265:         static Stopwatch stopwatch = new Stopwatch();
266:         static void TestBenchSetup()
267:         {
268:             // Uses the second Core or Processor for the Test
269:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
270:             // Prevents "Normal" processes from interrupting Threads
271:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
272:             // Prevents "Normal" Threads from interrupting this thread
273:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
274:         }
275:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
276:         static void TestBenchLoader(Func<int> test_method)
277:         {
278:             stopwatch.Reset();
279:             stopwatch.Start();
280:             var result = 0;
281:             long avg_tick = 0;
282:             long avg_ms = 0;
283:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
284:             // stabilizes the CPU cache and pipeline.
285:             {
286:                 result = test_method(); // Warmup
287:             }
288:             stopwatch.Stop();
289:             for (int repeat = 0; repeat < 20; ++repeat)
290:             {
291:                 stopwatch.Reset();
292:                 stopwatch.Start();
293:                 result = test_method();
294:                 stopwatch.Stop();
295:                 avg_tick += stopwatch.ElapsedTicks;
296:                 avg_ms += stopwatch.ElapsedMilliseconds;
297:             }
298:             avg_tick = avg_tick / 20;
299:             avg_ms = avg_ms / 20;
300:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
301:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
302:         }
303:     }

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