// labeled TRIGRAM 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[][][] trigram = new int[NSYMBOLS][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 trigram 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<trigram.length; i++) 
            for (int j = 0; j<trigram[i].length; j++)
            	for (int k = 0; k<trigram[i][j].length; k++)
                	d += Math.abs(trigram[i][j][k]/n - t.trigram[i][j][k]/nt);
        return d;
    }

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

    // add trigram tallies of t to current tallies -- 
    // convert spaces to double spaces, ignore triple spaces
    private void tallytrigram(String t) {
        char[] s = t.toLowerCase().toCharArray();
        // below, "array code" = the indices into $trigram$
        //                     = positions of characters in $alphabet$
        int prev2 = SPACE; // array code for char 2 places back, initially ' '
        int prev = SPACE;  // array code for char 1 place back, 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;
            trigram[prev2][prev][c]++;
            if (c == SPACE) {
            	trigram[prev][SPACE][SPACE]++;
            	prev2 = SPACE; prev = SPACE;
            } else {
            	prev2 = prev;
            	prev = c;            	
            }
        }
        trigram[prev2][prev][SPACE]++;
        trigram[prev][SPACE][SPACE]++;
        trigram[SPACE][SPACE][SPACE] = 0; // ignore triple 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 trigram 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 Trigram {
    public static void main(String[] args) {
        Crypt.crack("acc1.txt","scramble.txt");
    }
}