jules0707

BaseballElimination.java

Apr 14th, 2021
450
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. Aggregate score: 89.57%
  3.  
  4. Correctness:  19/23 tests passed
  5. Memory:       4/4 tests passed
  6. Timing:       1/1 tests passed
  7.  
  8. Test 7b: check isEliminated() when n = 5
  9.         * teams5.txt
  10.         * teams5a.txt
  11.         * teams5b.txt
  12.         * teams5c.txt
  13.  
  14.         java.lang.ArrayIndexOutOfBoundsException: Index 1 out of bounds for length 1
  15.  
  16.         BaseballElimination.<init>(BaseballElimination.java:49)
  17.         TestBaseballElimination.checkIsEliminated(TestBaseballElimination.java:159)
  18.         TestBaseballElimination.test7b(TestBaseballElimination.java:558)
  19.         TestBaseballElimination.main(TestBaseballElimination.java:777)
  20.  
  21.         ==> FAILED
  22. */
  23.  
  24. import edu.princeton.cs.algs4.FlowEdge;
  25. import edu.princeton.cs.algs4.FlowNetwork;
  26. import edu.princeton.cs.algs4.In;
  27. import edu.princeton.cs.algs4.StdOut;
  28. import edu.princeton.cs.algs4.FordFulkerson;
  29.  
  30. import java.util.ArrayList;
  31. import java.util.Iterator;
  32.  
  33. public class BaseballElimination {
  34.  
  35.     private final int v;
  36.     private final int[] wins;
  37.     private final int[] losses;
  38.     private final int[] remaining; // remaining games
  39.     private final int[][] against; // games between team1 and team2
  40.     private final int c; // number of games combinations
  41.     private final int s; // source
  42.     private final int t; // target
  43.     private final String[] teams;
  44.  
  45.     // create a baseball division from given filename in format specified below
  46.     public BaseballElimination(String filename) {
  47.         In in = new In(filename);
  48.         v = in.readInt(); // teams vertices
  49.         c = v * (v - 1) / 2; // games confrontation pairs how many ways to choose 2 teams amongst V
  50.         s = c + v;
  51.         t = s + 1;
  52.         int items = 4;
  53.  
  54.         wins = new int[v];
  55.         losses = new int[v];
  56.         remaining = new int[v];
  57.         against = new int[v][v];
  58.         teams = new String[v];
  59.  
  60.         // reading the data
  61.         String all = in.readAll().substring(1);
  62.         String[] lines = all.split("\n"); // removes the new lines
  63.  
  64.         // saving the data
  65.         for (int i = 0; i < v; i++) {
  66.             lines[i] = lines[i].trim(); // removes leading and trailing whitespaces
  67.             String[] line = lines[i].split("[ ]+"); // reads line
  68.             teams[i] = line[0];
  69.             wins[i] = Integer.parseInt(line[1]); // wins
  70.             losses[i] = Integer.parseInt(line[2]); // loses
  71.             remaining[i] = Integer.parseInt(line[3]); // remaining
  72.             // games remaining
  73.             for (int j = 0; j < v; j++) {
  74.                 against[i][j] = Integer.parseInt(line[items + j]);
  75.             }
  76.         }
  77.     }
  78.  
  79.     // number of teams
  80.     public int numberOfTeams() {
  81.         return v;
  82.     }
  83.  
  84.     // all teams
  85.     public Iterable<String> teams() {
  86.         ArrayList<String> all = new ArrayList<>();
  87.         for (int i = 0; i < v; i++) all.add(teams[i]);
  88.         return all;
  89.     }
  90.  
  91.     // number of wins for given team
  92.     public int wins(String team) {
  93.         validate(team);
  94.         int i = id(team);
  95.         return wins[i];
  96.     }
  97.  
  98.     // number of losses for given team
  99.     public int losses(String team) {
  100.         validate(team);
  101.         int i = id(team);
  102.         return losses[i];
  103.     }
  104.  
  105.     // number of remaining games for given team
  106.     public int remaining(String team) {
  107.         validate(team);
  108.         int i = id(team);
  109.         return remaining[i];
  110.     }
  111.  
  112.     // number of remaining games between team1 and team2
  113.     public int against(String team1, String team2) {
  114.         validate(team1);
  115.         validate(team2);
  116.         int i = id(team1);
  117.         int j = id(team2);
  118.         return against[i][j];
  119.     }
  120.  
  121.     // is given team eliminated?
  122.     public boolean isEliminated(String team) {
  123.         validate(team);
  124.         int capacity = capacity(team);
  125.         if (trivialElimination(team)) return true;
  126.         else {
  127.             FlowNetwork fn = createFlowNetwork(c, s, t, team);
  128.             FordFulkerson ff = new FordFulkerson(fn, s, t);
  129.             // If some edges pointing from s are not full (flow is less than capacity)
  130.             // there is no scenario in which team x can win the division ie. team x loses
  131.             return ff.value() < capacity;
  132.         }
  133.     }
  134.  
  135.     // subset R of teams that eliminates given team; null if not eliminated
  136.     public Iterable<String> certificateOfElimination(String team) {
  137.         validate(team);
  138.         ArrayList<String> subset = new ArrayList<>();
  139.         if (trivialElimination(team)) subset.add(winner());
  140.         else {
  141.             FlowNetwork fn = createFlowNetwork(c, s, t, team);
  142.             FordFulkerson ff = new FordFulkerson(fn, s, t);
  143.             int k = id(team);
  144.             for (int i = 0; i < v; i++) {
  145.                 if (i != k && ff.inCut(i)) {
  146.                     subset.add(teams[i]);
  147.                 }
  148.             }
  149.         }
  150.         return subset.isEmpty() ? null : subset;
  151.     }
  152.  
  153.     // ----------------------------------------- //
  154.     ///////////////// UTILITIES //////////////////
  155.     // -----------------------------------------//
  156.  
  157.     private FlowNetwork createFlowNetwork(int ga, int source, int target, String team) {
  158.         FlowNetwork fn = new FlowNetwork(ga + v + 2); // games vertices plus teams vertices plus source and target
  159.         int k = v;
  160.         int x = id(team);
  161.         for (int i = 0; i < v; i++) {
  162.             int capacity = wins[x] + remaining[x] - wins[i];
  163.             if (i != x) { // we remove team from the flowNetwork to test if teamX can win
  164.                 if (capacity >= 0) {
  165.                     FlowEdge e3 = new FlowEdge(i, target, capacity); // team i to sink edge
  166.                     fn.addEdge(e3);
  167.                     for (int j = i + 1; j < v; j++) {
  168.                         if (j != x) {
  169.                             // add the edges
  170.                             FlowEdge e0 = new FlowEdge(source, k, this.against[i][j]); // source to game(i,j) edge
  171.                             FlowEdge e1 = new FlowEdge(k, i, Double.POSITIVE_INFINITY); // game(i,j) to team i edge
  172.                             FlowEdge e2 = new FlowEdge(k, j, Double.POSITIVE_INFINITY); // game(i,j) to team j edge
  173.                             fn.addEdge(e0);
  174.                             fn.addEdge(e1);
  175.                             fn.addEdge(e2);
  176.                             k++;
  177.                         }
  178.                     }
  179.                 }
  180.             }
  181.         }
  182.         return fn;
  183.     }
  184.  
  185.     private boolean trivialElimination(String team) {
  186.         int x = id(team);
  187.         int max = maxWins();
  188.         return wins[x] + remaining[x] < max;
  189.     }
  190.  
  191.     private int maxWins() {
  192.         int maxWins = -1; // lets find the maximum number of wins in the division
  193.         for (int i = 0; i < v; i++) {
  194.             maxWins = Math.max(maxWins, wins[i]);
  195.         }
  196.         return maxWins;
  197.     }
  198.  
  199.     private String winner() {
  200.         int max = -1;
  201.         int id = -1;
  202.         for (int i = 0; i < v; i++) {
  203.             if (max < wins[i]) {
  204.                 max = wins[i];
  205.                 id = i;
  206.             }
  207.         }
  208.         return teams[id];
  209.     }
  210.  
  211.     private int id(String team) {
  212.         int x = -1;
  213.         for (int i = 0; i < v; i++) { // lets find that team index
  214.             if (teams[i].equals(team)) {
  215.                 x = i;
  216.                 break;
  217.             }
  218.         }
  219.         return x;
  220.     }
  221.  
  222.     private int capacity(String team) {
  223.         int x = id(team);
  224.         int capacity = 0;
  225.         for (int i = 0; i < v; i++) {
  226.             for (int j = 0; j < v; j++) {
  227.                 if (i != x && j != x) {
  228.                     capacity += against[i][j];
  229.                 }
  230.             }
  231.         }
  232.         return capacity / 2; // as we double count each game
  233.     }
  234.  
  235.     private double checkCertificate(String team) {
  236.         Iterable<String> subset = certificateOfElimination(team);
  237.         Iterator<String> i1 = subset.iterator();
  238.         double a = 0.0;
  239.         int n = 0;
  240.  
  241.         while (i1.hasNext()) {
  242.             String t1 = i1.next(); // at least one team in subset
  243.             a += wins(t1);
  244.             Iterator<String> i2 = subset.iterator();
  245.             while (i2.hasNext()) {
  246.                 String t2 = i2.next();
  247.                 a += against(t1, t2); // ADD GAMES BETWEEN TEAMS
  248.             }
  249.             n++;
  250.         }
  251.         return a / n; // as we double counted the against games
  252.     }
  253.  
  254.     private void validate(String team) {
  255.         boolean found = false;
  256.         for (int i = 0; i < v; i++)
  257.             if (teams[i].equals(team)) {
  258.                 found = true;
  259.                 break;
  260.             }
  261.         if (!found) throw new IllegalArgumentException();
  262.     }
  263.  
  264.  
  265.     public static void main(String[] args) {
  266.  
  267.         BaseballElimination division = new BaseballElimination(args[0]);
  268.         for (String team : division.teams()) {
  269.             if (division.isEliminated(team)) {
  270.                 StdOut.print(team + " is eliminated by the subset R = { ");
  271.                 for (String t : division.certificateOfElimination(team)) {
  272.                     StdOut.print(t + " ");
  273.                 }
  274.                 StdOut.println("}");
  275.                 int x = division.id(team);
  276.                 int t = division.wins[x] + division.remaining[x]; // maximum number of wins for teamX
  277.                 StdOut.println("check certificate : " + t + " < " + division.checkCertificate(team));
  278.             } else {
  279.                 StdOut.println(team + " is not eliminated");
  280.  
  281.             }
  282.         }
  283.     }
  284. }
  285.  
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×