MVVM/WinP7/MultiMonitor/and more…

Project Euler problem 29~

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The total number of distinct terms are in the sequence:");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(construct_prime_factor_list_and_use_hashset_to_prevent_duplicate);
  9:             TestBenchLoader(using_brain_power_to_find_pattern);
 10: 
 11:             Console.WriteLine("Press any key to exit");
 12:             Console.ReadKey();
 13:         }
 14:       
 15:         static int construct_prime_factor_list_and_use_hashset_to_prevent_duplicate()
 16:         {
 17:             var len = 100;
 18:             var primes = new int[] { 2, 3, 5, 7 };
 19:             var sum = 0;
 20:             var distinct_set = new HashSet<string>();
 21:             var prime_factors = new Dictionary<int, int>();
 22:             var count = 0;
 23:             for (int i = 2; i <= len; i++)
 24:             {
 25:                 sum = i;
 26:                 prime_factors.Clear();
 27:                 foreach (var prime in primes)
 28:                 {
 29:                     count = 0;
 30:                     while (sum % prime == 0)
 31:                     {
 32:                         sum = sum / prime;
 33:                         ++count;
 34:                     }
 35:                     if (count > 0)
 36:                         prime_factors.Add(prime, count);
 37:                 }
 38:                 if (prime_factors.Count == 0 || sum != 1)
 39:                     prime_factors.Add(sum, 1);
 40: 
 41:                 for (int power = 2; power <= len; power++)
 42:                 {
 43:                     var factorList = new StringBuilder();
 44:                     foreach (var item in prime_factors)
 45:                     {
 46:                         factorList.Append(item.Key);
 47:                         factorList.Append('^');
 48:                         factorList.Append(item.Value * power);
 49:                         factorList.Append(' ');
 50:                     }
 51:                     distinct_set.Add(factorList.ToString());
 52:                 }
 53:             }
 54:             return distinct_set.Count;
 55:         }
 56: 
 57:         /// <summary>
 58:         /// The non-brute-force way explained by jorgbrown(from this q's discussion post, the code is by qbtruk)
 59:         /// 
 60:         /// C'mon guys, this is a pencil-and-paper problem, not a coding problem. 
 61:         /// Euler probably could have done this one in under 5 minutes. While asleep. 
 62:         /// 
 63:         /// The total number of powers is 9801; really, we're just trying to find duplicates. 
 64:         /// Specifically, let's think about, how many duplicates are there when a^b is a dupe of a 
 65:         /// smaller a raised to a larger power b? 
 66:         /// 
 67:         /// Suppose a is a perfect square of the smaller a, but not a square of a square. 
 68:         /// Then we have a duplicate when b is 2, 3, 4... up to 50. That is, 49 duplicates. 
 69:         /// 
 70:         /// Suppose a is a perfect cube of a smaller a. When b is 2 through 33, we have duplicates 
 71:         /// of smaller a raised to the power b*3. When b is 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 
 72:         /// 54, 56, 58, 60, 62, 64, 66, we have duplicates of a smaller a raised to the power (b/2)*3. 
 73:         /// Total is 32 plus 17, or again, 49 duplicates. 
 74:         /// 
 75:         /// Suppose a is the square of the square of a smaller a. When b is 2 through 49, we have duplicates
 76:         /// of the square root of a raised to the power (b*2). When b is 51, 54, 57, 60, 63, 66, 69, 72, or 75, 
 77:         /// we have dupes of a^(3/4) raised to the power (b*4/3). Total is 49 plus 9, or 58. 
 78:         /// 
 79:         /// Suppose a is the fifth power of a smaller a. We have dupes of fifth root of a raised to the power (b*5), 
 80:         /// which covers b from 2 to 20. Then we have dupes of a^(2/5) raised to the power (b*5/2), 
 81:         /// which covers b of 22, 24, 26, 28, 30, 32, 34, 36, 38, 40. Then we have dupes of a^(3/5) raised to the 
 82:         /// power (b*5/3), which covers b of 21, 27, 33, 39, 42, 45, 48, 51, 54, 57, 60. Last, we have dupes 
 83:         /// of a^(4/5) raised to the power (b*5/4), which covers b of 44, 52, 56, 64, 68, 72, 76, and 80. Total dupes: 48. 
 84:         /// And the last power we have to worry about is 6. We have dupes of the square root of a raised 
 85:         /// to power (b*2), which covers b from 2 to 50. Then we have dupes of the sixth root to the power (b*6/4), 
 86:         /// which covers b of 52, 54, 56, 58, 60, 62, 64, 66. And last we have dupes of the sixth root to the power (b*6/5), 
 87:         /// which covers b of 55, 65, 70, 75, and 80. Total dupes: 62. 
 88:         ///     
 89:         /// Now let's put it all together: 
 90:         /// squares: 4, 9, 25, 36, 49, 100: These 6 squares have 49 dupes each, 6 * 49 = 294 
 91:         /// cubes: 8, 27: These 3 cubes have 49 duplicates each: 2 * 49 = 98 
 92:         /// 4th power: 16, 81. These 2 have 58 dupes each: 2 * 58 = 116 
 93:         /// 5th power: 32. This has 48 dupes. 
 94:         /// 6th power: 64: this has 62 dupes. 
 95:         /// Total # dupes: 618. 9801-618 is 9183. 
 96:         /// </summary>
 97:         /// <returns></returns>
 98:         static int using_brain_power_to_find_pattern()
 99:         {
100:             int maxBase = 100;
101:             int maxPower = 100;
102: 
103:             int nonPowerCount = 85;
104:             int nonPowerDistinct = 99;
105: 
106:             int power2Count = 4;
107:             int power2Distinct = 50;
108: 
109:             int totalDistinct = nonPowerCount * nonPowerDistinct + power2Count * power2Distinct;
110: 
111:             bool[] pow2found = new bool[601];
112:             int maxPow2 = 6;
113: 
114:             bool[] pow3found = new bool[401];
115:             int maxPow3 = 4;
116: 
117:             for (int pow2 = 1; pow2 < maxPow2 + 1; pow2++)
118:                 for (int power = 2; power < maxPower + 1; power++)
119:                     pow2found[power * pow2] = true;
120: 
121:             for (int pow3 = 1; pow3 < maxPow3 + 1; pow3++)
122:                 for (int power = 2; power < maxPower + 1; power++)
123:                     pow3found[power * pow3] = true;
124: 
125:             for (int index = 0; index < pow2found.Length; index++)
126:                 if (pow2found[index])
127:                     totalDistinct++;
128: 
129:             for (int index = 0; index < pow3found.Length; index++)
130:                 if (pow3found[index])
131:                     totalDistinct++;
132: 
133:             return totalDistinct;
134:         }
135: 
136:         static Stopwatch stopwatch = new Stopwatch();
137:         static void TestBenchSetup()
138:         {
139:             // Uses the second Core or Processor for the Test
140:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
141:             // Prevents "Normal" processes from interrupting Threads
142:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
143:             // Prevents "Normal" Threads from interrupting this thread
144:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
145:         }
146:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
147:         static void TestBenchLoader(Func<int> test_method)
148:         {
149:             stopwatch.Reset();
150:             stopwatch.Start();
151:             var result = 0;
152:             long avg_tick = 0;
153:             long avg_ms = 0;
154:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
155:             // stabilizes the CPU cache and pipeline.
156:             {
157:                 result = test_method(); // Warmup
158:             }
159:             stopwatch.Stop();
160:             for (int repeat = 0; repeat < 20; ++repeat)
161:             {
162:                 stopwatch.Reset();
163:                 stopwatch.Start();
164:                 result = test_method();
165:                 stopwatch.Stop();
166:                 avg_tick += stopwatch.ElapsedTicks;
167:                 avg_ms += stopwatch.ElapsedMilliseconds;
168:             }
169:             avg_tick = avg_tick / 20;
170:             avg_ms = avg_ms / 20;
171:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
172:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
173:         }
174:     }

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