diff options
Diffstat (limited to 'Algorithms')
| -rw-r--r-- | Algorithms/Part-II/3-BaseballElimination/BaseballElimination.java | 221 | ||||
| -rw-r--r-- | Algorithms/Part-II/3-BaseballElimination/Makefile | 2 |
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) |