public class P6_2 {

    // plain Condorcet winners (as letters) for pairwise matrix $pwm$,
    // which is modified
    public static String plainCondorcet(int[][] pwm) {
        return null; /* --- replace with your code --- */
/*
    suggested algorithm for plain(pwm) -- pseudocode:

    set $winners$ to empty
    ($smallest$ = smallest magnitude of remaining defeats)
    set $smallest$ to 0 (initially, do not delete any defeats)
    while there are no winners
    |   ($smallest2$ = 2nd smallest magnitude of remaining defeats)
    |   set $smallest2$ to conceptual infinity
    |   (delete defeats of magnitude $smallest$, update $winners$, $smallest2$)
    |   |   loop over each column/candidate $j$
    |   |   |   set $defeated$ to false
    |   |   |   ($defeated$ = "candidate $j$ has been defeated by some $k<i$?")
    |   |   |   loop over each row/candidate $i$
    |   |   |   |   if $i$ defeats $j$ with magnitude $v$
    |   |   |   |   |   set $defeated$ to true
    |   |   |   |   |   if $v == smallest$
    |   |   |   |   |       delete defeat $i/j (v)$
    |   |   |   |   |   else 
    |   |   |   \   \       set $smallest2$ to $min(smallest2, v)$
    |   |   |   if $j$ was never defeated
    |   \   \       add $j$ to $winners$
    \   set $smallest$ to $smallest2$
    return $winners$
*/
    }

    // pairwise matrix for ballots (same format as for $tally$) in $election$.
    // each ballot is assumed to have the same number of candidates.
    public static int[][] tallies(String[] election) {
        return null; /* --- replace with your code --- */
    }

    /* pairwise matrix obtained from updating $pwm$ with $ballot$.
       if $pwm = null$, a new matrix is created, otherwise the old
       matrix is modified and its reference returned.  
       $ballot$ holds ordered sequence of candidates.
       + candidates are represented by consecutive letters of the alphabet,
         starting at $"a"$, and ignoring case ($"a"$ and $"A"$ are the same)
       + between candidates is a comparison -- either $">"$ or $"="$
       example: $tally("d>c=e=b>a", null)$
    */
    public static int[][] tally(String ballot, int[][] pwm) {
        return null; /* --- replace with your code --- */
    }

   // you may define additional methods, but it is possible to write clear, 
   // concise, non-redundant code without doing so.

// ***************** nothing for you to modify below this line ****************

    // test $plainCondorcet$
    // note: partial support for $ssdCondorcet$
    public static void main(String args[]) {
        String[] election1 = new String[] {
            "A>D>E>C>B",
            "C=B=E>D=A",
            "A>E>C=D=B",
            "A>B=E=D=C",
            "D>C>E>B>A",
            "D=A=C>B=E",
            "A>C>E>B=D",
            "A>D=C>E>B",
            "A=C>E>B=D",
            "B=C>E=D>A" };
        int[][] pwm1 = new int[][] {
              new int[] { 0, 7, 5, 6, 7 },
              new int[] { 3, 0, 0, 2, 1 },
              new int[] { 3, 6, 0, 4, 6 },
              new int[] { 2, 4, 2, 0, 4 },
              new int[] { 3, 6, 2, 4, 0 } };
        System.out.println("winner should be: A");
        System.out.println("election1 winners: " + 
                            plainCondorcet(tallies(election1)));
        System.out.println("pwm1 winners: " + plainCondorcet(pwm1));

        String[] election2 = new String[] {
            "B>C=A>E>D",
            "A>E>C=B=D",
            "D>E>B=C=A",
            "C=E=A>B>D",
            "A>B=D>C=E",
            "D=C=B=A>E",
            "A=D=C>B>E",
            "A>B=C=D=E",
            "B=A=D=E>C",
            "C>A>E=D=B",
            "E>C>B=A>D",
            "D=E=A=C>B",
            "C=A>E=D=B",
            "C>B>D=E=A",
            "B=A>E>C>D",
            "D>E=B>A>C",
            "D>B>A=C>E",
            "A=D>C=B>E",
            "D=C>E>B=A",
            "C>D>A=B>E" };
        int[][] pwm2 = new int[][] {
            new int[] { 0, 9, 7, 9, 12 }, 
            new int[] { 4, 0, 6, 5,  9 }, 
            new int[] { 5, 9, 0, 8, 10 }, 
            new int[] { 5, 8, 6, 0,  9 }, 
            new int[] { 4, 6, 6, 5,  0 } };
        System.out.println("winner should be: A");
        System.out.println("election2 winners: " + 
                            plainCondorcet(tallies(election2)));
        System.out.println("pwm2 winners: " + plainCondorcet(pwm2));

        int[][] pwm3 = new int[][] {
            new int[] {  0, 47, 52, 58, 60 },
            new int[] { 37,  0, 77, 37, 33 },
            new int[] { 57, 39,  0, 30, 60 },
            new int[] { 42, 67, 65,  0, 57 },
            new int[] { 75, 52, 47, 35,  0 } };
        System.out.println("winner should be: D");
        System.out.println("pwm3 winners: " + plainCondorcet(pwm3));

                       // 123456789123456789123456789123456789
        char[] defeats = "B/C (10) C/D (11) D/B (12) C/A (07) ".toCharArray();
        int[][] pwm4 = new int[4][4];
        int k = 0;
        while (k < defeats.length) {
            pwm4[defeats[k]-'A'][defeats[k+2]-'A']
                = 10 * (defeats[k+5] - '0') + (defeats[k+6] - '0');
            k += 9;
        }

        System.out.println("plain winner is A, SSD winner is C");
        System.out.println("plain pwm4 winners: " + plainCondorcet(pwm4));
        

          //1234123412341234123412341234123412341234123412341234123412341234
defeats = "C/G G/H H/C F/K K/I I/M M/F C/B F/D B/E E/D D/B E/A A/J J/L L/A "
           .toCharArray();
        k = 0;
        int[][] pwm5 = new int[13][13];
        while (k < defeats.length) {
            pwm5[defeats[k]-'A'][defeats[k+2]-'A'] 
                = (int) (Math.ceil(Math.random() * 99));
            k += 4;
        }
        System.out.println("topmostSets are (subsets of) CGH and IKFM");
        System.out.println("plain pwm5 winners: " + plainCondorcet(pwm5));
    }
}