Twitter/LINQ/XNA/and more…

Project Euler problem 52~

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits:");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(test_each_number_between_100k_to_166666);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// starting with 6-digit number, the range would be 100k to 166666
 16:         /// for each number, basically test each 6x,5x,4x,...,1x to see if they all have the same
 17:         /// digits(essentially permutation of each other)
 18:         /// luckily in 6-digit realm, such number does exist
 19:         /// </summary>
 20:         static int test_each_number_between_100k_to_166666()
 21:         {
 22:             int n, x;
 23:             var same = true;
 24:             for (n = 100000; n <= 166666; n++) // since more than 166666, 6x will produce extra digit
 25:             {
 26:                 for (x = 6; x > 1; x--) //reverse == fail early
 27:                 {
 28:                     same = isPerm(n, n * x);
 29:                     if (same == false)
 30:                         break;
 31:                 }
 32:                 if (same == true)
 33:                     return n;
 34:             }
 35:             return 0;
 36:         }
 37: 
 38:         /// <summary>
 39:         /// basically the same code from problem 49
 40:         /// </summary>
 41:         static bool isPerm(int original, int candidate)
 42:         {
 43:             var map = new int[10];
 44:             while (original > 0)
 45:             {
 46:                 map[original % 10]++;
 47:                 original /= 10;
 48:                 map[candidate % 10]--;
 49:                 candidate /= 10;
 50:             }
 51:             return map.All(n => n == 0);
 52:         }
 53: 
 54:         static Stopwatch stopwatch = new Stopwatch();
 55:         static void TestBenchSetup()
 56:         {
 57:             // Uses the second Core or Processor for the Test
 58:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
 59:             // Prevents "Normal" processes from interrupting Threads
 60:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
 61:             // Prevents "Normal" Threads from interrupting this thread
 62:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
 63:         }
 64:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
 65:         static void TestBenchLoader(Func<int> test_method)
 66:         {
 67:             stopwatch.Reset();
 68:             stopwatch.Start();
 69:             var result = 0;
 70:             long avg_tick = 0;
 71:             long avg_ms = 0;
 72:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
 73:             // stabilizes the CPU cache and pipeline.
 74:             {
 75:                 result = test_method(); // Warmup
 76:             }
 77:             stopwatch.Stop();
 78:             for (int repeat = 0; repeat < 20; ++repeat)
 79:             {
 80:                 stopwatch.Reset();
 81:                 stopwatch.Start();
 82:                 result = test_method();
 83:                 stopwatch.Stop();
 84:                 avg_tick += stopwatch.ElapsedTicks;
 85:                 avg_ms += stopwatch.ElapsedMilliseconds;
 86:             }
 87:             avg_tick = avg_tick / 20;
 88:             avg_ms = avg_ms / 20;
 89:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
 90:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
 91:         }
 92:     }

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