its friday~

Project Euler problem 33~

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The sum of all numbers that can be written as pandigital products:");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(using_lowest_terms_to_limit_search_range);
  9:             TestBenchLoader(brute_froce_all_fraction_under_range);
 10: 
 11:             Console.WriteLine("Press any key to exit");
 12:             Console.ReadKey();
 13:         }
 14: 
 15:         /// <summary>
 16:         /// since the range is under 1, all curious fraction will have a equivalent fraction of
 17:         /// 1-digit numerator and denominator. so basically all curious fraction is a multiple of 
 18:         /// one of the lowest term single digit numerator and denominator fraction.
 19:         /// start from each lowest term fraction and iterate and test all the multiple below 1 to find
 20:         /// curious fraction
 21:         /// </summary>
 22:         static int using_lowest_terms_to_limit_search_range()
 23:         {
 24:             int result_a = 1;
 25:             int result_b = 1;
 26:             int len, start, i;
 27:             foreach (var seed in generate_seeds())
 28:             {
 29:                 len = 99 / seed.b;
 30:                 start = 10 % seed.a == 0 ? 10 / seed.a : 10 / seed.a + 1;
 31:                 for (i = start; i <= len; i++)
 32:                 {
 33:                     find_curious_fraction2(seed.a * i, seed.b * i, ref result_a, ref result_b);
 34:                 }
 35:             }
 36:             return result_b / find_GCD(result_a, result_b);
 37:         }
 38: 
 39:         /// <summary>
 40:         /// iterate through all possible fraction(2-digit max) under 1
 41:         /// </summary>
 42:         static int brute_froce_all_fraction_under_range()
 43:         {
 44:             int result_a = 1;
 45:             int result_b = 1;
 46:             
 47:             for (int b = 99; b >= 10; b--)
 48:             {
 49:                 for (int a = b - 1; a >= 10; a--)
 50:                 {
 51:                     find_curious_fraction2(a, b, ref result_a, ref result_b);
 52:                 }
 53:             }
 54:             return result_b / find_GCD(result_a, result_b);
 55:         }
 56: 
 57:         /// <summary>
 58:         /// create a struct to represent a fraction
 59:         /// </summary>
 60:         struct fraction
 61:         {
 62:             public int a; // numerator
 63:             public int b; // denominator
 64:         }
 65: 
 66:         /// <summary>
 67:         /// use Euclidean algorithm to find GCD
 68:         /// http://en.wikipedia.org/wiki/Euclidean_algorithm
 69:         /// </summary>
 70:         static int find_GCD(int x, int y)
 71:         {
 72:             while (x > 0)
 73:             {
 74:                 y = y % x;
 75:                 y = y + x; // the next three lines is just swapping x and y
 76:                 x = y - x;
 77:                 y = y - x;
 78:             }
 79:             return y;
 80:         }
 81: 
 82:         /// <summary>
 83:         /// generate a list of fraction which contain lowest term single digit fraction for both
 84:         /// numerator and denominator. e.g. 1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5.... 
 85:         /// </summary>
 86:         static IEnumerable<fraction> generate_seeds()
 87:         {
 88:             var seeds = new List<fraction>();
 89:             for (int b = 2; b <= 9; b++)
 90:             {
 91:                 for (int a = 1; a < b; a++)
 92:                 {
 93:                     if (find_GCD(a, b) == 1 || a == 1)
 94:                         seeds.Add(new fraction() { a = a, b = b });
 95:                 }
 96:             }
 97:             return seeds;
 98:         }
 99: 
100:         /// <summary>
101:         /// test to see if given fraction(a/b) is a "curious fraction"
102:         /// since there are 4 possible ways of finding a curious fraction
103:         ///     1. a1 a2 / b1 b2    =   a1 / b2 (a2 is equal to b1, and b1 is not zero)
104:         ///     2. a1 a2 / b1 b2    =   a2 / b1 (a1 is equal to b2, and b2 is not zero)
105:         ///     3. a1 a2 / b1 b2    =   a1 / b1 (a2 is equal to b2, and b2 is not zero)
106:         ///     4. a1 a2 / b1 b2    =   a2 / b2 (a1 is equal to b1, and b1 is not zero)
107:         /// </summary>
108:         static void find_curious_fraction2(int a, int b, ref int result_a, ref int result_b)
109:         {
110:             var a1 = a / 10;
111:             var a2 = a % 10;
112:             var b1 = b / 10;
113:             var b2 = b % 10;
114: 
115:             if (b2 == a1 && b2 != 0 && a * b1 == b * a2)
116:             {
117:                 result_a *= a2;
118:                 result_b *= b1;
119:             }
120:             else if (b1 == a2 && b1 != 0 && a * b2 == b * a1)
121:             {
122:                 result_a *= a1;
123:                 result_b *= b2;
124:             }
125:             else if (b2 == a2 && b2 != 0 && a * b1 == b * a1)
126:             {
127:                 result_a *= a1;
128:                 result_b *= b1;
129:             }
130:             else if (b1 == a1 && b1 != 0 && a * b2 == b * a2)
131:             {
132:                 result_a *= a2;
133:                 result_b *= b2;
134:             }
135:         }
136: 
137:         static Stopwatch stopwatch = new Stopwatch();
138:         static void TestBenchSetup()
139:         {
140:             // Uses the second Core or Processor for the Test
141:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
142:             // Prevents "Normal" processes from interrupting Threads
143:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
144:             // Prevents "Normal" Threads from interrupting this thread
145:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
146:         }
147:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
148:         static void TestBenchLoader(Func<int> test_method)
149:         {
150:             stopwatch.Reset();
151:             stopwatch.Start();
152:             var result = 0;
153:             long avg_tick = 0;
154:             long avg_ms = 0;
155:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
156:             // stabilizes the CPU cache and pipeline.
157:             {
158:                 result = test_method(); // Warmup
159:             }
160:             stopwatch.Stop();
161:             for (int repeat = 0; repeat < 20; ++repeat)
162:             {
163:                 stopwatch.Reset();
164:                 stopwatch.Start();
165:                 result = test_method();
166:                 stopwatch.Stop();
167:                 avg_tick += stopwatch.ElapsedTicks;
168:                 avg_ms += stopwatch.ElapsedMilliseconds;
169:             }
170:             avg_tick = avg_tick / 20;
171:             avg_ms = avg_ms / 20;
172:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
173:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
174:         }
175:     }

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