XNA/Algorithm/WP7/BestPractices/and more…

Project Euler problem 89~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The sum of all the minimal product-sum numbers for 2≤k≤12000: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(find_bloated_form_and_subtract_accordingly);
  9:             TestBenchLoader(parse_to_int_then_convert_to_minimum_form);
 10: 
 11:             Console.WriteLine("Press any key to exit");
 12:             Console.ReadKey();
 13:         }
 14: 
 15:         /// <summary>
 16:         /// DCCCC(900) -> CM
 17:         /// CCCC(400)  -> CD
 18:         /// LXXXX(90)  -> XC
 19:         /// XXXX(40)   -> XL
 20:         /// VIIII(9)   -> IX
 21:         /// IIII(4)    -> IV
 22:         /// since the problem stated that "the file contain no more than four consecutive identical units",
 23:         /// so dont need to worry about 5-ish numeral units
 24:         /// </summary>
 25:         static int find_bloated_form_and_subtract_accordingly()
 26:         {
 27:             var saved = 0;
 28:             foreach (var line in File.ReadAllLines("roman.txt"))
 29:             {
 30:                 if (line.Contains("DCCCC") == true) saved += 3;
 31:                 else if (line.Contains("CCCC") == true) saved += 2;
 32: 
 33:                 if (line.Contains("LXXXX") == true) saved += 3;
 34:                 else if (line.Contains("XXXX") == true) saved += 2;
 35: 
 36:                 if (line.Contains("VIIII") == true) saved += 3;
 37:                 else if (line.Contains("IIII") == true) saved += 2;
 38:             }
 39:             return saved;
 40:         }
 41: 
 42:         /// <summary>
 43:         /// 1. covert each line in roman.txt from roman numerals form to int value
 44:         /// 2. construct a minimum form of roman numerals from the int value in 1.
 45:         /// 3. save the length difference between 1 and 2 and save the result
 46:         /// </summary>
 47:         static int parse_to_int_then_convert_to_minimum_form()
 48:         {
 49:             var result = 0;
 50:             foreach (var line in File.ReadAllLines("roman.txt"))
 51:             {
 52:                 var num = parse_numerals(line);
 53:                 var reduced = generate_minimum_numerals(num);
 54:                 var count = reduced.Length - line.Length;
 55:                 result += (line.Length - reduced.Length);
 56:             }
 57:             return result;
 58:         }
 59: 
 60:         /// <summary>
 61:         /// 1. Only I, X, and C can be used as the leading numeral in part of a subtractive pair.
 62:         /// 2. I can only be placed before V and X.
 63:         /// 3. X can only be placed before L and C.
 64:         /// 4. C can only be placed before D and M. (1900 = MCM 2400 = MMCD)
 65:         /// </summary>
 66:         static StringBuilder generate_minimum_numerals(int number)
 67:         {
 68:             int rem, n;
 69:             var numerals = new StringBuilder();
 70:             // thousands
 71:             if (number >= 1000)
 72:             {
 73:                 n = Math.DivRem(number, 1000, out rem);
 74:                 Enumerable.Range(0, n).Aggregate(numerals, (a, b) => numerals.Append('M'));
 75:                 number = rem;
 76:             }
 77:             // hundreds
 78:             if (number >= 100)
 79:             {
 80:                 n = Math.DivRem(number, 100, out rem);
 81:                 if (n == 9)
 82:                 {
 83:                     numerals.Append('C');
 84:                     numerals.Append('M');
 85:                     n -= 9;
 86:                 }
 87:                 else if (n >= 5)
 88:                 {
 89:                     numerals.Append('D');
 90:                     n -= 5;
 91:                 }
 92:                 else if (n == 4)
 93:                 {
 94:                     numerals.Append('C');
 95:                     numerals.Append('D');
 96:                     n -= 4;
 97:                 }
 98:                 Enumerable.Range(0, n).Aggregate(numerals, (a, b) => numerals.Append('C'));
 99:                 number = rem;
100:             }
101:             // tens
102:             if (number >= 10)
103:             {
104:                 n = Math.DivRem(number, 10, out rem);
105:                 if (n == 9)
106:                 {
107:                     numerals.Append('X');
108:                     numerals.Append('C');
109:                     n -= 9;
110:                 }
111:                 else if (n >= 5)
112:                 {
113:                     numerals.Append('L');
114:                     n -= 5;
115:                 }
116:                 else if (n == 4)
117:                 {
118:                     numerals.Append('X');
119:                     numerals.Append('L');
120:                     n -= 4;
121:                 }
122:                 Enumerable.Range(0, n).Aggregate(numerals, (a, b) => numerals.Append('X'));
123:                 number = rem;
124:             }
125:             //ones
126:             if (number >= 1)
127:             {
128:                 n = number;
129:                 if (n == 9)
130:                 {
131:                     numerals.Append('I');
132:                     numerals.Append('X');
133:                     n -= 9;
134:                 }
135:                 else if (n >= 5)
136:                 {
137:                     numerals.Append('V');
138:                     n -= 5;
139:                 }
140:                 else if (n == 4)
141:                 {
142:                     numerals.Append('I');
143:                     numerals.Append('V');
144:                     n -= 4;
145:                 }
146:                 Enumerable.Range(0, n).Aggregate(numerals, (a, b) => numerals.Append('I'));
147:             }
148:             return numerals;
149:         }
150: 
151:         /// <summary>
152:         /// I = 1
153:         /// V = 5
154:         /// X = 10
155:         /// L = 50
156:         /// C = 100
157:         /// D = 500
158:         /// M = 1000
159:         /// </summary>
160:         static int parse_numerals(string numerals)
161:         {
162:             var queue = new Queue<int>();
163:             for (int i = 0; i < numerals.Length; i++)
164:             {
165:                 switch (numerals[i])
166:                 {
167:                     case 'I': queue.Enqueue(1); break;
168:                     case 'V': queue.Enqueue(5); break;
169:                     case 'X': queue.Enqueue(10); break;
170:                     case 'L': queue.Enqueue(50); break;
171:                     case 'C': queue.Enqueue(100); break;
172:                     case 'D': queue.Enqueue(500); break;
173:                     case 'M': queue.Enqueue(1000); break;
174:                 }
175:             }
176:             var num = 0;
177:             while (queue.Count > 1)
178:             {
179:                 var n1 = queue.Dequeue();
180:                 var n2 = queue.Peek();
181:                 if (n1 < n2)
182:                 {
183:                     queue.Dequeue();
184:                     num += (n2 - n1);
185:                 }
186:                 else
187:                     num += n1;
188:             }
189:             if (queue.Count > 0)
190:                 num += queue.Dequeue();
191:             return num;
192:         }
193: 
194:         static Stopwatch stopwatch = new Stopwatch();
195:         static void TestBenchSetup()
196:         {
197:             // Uses the second Core or Processor for the Test
198:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
199:             // Prevents "Normal" processes from interrupting Threads
200:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
201:             // Prevents "Normal" Threads from interrupting this thread
202:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
203:         }
204:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
205:         static void TestBenchLoader(Func<int> test_method)
206:         {
207:             stopwatch.Reset();
208:             stopwatch.Start();
209:             var result = 0;
210:             long avg_tick = 0;
211:             long avg_ms = 0;
212:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
213:             // stabilizes the CPU cache and pipeline.
214:             {
215:                 result = test_method(); // Warmup
216:             }
217:             stopwatch.Stop();
218:             for (int repeat = 0; repeat < 20; ++repeat)
219:             {
220:                 stopwatch.Reset();
221:                 stopwatch.Start();
222:                 result = test_method();
223:                 stopwatch.Stop();
224:                 avg_tick += stopwatch.ElapsedTicks;
225:                 avg_ms += stopwatch.ElapsedMilliseconds;
226:             }
227:             avg_tick = avg_tick / 20;
228:             avg_ms = avg_ms / 20;
229:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
230:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
231:         }
232:     }

c++

Advertisements
This entry was posted in Uncategorized. 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