today’s euler

Project Euler problem 34~

  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(); // comment out this call if testing the parallel way
  8:             TestBenchLoader(test_each_number_under_calculated_upper_bound);
  9:             TestBenchLoader(test_numbers_in_parallel);
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         static void test_upperbound()
 15:         {
 16:             var unit = Enumerable.Range(1, 9).Aggregate((s, i) => s *= i);
 17:             var length = 1;
 18:             int digit_max, digit_min, factorial_max;
 19:             while (true)
 20:             {
 21:                 var s_max = Enumerable.Range(1, length)
 22:                     .Select(i => "9")
 23:                     .Aggregate(string.Empty, (s, i) => s += i);
 24:                 var s_min = Enumerable.Range(1, length)
 25:                     .Select(i => "1")
 26:                     .Aggregate(string.Empty, (s, i) => s += i);
 27:                 digit_max = Convert.ToInt32(s_max);
 28:                 digit_min = Convert.ToInt32(s_min);
 29:                 factorial_max = unit * length;
 30:                 Console.WriteLine(string.Format("{0}-digit: min:{1} max:{2} factorial max={3}",
 31:                     length, s_min.PadRight(10), s_max.PadRight(10), factorial_max));
 32:                 if (digit_min > factorial_max)
 33:                     break;
 34:                 length++;
 35:             }
 36:             Console.WriteLine();
 37:         }
 38: 
 39:         /// <summary>
 40:         /// pretty similar to question 30, so the key here is to find a upperbound and test each number blow it
 41:         /// from test_upperbound method, we know that for 8 digits number, the max(99999999) factorial is
 42:         /// 9!*8 = 2903040, and minimal 8-digit number is 11111111, which is greater. so we know the upper bound
 43:         /// is within 7-digit number, so we can just use 9!*7 = 2540160 as upperbound.
 44:         /// </summary>
 45:         /// <returns></returns>
 46:         static int test_each_number_under_calculated_upper_bound()
 47:         {
 48:             var map = Enumerable.Range(0, 10)
 49:                 .Select(n => n == 0 ? 1 : Enumerable.Range(1, n).Aggregate((s, i) => s *= i)).ToArray();
 50:             var limit = map[9] * 7;
 51:             int sum, num;
 52:             var result = 0;
 53:             for (int i = limit; i >=3 ; i--)
 54:             {
 55:                 sum = 0;
 56:                 num = i;
 57:                 do
 58:                 {
 59:                     sum += map[num % 10];
 60:                 } while ((num /= 10) > 0);
 61:                 if (sum == i)
 62:                     result += i;
 63:             }
 64:             return result;
 65:         }
 66: 
 67:         class WorkItem
 68:         {
 69:             public int from;
 70:             public int to;
 71:             public AutoResetEvent signal;
 72:             public int result;
 73:         }
 74: 
 75:         /// <summary>
 76:         /// the testing for each number for match can be easily parallelized.
 77:         /// so this method divides all the number to be tested in 7 chunks, and test
 78:         /// each chunk in parallel(through threadpool).
 79:         /// the method is coded in such way that no lock is required, since by the time we need
 80:         /// to access the result of each chunk, the thread is already finished.
 81:         /// </summary>
 82:         /// <returns></returns>
 83:         static int test_numbers_in_parallel()
 84:         {
 85:             var map = Enumerable.Range(0, 10)
 86:                 .Select(n => n == 0 ? 1 : Enumerable.Range(1, n).Aggregate((s, i) => s *= i)).ToArray();
 87:             var limit = map[9] * 7;
 88:             var size = limit / 7;
 89:             var result = 0;
 90:             var work_items = Enumerable.Range(1, 7)
 91:                 .Select(l => new WorkItem
 92:                     {
 93:                         from = l == 1 ? 3 : (l - 1) * size + 1,
 94:                         to = l * size,
 95:                         signal = new AutoResetEvent(false),
 96:                         result = 0
 97:                     }).ToList();
 98:             foreach (var item in work_items)
 99:             {
100:                 ThreadPool.QueueUserWorkItem((o) =>
101:                     {
102:                         int sum, num, i;
103:                         var work_item = o as WorkItem;
104:                         for (i = work_item.from; i <=work_item.to; i++)
105:                         {
106:                             sum = 0;
107:                             num = i;
108:                             do
109:                             {
110:                                 sum += map[num % 10];
111:                             } while ((num /= 10) > 0);
112:                             if (sum == i)
113:                                 work_item.result += i;
114:                         }
115:                         work_item.signal.Set();
116:                     }, item);
117:             }
118:             work_items.ForEach(w => { w.signal.WaitOne(); result += w.result; });
119:             return result;
120:         }
121: 
122:         static Stopwatch stopwatch = new Stopwatch();
123:         static void TestBenchSetup()
124:         {
125:             // Uses the second Core or Processor for the Test
126:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
127:             // Prevents "Normal" processes from interrupting Threads
128:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
129:             // Prevents "Normal" Threads from interrupting this thread
130:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
131:         }
132:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
133:         static void TestBenchLoader(Func<int> test_method)
134:         {
135:             stopwatch.Reset();
136:             stopwatch.Start();
137:             var result = 0;
138:             long avg_tick = 0;
139:             long avg_ms = 0;
140:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
141:             // stabilizes the CPU cache and pipeline.
142:             {
143:                 result = test_method(); // Warmup
144:             }
145:             stopwatch.Stop();
146:             for (int repeat = 0; repeat < 20; ++repeat)
147:             {
148:                 stopwatch.Reset();
149:                 stopwatch.Start();
150:                 result = test_method();
151:                 stopwatch.Stop();
152:                 avg_tick += stopwatch.ElapsedTicks;
153:                 avg_ms += stopwatch.ElapsedMilliseconds;
154:             }
155:             avg_tick = avg_tick / 20;
156:             avg_ms = avg_ms / 20;
157:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
158:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
159:         }
160:     }

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