WP7/Algorithm/and more…

Project Euler problem 98~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The largest square number formed by any member of such a pair: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(plain_group_and_iterating_through_each_anagram_pairs);
  9: 
 10:             Console.WriteLine("press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         static int plain_group_and_iterating_through_each_anagram_pairs()
 15:         {
 16:             // ---- create a dictionary which group words that are anagrams to each other ----
 17:             var word_map = new Dictionary<string, List<string>>();
 18:             foreach (var word in File.ReadAllText("words.txt")
 19:                 .Split(new char[] { ',', '"' }, StringSplitOptions.RemoveEmptyEntries))
 20:             {
 21:                 var key = new string(word.ToCharArray().OrderBy(c => c).ToArray());
 22:                 if (word_map.ContainsKey(key) == false)
 23:                     word_map.Add(key, new List<string>());
 24: 
 25:                 word_map[key].Add(word);
 26:             }
 27:             // ---- create a square number dictionary which firstly group numbers by their digits count ----
 28:             //      then map the number to their square value
 29:             var bound = (int)Math.Sqrt(999999999); // since the longest anagrams group is 9 in length
 30:             var power_map = new Dictionary<int, Dictionary<int, int>>();
 31:             var len = 1;
 32:             var tens = 10;
 33:             var square = 0;
 34:             for (int i = 0; i < bound; i++)
 35:             {
 36:                 square = i * i;
 37:                 if (square >= tens)
 38:                 {
 39:                     tens *= 10;
 40:                     len++;
 41:                 }
 42:                 if (power_map.ContainsKey(len) == false)
 43:                     power_map.Add(len, new Dictionary<int, int>());
 44: 
 45:                 power_map[len].Add(square, i);
 46:             }
 47:             // ---- for each anagrams group, try to create a working and valid mapping for each word and each ----
 48:             //      square number with same length, and then use the mapping to test rest of the word to see
 49:             //      if such pair exists, and store the pair with highest square number produced
 50:             var result_num = 0;
 51:             foreach (var groups in word_map.Where(e => e.Value.Count > 1)) // only check if group has pairs
 52:             {
 53:                 len = groups.Key.Length;
 54: 
 55:                 var powers = power_map[len];
 56:                 bound = groups.Value.Count;
 57:                 for (int i = 0; i < bound; i++)
 58:                 {
 59:                     var word1 = groups.Value[i];
 60:                     foreach (var num1 in powers.Keys) // iterate through all the square numbers that have same length as word
 61:                     {
 62:                         var mapping = create_mapping(word1, num1);
 63:                         if (mapping != null)
 64:                         {
 65:                             for (int j = i + 1; j < bound; j++)
 66:                             {
 67:                                 var word2 = groups.Value[j];
 68:                                 var num2 = map_word_to_num(mapping, word2);
 69:                                 if (powers.ContainsKey(num2) == true)
 70:                                 {
 71:                                     if (num2 > result_num)
 72:                                         result_num = Math.Max(num1, num2);
 73:                                 }
 74:                             }
 75:                         }
 76:                     }
 77:                 }
 78:             }
 79:             return result_num;
 80:         }
 81: 
 82:         /// <summary>
 83:         /// attempt to create a mapping from word to num.
 84:         /// return null, if unable to create one to one mapping in both direction
 85:         /// </summary>
 86:         static Dictionary<char, int> create_mapping(string word, int num)
 87:         {
 88:             var map_int_char = new Dictionary<int, char>();
 89:             var c_index = word.Length - 1;
 90:             do
 91:             {
 92:                 var n = num % 10;
 93:                 var c = word[c_index--];
 94:                 if (map_int_char.ContainsKey(n) == false)
 95:                     map_int_char.Add(n, c);
 96:                 else
 97:                 {
 98:                     if (map_int_char[n] != c)
 99:                         return null;
100:                 }
101:             } while ((num /= 10) > 0);
102:             var map_char_int = new Dictionary<char, int>();
103:             foreach (var item in map_int_char) // double check both int->char and char->int are one to one
104:             {
105:                 if (map_char_int.ContainsKey(item.Value) == true)
106:                     return null;
107:                 else
108:                     map_char_int.Add(item.Value, item.Key);
109:             }
110:             return map_char_int;
111:         }
112: 
113:         /// <summary>
114:         /// using mapping dictionary to tranform word into numeric value
115:         /// </summary>
116:         static int map_word_to_num(Dictionary<char, int> mapping, string word)
117:         {
118:             var num = 0;
119:             for (int i = 0; i < word.Length; i++)
120:             {
121:                 var n = mapping[word[i]];
122:                 num += n;
123:                 num *= 10;
124:             }
125:             return num / 10;
126:         }
127: 
128:         static Stopwatch stopwatch = new Stopwatch();
129:         static void TestBenchSetup()
130:         {
131:             // Uses the second Core or Processor for the Test
132:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
133:             // Prevents "Normal" processes from interrupting Threads
134:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
135:             // Prevents "Normal" Threads from interrupting this thread
136:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
137:         }
138:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
139:         static void TestBenchLoader(Func<int> test_method)
140:         {
141:             stopwatch.Reset();
142:             stopwatch.Start();
143:             long result = 0;
144:             long avg_tick = 0;
145:             long avg_ms = 0;
146:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms
147:             // stabilizes the CPU cache and pipeline.
148:             {
149:                 result = test_method(); // Warmup
150:             }
151:             stopwatch.Stop();
152:             for (int repeat = 0; repeat < 20; ++repeat)
153:             {
154:                 stopwatch.Reset();
155:                 stopwatch.Start();
156:                 result = test_method();
157:                 stopwatch.Stop();
158:                 avg_tick += stopwatch.ElapsedTicks;
159:                 avg_ms += stopwatch.ElapsedMilliseconds;
160:             }
161:             avg_tick = avg_tick / 20;
162:             avg_ms = avg_ms / 20;
163:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
164:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
165:         }
166:     }

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