BaseballElimination.java

/*
Aggregate score: 89.57%

Correctness:  19/23 tests passed
Memory:       4/4 tests passed
Timing:       1/1 tests passed

Test 7b: check isEliminated() when n = 5
        * teams5.txt
        * teams5a.txt
        * teams5b.txt
        * teams5c.txt

        java.lang.ArrayIndexOutOfBoundsException: Index 1 out of bounds for length 1

        BaseballElimination.<init>(BaseballElimination.java:49)
        TestBaseballElimination.checkIsEliminated(TestBaseballElimination.java:159)
        TestBaseballElimination.test7b(TestBaseballElimination.java:558)
        TestBaseballElimination.main(TestBaseballElimination.java:777)

        ==> FAILED
*/

import edu.princeton.cs.algs4.FlowEdge;
import edu.princeton.cs.algs4.FlowNetwork;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.FordFulkerson;

import java.util.ArrayList;
import java.util.Iterator;

public class BaseballElimination {

    private final int v;
    private final int[] wins;
    private final int[] losses;
    private final int[] remaining; // remaining games
    private final int[][] against; // games between team1 and team2
    private final int c; // number of games combinations
    private final int s; // source
    private final int t; // target
    private final String[] teams;

    // create a baseball division from given filename in format specified below
    public BaseballElimination(String filename) {
        In in = new In(filename);
        v = in.readInt(); // teams vertices
        c = v * (v - 1) / 2; // games confrontation pairs how many ways to choose 2 teams amongst V
        s = c + v;
        t = s + 1;
        int items = 4;

        wins = new int[v];
        losses = new int[v];
        remaining = new int[v];
        against = new int[v][v];
        teams = new String[v];

        // reading the data
        String all = in.readAll().substring(1);
        String[] lines = all.split("\n"); // removes the new lines

        // saving the data
        for (int i = 0; i < v; i++) {
            lines[i] = lines[i].trim(); // removes leading and trailing whitespaces
            String[] line = lines[i].split("[ ]+"); // reads line
            teams[i] = line[0];
            wins[i] = Integer.parseInt(line[1]); // wins
            losses[i] = Integer.parseInt(line[2]); // loses
            remaining[i] = Integer.parseInt(line[3]); // remaining
            // games remaining
            for (int j = 0; j < v; j++) {
                against[i][j] = Integer.parseInt(line[items + j]);
            }
        }
    }

    // number of teams
    public int numberOfTeams() {
        return v;
    }

    // all teams
    public Iterable<String> teams() {
        ArrayList<String> all = new ArrayList<>();
        for (int i = 0; i < v; i++) all.add(teams[i]);
        return all;
    }

    // number of wins for given team
    public int wins(String team) {
        validate(team);
        int i = id(team);
        return wins[i];
    }

    // number of losses for given team
    public int losses(String team) {
        validate(team);
        int i = id(team);
        return losses[i];
    }

    // number of remaining games for given team
    public int remaining(String team) {
        validate(team);
        int i = id(team);
        return remaining[i];
    }

    // number of remaining games between team1 and team2
    public int against(String team1, String team2) {
        validate(team1);
        validate(team2);
        int i = id(team1);
        int j = id(team2);
        return against[i][j];
    }

    // is given team eliminated?
    public boolean isEliminated(String team) {
        validate(team);
        int capacity = capacity(team);
        if (trivialElimination(team)) return true;
        else {
            FlowNetwork fn = createFlowNetwork(c, s, t, team);
            FordFulkerson ff = new FordFulkerson(fn, s, t);
            // If some edges pointing from s are not full (flow is less than capacity)
            // there is no scenario in which team x can win the division ie. team x loses
            return ff.value() < capacity;
        }
    }

    // subset R of teams that eliminates given team; null if not eliminated
    public Iterable<String> certificateOfElimination(String team) {
        validate(team);
        ArrayList<String> subset = new ArrayList<>();
        if (trivialElimination(team)) subset.add(winner());
        else {
            FlowNetwork fn = createFlowNetwork(c, s, t, team);
            FordFulkerson ff = new FordFulkerson(fn, s, t);
            int k = id(team);
            for (int i = 0; i < v; i++) {
                if (i != k && ff.inCut(i)) {
                    subset.add(teams[i]);
                }
            }
        }
        return subset.isEmpty() ? null : subset;
    }

