import java.util.*;
import java.text.DecimalFormat;

// Milestone 3: bigram/unigram/total tallies from String/TokenReader

class Tally {
    final static String ALPHABET = " abcdefghijklmnopqrstuvwxyz";
    final static int NSYMBOLS = ALPHABET.length();
    final int SPACE = 0; // array index for space
    final int OFFSET = 'a' - 1; // offset to shift char code to array index
    int[] unigram = new int[NSYMBOLS];
    int[][] bigram = new int[NSYMBOLS][NSYMBOLS];
    int total = 0;

    // create new Tally with tallies from s
    Tally(String s) {
        tallybigram(s);
        tallyunigram();
    }

    // create new Tally with tallies from in
    Tally(TokenReader in) {
        for (String s = in.readLine(); !in.eof(); s = in.readLine())
            tallybigram(s);
        tallyunigram();
    }

    // add bigram tallies of t to current tallies
    private void tallybigram(String t) {
        char[] s = t.toLowerCase().toCharArray();
        // below, "array code" = the indices into $unigram$, $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 = ALPHABET.indexOf(s[i]);
            c = Math.max(0,c); // convert "unknown" characters to spaces
            /* faster alternative to two lines above:
                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
    }

    // compute unigram tallies and total from bigram tallies
    private void tallyunigram() {
        // compute unigram tallies from bigram tallies
            for (int i = 0; i<NSYMBOLS; i++)
                for (int j = 0; j<NSYMBOLS; j++)
                    unigram[i] += bigram[i][j];
        // compute total from unigram tallies
            for (int i = 0; i<NSYMBOLS; i++) total += unigram[i];
    }
}

class p6 {

// Milestone 1
    static int[] table1 = { 17, 20, 8, 7, 12 } ;
    static int[][] table2 = { { 0, 8, 2, 3, 4 },
                              { 6, 3, 4, 1, 6 },
                              { 3, 3, 1, 1, 0 },
                              { 4, 1, 1, 0, 1 },
                              { 4, 5, 0, 2, 1 } };
    static int[][] table3 = { { 8, 3, 3 }, { 5, 2, 6 }, { 6, 3, 4 } };
    static int[][] table4 = { { 9, 2, 4 }, { 7, 5, 3 }, { 5, 4, 1 } };

    // return a positive number that, when printed, takes up
    // the max number of spaces required by any element of a
    static int maxspace(int[] a) {
        int m = 1; // max so far
        for (int i = 0; i < a.length; i++) {
            int x = a[i];
            if (x<0) x = -10*x; // make positive, with one more digit
            m = Math.max(m, x);
        }
        return m;
    }

    // print 1-d table a with numbers evenly spaced according to maxspace
    // (see above)
    static void print(int[] a, int maxspace) {
        int spaces = 1 + ("" + maxspace).length(); // # spaces per #
        for (int i = 0; i < a.length; i++) {
            String s = " " + a[i];
            while (s.length() < spaces) s = " " + s;
            System.out.print(s);
        }
        System.out.println();
    }

    // print 1-d table a with numbers evenly spaced
    static void print(int[] a) {
        print(a, maxspace(a));
    }

    // print 2-d table a with numbers evenly spaced
    static void print(int[][] a) {
        // compute max magnitude element m in a
            int maxspace = 1; // maxspace so far
            for (int i = 0; i < a.length; i++) 
                maxspace = Math.max(maxspace, maxspace(a[i]));
        // print each row: i = next row to print = #rows already printed
            for (int i = 0; i < a.length; i++) print(a[i], maxspace);
    }

// Milestone 2

    // return transformation of text according to key (top, bottom)
    
    // concise version
    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 = s[i];
            int bias = 0; // lower-to-upper shift, if any
            if ('A' <= c && c  <= 'Z') { 
                bias = 'A' - 'a'; 
                c = (char) (c - bias); 
            }
            // where = top.indexOf(c);
                int where = top.length()-1; // next position to try
                while (where>=0 && top.charAt(where) != c) where--;
            if (where>=0) c = bottom.charAt(where);
            s[i] = (char) (c + bias);
        }
        return new String(s);
    }

    // slower version: if add "missing" character to ends of
    // top and bottom, then it will be found, unchanged!
    // problem: adding to the end of a String is slow --
    // it takes time proportional to length of the String.
    static String transform2(String top, String bottom, String text) {
        top = top.toLowerCase(); bottom = bottom.toLowerCase();
        String lower = text.toLowerCase();
        String s = "";
        for (int i = 0; i < text.length(); i++) {
            char c = lower.charAt(i);
            int bias = text.charAt(i) - c; // lower-to-upper shift, if any
            int where = (top + c).indexOf(c);
            c = (bottom + c).charAt(where);
            s += (char) (c + bias);
        }
        return s;
    }

// Milestone 3 -- see class Tally

// Milestone 4

    // return L1 distance between equal-sized arrays a, b
    static int distance(int[] a, int[] b) {
        int d = 0;
        for (int i = 0; i < a.length; i++) d += Math.abs(a[i] - b[i]);
        return d;
    }

    // return L1 distance between equal-sized arrays a, b
    static int distance(int[][] a, int[][] b) {
        int d = 0;
        for (int i = 0; i<a.length; i++) d += distance(a[i], b[i]);
		/* alternate solution:
            for (int i = 0; i<a.length; i++)
                for (int j = 0; j<a[i].length; j++)
                    d += Math.abs(a[i][j] - b[i][j]);
		*/
        return d;
    }

// Milestone 5

