{"id":631,"date":"2012-08-11T16:07:20","date_gmt":"2012-08-11T20:07:20","guid":{"rendered":"http:\/\/www.joshho.com\/blog\/?p=631"},"modified":"2012-09-07T16:02:19","modified_gmt":"2012-09-07T20:02:19","slug":"project-euler-problem-59","status":"publish","type":"post","link":"https:\/\/www.joshho.com\/blog\/2012\/08\/11\/project-euler-problem-59\/","title":{"rendered":"Project Euler &#8211; Problem 59"},"content":{"rendered":"<p>Problem 59:<br \/>\nThe encryption key consists of three lower case characters. Using <a href='http:\/\/archiver.joshho.com\/display.php?full=1&#038;q=https:\/\/projecteuler.net\/project\/cipher1.txt' target='_blank'>cipher1.txt<\/a>, a file containing the encrypted ASCII codes, and the knowledge that the plain text must contain common English words, decrypt the message and find the sum of the ASCII values in the original text.<\/p>\n<p>Note that the key is repeated cyclically throughout the message utilizing XOR.<br \/>\n<!--more--><br \/>\n<code><\/p>\n<pre lang='java'>\r\nimport java.util.HashMap;\r\n\r\n\r\nclass runner\r\n{\r\n\tpublic static void main (String[] args) throws java.lang.Exception\r\n\t{\r\n\t\tlong time = System.currentTimeMillis();\r\n\r\n\t\tString[] keys = new String[26*26*26];\r\n\t\tint l=0;\r\n\t\tfor(int i=97;i<97+26;i++)\r\n\t\t\tfor(int j=97;j<97+26;j++)\r\n\t\t\t\tfor(int k=97;k<97+26;k++)\r\n\t\t\t\t\tkeys[l++] = \"\"+(char)i+(char)j+(char)k;\r\n\r\n\t\tString input = \"http:\/\/archiver.joshho.com\/display.php?full=1&#038;q=https:\/\/projecteuler.net\/project\/cipher1.txt\";\r\n\t\tString[] cipher = input.split(\",\");\r\n\r\n\t\tHashMap<String, int[]> freq_results = new HashMap<String, int[]>(); \r\n\r\n\t\tfor(String k: keys){\r\n\t\t\tint[] freq = new int[128-32];\r\n\t\t\tboolean valid = true;\r\n\t\t\tfor(int i=0;i<cipher.length; i++){\r\n\t\t\t\tint cipherVal = Integer.valueOf(cipher[i]);\r\n\t\t\t\tint cur =  cipherVal ^ k.charAt(i%3);\r\n\r\n\t\t\t\tif(cur < 32 || cur > 127){\r\n\t\t\t\t\tvalid = false;\r\n\t\t\t\t\tbreak;\r\n\t\t\t\t}else if(cur >= 65 && cur <= 90){\r\n\t\t\t\t\tcur += 32;\/\/lowercase..\r\n\t\t\t\t}\r\n\r\n\t\t\t\tfreq[cur-32]++;\r\n\t\t\t}\r\n\t\t\tif(valid){\r\n\t\t\t\tfreq_results.put(k, freq);\r\n\t\t\t}\r\n\t\t}\r\n\r\n\t\t\/\/http:\/\/www.data-compression.com\/english.shtml#first\r\n\t\tdouble[] dist = {0.1918182, 0.0651738,0.0124248,\r\n\t\t\t\t0.0217339,0.0349835,0.1041442,0.0197881,\r\n\t\t\t\t0.0158610,0.0492888,0.0558094,0.0009033,\r\n\t\t\t\t0.0050529,0.0331490,0.0202124,0.0564513,\r\n\t\t\t\t0.0596302,0.0137645,0.0008606,0.0497563,\r\n\t\t\t\t0.0515760,0.0729357,0.0225134,0.0082903,\r\n\t\t\t\t0.0171272,0.0013692,0.0145984,0.0007836};\r\n\t\tint[] investigate = {0,65,66,67,68,69,70,71,72,73,\r\n\t\t\t\t74,75,76,77,78,79,80,81,82,83,84,85,86,87,\r\n\t\t\t\t88,89,90};\/\/97-32 as space is 0, and we already converted upper case to lower.\r\n\r\n\t\tdouble lowest_deviation = 1; String lowest_deviation_key = \"\";\r\n\t\t\r\n\t\tfor(String key: freq_results.keySet()){\r\n\t\t\tdouble deviation = 0;\r\n\t\t\tint[] freq = freq_results.get(key);\r\n\t\t\tfor(int i=0; i<investigate.length;i++){\r\n\t\t\t\tdeviation -= (freq[investigate[i]]\/(double)input.length() - dist[i]);  \r\n\t\t\t}\r\n\t\t\tif(deviation < lowest_deviation){\r\n\t\t\t\tlowest_deviation = deviation;\r\n\t\t\t\tlowest_deviation_key = key;\r\n\t\t\t}\r\n\t\t}\r\n\t\t\/\/Note that it may be wise to check a few of the lowest deviation keys, \r\n\t\t\/\/as opposed to assuming it's the lowest one.\r\n\t\tSystem.out.println(\"k:\"+lowest_deviation_key+ \" d:\"+lowest_deviation);\r\n\r\n\t\t\r\n\t\t\/\/calculate the problem's answer\r\n\t\tint sum = 0;\r\n\t\tStringBuffer result = new StringBuffer();\r\n\t\tresult.append(\"  \");\r\n\r\n\t\tfor(int i=0;i<cipher.length; i++){\r\n\t\t\tint cipherVal = Integer.valueOf(cipher[i]);\r\n\t\t\tchar cur = (char)( cipherVal ^ lowest_deviation_key.charAt(i%3));\r\n\t\t\tsum += cur;\r\n\t\t\tresult.append(cur);\r\n\t\t}\r\n\t\tresult.append(\"\\n\");\r\n\t\tSystem.out.println(result);\r\n\t\tSystem.out.println(sum);\r\n\t\t \r\n\r\n\t\tSystem.out.println(\"time:\"+(System.currentTimeMillis()-time));\r\n\t}\r\n}\r\n<\/pre>\n<p><\/code><br \/>\nMirror: <a href='http:\/\/archiver.joshho.com\/display.php?full=1&#038;q=http:\/\/www.data-compression.com\/english.shtml' target='_blank'>http:\/\/www.data-compression.com\/english.shtml<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem 59:<br \/>\nThe encryption key consists of three lower case characters. Using <a href='http:\/\/archiver.joshho.com\/display.php?full=1&#038;q=https:\/\/projecteuler.net\/project\/cipher1.txt' target='_blank'>cipher1.txt<\/a>, a file containing the encrypted ASCII codes, and the knowledge that the plain text must contain common English words, decrypt the message and find the sum of the ASCII values in the original text.<\/p>\n<p>Note that the key is repeated cyclically throughout the message utilizing XOR.<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[56],"tags":[],"_links":{"self":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/631"}],"collection":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/comments?post=631"}],"version-history":[{"count":0,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/631\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/media?parent=631"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/categories?post=631"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/tags?post=631"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}