SpellChecker/WPF/xaml/.NET4.0/and more…

Project Euler problem 36~

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The sum of all numbers which are equal to the sum of the factorial of their digits:");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(store_number_in_array_and_brute_force_every_number);
  9:             TestBenchLoader(brute_force_every_number_using_formula_from_q_description);
 10:             TestBenchLoader(generate_palindromes_using_algorithm_from_q_description_base_ten);
 11:             TestBenchLoader(generate_palindromes_using_algorithm_from_q_description_base_two);
 12: 
 13:             Console.WriteLine("Press any key to exit");
 14:             Console.ReadKey();
 15:         }
 16: 
 17:         /// <summary>
 18:         /// bascially store the number in array so checking whether it is palindrome can be easily done
 19:         /// but this method is only slightly faster than just checking each number
 20:         /// i guess array operation is not cheap
 21:         /// </summary>
 22:         /// <returns></returns>
 23:         static int store_number_in_array_and_brute_force_every_number()
 24:         {
 25:             var max = 999999;
 26:             var bin_len = Convert.ToString(max, 2).Length; // convert to binary to get length
 27:             var bin = new int[bin_len];
 28:             var dec_len = max.ToString().Length;
 29:             var dec = new int[dec_len];
 30:             int i, carry, fwd, rwd;
 31:             var num = 0;
 32:             var bin_count = 0;
 33:             var dec_count = 0;
 34:             var result = 0;
 35:             var isPal = true;
 36:             while (++num <= max)
 37:             {
 38:                 isPal = true;
 39:                 //calculate in binary
 40:                 i = bin_len;
 41:                 carry = 1;
 42:                 while (carry >= 1) //adding one
 43:                 {
 44:                     i--;
 45:                     bin[i] += carry;
 46:                     carry = bin[i] > 1 ? 1 : 0;
 47:                     bin[i] = bin[i] > 1 ? 0 : bin[i];
 48:                     if (bin_len - i > bin_count)
 49:                         bin_count = bin_len - i;
 50:                 }
 51:                 fwd = bin_len - bin_count;
 52:                 rwd = bin_len - 1;
 53:                 while (isPal && rwd >= fwd) // test for palindrome
 54:                 {
 55:                     if (bin[fwd++] != bin[rwd--])
 56:                         isPal = false;
 57:                 }
 58:                 // calculate in decimal
 59:                 i = dec_len;
 60:                 carry = 1;
 61:                 while (carry >= 1) // adding one
 62:                 {
 63:                     i--;
 64:                     dec[i] += carry;
 65:                     carry = dec[i] > 9 ? 1 : 0;
 66:                     dec[i] = dec[i] > 9 ? 0 : dec[i];
 67:                     if (dec_len - i > dec_count)
 68:                         dec_count = dec_len - i;
 69:                 }
 70:                 fwd = dec_len - dec_count;
 71:                 rwd = dec_len - 1;
 72:                 while (isPal && rwd >= fwd) // test for palindrome
 73:                 {
 74:                     if (dec[fwd++] != dec[rwd--])
 75:                         isPal = false;
 76:                 }
 77:                 if (isPal)
 78:                     result += num;
 79:             }
 80:             return result;
 81:         }
 82: 
 83:         /// <summary>
 84:         /// loop through all the number and use the method described in the question's
 85:         /// note to test whether or not it is palindrome
 86:         /// </summary>
 87:         /// <returns></returns>
 88:         static int brute_force_every_number_using_formula_from_q_description()
 89:         {
 90:             var result = 0;
 91:             for (int i = 1; i < 1000000; i += 2)
 92:             {
 93:                 if (isPalindrome(i, 2) && isPalindrome(i, 10))
 94:                     result += i;
 95:             }
 96:             return result;
 97:         }
 98: 
 99:         /// <summary>
