WP7~~~~~~~~~~~~~

Project Euler problem 105~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The sum of all special sum sets: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(using_binary_counter_mechanism_from_problem_103);
  9: 
 10:             Console.WriteLine("press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         static int using_binary_counter_mechanism_from_problem_103()
 15:         {
 16:             var mask = new int[12];
 17:             var total = 0;
 18:             foreach (var line in File.ReadAllLines(@"..\..\sets.txt"))
 19:             {
 20:                 var nums = line.Split(new char[] { ',' }).Select(s => Convert.ToInt32(s)).ToList();
 21:                 total += check(nums, mask);
 22:             }
 23:             return total;
 24:         }
 25: 
 26:         /// <summary>
 27:         /// returns 0 if the nums is not a special sum set, 
 28:         /// for any other number, it means that the nums is a special sum set, and the returned number is
 29:         /// sum of all the number in the set
 30:         /// </summary>
 31:         static int check(List<int> nums, int[] mask)
 32:         {
 33:             // resets the mask(since the max is 12 as stated in problem's description
 34:             mask[0] = 0; mask[1] = 0; mask[2] = 0; mask[3] = 0;
 35:             mask[4] = 0; mask[5] = 0; mask[6] = 0; mask[7] = 0;
 36:             mask[8] = 0; mask[9] = 0; mask[10] = 0; mask[11] = 0;
 37: 
 38:             var pos = nums.Count - 1;
 39:             var map = new SortedDictionary<int, int>();
 40:             var sum = 0;
 41:             var counter = 0;
 42:             // using binary counter mechanism to generate subsets
 43:             while (pos >= 0)
 44:             {
 45:                 if (mask[pos] == 0)
 46:                 {
 47:                     mask[pos] = 1;
 48:                     pos = nums.Count - 1;
 49: 
 50:                     sum = 0;
 51:                     counter = 0;
 52:                     for (int i = 0; i < nums.Count; i++)
 53:                     {
 54:                         if (mask[i] == 1)
 55:                         {
 56:                             counter++;
 57:                             sum += nums[i];
 58:                         }
 59:                     }
 60:                     if (map.ContainsKey(sum) == true)
 61:                         return 0;
 62:                     else
 63:                         map.Add(sum, counter);
 64:                 }
 65:                 else
 66:                 {
 67:                     mask[pos] = 0;
 68:                     pos--;
 69:                 }
 70:             }
 71:             var prev = 0;
 72:             var cur = 0;
 73:             foreach (var pair in map)
 74:             {
 75:                 cur = pair.Value;
 76:                 if (cur < prev)
 77:                     return 0;
 78: 
 79:                 prev = cur;
 80:             }
 81:             return nums.Sum();
 82:         }
 83: 
 84:         static Stopwatch stopwatch = new Stopwatch();
 85:         static void TestBenchSetup()
 86:         {
 87:             // Uses the second Core or Processor for the Test
 88:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
 89:             // Prevents "Normal" processes from interrupting Threads
 90:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
 91:             // Prevents "Normal" Threads from interrupting this thread
 92:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
 93:         }
 94:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
 95:         static void TestBenchLoader(Func<int> test_method)
 96:         {
 97:             stopwatch.Reset();
 98:             stopwatch.Start();
 99:             long result = 0;
100:             long avg_tick = 0;
101:             long avg_ms = 0;
102:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms
103:             // stabilizes the CPU cache and pipeline.
104:             {
105:                 result = test_method(); // Warmup
106:             }
107:             stopwatch.Stop();
108:             for (int repeat = 0; repeat < 20; ++repeat)
109:             {
110:                 stopwatch.Reset();
111:                 stopwatch.Start();
112:                 result = test_method();
113:                 stopwatch.Stop();
114:                 avg_tick += stopwatch.ElapsedTicks;
115:                 avg_ms += stopwatch.ElapsedMilliseconds;
116:             }
117:             avg_tick = avg_tick / 20;
118:             avg_ms = avg_ms / 20;
119:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
120:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
121:         }
122:     }

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