// Name: Anita Blake              Partner: Ted Forrester
// ID:   014916                   ID:      642708
// Sec:  Yan T 2:30               Sec:     Artemov R 1:25

// Date: May 4, 2000
// Project 7: Cracking the Code

// labeled bigram and total tallies of text from TokenReader
class Tally {
    final static String ALPHABET = Crypt.ALPHABET;
    final static int NSYMBOLS = Crypt.NSYMBOLS;
    final static int SPACE = Crypt.SPACE;
    private final int OFFSET = 'a'-1; // offset to shift ASCII to array index
    private int[][] bigram = new int[NSYMBOLS][NSYMBOLS];
    private int total = 0;
    private char[] labels = ALPHABET.toCharArray();

    // return labels
    String labels() { return new String(labels); }

    // return L1 distance between own and t's bigram frequencies (fractions)
    double distance(Tally t) {
        double d = 0; // distance so far
        // denominators to convert tallies to fractions
            double n = total, nt = t.total; 
        for (int i = 0; i<bigram.length; i++) 
            for (int j = 0; j<bigram[i].length; j++)
                d += Math.abs(bigram[i][j]/n - t.bigram[i][j]/nt);
        return d;
    }

    // swap positions i and j in labels and bigram
    void swap(int i, int j) {
        char c = labels[i]; labels[i] = labels[j]; labels[j] = c;
        // swap rows i and j of bigram
            int[] row = bigram[i]; bigram[i] = bigram[j]; bigram[j] = row; 
        // swap cols i and j of bigram
            for (int k = 0; k < bigram.length; k++) {
                int f = bigram[k][i]; 
                bigram[k][i] = bigram[k][j]; bigram[k][j] = f; 
            }
    }
    
    // create new Tally with tallies from in
    Tally(TokenReader in) {
        for (String s = in.readLine(); !in.eof(); s = in.readLine())
            tallybigram(s);
        // compute total tallies from bigram tallies
            for (int i = 0; i<NSYMBOLS; i++)
                for (int j = 0; j<NSYMBOLS; j++)
                    total += bigram[i][j];
    }

    // add bigram tallies of t to current tallies
    private void tallybigram(String t) {
        char[] s = t.toLowerCase().toCharArray();
        // below, "array code" = the indices into $bigram$
        //                     = positions of characters in $alphabet$
        int prev = SPACE; // array code for previous char, initially ' '
        int c;        // array code for next char to process
        for (int i = 0; i<s.length; i++) {
            c = SPACE; // assume have a non-letter: map to space
            if ('a' <= s[i] && s[i] <= 'z') c = s[i] - OFFSET;
            bigram[prev][c]++;
            prev = c;
        }
        c = SPACE;
        bigram[prev][c]++;
        bigram[SPACE][SPACE] = 0; // ignore double spaces
    }
}

// perform encryption and decryption and cracking for substitution ciphers
class Crypt {
    final static String ALPHABET = " abcdefghijklmnopqrstuvwxyz";
    final static int NSYMBOLS = ALPHABET.length();
    final static int SPACE = 0; // array index for space

    // return transformation of text according to key (top, bottom)
    static String transform(String top, String bottom, String text) {
        top = top.toLowerCase(); bottom = bottom.toLowerCase();
        char[] s = text.toCharArray();
        for (int i = 0; i < s.length; i++) {
            char c = Character.toLowerCase(s[i]);
            int bias = s[i] - c; // lower-to-upper shift, if any
            int where = top.indexOf(c);
            if (where>=0) s[i] = (char) (bottom.charAt(where) + bias);
        }
        return new String(s);
    }
    
    // unscramble bigram frequences of cipher to match those of train
    static void unscramble(Tally train, Tally cipher) {
        // repeat as long as there are improvements
        // for each position i (other than space)
        //     find best position j
        //     commit "swap i&j"
            boolean go = true; // improvements were made
            double d = cipher.distance(train); // current distance
            while (go) {
                go = false;
                for (int i = SPACE+1; i<NSYMBOLS; i++) {
                    double bestd = d; // best distance so far
                    int bestj = -1;   // best swap so far; -1 means "none"
                    for (int j = SPACE+1; j<NSYMBOLS; j++) {
                        cipher.swap(i,j);
                        double d2 = cipher.distance(train);
                        cipher.swap(i,j);
                        if (d2<bestd) { bestd = d2; bestj = j; }
                    }
                    if (bestd<d) {
                        go = true;
                        cipher.swap(i,bestj);
                        String s = cipher.labels();
                        d = bestd;
                        System.out.println
                            ("swap " + s.charAt(i) + "<-->" + s.charAt(bestj)
                            + "; distance " + (int) (bestd*10000) 
                            + "; labels " + s);
                    }
                }
            }
    }

