import java.util.*;

public class SimpleCiphers {

    public static HashMap<String, Integer> freqCount(String s) {
	HashMap<String, Integer> fc = new HashMap<String, Integer>();
	for (int i = 0; i < s.length(); i++) {
	    char c = s.charAt(i);
	    if ((int)c > 64 && (int)c < 92) {
		if (fc.containsKey("" + c)) {
		    Integer t = fc.get("" + c);
		    fc.put("" + c, new Integer(t.intValue() + 1));
		} else {
		    fc.put("" + c, new Integer(1));
		}
	    }
	}
	return fc;
    }

    public static String caesarEncrypt(String s, int shift) {
	String s2 = "";
	for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if ((int)c > 64 && (int)c < 92) {
		int c2 = (((int)c - 65 + shift) % 26) + 65;
		s2 += (char)c2;
	    } else {
		s2 += c;
	    }
	}
	return s2;
    }

    public static String vigenereEncrypt(String s, String key) {
	String s2 = "";
	int index = 0;
	for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
	    int shift = (int)key.charAt(index) - 65;
            if ((int)c > 64 && (int)c < 92) {
		int c2 = (((int)c - 65 + shift) % 26) + 65;
		s2 += (char)c2;
	    } else {
		s2 += c;
	    }
	    index = (index + 1) % key.length();
	}
	return s2;
    }

    public static String affineDecrypt(String s, int k1, int k2) {
	String s2 = "";
	for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if ((int)c > 64 && (int)c < 92) {
		int c2 = ((((int)c - 65 + (26 - k2)) * k1) % 26) + 65;
		s2 += (char)c2;
	    } else {
		s2 += c;
	    }
	}
	return s2;

    }

    public static int gcd(int a, int b) {
	if (b == 0) {
	    return a;
	} else {
	    return gcd(b, a % b);
	}
    }
    
    public static int[] eegcd(int a, int b) {
	if (b == 0) {
	    int[] r = {a, 1, 0};
	    return r;
	} else {
	    int[] r = eegcd(b, a % b);
	    int[] r2 = {r[0], r[2], r[1] - (a / b) * r[2]};
	    return r2;
	}
    }
    
    public static void main(String[] args) {
	String s1 = "ABCDEFG";
	String a1 = "PWUFFOGWCHFDWIWEJOUUNJOR";

	// test frequency count
	HashMap<String, Integer> s1fc = freqCount(s1);
	for (int i = 65; i < 92; i++) {
	    if (s1fc.containsKey("" + (char)i)) {
		System.out.println("" + (char)i + " -> " + 
				   s1fc.get("" + (char)i));
	    }
	}

	// test Caesar Encrypt
	String s2 = caesarEncrypt(s1, 13);
	System.out.println(s2);
	
	// test Affine Decrypt
	String s3 = affineDecrypt(a1, 19, 4);
	System.out.println(s3);

	// test Vigenere Encrypt
	String s4 = vigenereEncrypt(s1, "BOB");
	System.out.println(s4);

	// test gcd
	System.out.println("GCD of 26 and 11 is " + gcd(26, 11));

	// test eegcd
	int[] r = eegcd(26, 11);
	System.out.println("s and t are " + r[1] + " " + r[2]);
    }

}