Algorithms-II : 3-BaseballElimination: implementation

2 files changed, 205 insertions, 18 deletions

diff --git a/Algorithms/Part-II/3-BaseballElimination/BaseballElimination.java b/Algorithms/Part-II/3-BaseballElimination/BaseballElimination.java
index 3021da6..2c65a4a 100644
--- a/Algorithms/Part-II/3-BaseballElimination/BaseballElimination.java
+++ b/Algorithms/Part-II/3-BaseballElimination/BaseballElimination.java
@@ -1,50 +1,237 @@
 /* vim: set expandtab tabstop=4 shiftwidth=4 : */
 
+import java.util.HashMap;
+
 public class BaseballElimination
 {
+    private static final boolean DEBUG = false;
+
+    private int n;
+    private String[] names;
+    private int[] wins;
+    private int[] losses;
+    private int[] remains;
+    private int[][] games;
+    private HashMap<String, Integer> nameToI;
+    private boolean[] eliminated;
+    private HashMap<Integer, Stack<String>> eliminatedBy;
+
     public BaseballElimination(String filename)
     {
-        // create a baseball division from given filename in format specified below
+        In in = new In(filename);
+
+        n = in.readInt();
+
+        names = new String[n];
+        wins = new int[n];
+        losses = new int[n];
+        remains = new int[n];
+        games = new int[n][n];
+        nameToI = new HashMap<String, Integer>();
+        eliminated = new boolean[n];
+        eliminatedBy = new HashMap<Integer, Stack<String>>();
+
+        for (int i = 0; i < n; i++) {
+            names[i] = in.readString();
+            wins[i] = in.readInt();
+            losses[i] = in.readInt();
+            remains[i] = in.readInt();
+            for (int j = 0; j < n; j++) {
+                games[i][j] = in.readInt();
+            }
+            nameToI.put(names[i], i);
+        }
+
+        trivialEliminations();
+
+        for (int i = 0; i < n; i++) {
+            // if (!eliminated[i] && shouldBeEliminated(i)) {
+            if (!eliminated[i]) {
+                maxFlowComputation(i);
+            }
+        }
+    }
+
+    private void addEliminatedBy(int who, int by)
+    {
+        Stack<String> s = eliminatedBy.get(who);
+        if (s == null) {
+            s = new Stack<String>();
+            s.push(names[by]);
+            eliminatedBy.put(who, s);
+        } else {
+            s.push(names[by]);
+        }
+    }
+
+    private void trivialEliminations()
+    {
+        // even if the team wins all its remaining games
+        // it won't catch up with the best teams
+        for (int i = 0; i < n; i++) {
+            int w = wins[i] + remains[i];
+            for (int j = 0; j < n; j++) {
+                // (i == j) is safe
+                if (w < wins[j]) {
+                    eliminated[i] = true;
+                    addEliminatedBy(i, j);
+                }
+            }
+        }
+    }
+
+    private boolean shouldBeEliminated(int t)
+    {
+        // even if the team wins all its remaining games
+        // it won't catch up with the min of the others wins
+        int w = wins[t] + remains[t];
+        int ws = 0;
+        for (int i = 0; i < n; i++) {
+            if (i == t) continue;
+            ws += wins[i];
+            for (int j = i; j < n; j++) {
+                if (j == t) continue;
+                ws += games[i][j];
+            }
+        }
+        if (w < Math.ceil(ws / (float) (n-1))) {
+            return true;
+        }
+        return false;
+    }
+
+    private int countGamesWithout(int t)
+    {
+        int c = 0;
+        for (int i = 0; i < n; i++) {
+            if (i == t) continue;
+            for (int j = i; j < n; j++) {
+                if (j == t) continue;
+                if (games[i][j] > 0) c++;
+            }
+        }
+
+        return c;
     }
+
+    private void maxFlowComputation(int t)
+    {
+        int g = countGamesWithout(t);
+        // s + t + games + teams
+        int vertices = 2 + g + n;
+
+        FlowNetwork flowNetwork = new FlowNetwork(vertices);
+
+        int S = vertices - 2;
+        int T = vertices - 1;
+        int idx = n;
+        int b = wins[t] + remains[t];
+        for (int i = 0; i < n; i++) {
+            if (i == t) continue;
+            // team -> T
+            FlowEdge e = new FlowEdge(i, T, (b - wins[i]));
+            flowNetwork.addEdge(e);
+            for (int j = i; j < n; j++) {
+                if (j == t) continue;
+                if (games[i][j] > 0) {
+                    // S -> game
+                    e = new FlowEdge(S, idx, games[i][j]);
+                    flowNetwork.addEdge(e);
+                    // game -> team i
+                    e = (new FlowEdge(idx, i, Double.POSITIVE_INFINITY));
+                    flowNetwork.addEdge(e);
+                    // game -> team j
+                    e = (new FlowEdge(idx, j, Double.POSITIVE_INFINITY));
+                    flowNetwork.addEdge(e);
+                    idx++;
+                }
+            }
+        }
+
+        if (DEBUG) {
+            System.out.println(names[t]+" should be out…");
+            System.out.println(flowNetwork.toString());
+        }
+
+        FordFulkerson maxFlow = new FordFulkerson(flowNetwork, S, T);
+
+        if (DEBUG) {
+            System.out.println(flowNetwork.toString());
+            System.out.printf("Team: %s got :%g \n", names[t], maxFlow.value());
+        }
+
+        boolean out = false;
+        for (FlowEdge e : flowNetwork.adj(S)) {
+            if (DEBUG) System.out.println(e);
+            if (e.flow() != e.capacity()) {
+                out = true;
+                break;
+            }
+        }
+
+        if (out) {
+            eliminated[t] = true;
+            for (int i = 0; i < n; i++) {
+                if (maxFlow.inCut(i) && !eliminated[i]) {
+                    addEliminatedBy(t, i);
+                }
+            }
+        }
+    }
+
+    private int teamI(String team)
+    {
+        Object i = nameToI.get(team);
+        if (i == null)
+            throw new IllegalArgumentException(team);
+
+        return (int) i;
+    }
+
     public int numberOfTeams()
     {
-        // number of teams
-        return 0;
+        return n;
     }
+
     public Iterable<String> teams()
     {
-        // all teams
-        return null;
+        return nameToI.keySet();
     }
+
     public int wins(String team)
     {
-        // number of wins for given team
-        return 0;
+        return wins[teamI(team)];
     }
+
     public int losses(String team)
     {
-        // number of losses for given team
-        return 0;
+        return losses[teamI(team)];
     }
+
     public int remaining(String team)
     {
-        // number of remaining games for given team
-        return 0;
+        return remains[teamI(team)];
     }
+
     public int against(String team1, String team2)
     {
-        // number of remaining games between team1 and team2
-        return 0;
+        return games[teamI(team1)][teamI(team2)];
     }
+
     public boolean isEliminated(String team)
     {
-        // is given team eliminated?
-        return false;
+        return eliminated[teamI(team)];
     }
+
     public Iterable<String> certificateOfElimination(String team)
     {
-        // subset R of teams that eliminates given team; null if not eliminated
-        return null;
+        int t = teamI(team);
+
+        if (!eliminated[t])
+            return null;
+        else {
+            return eliminatedBy.get(t);
+        }
     }
 
     public static void main(String[] args) {
diff --git a/Algorithms/Part-II/3-BaseballElimination/Makefile b/Algorithms/Part-II/3-BaseballElimination/Makefile
index cf2b9bb..617e824 100644
--- a/Algorithms/Part-II/3-BaseballElimination/Makefile
+++ b/Algorithms/Part-II/3-BaseballElimination/Makefile
@@ -22,7 +22,7 @@ test: $(BIN)
 zip: $(BIN)
 	$(ALGS4)/bin/findbugs $(BIN).class
 	rm -f *.zip
-	zip seamCarving.zip $(SRCS)
+	zip baseball.zip $(SRCS)
 
 clean:
 	rm -f *.class *.zip check.sh $(BIN)