Programming/XNA/GameDev/WP7/and more…

Project Euler problem 103~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The set string: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(slow_brute_force_with_combination_and_subsets_generation);
  9: 
 10:             Console.WriteLine("press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// bascially generates all the combination of picking 7 numbers out of 20-50
 16:         /// (the 50 is coming from http://journals.cambridge.org/production/action/cjoGetFulltext?fulltextid=6993056)
 17:         /// and then using check_OSS_conditions method to see if it satisfies the OSS set conditions.
 18:         /// extremely slow. takes 22sec on my machine
 19:         /// and the answer is same as the result produced by "near optimum set algorithm" provided by the question 
 20:         /// </summary>
 21:         /// <returns></returns>
 22:         static long slow_brute_force_with_combination_and_subsets_generation()
 23:         {
 24:             var set = new int[7];
 25:             var mask = new int[7];
 26:             var lower = 20;
 27:             var upper = 50; //  according to paper, the upperbound is less or equal to previous OSS's largest element
 28:             var bucket = new int[50 + 49 + 48 + 47 + 46 + 45 + 44]; //329
 29:             var map = new SortedDictionary<int, int>();
 30:             int n1, n2, n3, n4, n5, n6, n7, sum;
 31:             var min = int.MaxValue;
 32:             long result = 0;
 33:             for (n1 = lower; n1 < 45; n1++)
 34:             {
 35:                 set[0] = n1;
 36:                 for (n2 = n1 + 1; n2 < 46; n2++)
 37:                 {
 38:                     set[1] = n2;
 39:                     for (n3 = n2 + 1; n3 < 47; n3++)
 40:                     {
 41:                         set[2] = n3;
 42:                         for (n4 = n3 + 1; n4 < 48; n4++)
 43:                         {
 44:                             set[3] = n4;
 45:                             for (n5 = n4 + 1; n5 < 49; n5++)
 46:                             {
 47:                                 set[4] = n5;
 48:                                 for (n6 = n5 + 1; n6 < 50; n6++)
 49:                                 {
 50:                                     set[5] = n6;
 51:                                     for (n7 = n6 + 1; n7 < 51; n7++)
 52:                                     {
 53:                                         set[6] = n7;
 54:                                         sum = check_OSS_conditions(set, mask);
 55:                                         if (sum != 0 && sum < min)
 56:                                         {
 57:                                             min = sum;
 58:                                             result = set[0];
 59:                                             for (int i = 1; i < 7; i++)
 60:                                             {
 61:                                                 result = result * 100 + set[i];
 62:                                             }
 63:                                         }
 64:                                     }
 65:                                 }
 66:                             }
 67:                         }
 68:                     }
 69:                 }
 70:             }
 71:             return result;
 72:         }
 73: 
 74:         /// <summary>
 75:         /// generates subsets by using binary counter (http://compprog.wordpress.com/2007/10/10/generating-subsets/)
 76:         /// checks the condition of sums of subsets cannot be equal by using a sorted dictionary
 77:         /// </summary>
 78:         /// <param name="nums">contains the set to be check for optimum special sum set</param>
 79:         /// <param name="mask">the mask which is used for generating subsets</param>
 80:         /// <returns></returns>
 81:         static int check_OSS_conditions(int[] nums, int[] mask)
 82:         {
 83:             for (int i = 0; i < 7; i++)
 84:             {
 85:                 mask[i] = 0;
 86:             }
 87:             var pos = 6;
 88:             var map = new SortedDictionary<int, int>();
 89:             var sum = 0;
 90:             var counter = 0;
 91:             while (pos >= 0)
 92:             {
 93:                 if (mask[pos] == 0)
 94:                 {
 95:                     mask[pos] = 1;
 96:                     pos = 6;
 97: 
 98:                     sum = 0;
 99:                     counter = 0;
100:                     for (int z = 0; z < mask.Length; z++)
101:                     {
102:                         if (mask[z] == 1)
103:                         {
104:                             counter++;
105:                             sum += nums[z];
106:                         }
107:                     }
108:                     if (map.ContainsKey(sum) == true)
109:                         return 0;
110:                     else
111:                         map.Add(sum, counter);
112:                 }
113:                 else
114:                 {
115:                     mask[pos] = 0;
116:                     pos--;
117:                 }
118:             }
119:             var prev = 0;
120:             var cur = 0;
121:             foreach (var pair in map)
122:             {
123:                 cur = pair.Value;
124:                 if (cur < prev)
125:                     return 0;
126: 
127:                 prev = cur;
128:             }
129:             return nums.Sum();
130:         }
131: 
132:         static Stopwatch stopwatch = new Stopwatch();
133:         static void TestBenchSetup()
134:         {
135:             // Uses the second Core or Processor for the Test
136:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
137:             // Prevents "Normal" processes from interrupting Threads
138:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
139:             // Prevents "Normal" Threads from interrupting this thread
140:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
141:         }
142:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
143:         static void TestBenchLoader(Func<long> test_method)
144:         {
145:             stopwatch.Reset();
146:             stopwatch.Start();
147:             long result = 0;
148:             long avg_tick = 0;
149:             long avg_ms = 0;
150:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms
151:             // stabilizes the CPU cache and pipeline.
152:             {
153:                 result = test_method(); // Warmup
154:             }
155:             stopwatch.Stop();
156:             for (int repeat = 0; repeat < 20; ++repeat)
157:             {
158:                 stopwatch.Reset();
159:                 stopwatch.Start();
160:                 result = test_method();
161:                 stopwatch.Stop();
162:                 avg_tick += stopwatch.ElapsedTicks;
163:                 avg_ms += stopwatch.ElapsedMilliseconds;
164:             }
165:             avg_tick = avg_tick / 20;
166:             avg_ms = avg_ms / 20;
167:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
168:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
169:         }
170:     }

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