    // ----------------------------------------- //
    ///////////////// UTILITIES //////////////////
    // -----------------------------------------//

    private FlowNetwork createFlowNetwork(int ga, int source, int target, String team) {
        FlowNetwork fn = new FlowNetwork(ga + v + 2); // games vertices plus teams vertices plus source and target
        int k = v;
        int x = id(team);
        for (int i = 0; i < v; i++) {
            int capacity = wins[x] + remaining[x] - wins[i];
            if (i != x) { // we remove team from the flowNetwork to test if teamX can win
                if (capacity >= 0) {
                    FlowEdge e3 = new FlowEdge(i, target, capacity); // team i to sink edge
                    fn.addEdge(e3);
                    for (int j = i + 1; j < v; j++) {
                        if (j != x) {
                            // add the edges
                            FlowEdge e0 = new FlowEdge(source, k, this.against[i][j]); // source to game(i,j) edge
                            FlowEdge e1 = new FlowEdge(k, i, Double.POSITIVE_INFINITY); // game(i,j) to team i edge
                            FlowEdge e2 = new FlowEdge(k, j, Double.POSITIVE_INFINITY); // game(i,j) to team j edge
                            fn.addEdge(e0);
                            fn.addEdge(e1);
                            fn.addEdge(e2);
                            k++;
                        }
                    }
                }
            }
        }
        return fn;
    }

    private boolean trivialElimination(String team) {
        int x = id(team);
        int max = maxWins();
        return wins[x] + remaining[x] < max;
    }

    private int maxWins() {
        int maxWins = -1; // lets find the maximum number of wins in the division
        for (int i = 0; i < v; i++) {
            maxWins = Math.max(maxWins, wins[i]);
        }
        return maxWins;
    }

    private String winner() {
        int max = -1;
        int id = -1;
        for (int i = 0; i < v; i++) {
            if (max < wins[i]) {
                max = wins[i];
                id = i;
            }
        }
        return teams[id];
    }

    private int id(String team) {
        int x = -1;
        for (int i = 0; i < v; i++) { // lets find that team index
            if (teams[i].equals(team)) {
                x = i;
                break;
            }
        }
        return x;
    }

    private int capacity(String team) {
        int x = id(team);
        int capacity = 0;
        for (int i = 0; i < v; i++) {
            for (int j = 0; j < v; j++) {
                if (i != x && j != x) {
                    capacity += against[i][j];
                }
            }
        }
        return capacity / 2; // as we double count each game
    }

    private double checkCertificate(String team) {
        Iterable<String> subset = certificateOfElimination(team);
        Iterator<String> i1 = subset.iterator();
        double a = 0.0;
        int n = 0;

        while (i1.hasNext()) {
            String t1 = i1.next(); // at least one team in subset
            a += wins(t1);
            Iterator<String> i2 = subset.iterator();
            while (i2.hasNext()) {
                String t2 = i2.next();
                a += against(t1, t2); // ADD GAMES BETWEEN TEAMS
            }
            n++;
        }
        return a / n; // as we double counted the against games
    }

    private void validate(String team) {
        boolean found = false;
        for (int i = 0; i < v; i++)
            if (teams[i].equals(team)) {
                found = true;
                break;
            }
        if (!found) throw new IllegalArgumentException();
    }


    public static void main(String[] args) {

        BaseballElimination division = new BaseballElimination(args[0]);
        for (String team : division.teams()) {
            if (division.isEliminated(team)) {
                StdOut.print(team + " is eliminated by the subset R = { ");
                for (String t : division.certificateOfElimination(team)) {
                    StdOut.print(t + " ");
                }
                StdOut.println("}");
                int x = division.id(team);
                int t = division.wins[x] + division.remaining[x]; // maximum number of wins for teamX
                StdOut.println("check certificate : " + t + " < " + division.checkCertificate(team));
            } else {
                StdOut.println(team + " is not eliminated");

            }
        }
    }
}