Project Euler – Problem 59

Problem 59:
The encryption key consists of three lower case characters. Using cipher1.txt, 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.

Note that the key is repeated cyclically throughout the message utilizing XOR.

import java.util.HashMap;
 
 
class runner
{
	public static void main (String[] args) throws java.lang.Exception
	{
		long time = System.currentTimeMillis();
 
		String[] keys = new String[26*26*26];
		int l=0;
		for(int i=97;i<97+26;i++)
			for(int j=97;j<97+26;j++)
				for(int k=97;k<97+26;k++)
					keys[l++] = ""+(char)i+(char)j+(char)k;
 
		String input = "http://archiver.joshho.com/display.php?full=1&q=https://projecteuler.net/project/cipher1.txt";
		String[] cipher = input.split(",");
 
		HashMap<String, int[]> freq_results = new HashMap<String, int[]>(); 
 
		for(String k: keys){
			int[] freq = new int[128-32];
			boolean valid = true;
			for(int i=0;i<cipher.length; i++){
				int cipherVal = Integer.valueOf(cipher[i]);
				int cur =  cipherVal ^ k.charAt(i%3);
 
				if(cur < 32 || cur > 127){
					valid = false;
					break;
				}else if(cur >= 65 && cur <= 90){
					cur += 32;//lowercase..
				}
 
				freq[cur-32]++;
			}
			if(valid){
				freq_results.put(k, freq);
			}
		}
 
		//http://www.data-compression.com/english.shtml#first
		double[] dist = {0.1918182, 0.0651738,0.0124248,
				0.0217339,0.0349835,0.1041442,0.0197881,
				0.0158610,0.0492888,0.0558094,0.0009033,
				0.0050529,0.0331490,0.0202124,0.0564513,
				0.0596302,0.0137645,0.0008606,0.0497563,
				0.0515760,0.0729357,0.0225134,0.0082903,
				0.0171272,0.0013692,0.0145984,0.0007836};
		int[] investigate = {0,65,66,67,68,69,70,71,72,73,
				74,75,76,77,78,79,80,81,82,83,84,85,86,87,
				88,89,90};//97-32 as space is 0, and we already converted upper case to lower.
 
		double lowest_deviation = 1; String lowest_deviation_key = "";
 
		for(String key: freq_results.keySet()){
			double deviation = 0;
			int[] freq = freq_results.get(key);
			for(int i=0; i<investigate.length;i++){
				deviation -= (freq[investigate[i]]/(double)input.length() - dist[i]);  
			}
			if(deviation < lowest_deviation){
				lowest_deviation = deviation;
				lowest_deviation_key = key;
			}
		}
		//Note that it may be wise to check a few of the lowest deviation keys, 
		//as opposed to assuming it's the lowest one.
		System.out.println("k:"+lowest_deviation_key+ " d:"+lowest_deviation);
 
 
		//calculate the problem's answer
		int sum = 0;
		StringBuffer result = new StringBuffer();
		result.append("  ");
 
		for(int i=0;i<cipher.length; i++){
			int cipherVal = Integer.valueOf(cipher[i]);
			char cur = (char)( cipherVal ^ lowest_deviation_key.charAt(i%3));
			sum += cur;
			result.append(cur);
		}
		result.append("\n");
		System.out.println(result);
		System.out.println(sum);
 
 
		System.out.println("time:"+(System.currentTimeMillis()-time));
	}
}


Mirror: http://www.data-compression.com/english.shtml