FacetedNavigation/FunctionalC#/SL/WEPF/and more…

Project Euler problem 43~

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The sum of all 0 to 9 pandigital numbers with this property");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(precalculate_possible_d8d9d10_to_limit_permu_range);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// basically first calculate all the 3-digit number that is multiple of 17 and contain all unique number
 16:         /// then generate permutation for each number and check for all conditions specified by the question
 17:         /// </summary>
 18:         /// <returns></returns>
 19:         static long precalculate_possible_d8d9d10_to_limit_permu_range()
 20:         {
 21:             var num = 17;
 22:             var upper = 999;
 23:             var cur = num * 6;
 24:             char[] tmp;
 25:             var seeds = new List<string>();
 26:             while (cur <= upper)
 27:             {
 28:                 cur += num;
 29:                 tmp = cur.ToString().ToCharArray();
 30: 
 31:                 if (tmp.Length == tmp.Distinct().Count())
 32:                     seeds.Add(cur.ToString());
 33:             }
 34:             var permu = new List<int>() { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 35:             long result = 0;
 36:             foreach (var item in seeds)
 37:             {
 38:                 result += find_largest_prime_within_permutations(Enumerable.Range(0, 10)
 39:                      .Where(l => item.Contains(l.ToString()) == false).ToArray(),
 40:                      Convert.ToInt32(item[0]) - 48,
 41:                      Convert.ToInt32(item[1]) - 48,
 42:                      Convert.ToInt32(item[2]) - 48);
 43:             }
 44:             return result;
 45:         }
 46: 
 47:         /// <summary>
 48:         /// basically the same code from question 24, which uses the algorithm from knuth's book
 49:         /// http://en.wikipedia.org/wiki/Permutation#Systematic_generation_of_all_permutations
 50:         /// </summary>
 51:         /// <param name="a">contains seed values for permutation to be generated from</param>
 52:         /// <returns></returns>
 53:         static long find_largest_prime_within_permutations(int[] a, int d8, int d9, int d10)
 54:         {
 55:             var j = 0;
 56:             var l = 0;
 57:             var tmp = 0;
 58:             var len = a.Length;
 59:             var z = 0;
 60:             long result = 0;
 61:             while (true)
 62:             {
 63:                 //step 1. Find the largest index j such that a[j] < a[j + 1].
 64:                 for (j = len - 2; j >= 0; j--)
 65:                 {
 66:                     if (a[j] < a[j + 1])
 67:                         break;
 68:                 }
 69:                 if (j == -1)
 70:                     break; // no more permutation, since no such index exist
 71:                 //step 2. Find the largest index l such that a[j] < a[l]
 72:                 for (l = len - 1; l >= 0; l--)
 73:                 {
 74:                     if (a[j] < a[l])
 75:                         break;
 76:                 }
 77:                 //step 3. Swap a[j] with a[l].
 78:                 tmp = a[j];
 79:                 a[j] = a[l];
 80:                 a[l] = tmp;
 81:                 //step 4. Reverse the sequence from a[j + 1] up to and including the final element a[n]
 82:                 z = len - 1;
 83:                 for (l = j + 1; l < len; l++)
 84:                 {
 85:                     if (l >= z)
 86:                         break;
 87:                     tmp = a[l];
 88:                     a[l] = a[z];
 89:                     a[z] = tmp;
 90:                     z--;
 91:                 }
 92:                 if (a[5] == 5 && (a[6] * 100 + d8 * 10 + d9) % 13 == 0 && a[3] % 2 == 0 && (a[2] + a[3] + a[4]) % 3 == 0 
 93:                     && (a[4] * 100 + a[5] * 10 + a[6]) % 7 == 0 && (a[5] * 100 + a[6] * 10 + d8) % 11 == 0)
 94:                 {
 95:                     result += Convert.ToInt64(a
 96:                         .Aggregate(new StringBuilder(len), (s, n) => s.Append(n)).ToString() + d8 + d9 + d10);
 97:                 }
 98:             }
 99:             return result;
100:         }
101: 
102:         static Stopwatch stopwatch = new Stopwatch();
103:         static void TestBenchSetup()
104:         {
105:             // Uses the second Core or Processor for the Test
106:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
107:             // Prevents "Normal" processes from interrupting Threads
108:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
109:             // Prevents "Normal" Threads from interrupting this thread
110:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
111:         }
112:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
113:         static void TestBenchLoader(Func<long> test_method)
114:         {
115:             stopwatch.Reset();
116:             stopwatch.Start();
117:             long result = 0;
118:             long avg_tick = 0;
119:             long avg_ms = 0;
120:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
121:             // stabilizes the CPU cache and pipeline.
122:             {
123:                 result = test_method(); // Warmup
124:             }
125:             stopwatch.Stop();
126:             for (int repeat = 0; repeat < 20; ++repeat)
127:             {
128:                 stopwatch.Reset();
129:                 stopwatch.Start();
130:                 result = test_method();
131:                 stopwatch.Stop();
132:                 avg_tick += stopwatch.ElapsedTicks;
133:                 avg_ms += stopwatch.ElapsedMilliseconds;
134:             }
135:             avg_tick = avg_tick / 20;
136:             avg_ms = avg_ms / 20;
137:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
138:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
139:         }
140: 
141:     }

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