    // crack the ciphertext in file cipherfile by unscrambling its frequencies
    // according to the training text in file trainfile
    static void crack(String trainfile, String cipherfile) {
        System.out.println("Using " + trainfile + " to crack " + cipherfile);
        Tally train = new Tally(new TokenReader(trainfile));
        Tally cipher = new Tally(new TokenReader(cipherfile));
        unscramble(train,cipher);
        TokenReader in = new TokenReader(cipherfile);
        for (String s = in.readLine(); !in.eof(); s = in.readLine())
            System.out.println(transform(cipher.labels(),train.labels(),s));
    }
}

// target class
public class p7 {
    public static void main(String[] args) {
        Crypt.crack("oldannounce.txt","challenge.txt");
        System.out.println();
        Crypt.crack("oldannounce.txt","official.txt");
    }
}

/* Sample output:

Using oldannounce.txt to crack challenge.txt
swap v<-->a; distance 14459; labels  vbcdefghijklmnopqrstuawxyz
swap s<-->b; distance 13842; labels  vscdefghijklmnopqrbtuawxyz
swap z<-->c; distance 13510; labels  vszdefghijklmnopqrbtuawxyc
swap q<-->d; distance 13096; labels  vszqefghijklmnopdrbtuawxyc
swap f<-->e; distance 12735; labels  vszqfeghijklmnopdrbtuawxyc
swap i<-->e; distance 12569; labels  vszqfighejklmnopdrbtuawxyc
swap t<-->g; distance 11816; labels  vszqfithejklmnopdrbguawxyc
swap u<-->h; distance 11507; labels  vszqfituejklmnopdrbghawxyc
swap y<-->e; distance 11268; labels  vszqfituyjklmnopdrbghawxec
swap p<-->j; distance 10974; labels  vszqfituypklmnojdrbghawxec
swap x<-->k; distance 10865; labels  vszqfituypxlmnojdrbghawkec
swap e<-->l; distance 10530; labels  vszqfituypxemnojdrbghawklc
swap a<-->m; distance 10379; labels  vszqfituypxeanojdrbghmwklc
swap a<-->n; distance 10085; labels  vszqfituypxenaojdrbghmwklc
swap n<-->o; distance 9989; labels  vszqfituypxeoanjdrbghmwklc
swap o<-->j; distance 9986; labels  vszqfituypxejanodrbghmwklc
swap c<-->d; distance 9982; labels  vszqfituypxejanocrbghmwkld
swap f<-->r; distance 9009; labels  vszqrituypxejanocfbghmwkld
swap y<-->b; distance 8629; labels  vszqritubpxejanocfyghmwkld
swap x<-->m; distance 8575; labels  vszqritubpmejanocfyghxwkld
swap j<-->w; distance 8480; labels  vszqritubpmewanocfyghxjkld
swap p<-->k; distance 8400; labels  vszqritubkmewanocfyghxjpld
swap c<-->d; distance 8394; labels  vszqritubkmewanodfyghxjplc
swap n<-->v; distance 8359; labels  nszqritubkmewavodfyghxjplc
swap i<-->s; distance 8233; labels  nizqrstubkmewavodfyghxjplc
swap w<-->z; distance 8195; labels  niwqrstubkmezavodfyghxjplc
swap x<-->s; distance 8101; labels  niwqrxtubkmezavodfyghsjplc
swap v<-->b; distance 7758; labels  niwqrxtuvkmezabodfyghsjplc
swap c<-->k; distance 7710; labels  niwqrxtuvcmezabodfyghsjplk
swap s<-->m; distance 7647; labels  niwqrxtuvcsezabodfyghmjplk
swap f<-->e; distance 7641; labels  niwqrxtuvcsfzabodeyghmjplk
swap f<-->y; distance 6772; labels  niwqrxtuvcsyzabodefghmjplk
swap w<-->p; distance 6756; labels  nipqrxtuvcsyzabodefghmjwlk
swap w<-->k; distance 6752; labels  nipqrxtuvcsyzabodefghmjklw
swap w<-->d; distance 6737; labels  nipqrxtuvcsyzabowefghmjkld
What I am thinfing (semi-out loud here) is that writing used to
encomjass barious "genres" in one story.  It seems life poofs habe
gotten so sjecialived, kew stories do that well any more.  I thinf
that Laurell F Hamilton, Diana Gapaldon, and Lois McMaster Puqold do a
good qop ok preafing some ok these parriers, put I am not sure I would
say their writing is lasting (as much I would life it to pe:)).

Using oldannounce.txt to crack official.txt
swap j<-->a; distance 14585; labels  jbcdefghiaklmnopqrstuvwxyz
swap e<-->b; distance 14238; labels  jecdbfghiaklmnopqrstuvwxyz
swap s<-->c; distance 13966; labels  jesdbfghiaklmnopqrctuvwxyz
swap q<-->d; distance 13503; labels  jesqbfghiaklmnopdrctuvwxyz
swap q<-->b; distance 11852; labels  jesbqfghiaklmnopdrctuvwxyz
swap t<-->f; distance 11354; labels  jesbqtghiaklmnopdrcfuvwxyz
swap n<-->g; distance 11055; labels  jesbqtnhiaklmgopdrcfuvwxyz
swap c<-->h; distance 10697; labels  jesbqtnciaklmgopdrhfuvwxyz
swap l<-->i; distance 10384; labels  jesbqtnclakimgopdrhfuvwxyz
swap o<-->a; distance 9704; labels  jesbqtnclokimgapdrhfuvwxyz
swap v<-->k; distance 9624; labels  jesbqtnclovimgapdrhfukwxyz
swap h<-->i; distance 9202; labels  jesbqtnclovhmgapdrifukwxyz
swap c<-->m; distance 8897; labels  jesbqtnmlovhcgapdrifukwxyz
swap h<-->g; distance 8505; labels  jesbqtnmlovgchapdrifukwxyz
swap z<-->a; distance 8429; labels  jesbqtnmlovgchzpdrifukwxya
swap a<-->p; distance 8060; labels  jesbqtnmlovgchzadrifukwxyp
swap n<-->d; distance 7730; labels  jesbqtdmlovgchzanrifukwxyp
swap f<-->i; distance 7101; labels  jesbqtdmlovgchzanrfiukwxyp
swap a<-->u; distance 6759; labels  jesbqtdmlovgchzunrfiakwxyp
swap o<-->k; distance 6705; labels  jesbqtdmlkvgchzunrfiaowxyp
swap u<-->w; distance 6647; labels  jesbqtdmlkvgchzwnrfiaouxyp
swap y<-->x; distance 6571; labels  jesbqtdmlkvgchzwnrfiaouyxp
swap o<-->x; distance 6486; labels  jesbqtdmlkvgchzwnrfiaxuyop
swap n<-->p; distance 6482; labels  jesbqtdmlkvgchzwprfiaxuyon
swap k<-->e; distance 6406; labels  jksbqtdmlevgchzwprfiaxuyon
swap u<-->s; distance 6354; labels  jkubqtdmlevgchzwprfiaxsyon
swap d<-->b; distance 6172; labels  jkudqtbmlevgchzwprfiaxsyon
swap w<-->t; distance 6129; labels  jkudqwbmlevgchztprfiaxsyon
swap z<-->l; distance 5598; labels  jkudqwbmzevgchltprfiaxsyon
swap y<-->e; distance 5541; labels  jkudqwbmzyvgchltprfiaxseon
swap w<-->v; distance 5456; labels  jkudqvbmzywgchltprfiaxseon
swap c<-->g; distance 5229; labels  jkudqvbmzywcghltprfiaxseon
swap o<-->g; distance 5054; labels  jkudqvbmzywcohltprfiaxsegn
swap w<-->k; distance 4884; labels  jwudqvbmzykcohltprfiaxsegn
swap d<-->u; distance 4543; labels  jwduqvbmzykcohltprfiaxsegn
to secret operative from evil group of people:
have you infiltrated bureau thirteen yet? beware of yan and 
especially dis; they might be onto us. beware also artemov -- we have
reason to suspect he is a double agent, and not just because of his
ethnicity! whoever thought of such a silly stereotype? anyway,
internal reviews by our advisory panel concluded that our plans might backfire,
since we actually live on the same world we're supposedly trying to
nuke -- we're supposed to be "evil," not hella lame or hella stupid. 
our new goal is to make a lot of money to fund future egop projects 
since we're draining our budget on these blasted encryption keys that are
perpetually getting cracked. once we raise enough money, we might even take 
over the world and place our supreme leader in charge.
ok, so, here are the new plans. after infiltrating bureau thirteen, you must
next discover the secret password so we can access their unix system. they're 
hiding plans for a top secret device that measures pressure using 
only three molecules. countless computer simultations suggest that it is the
legendary holland-minkley pressure testing device (HMPTD) we have sought for
years.  find and download the plans, then destroy all records to
slow down bureau thirteen so they don't beat us to the patent. once we 
have those plans, we will build and market the device and make millions. 
if you act with haste and qest, we can all laugh at bureau thriteen in a big
party celebrating our success.
*/