zing

Project Euler problem 68~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The the maximum 16-digit string for a magic 5-gon ring: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(brute_force_with_lexicographic_permutation);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// basically using the lexicographic permutation to generate all possible number combination and 
 16:         /// applies each rule to see the if number set matched all the criteria.
 17:         /// really slow(1 sec!). just the permutation itself is 3mil+ iterations, and rules checking take some time too
 18:         /// a lot optimization could be made, or another way. but not today. im done!
 19:         /// </summary>
 20:         static ulong brute_force_with_lexicographic_permutation()
 21:         {
 22:             var a = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
 23:             Func<int> line1 = () => a[5] + a[0] + a[1]; // so inner 5 nodes are a[0] to a[4] (clockwise)
 24:             Func<int> line2 = () => a[6] + a[1] + a[2]; //    outer 5 nodes are a[5] to a[9] (clockwise)
 25:             Func<int> line3 = () => a[7] + a[2] + a[3];
 26:             Func<int> line4 = () => a[8] + a[3] + a[4];
 27:             Func<int> line5 = () => a[9] + a[4] + a[0];
 28:             Func<bool> rule1 = () => a.Take(5).All(n => n != 10); // 10 cannot appear in centers (16-digits only)
 29:             Func<bool> rule2 = () => a[5] < a[6] && a[5] < a[7] && a[5] < a[8] && a[5] < a[9]; // first must be smallest
 30:             Func<bool> rule3 = () => line1() == line2() && line1() == line3() && line1() == line4() && line1() == line5();
 31:             var j = 0;
 32:             var l = 0;
 33:             var tmp = 0;
 34:             var len = a.Length;
 35:             var z = 0;
 36:             ulong cur = 0;
 37:             ulong max = 0;
 38:             while (true)
 39:             {
 40:                 //step 1. Find the largest index j such that a[j] < a[j + 1].
 41:                 for (j = len - 2; j >= 0; j--)
 42:                 {
 43:                     if (a[j] < a[j + 1])
 44:                         break;
 45:                 }
 46: 
 47:                 if (j == -1)
 48:                     break; // no more permutation, since no such index exist
 49: 
 50:                 //step 2. Find the largest index l such that a[j] < a[l]
 51:                 for (l = len - 1; l >= 0; l--)
 52:                 {
 53:                     if (a[j] < a[l])
 54:                         break;
 55:                 }
 56: 
 57:                 //step 3. Swap a[j] with a[l].
 58:                 tmp = a[j];
 59:                 a[j] = a[l];
 60:                 a[l] = tmp;
 61: 
 62:                 //step 4. Reverse the sequence from a[j + 1] up to and including the final element a[n]
 63:                 z = len - 1;
 64:                 for (l = j + 1; l < len; l++)
 65:                 {
 66:                     if (l >= z)
 67:                         break;
 68: 
 69:                     tmp = a[l];
 70:                     a[l] = a[z];
 71:                     a[z] = tmp;
 72:                     z--;
 73:                 }
 74:                 if (rule1() && rule2() && rule3())
 75:                 {
 76:                     var str = new StringBuilder();
 77:                     str.Append(string.Format("{0}{1}{2}", a[5], a[0], a[1]));
 78:                     str.Append(string.Format("{0}{1}{2}", a[6], a[1], a[2]));
 79:                     str.Append(string.Format("{0}{1}{2}", a[7], a[2], a[3]));
 80:                     str.Append(string.Format("{0}{1}{2}", a[8], a[3], a[4]));
 81:                     str.Append(string.Format("{0}{1}{2}", a[9], a[4], a[0]));
 82:                     cur = Convert.ToUInt64(str.ToString());
 83:                     if (max < cur)
 84:                         max = cur;
 85:                 }
 86:             }
 87:             return max;
 88:         }
 89: 
 90:         static Stopwatch stopwatch = new Stopwatch();
 91:         static void TestBenchSetup()
 92:         {
 93:             // Uses the second Core or Processor for the Test
 94:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
 95:             // Prevents "Normal" processes from interrupting Threads
 96:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
 97:             // Prevents "Normal" Threads from interrupting this thread
 98:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
 99:         }
100:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
101:         static void TestBenchLoader(Func<ulong> test_method)
102:         {
103:             stopwatch.Reset();
104:             stopwatch.Start();
105:             ulong result = 0;
106:             long avg_tick = 0;
107:             long avg_ms = 0;
108:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
109:             // stabilizes the CPU cache and pipeline.
110:             {
111:                 result = test_method(); // Warmup
112:             }
113:             stopwatch.Stop();
114:             for (int repeat = 0; repeat < 20; ++repeat)
115:             {
116:                 stopwatch.Reset();
117:                 stopwatch.Start();
118:                 result = test_method();
119:                 stopwatch.Stop();
120:                 avg_tick += stopwatch.ElapsedTicks;
121:                 avg_ms += stopwatch.ElapsedMilliseconds;
122:             }
123:             avg_tick = avg_tick / 20;
124:             avg_ms = avg_ms / 20;
125:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
126:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
127:         }
128:     }

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