xna/wpf/vs2010/c#/and more…

Project Euler problem 38~

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The largest 1 to 9 pandigital 9-digit number that can be formed:");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(test_each_number_start_with_nine_below_ten_thousands);
  9:             TestBenchLoader(test_number_within_nine_to_ten_thousand);
 10: 
 11:             Console.WriteLine("Press any key to exit");
 12:             Console.ReadKey();
 13:         }
 14: 
 15:         /// <summary>
 16:         /// since the question stated that 9 * (n=1,2,3,4,5) = 918273645
 17:         /// and obviously from how the question is phrased, the number(918273645) is not the largest number
 18:         /// so the answer can only be greater than that. that means the number has to be 9
 19:         /// e.g. since answer must consist of x * n(1,2,3) = (x*1)(x*2)(x*3) and x*1 must start with 9
 20:         /// which makes x be 9, 9.. , 9... , 9....  and the number cant be greater than 5 digits, since
 21:         /// (5-digit*1)(5-digit*2)=at least 10 digits, so this method test each number in range of 90~99,
 22:         /// 900~999, 9000~9999 to find the answer
 23:         /// </summary>
 24:         /// <returns></returns>
 25:         static int test_each_number_start_with_nine_below_ten_thousands()
 26:         {
 27:             var init = 9;
 28:             var tens = 10;
 29:             var n = 0;
 30:             var cur = 0;
 31:             var set = new HashSet<int>();
 32:             var duplicate = false;
 33:             var str = new StringBuilder();
 34:             var tmp = 0;
 35:             var result = new List<string>();
 36:             while (tens <= 10000)
 37:             {
 38:                 for (int i = init; i < tens; i++)
 39:                 {
 40:                     n = 1;
 41:                     duplicate = false;
 42:                     set.Clear();
 43:                     set.Add(0);
 44:                     str.Remove(0, str.Length);
 45:                     while (true)
 46:                     {
 47:                         cur = i * n;
 48:                         tmp = cur;
 49:                         while (tmp > 0)
 50:                         {
 51:                             if (set.Add(tmp % 10) == false)
 52:                             {
 53:                                 duplicate = true;
 54:                                 break;
 55:                             }
 56:                             tmp /= 10;
 57:                         }
 58:                         if (duplicate)
 59:                             break;
 60:                         else
 61:                             str.Append(cur);
 62:                         n++;
 63:                     }
 64:                     if (str.Length == 9)
 65:                         result.Add(str.ToString());
 66:                         //Console.WriteLine(string.Format("int:{0},   product:{1}", i, str));
 67:                 }
 68:                 init *= 10;
 69:                 tens *= 10;
 70:             }
 71:             return Convert.ToInt32(result.Max());
 72:         }
 73: 
 74:         /// <summary>
 75:         /// this method is more refined than previous method, since the number has to start with digit 9
 76:         /// which makes 9x, 9xx, 9xxx...etc, when n=2, the number times 2 would definitely add 1 more digit to it
 77:         /// so for example, 9*2 = 18, 98*2= 196. so 3 digit number would become 9xx = (3-digit) (4-digit) (4-digit)
 78:         /// either way, it wouldnt fit to be a 9-digit number.
 79:         /// so the only possible range for the number is 4 digit with n=1,2, which makes (4-digit, n=1) (5-digit, n=2)
 80:         /// this method test number range from 9999 down to 9000, the first number found must be the largest number, 
 81:         /// and therefore the answer.
 82:         /// </summary>
 83:         /// <returns></returns>
 84:         static int test_number_within_nine_to_ten_thousand()
 85:         {
 86:             int num, digits;
 87:             var set = new HashSet<int>();
 88:             var has_duplicate = false;
 89:             for (int i = 9876; i >= 9123; i--)
 90:             {
 91:                 num = i * 100000 + i * 2;
 92:                 has_duplicate = false;
 93:                 set.Clear();
 94:                 set.Add(0);
 95:                 digits = num;
 96:                 while (digits > 0)
 97:                 {
 98:                     if (set.Add(digits % 10) == false)
 99:                     {
100:                         has_duplicate = true;
101:                         break;
102:                     }
103:                     digits /= 10;
104:                 }
105:                 if (has_duplicate == false)
106:                     return num;
107:             }
108:             return 0;
109:         }
110: 
111:         static Stopwatch stopwatch = new Stopwatch();
112:         static void TestBenchSetup()
113:         {
114:             // Uses the second Core or Processor for the Test
115:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
116:             // Prevents "Normal" processes from interrupting Threads
117:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
118:             // Prevents "Normal" Threads from interrupting this thread
119:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
120:         }
121:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
122:         static void TestBenchLoader(Func<int> test_method)
123:         {
124:             stopwatch.Reset();
125:             stopwatch.Start();
126:             var result = 0;
127:             long avg_tick = 0;
128:             long avg_ms = 0;
129:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
130:             // stabilizes the CPU cache and pipeline.
131:             {
132:                 result = test_method(); // Warmup
133:             }
134:             stopwatch.Stop();
135:             for (int repeat = 0; repeat < 20; ++repeat)
136:             {
137:                 stopwatch.Reset();
138:                 stopwatch.Start();
139:                 result = test_method();
140:                 stopwatch.Stop();
141:                 avg_tick += stopwatch.ElapsedTicks;
142:                 avg_ms += stopwatch.ElapsedMilliseconds;
143:             }
144:             avg_tick = avg_tick / 20;
145:             avg_ms = avg_ms / 20;
146:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
147:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
148:         }
149:     }

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