GameDev/XNA/WP7/C#/and more…

Project Euler problem 93~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The longest set of consecutive positive integers, 1 to n, can be obtained: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(plain_brute_force_test_all_possible_combinations);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// basically construct all the possible combinations of numbers, operators, and parentheses and calculate
 16:         /// the generated formula:
 17:         /// 1. generate all subset of 4 numbers out of 10 numbers
 18:         /// 2. for each subset, generate all the permutation
 19:         /// 3. for each permutation, generate all the operators combinations
 20:         /// 4. compute the 5 placement of parentheses that reall matters and store the result
 21:         /// 5. find and record the longest chain for the given subset of 4 number from 1.
 22:         /// </summary>
 23:         static string plain_brute_force_test_all_possible_combinations()
 24:         {
 25:             var s = new int[4];
 26:             var ops = new char[] { '+', '-', '*', '/' };
 27:             var len = s.Length;
 28:             int j, l, z, tmp;
 29:             var answer = string.Empty;
 30:             var max = 0;
 31:             // generates combination of 4 numbers from 0 to 9
 32:             for (int a = 0; a < 7; a++)
 33:             {
 34:                 for (int b = a + 1; b < 8; b++)
 35:                 {
 36:                     for (int c = b + 1; c < 9; c++)
 37:                     {
 38:                         for (int d = c + 1; d < 10; d++)
 39:                         {
 40:                             s[0] = a;
 41:                             s[1] = b;
 42:                             s[2] = c;
 43:                             s[3] = d;
 44:                             var chain = new bool[1000]; // used to test for continutation of calculated results
 45:                             // generates lexicographic permutation of set {a,b,c,d}
 46:                             while (true)
 47:                             {
 48:                                 //step 1. Find the largest index j such that a[j] < a[j + 1].
 49:                                 for (j = len - 2; j >= 0; j--)
 50:                                 {
 51:                                     if (s[j] < s[j + 1]) break;
 52:                                 }
 53:                                 if (j == -1) break; // no more permutation, since no such index exist
 54: 
 55:                                 //step 2. Find the largest index l such that a[j] < a[l]
 56:                                 for (l = len - 1; l >= 0; l--)
 57:                                 {
 58:                                     if (s[j] < s[l]) break;
 59:                                 }
 60: 
 61:                                 //step 3. Swap a[j] with a[l].
 62:                                 tmp = s[j];
 63:                                 s[j] = s[l];
 64:                                 s[l] = tmp;
 65: 
 66:                                 //step 4. Reverse the sequence from a[j + 1] up to and including the final element a[n]
 67:                                 z = len - 1;
 68:                                 for (l = j + 1; l < len; l++)
 69:                                 {
 70:                                     if (l >= z) break;
 71: 
 72:                                     tmp = s[l];
 73:                                     s[l] = s[z];
 74:                                     s[z] = tmp;
 75:                                     z--;
 76:                                 }
 77: 
 78:                                 // generates combinations of operators(+,-,*,/)
 79:                                 generate_operators(ops, s[0], s[1], s[2], s[3], chain);
 80:                             }
 81:                             // find out maximum continuous chain length from n = 1
 82:                             var cur = 0;
 83:                             for (j = 1; j < 1000; j++)
 84:                             {
 85:                                 if (chain[j] == false)
 86:                                     break;
 87:                                 cur++;
 88:                             }
 89:                             if (max < cur)
 90:                             {
 91:                                 max = cur;
 92:                                 answer = string.Format("{0}{1}{2}{3}", a, b, c, d);
 93:                             }
 94:                         }
 95:                     }
 96:                 }
 97:             }
 98:             return answer;
 99:         }
100: 
101:         static void generate_operators(char[] ops, int a, int b, int c, int d, bool[] chain)
102:         {
103:             foreach (var op1 in ops)
104:             {
105:                 foreach (var op2 in ops)
106:                 {
107:                     foreach (var op3 in ops)
108:                     {
109:                         //  since there are only 5 parentheses combinations that really matters
110:                         validate_and_log_calculation(cal(cal(cal(a, b, op1), c, op2), d, op3), chain); // ((a + b) + c) + d
111:                         validate_and_log_calculation(cal(cal(a, cal(b, c, op2), op1), d, op3), chain); // (a + (b + c)) + d
112:                         validate_and_log_calculation(cal(a, cal(cal(b, c, op2), d, op3), op1), chain); // a + ((b + c) + d)
113:                         validate_and_log_calculation(cal(a, cal(b, cal(c, d, op3), op2), op1), chain); // a + (b + (c + d))
114:                         validate_and_log_calculation(cal(cal(a, b, op1), cal(c, d, op3), op2), chain); // (a + b) + (c + d)
115:                     }
116:                 }
117:             }
118:         }
119: 
120:         static void validate_and_log_calculation(double value, bool[] chain)
121:         {
122:             if (value > 0 && value < 1000) // 1k should be well above the end of maximum chain 
123:             {
124:                 var int_value = (int)value; // only integer result 
125:                 if (value == int_value)
126:                     chain[int_value] = true;
127:             }
128:         }
129: 
130:         static double cal(double a, double b, char op)
131:         {
132:             double result = 0;
133:             switch (op)
134:             {
135:                 case '+': result = a + b; break;
136:                 case '-': result = a - b; break;
137:                 case '*': result = a * b; break;
138:                 case '/': result = b != 0 ? a / b : int.MinValue; break; // indicate that division by zero
139:             }
140:             return result;
141:         }
142: 
143:         static Stopwatch stopwatch = new Stopwatch();
144:         static void TestBenchSetup()
145:         {
146:             // Uses the second Core or Processor for the Test
147:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
148:             // Prevents "Normal" processes from interrupting Threads
149:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
150:             // Prevents "Normal" Threads from interrupting this thread
151:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
152:         }
153:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
154:         static void TestBenchLoader(Func<string> test_method)
155:         {
156:             stopwatch.Reset();
157:             stopwatch.Start();
158:             var result = string.Empty;
159:             long avg_tick = 0;
160:             long avg_ms = 0;
161:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
162:             // stabilizes the CPU cache and pipeline.
163:             {
164:                 result = test_method(); // Warmup
165:             }
166:             stopwatch.Stop();
167:             for (int repeat = 0; repeat < 20; ++repeat)
168:             {
169:                 stopwatch.Reset();
170:                 stopwatch.Start();
171:                 result = test_method();
172:                 stopwatch.Stop();
173:                 avg_tick += stopwatch.ElapsedTicks;
174:                 avg_ms += stopwatch.ElapsedMilliseconds;
175:             }
176:             avg_tick = avg_tick / 20;
177:             avg_ms = avg_ms / 20;
178:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
179:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
180:         }
181:     }

c++

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