    // swap position i and j
    static void swap(int[] a, int i, int j) {
        int tmp = a[i]; a[i] = a[j]; a[j] = tmp;
    }
    // swap rows i and j and cols i and j
    static void swap(int[][] a, int i, int j) {
        // swap rows
            int[] tmp = a[i]; a[i] = a[j]; a[j] = tmp;
        // swap columns
            for (int k = 0; k < a.length; k++) swap(a[k], i, j);
    }
    // verbose version: swap rows i and j and cols i and j
    static void swap2(int[][] a, int i, int j) {
        // swap rows
            for (int k = 0; k < a[0].length; k++) {
                int tmp = a[i][k]; a[i][k] = a[j][k]; a[j][k] = tmp;
            }
        // swap columns
            for (int k = 0; k < a.length; k++) {
                int tmp = a[k][i]; a[k][i] = a[k][j]; a[k][j] = tmp;
            }
    }

// main method

    public static void main(String[] args) {

    // Milestone 1
        System.out.println("Milestone 1 output:");
        System.out.println();

        print(new int[][] 
              { {      29, -693, -717,  -26, -8154 },
                {     -16,  -35,  975,    5, 90886 },
                { -731025, -504, 8943, -841,    95 } });
        System.out.println();
        
    // Milestone 2
        System.out.println("Milestone 2 output:");
        System.out.println();

        final int top = 0, bot = 1, plain = 2;
        String[][] crypt = 
        { { "abnocdgpwxyefqrstuvhijklmz",
            "deqrfgjszabhituvwxyklmnopc",
            "We Apologize for the Inconvenience" },
          { "sLvWPdEncFRjQBahOItMzgyxku",
            "CpaTQoweZirBYVhlndxSMKuGfj",
            "Time to feed the chickens, Paw!  Ay-yup!  Git the lunch bag, Maw!" } };
        for (int i = 0; i<crypt.length; i++) {
            String cipher = 
                transform(crypt[i][top], crypt[i][bot], crypt[i][plain]);
            String decipher =
                transform(crypt[i][bot], crypt[i][top], cipher);
            System.out.println("Key      " + crypt[i][top]);
            System.out.println("         " + crypt[i][bot]);
            System.out.println("plain    " + crypt[i][plain]);
            System.out.println("encipher " + cipher);
            System.out.println("decipher " + decipher);
            System.out.println();
        }

    // Milestone 3
        System.out.println("Milestone 3 output:");
        System.out.println();

        Tally[] t = {
            null, // no t[0]!
            new Tally ("a aaa abba abc ac ad ada add baa " +
                        "bad cab cb cdc dab dad dada dc"),
            new Tally(new TokenReader("small.txt")),
            new Tally(new TokenReader("www/oldannounce.txt")),
            new Tally(new TokenReader("www/cryptannounce.txt")) };
        for (int i = 1; i<t.length; i++) {
            System.out.println("t" + i + " Unigram Tallies:");
            print(t[i].unigram);
            System.out.println("t" + i + " Total = " + t[i].total);
            System.out.println();
        }

        for (int i = 1; i+1<t.length; i += 2) {
            System.out.println("t" +i+ "&t" +(i+1)+ "unigram tally distance = "
                    + distance(t[i].unigram, t[i+1].unigram));
            System.out.println("t" +i+ "&t" +(i+1)+ "bigram  tally distance = "
                    + distance(t[i].bigram, t[i+1].bigram));
            System.out.println();
        }
        
        System.out.println("t3 Bigram Tallies:");
        print(t[3].bigram);
        System.out.println();

        System.out.println("t4 Bigram Tallies:");
        print(t[4].bigram);
        System.out.println();
        
    // Milstone 4
        System.out.println("Milestone 4 Output:");
        System.out.println();

        System.out.println("Table 3:");
        print(table3);
        System.out.println();

        System.out.println("Table 4:");
        print(table4);
        System.out.println();

        System.out.println("Distance = " + distance(table3, table4));
        System.out.println();

    // Milestone 5
        System.out.println("Milestone 5 Output:");
        System.out.println();

        int[][] swap = { { 0, 3 }, { 1, 3 }, { 3, 0 }, { 1, 0 } };
        System.out.print("Table1:        ");
        print(table1);
        for (int i = 0; i<swap.length; i++) {
            System.out.print("After Swap " + swap[i][0] +","+ swap[i][1] +" ");
            swap(table1, swap[i][0], swap[i][1]);
            print(table1);
        }
        System.out.println();

        swap = new int[][] { { 1, 4}, { 1, 4} };
        System.out.println("Table2:");
        print(table2);
        for (int i = 0; i<swap.length; i++) {
            System.out.println("After Swap " + swap[i][0] + "," + swap[i][1]);
            swap(table2, swap[i][0], swap[i][1]);
            print(table2);
        }
        System.out.println();
    }
}