WP7/jQuery/GameDev/and more…

Project Euler problem 59~

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The sum of the ASCII values in the original text: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(using_heuristic_method_to_find_best_matching_key);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// basically by finding out all the keys that produce the most alphabetical characters,
 16:         /// since the message is likely to be paragraphs of english text. And then base on the commonly
 17:         /// occured english word, narrow down the possible keys to one with highest "score", and decrypt
 18:         /// the message with that key, and sums up all the ascii value of each character
 19:         /// </summary>
 20:         /// <returns></returns>
 21:         static int using_heuristic_method_to_find_best_matching_key()
 22:         {
 23:             var keys = Enumerable.Range(97, 26).ToArray();
 24:             var text = File.ReadAllText("cipher1.txt")
 25:                 .Split(new char[] { ',' })
 26:                 .Select(c => int.Parse(c)).ToArray();
 27:             var possible_keys = new int[3][];
 28:             possible_keys[0] = find_key_candidate(text, keys, 0);
 29:             possible_keys[1] = find_key_candidate(text, keys, 1);
 30:             possible_keys[2] = find_key_candidate(text, keys, 2);
 31:             var max = 0;
 32:             var cur = 0;
 33:             var best = new int[3];
 34:             int[] decrypted_text = null;
 35:             int[] tmp;
 36:             foreach (var k1 in possible_keys[0])
 37:             {
 38:                 foreach (var k2 in possible_keys[1])
 39:                 {
 40:                     foreach (var k3 in possible_keys[2])
 41:                     {
 42:                         tmp = decrypt_with_key(text, new int[] { k1, k2, k3 });
 43:                         cur = calculate_key_score_using_heuristic(tmp);
 44:                         if (cur > max)
 45:                         {
 46:                             decrypted_text = tmp;
 47:                             max = cur;
 48:                         }
 49:                     }
 50:                 }
 51:             }
 52:             return decrypted_text.Sum();
 53:         }
 54: 
 55:         /// <summary>
 56:         /// so this method return all the possible key candidate based on
 57:         /// how many whites space or alphabetical characters the decrypted text returns
 58:         /// that are above the value of (average + 2x STD)
 59:         /// </summary>
 60:         /// <param name="text">the encrypted text</param>
 61:         /// <param name="keys">array of all possible keys(a-z)</param>
 62:         /// <param name="key_selector">indicates which key</param>
 63:         /// <returns>array contains all the key that has value above cut off point</returns>
 64:         static int[] find_key_candidate(int[] text, int[] keys, int key_selector)
 65:         {
 66:             int i, j, d, k;
 67:             var result = new int[26];
 68:             for (i = 0; i < keys.Length; i++)
 69:             {
 70:                 k = keys[i];
 71:                 for (j = key_selector; j < text.Length; j += 3)
 72:                 {
 73:                     d = text[j] ^ k;
 74:                     if (is_ascii_char_or_space(d) == true)
 75:                         result[i]++;
 76:                 }
 77:             }
 78:             var std = standard_deviation(result.ToList());
 79:             var cut_off = result.Average() + 2 * std;
 80:             return result.Select((num, index) => new { ch = index + 97, count = num })
 81:                .Where(l => l.count > cut_off)
 82:                .Select(l => l.ch)
 83:                .ToArray();
 84:         }
 85: 
 86:         /// <summary>
 87:         /// using the most commonly used english word(http://www.world-english.org/english500.htm)
 88:         /// top 4: (T)the, (O)of, (T)to, and, (A)and
 89:         /// each word gives a score of 1;
 90:         /// </summary>
 91:         /// <param name="text"> already decrypted text using the key to be tested</param>
 92:         /// <returns>score base on commonly used words</returns>
 93:         static int calculate_key_score_using_heuristic(int[] text)
 94:         {
 95:             var score = 0;
 96:             int i, d1, d2, d3, d4, d5;
 97:             for (i = 0; i < text.Length - 4; i++)
 98:             {
 99:                 d1 = text[i];
100:                 d2 = text[i + 1];
101:                 d3 = text[i + 2];
102:                 d4 = text[i + 3];
103:                 d5 = text[i + 4];
104: 
105:                 if (d1 == ' ' && (d2 == 'T' || d2 == 't'))
106:                 {
107:                     if (d3 == 'h' && d4 == 'e' && d5 == ' ')
108:                         score++;
109:                     else if (d3 == 'o' && d4 == ' ')
110:                         score++;
111:                 }
112:                 else if (d1 == ' ' && (d2 == 'O' || d2 == 'o'))
113:                 {
114:                     if (d3 == 'f' && d4 == ' ')
115:                         score++;
116:                 }
117:                 else if (d1 == ' ' && (d2 == 'A' || d2 == 'a'))
118:                 {
119:                     if (d3 == 'n' && d4 == 'd' && d5 == ' ')
120:                         score++;
121:                 }
122:             }
123:             return score;
124:         }
125: 
126:         static int[] decrypt_with_key(int[] text, int[] key)
127:         {
128:             var index = 0;
129:             return text.Select(c => c ^ key[(index++ % 3)]).ToArray();
130:         }
131: 
132:         static bool is_ascii_char_or_space(int code)
133:         {
134:             return code == 32 || (code >= 64 && code <= 90) || (code >= 97 && code <= 122);
135:         }
136: 
137:         /// <summary>
138:         /// http://stackoverflow.com/questions/895929/how-do-i-determine-the-standard-deviation-stddev-of-a-set-of-values
139:         /// using Welford's method
140:         /// </summary>
141:         static double standard_deviation(List<int> nums)
142:         {
143:             double M = 0.0;
144:             double S = 0.0;
145:             double tmpM = 0.0;
146:             int k = 1;
147:             foreach (double value in nums)
148:             {
149:                 tmpM = M;
150:                 M += (value - tmpM) / k;
151:                 S += (value - tmpM) * (value - M);
152:                 k++;
153:             }
154:             return Math.Sqrt(S / (k - 1));
155:         }
156: 
157:         static Stopwatch stopwatch = new Stopwatch();
158:         static void TestBenchSetup()
159:         {
160:             // Uses the second Core or Processor for the Test
161:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
162:             // Prevents "Normal" processes from interrupting Threads
163:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
164:             // Prevents "Normal" Threads from interrupting this thread
165:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
166:         }
167:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
168:         static void TestBenchLoader(Func<int> test_method)
169:         {
170:             stopwatch.Reset();
171:             stopwatch.Start();
172:             var result = 0;
173:             long avg_tick = 0;
174:             long avg_ms = 0;
175:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms
176:             // stabilizes the CPU cache and pipeline.
177:             {
178:                 result = test_method(); // Warmup
179:             }
180:             stopwatch.Stop();
181:             for (int repeat = 0; repeat < 20; ++repeat)
182:             {
183:                 stopwatch.Reset();
184:                 stopwatch.Start();
185:                 result = test_method();
186:                 stopwatch.Stop();
187:                 avg_tick += stopwatch.ElapsedTicks;
188:                 avg_ms += stopwatch.ElapsedMilliseconds;
189:             }
190:             avg_tick = avg_tick / 20;
191:             avg_ms = avg_ms / 20;
192:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
193:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
194:         }
195:     }

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