WinPhone7/YUI/C#/and more…

Project Euler problem 55~

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The number of Lychrel numbers below ten-thousand: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(using_decimal_number_type_for_calculation);
  9:             TestBenchLoader(using_ulong_number_type_for_calculation);
 10:             TestBenchLoader(using_int_array_type_for_calculation);
 11: 
 12:             Console.WriteLine("Press any key to exit");
 13:             Console.ReadKey();
 14:         }
 15: 
 16:         /// <summary>
 17:         /// since from the question's post, 28-digit seems to be a good upper bound for number(below 10k) with 50k
 18:         /// so decimal value with 28 precision is enough to avoid overflow
 19:         /// </summary>
 20:         static int using_decimal_number_type_for_calculation()
 21:         {
 22:             int n, t;
 23:             decimal num = 0;
 24:             var result = 0;
 25:             for (n = 10; n < 10000; n++)
 26:             {
 27:                 num = n;
 28:                 for (t = 0; t < 50; t++)
 29:                 {
 30:                     num += reverse_dec(num);
 31:                     if (num == reverse_dec(num))
 32:                         break;
 33:                 }
 34:                 if (t == 50)
 35:                     result++;
 36:             }
 37:             return result;
 38:         }
 39: 
 40:         static decimal reverse_dec(decimal n)
 41:         {
 42:             decimal result = 0;
 43:             while (n > 0)
 44:             {
 45:                 result = result * 10 + n % 10;
 46:                 n = decimal.Floor(n / 10);
 47:             }
 48:             return result;
 49:         }
 50: 
 51:         /// <summary>
 52:         /// using ulong, only 18-digits, and very likely to overflow(and it did), but still
 53:         /// the answer came out to be correct
 54:         /// </summary>
 55:         static int using_ulong_number_type_for_calculation()
 56:         {
 57:             uint n, t;
 58:             ulong num = 0;
 59:             var result = 0;
 60:             for (n = 10; n < 10000; n++)
 61:             {
 62:                 num = n;
 63:                 for (t = 0; t < 50; t++)
 64:                 {
 65:                     num += reverse_ulong(num);
 66:                     if (num == reverse_ulong(num))
 67:                         break;
 68:                 }
 69:                 if (t == 50)
 70:                     result++;
 71:             }
 72:             return result;
 73:         }
 74: 
 75:         /// <summary>
 76:         /// reverse the number and return as ulong
 77:         /// </summary>
 78:         static ulong reverse_ulong(ulong n)
 79:         {
 80:             ulong result = 0;
 81:             while (n > 0)
 82:             {
 83:                 result = result * 10 + n % 10;
 84:                 n /= 10;
 85:             }
 86:             return result;
 87:         }
 88: 
 89:         /// <summary>
 90:         /// using array to store number, it also makes comparing and test palindrome easier
 91:         /// </summary>
 92:         static int using_int_array_type_for_calculation()
 93:         {
 94:             int n, t;
 95:             var result = 0;
 96:             int[] num;
 97:             for (n = 10; n < 10000; n++)
 98:             {
 99:                 num = num_to_array(n);
100:                 for (t = 0; t < 50; t++)
101:                 {
102:                     num = addition(num, num.Reverse().ToArray());
103:                     if (num.SequenceEqual(num.Reverse()))
104:                         break;
105:                 }
106:                 if (t == 50)
107:                     result++;
108:             }
109:             return result;
110:         }
111: 
112:         static int[] num_to_array(int n)
113:         {
114:             // same alogorithm as itoa0
115:             var result = new List<int>();
116:             do
117:             {
118:                 result.Add(n % 10);
119:             } while ((n /= 10) > 0);
120: 
121:             return result.ToArray();
122:         }
123: 
124:         static int[] addition(int[] a, int[] b)
125:         {
126:             var len = a.Length > b.Length ? a.Length : b.Length;
127:             var result = new List<int>(len);
128:             int carry = 0;
129:             int x, y, sum;
130:             for (int i = 0; i < len; i++)
131:             {
132:                 x = i < a.Length ? a[i] : 0;
133:                 y = i < b.Length ? b[i] : 0;
134: 
135:                 sum = x + y + carry;
136:                 result.Add(sum % 10);
137:                 carry = sum / 10;
138:             }
139:             if (carry > 0)
140:                 result.Add(carry);
141:             return result.ToArray<int>();
142:         }
143: 
144:         static Stopwatch stopwatch = new Stopwatch();
145:         static void TestBenchSetup()
146:         {
147:             // Uses the second Core or Processor for the Test
148:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
149:             // Prevents "Normal" processes from interrupting Threads
150:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
151:             // Prevents "Normal" Threads from interrupting this thread
152:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
153:         }
154:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
155:         static void TestBenchLoader(Func<int> test_method)
156:         {
157:             stopwatch.Reset();
158:             stopwatch.Start();
159:             var result = 0;
160:             long avg_tick = 0;
161:             long avg_ms = 0;
162:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms
163:             // stabilizes the CPU cache and pipeline.
164:             {
165:                 result = test_method(); // Warmup
166:             }
167:             stopwatch.Stop();
168:             for (int repeat = 0; repeat < 20; ++repeat)
169:             {
170:                 stopwatch.Reset();
171:                 stopwatch.Start();
172:                 result = test_method();
173:                 stopwatch.Stop();
174:                 avg_tick += stopwatch.ElapsedTicks;
175:                 avg_ms += stopwatch.ElapsedMilliseconds;
176:             }
177:             avg_tick = avg_tick / 20;
178:             avg_ms = avg_ms / 20;
179:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
180:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
181:         }
182:     }

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