not much

Project Euler problem 39~

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The number(<=1000) with most solution:");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(brute_force_every_possible_triplet_under_one_k);
  9:             TestBenchLoader(calculate_every_prime_triplet_and_test_each_s_multuples);
 10:             TestBenchLoader(someone_solution_from_q_discussion_thread);
 11: 
 12:             Console.WriteLine("Press any key to exit");
 13:             Console.ReadKey();
 14:         }
 15: 
 16:         /// <summary>
 17:         /// since a^2 + b^2 = c^2 and (a+b+c less or equal to 1000)
 18:         /// that makes range for c from 4 to 500, calculate all c^2 and store in power_map,
 19:         /// and c_map for fast Contains(...) operation(hashset is one of the fastest c# built-in collection
 20:         /// for set operation and methods like Contains), iterate through every combination for
 21:         /// a and b and if the a^2+b^2(power_map comes in handy) is in c_map, then it is a pythagorean triples.
 22:         /// the rest is history~
 23:         /// </summary>
 24:         /// <returns></returns>
 25:         static int brute_force_every_possible_triplet_under_one_k()
 26:         {
 27:             var len = 501;
 28:             var power_map = new int[len];
 29:             var c_map = new HashSet<int>();
 30:             for (int i = 3; i < len; i++)
 31:             {
 32:                 power_map[i] = (int)Math.Pow(i, 2);
 33:                 c_map.Add(power_map[i]);
 34:             }
 35:             int a, b, c;
 36:             var map = new int[1001];
 37:             for (a = 4; a < 500; a++)
 38:             {
 39:                 for (b = 3; b < a; b++)
 40:                 {
 41:                     c = power_map[a] + power_map[b];
 42:                     if (c_map.Contains(c))
 43:                     {
 44:                         c = (int)Math.Sqrt(c);
 45:                         if (a + b + c <= 1000)
 46:                             map[a + b + c]++;
 47:                     }
 48:                 }
 49:             }
 50:             var max = 0;
 51:             var result = 0;
 52:             for (int i = 0; i < 1001; i++)
 53:             {
 54:                 if (map[i] > max)
 55:                 {
 56:                     max = map[i];
 57:                     result = i;
 58:                 }
 59:             }
 60:             return result;
 61:         }
 62: 
 63:         /// <summary>
 64:         /// using method IV from http://en.wikipedia.org/wiki/Formulas_for_generating_Pythagorean_triples
 65:         /// to generate every prime triplet which no side(a,b,c) can be greater than 500
 66:         /// (For the resulting triple to be primitive, u and v must be co-prime and u must be odd)
 67:         /// thus, u or v cannot exceed 23(for u:  u^2+2uv~500, for v: 2v^2+2uv~500)
 68:         /// </summary>
 69:         /// <returns></returns>
 70:         static int calculate_every_prime_triplet_and_test_each_s_multuples()
 71:         {
 72:             var map = new int[1001];
 73:             int u, v, g, h, i, a, b, c, p, m;
 74:             for (u = 23; u > 0; u -= 2)
 75:             {
 76:                 for (v = 23; v > 0; v--)
 77:                 {
 78:                     if (find_GCD(u, v) != 1)
 79:                         continue;
 80: 
 81:                     g = u * u;
 82:                     h = 2 * (v * v);
 83:                     i = 2 * u * v;
 84:                     a = g + i;
 85:                     b = h + i;
 86:                     c = g + h + i;
 87:                     p = a + b + c;
 88:                     if (p <= 1000)
 89:                     {
 90:                         m = 1;
 91:                         while (p * m <= 1000)
 92:                         {
 93:                             map[p * m]++;
 94:                             m++;
 95:                         }
 96:                     }
 97:                 }
 98:             }
 99:             var max = 0;
100:             var result = 0;
101:             for (i = 0; i < 1001; i++)
102:             {
103:                 if (map[i] > max)
104:                 {
105:                     max = map[i];
106:                     result = i;
107:                 }
108:             }
109:             return result;
110:         }
111: 
112:         /// <summary>
113:         /// Kvom's java solution(from this question's discussion thread)
114:         /// http://projecteuler.net/index.php?section=forum&id=39&page=4
115:         /// </summary>
116:         /// <returns></returns>
117:         static int someone_solution_from_q_discussion_thread()
118:         {
119:             int total = 0;
120:             int maxp = 0;
121:             for (int p = 12; p <= 1000; p += 2)
122:             {
123:                 int count = 0;
124:                 for (int a = 1; a < p / 2; a++)
125:                 {
126:                     for (int b = p / 2; b > a; b--)
127:                     {
128:                         if ((a * b) % 12 != 0)
129:                             continue;
130:                         int c = p - a - b;
131:                         if ((c * c) != (a * a + b * b))
132:                             continue;
133:                         count++;
134:                     }
135:                 }
136:                 if (count > total)
137:                 {
138:                     total = count;
139:                     maxp = p;
140:                 }
141:             }
142:             return maxp;
143:         }
144: 
145:         /// <summary>
146:         /// use Euclidean algorithm to find GCD, returns 1 if x and y are coprime
147:         /// http://en.wikipedia.org/wiki/Euclidean_algorithm
148:         /// </summary>
149:         static int find_GCD(int x, int y)
150:         {
151:             while (x > 0)
152:             {
153:                 y = y % x;
154:                 y = y + x; // the next three lines is just swapping x and y
155:                 x = y - x;
156:                 y = y - x;
157:             }
158:             return y;
159:         }
160: 
161:         static Stopwatch stopwatch = new Stopwatch();
162:         static void TestBenchSetup()
163:         {
164:             // Uses the second Core or Processor for the Test
165:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
166:             // Prevents "Normal" processes from interrupting Threads
167:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
168:             // Prevents "Normal" Threads from interrupting this thread
169:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
170:         }
171:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
172:         static void TestBenchLoader(Func<int> test_method)
173:         {
174:             stopwatch.Reset();
175:             stopwatch.Start();
176:             var result = 0;
177:             long avg_tick = 0;
178:             long avg_ms = 0;
179:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
180:             // stabilizes the CPU cache and pipeline.
181:             {
182:                 result = test_method(); // Warmup
183:             }
184:             stopwatch.Stop();
185:             for (int repeat = 0; repeat < 20; ++repeat)
186:             {
187:                 stopwatch.Reset();
188:                 stopwatch.Start();
189:                 result = test_method();
190:                 stopwatch.Stop();
191:                 avg_tick += stopwatch.ElapsedTicks;
192:                 avg_ms += stopwatch.ElapsedMilliseconds;
193:             }
194:             avg_tick = avg_tick / 20;
195:             avg_ms = avg_ms / 20;
196:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
197:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
198:         }
199:     }

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