MVVM/WinP7/MultiMonitor/and more…

• Three Monitors For Every User (Jeff Atwood)
• MVVM Light Toolkit V3 SP1 for Windows Phone 7 (Laurent Bugnion)
• Changing States using GoToStateAction (Kirupa Chinnathambi)
• Windows Phone: Frame/Page navigation and transitions using the TransitioningContentControl (Avi Pilosof)
• Rethinking Programming Language Tutorials
• Refactor This!
• Refactor This: Answers
• Paint With Light
• Programmer Tip: Trying To Be There When The Sky Is Falling Or You Are Needed
• Windows Phone development and design – ultimate guide
• Making the Most of the Reactive Extentions for .NET

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:     }