100:         /// basically generate palindromic number rather than test each number under 1mil to see
101:         /// if it is palindrome. so
102:         /// 1->11
103:         /// 2->22
104:         /// 12-> 1221
105:         /// until 1000-> 10000001 for even length palindrome
106:         /// 11->111
107:         /// 12->121
108:         /// until 1000-> 1000001 for odd length palindrome
109:         /// so using base 10 to generate all the palindrome, and then use isPalindrome method for base 2
110:         /// see http://mathworld.wolfram.com/PalindromicNumber.html
111:         /// for info on finding total # of palindromic under given range
112:         /// total Palindromic a(n) = 2*(10^(n/2)-1) when n=even, n is the power of 10(10^6, n=6)
113:         /// when n is odd:11*10^((n-1)/2)-2
114:         /// the possible combination of palindromic number under 1 mil:
115:         /// a,aa,aba,abba,abcba,abccba
116:         /// </summary>
117:         /// <returns></returns>
118:         static int generate_palindromes_using_algorithm_from_q_description_base_ten()
119:         {
120:             var limit = 1000000;
121:             var sum = 0;
122:             var i = 1;
123:             var p = makePalindrome(i, 10, true);
124:             while (p < limit)
125:             {
126:                 if (isPalindrome(p, 2))
127:                     sum += p;
128:                 p = makePalindrome(++i, 10, true);
129:             }
130:             i = 1;
131:             p = makePalindrome(i, 10, false);
132:             while (p < limit)
133:             {
134:                 if (isPalindrome(p, 2))
135:                     sum += p;
136:                 p = makePalindrome(++i, 10, false);
137:             }
138:             return sum;
139:         }
140: 
141:         /// <summary>
142:         /// reverse version of generate_palindromes_using_algorithm_from_q_description_base_ten,
143:         /// generate base 2 palindromic, this is slightly faster since we can use bit operator
144:         /// to do division and modulo, which is faster than normal divison and modulo
145:         /// </summary>
146:         /// <returns></returns>
147:         static int generate_palindromes_using_algorithm_from_q_description_base_two()
148:         {
149:             var limit = 1000000;
150:             var sum = 0;
151:             var i = 1;
152:             var p = makePalindromeBase2(i, true);
153:             while (p < limit)
154:             {
155:                 if (isPalindrome(p, 10))
156:                     sum += p;
157:                 p = makePalindromeBase2(++i, true);
158:             }
159:             i = 1;
160:             p = makePalindromeBase2(i, false);
161:             while (p < limit)
162:             {
163:                 if (isPalindrome(p, 10))
164:                     sum += p;
165:                 p = makePalindromeBase2(++i, false);
166:             }
167:             return sum;
168:         }
169: 
170:         /// <summary>
171:         /// basically for if the number is 1234
172:         /// the reverse is 4321, that mean 4*10*10*10 = 4000
173:         /// and this is what b*reverse is about (in this example, base is 10)
174:         /// r       k(k=n)
175:         /// 0+4     123
176:         /// 40+3    12
177:         /// 430+2   1
178:         /// 4320+1  0
179:         /// 4321
180:         /// </summary>
181:         /// <param name="n"></param>
182:         /// <param name="b"></param>
183:         /// <returns></returns>
184:         static bool isPalindrome(int n, int b)
185:         {
186:             var reverse = 0;
187:             var k = n;
188:             while (k > 0)
189:             {
190:                 reverse = b * reverse + k % b;
191:                 k /= b;
192:             }
193:             return n == reverse;
194:         }
195: 
196:         /// <summary>
197:         /// basically create a new number with n + reverse of n
198:         /// e.g: n= 86, the output would be 8668
199:         /// the isOdd is for generting odd length, since the above
200:         /// method always generate even: 123 =>123321
201:         /// when set odd to true, 3 is removed
202:         /// 123=> 12(3-removed)+ 321 = 12321
203:         /// </summary>
204:         /// <param name="n"></param>
205:         /// <param name="b"></param>
206:         /// <param name="isOdd"></param>
207:         /// <returns></returns>
208:         static int makePalindrome(int n, int b, bool isOdd)
209:         {
210:             var res = n;
211:             if (isOdd)
212:                 n /= b;
213:             while (n > 0)
214:             {
215:                 res = b * res + n % b;
216:                 n /= b;
217:             }
218:             return res;
219:         }
220: 
221:         /// <summary>
222:         /// well bit-shift is faster, and especially we need to do it in base 2
223:         ///   10111011  =  187
224:         ///   11011111  =  223
225:         ///AND
226:         ///   10011011  =  155
227:         /// (so n & 1 is effectively n % 2)
228:         /// shift left
229:         /// 00001111  =  15
230:         /// SHIFT LEFT
231:         /// 00011110  =  30
232:         /// (so n >>= 1 is effectively n= n/2)
233:         /// (so res << 1 is effectuveky n*2
234:         /// </summary>
235:         /// <param name="n"></param>
236:         /// <param name="isOdd"></param>
237:         /// <returns></returns>
238:         static int makePalindromeBase2(int n, bool isOdd)
239:         {
240:             var res = n;
241:             if (isOdd)
242:                 n >>= 1;
243:             while (n > 0)
244:             {
245:                 res = (res << 1) + (n & 1);
246:                 n >>= 1; ;
247:             }
248:             return res;
249:         }
250: 
251:         static Stopwatch stopwatch = new Stopwatch();
252:         static void TestBenchSetup()
253:         {
254:             // Uses the second Core or Processor for the Test
255:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
256:             // Prevents "Normal" processes from interrupting Threads
257:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
258:             // Prevents "Normal" Threads from interrupting this thread
259:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
260:         }
261:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
262:         static void TestBenchLoader(Func<int> test_method)
263:         {
264:             stopwatch.Reset();
265:             stopwatch.Start();
266:             var result = 0;
267:             long avg_tick = 0;
268:             long avg_ms = 0;
269:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
270:             // stabilizes the CPU cache and pipeline.
271:             {
272:                 result = test_method(); // Warmup
273:             }
274:             stopwatch.Stop();
275:             for (int repeat = 0; repeat < 20; ++repeat)
276:             {
277:                 stopwatch.Reset();
278:                 stopwatch.Start();
279:                 result = test_method();
280:                 stopwatch.Stop();
281:                 avg_tick += stopwatch.ElapsedTicks;
282:                 avg_ms += stopwatch.ElapsedMilliseconds;
283:             }
284:             avg_tick = avg_tick / 20;
285:             avg_ms = avg_ms / 20;
286:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
287:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
288:         }
289:     }

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