its friday~

Project Euler problem 62~

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The smallest cube for which exactly five permutations of its digits are cube:");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(using_dictionary_and_key_to_find_match);
  9:             TestBenchLoader(using_linq_with_group_by_calculated_key);
 10:             TestBenchLoader(brute_force_test_all_possible_permutation);
 11: 
 12:             Console.WriteLine("Press any key to exit");
 13:             Console.ReadKey();
 14:         }
 15: 
 16:         /// <summary>
 17:         /// basically using dictionary to do bookkeeping, iterate all the number within range
 18:         /// and stop as soon as the answer is found.
 19:         /// using calculate_key method such that all the permuation of a cube number would produce same key number
 20:         /// as for range, arbitrarily choose 9999, and it worked lol
 21:         /// </summary>
 22:         static long using_dictionary_and_key_to_find_match()
 23:         {
 24:             long num, key;
 25:             var map = new Dictionary<long, List<long>>();
 26:             for (int i = 346; i < 9999; i++)
 27:             {
 28:                 num = (long)Math.Pow(i, 3);
 29:                 key = calculate_key(num);
 30: 
 31:                 if (map.ContainsKey(key) == true)
 32:                 {
 33:                     map[key].Add(num);
 34:                     if (map[key].Count == 5)
 35:                         return map[key][0];
 36:                 }
 37:                 else
 38:                     map.Add(key, new List<long>() { num });
 39:             }
 40:             return 0;
 41:         }
 42: 
 43:         /// <summary>
 44:         /// basically the linq version, since with the grouping and the count, it will
 45:         /// go through all the numbers within range
 46:         /// </summary>
 47:         static long using_linq_with_group_by_calculated_key()
 48:         {
 49:             var start = 346;
 50:             var end = 9999;
 51:             var map = Enumerable.Range(start, end - start + 1)
 52:                 .Select(n => new
 53:                 {
 54:                     num = (long)Math.Pow(n, 3),
 55:                     key = calculate_key((long)Math.Pow(n, 3))
 56:                 })
 57:                 .GroupBy(n => n.key)
 58:                 .First(n => n.Count() == 5).First();
 59:             return map.num;
 60:         }
 61: 
 62:         /// <summary>
 63:         /// basically pre-calcuated all the cube number within range
 64:         /// for each number in range, iterate though all the cube number to see if the count match to question's condition
 65:         /// </summary>
 66:         static long brute_force_test_all_possible_permutation()
 67:         {
 68:             var start = 346;
 69:             var end = 9999;
 70:             var map = Enumerable.Range(start, end - start + 1)
 71:                 .Select(n => (long)Math.Pow(n, 3)).ToArray();
 72: 
 73:             int i, j;
 74:             var len = map.Length;
 75:             var req = 5;
 76:             var ret = 0;
 77:             for (i = 0; i < len; i++)
 78:             {
 79:                 var count = 1;
 80:                 for (j = i + 1; j < len; j++)
 81:                 {
 82:                     ret = isPerm(map[i], map[j]);
 83:                     if (ret == 1 || count > req) // since the cube after that will all have more digits, no need to continue
 84:                         break;
 85:                     if (ret == 0)
 86:                         count++;
 87:                 }
 88:                 if (count == req)
 89:                     return map[i];
 90:             }
 91:             return 0;
 92:         }
 93: 
 94:         /// <summary>
 95:         /// returns 1 if the candidate is longer than original
 96:         /// returns 0 if it is permutation of original
 97:         /// returns -1 if it is not a permutation
 98:         /// </summary>
 99:         static int isPerm(long original, long candidate)
100:         {
101:             var map = new int[10];
102:             while (original > 0)
103:             {
104:                 map[original % 10]++;
105:                 original /= 10;
106:                 map[candidate % 10]--;
107:                 candidate /= 10;
108:             }
109: 
110:             if (candidate > 0)
111:                 return 1;
112: 
113:             if (map.All(n => n == 0) == true)
114:                 return 0;
115:             else
116:                 return -1;
117:         }
118: 
119:         /// <summary>
120:         /// basically extract all the digit from original, sort the digits
121:         /// and then create a key number from reverse digits from the list(to avoid leading zeros)
122:         /// and all the number with same key are permutation of each other
123:         /// </summary>
124:         static long calculate_key(long original)
125:         {
126:             var list = new List<long>();
127:             long rem = 0;
128:             while (original > 0)
129:             {
130:                 original = Math.DivRem(original, 10, out rem);
131:                 list.Add(rem);
132:             }
133:             list.Sort();
134:             long key = 0;
135:             for (int i = list.Count - 1; i >= 0; i--)
136:             {
137:                 key *= 10;
138:                 key += list[i];
139:             }
140:             return key;
141:         }
142: 
143:         static Stopwatch stopwatch = new Stopwatch();
144:         static void TestBenchSetup()
145:         {
146:             // Uses the second Core or Processor for the Test
147:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
148:             // Prevents "Normal" processes from interrupting Threads
149:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
150:             // Prevents "Normal" Threads from interrupting this thread
151:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
152:         }
153:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
154:         static void TestBenchLoader(Func<long> test_method)
155:         {
156:             stopwatch.Reset();
157:             stopwatch.Start();
158:             long result = 0;
159:             long avg_tick = 0;
160:             long avg_ms = 0;
161:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms
162:             // stabilizes the CPU cache and pipeline.
163:             {
164:                 result = test_method(); // Warmup
165:             }
166:             stopwatch.Stop();
167:             for (int repeat = 0; repeat < 20; ++repeat)
168:             {
169:                 stopwatch.Reset();
170:                 stopwatch.Start();
171:                 result = test_method();
172:                 stopwatch.Stop();
173:                 avg_tick += stopwatch.ElapsedTicks;
174:                 avg_ms += stopwatch.ElapsedMilliseconds;
175:             }
176:             avg_tick = avg_tick / 20;
177:             avg_ms = avg_ms / 20;
178:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
179:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
180:         }
181:     }

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