Homework 9: TournaKit¶

PerspecTV logo

Introduction¶

perspecTV is a (fictitious) company that designs, creates and markets products that provide a new perspective on television. Their products make television both more interactive and more informative. They have found that viewers of televised competitions of various kinds (including traditional sporting events, eSports, dance competitions, singing competitions, cooking contests, poker competitions, spelling bees, etc.) are very interested in historical statistics. perspecTV is developing various software products to help satisfy that demand.

TournaKit is a suite of products that can be used to analyze the results (Ex: scores, wins, losses, ties) of completed tournaments. For this assignment, you will implement methods for analyzing round robin tournaments, single elimination tournaments, and general tournaments.

Definitions¶

perspecTV uses the following definitions (listed in logical order, not alphabetical order) in relation to TournaKit.

Participant: A competitor in a competition of some kind.
Matchup: A competition involving exactly two participants.
Visitor/Home: Designations for the two participants in a matchup. The visiting participant is listed first, and the home participant is listed second.
Score: The number of points/runs/goals/etc. awarded to a single participant.
Point Differential: The absolute value of the difference between the visiting participant's points and the home participant's points.
Win/Loss/Tie: The three possible outcomes of a matchup for a particular participant. Notice that, in some matchups, the participant with the higher score wins (e.g., lacrosse) while in other matchups, the participant with the lower score wins (e.g., golf).
Round: A set of matchups in which none of the participants appears more than once.
Tournament: A set of rounds.
Round Robin Tournament: A tournament in which each competitor plays multiple other competitors, regardless of whether they win, lose, or tie. A round robin tournament is said to be regular if the number of competitors (n) is even, each competitor competes in each round, and each competitor competes against each other competitor exactly once (and hence, there are n-1 rounds).
Single Elimination Tournament: A tournament in which ties are not possible and only the winning teams in a round advance to the next round (i.e., the team that loses is eliminated). A single elimination tournament is said to be regular if the number of competitors (n) is a power of 2 (and hence, the number of rounds is log_2(n) + 1). Many single elimination tournaments are regular but many, especially those that involve "play-in" competitions, are not. For example, the NCAA Division I Basketball Tournament used to be regular (involving 64 competitors and 7 rounds) but now includes a "play-in" round (involving 8 competitors reduced to 4 that are added to the 60 teams that skip the "play-in" round).

Assumptions¶

You should assume that round robin tournaments are regular.
You must not assume that single elimination tournaments are regular.
You must not make any assumptions about any other tournaments.

UML Diagrams¶

The design of the initial components has already been completed, and is shown in the following diagrams. Existing classes (i.e., classes that are being provided to you) are outlined in perspecTV's trademarked green, and new classes (i.e, classes that you must write) are outlined in black.

Existing Classes¶

classDiagram

    class Participant {
        <<enumeration>>
        VISITOR
        HOME
        +other() Participant
    }

    class Matchup {
        +Matchup(visitor: String, home: String, \n &nbsp; &nbsp; &nbsp; &nbsp; visitorScore: int, homeScore: int)
        +getName(who: Participant) String
        +getScore(who: Participant) int
        +toString() String
    }

    class Tournament {
        +Tournament(description: String)
        +getDescription() String
        +getFinalMatchups() Matchup[]
        +iterator(endingWith: Matchup, team: String) Iterator~Matchup~
        +previous(matchup: Matchup, team: String) Matchup
        +read(fileName: String) Tournament$
    }

    class RoundRobinTournament {
        +RoundRobinTournament(description: String)
        +read(fileName: String) RoundRobinTournament$
    }

    class SingleEliminationTournament {
        +SingleEliminationTournament(description: String)
        +getFinalMatchup() Matchup
        +read(fileName: String) SingleEliminationTournament$
    }

    Participant "2" -- Matchup
    Matchup --o Tournament
    Tournament <|-- RoundRobinTournament
    Tournament <|-- SingleEliminationTournament

    style Participant stroke:#94ae6c,stroke-width:2
    style Matchup stroke:#94ae6c,stroke-width:2
    style Tournament stroke:#94ae6c,stroke-width:2
    style RoundRobinTournament stroke:#94ae6c,stroke-width:2
    style SingleEliminationTournament stroke:#94ae6c,stroke-width:2

Note: The static read() methods throw ClassNotFoundException if the file type is unknown and IOException if there is a problem reading the file.

Classes to Write¶

classDiagram
    direction LR

    class Judge {
        <<interface>>
        +result(matchup: Matchup, who: Participant) int*
    }

    class Standing {
        -wins: int
        -losses: int
        -ties: int
        +Standing()
        +Standing(wins: int, losses: int, ties: int)
        +getLosses() int
        +getTies() int
        +getWins() int
        +increaseLosses()
        +increaseTies()
        +increaseWins()
        +toString() String
    }

    class Analyst {
        <<utility>>
        +totalPointDifferential(t: Tournament, endingWith: Matchup, team: String) int$
        +buildSchedule(t: RoundRobinTournament) Map~String, List&lt;String&gt;~$
        +totalPointDifferential(t: SingleEliminationTournament) int$
        +buildSchedule(t: SingleEliminationTournament) Map~String, List&lt;String&gt;~$
        +calculateStandings(t: Tournament, j: Judge) Map~String, Standing~$
    }

    Judge <|.. HighWins
    Judge <|.. LowWins

    style Judge stroke:#000000
    style HighWins stroke:#000000
    style LowWins stroke:#000000
    style Standing stroke:#000000
    style Analyst stroke:#000000

Provided Files¶

Binary Data Files¶

perspecTV has provided three tournament files that you can use when running your code. They contain the results of the following tournaments:

2016 Fantasy Division I Quidditch World Cup (Regular Round Robin)
- quidditch_d1_2016.rrt
2017 NCAA Division III Women's Lacrosse Championship (Single Elimination)
- lacrosse-women_d3_2017.set
2018 Disney Division Golf Championship (Regular Round Robin followed by Single Elimination)
- golf_dd_2018.tmt

Regular round robin tournaments have a file type of .rrt, single elimination tournaments have a file type of .set, and other tournaments have a file type of .tmt.

Readable Formats¶

None of the above files are "human readable" — they use a binary format. To help you test your code, perspecTV has also provided the following files:

Quidditch:
- Spreadsheet
Lacrosse:
- Spreadsheet
- Visualization
Golf:
- Spreadsheet
- Visualization of the Single Elimination Portion

Note: These files contain the same data as the binary data files. We recommend you store all of the data files in the same folder.

Java Source Files¶

A senior developer created the following files before "handing off" the project to you:

Analyst.java
- Stubs and Javadoc comments for the Analyst class. This is the main class you will implement for the homework.
AnalystTest.java
- This small set of tests are sufficient to cover most of the reference solution. You are encouraged to add other tests.
tournakit.jar
- The Participant enum, Matchup class, and Tournament, RoundRobinTournament, and SingleEliminationTournament classes are provided in this .jar file.

Note: As shown in AnalystTest, the data files are expected to be found in src/hws/hw9/data/.

Existing Classes¶

Participant¶

The Participant enum represents whether a team is HOME or VISITOR. The enum provides a method for getting the "other" constant.

Matchup¶

This class represents a competition involving exactly two participants. The constructor may help you write early unit tests (i.e., before you feel ready to read() in an entire data file for testing).

Tournament¶

The getFinalMatchups() method returns an array of all of the "final" Matchup objects, regardless of the round in which they occur. This means that the the array that is returned will include every competitor in at least one Matchup (and, in some cases, in more than one Matchup).

For example, consider a Tournament that has six competitors; all six play a round robin portion and then the top four competitors in the round robin portion play a single elimination portion. The getFinalMatchups() method will return an array containing the one Matchup from the final round of the single elimination portion, and the Matchup objects from the last round of the round robin portion for the two teams that did not participate in the single elimination portion.

The iterator() method returns an Iterator containing all of the Matchup objects involving the given team, ending with the given Matchup. The Iterator is in "round order" (i.e., the first call to next() will return the earliest Matchup).

The previous() method returns the Matchup from the previous round (relative to the round of the given Matchup) for the given team. If there is no such Matchup, this method returns null.

RoundRobinTournament¶

The getFinalMatchups() method of a RoundRobinTournament object returns all of the Matchup objects from the final round.

SingleEliminationTournament¶

The getFinalMatchups() method of a SingleEliminationTournament object return an array containing one Matchup, the Matchup for the final round of the tournament.

The getFinalMatchup() method (note the lack of an "s") is a convenience method that returns the final round of the tournament. In other words, it returns getFinalMatchups()[0].

Supporting Classes¶

Judge¶

The Judge interface describes the capabilities of classes that can be used to determine the result of a Matchup.

The result(Matchup, Participant) method must return 1 if the given Participant won the given Matchup, must return -1 if the given Participant lost the given Matchup, and must return 0 if the given Matchup was a tie.

HighWins and LowWins¶

The HighWins class is a realization of the Judge interface that awards the win to the participant with the highest score. Both lacrosse and quidditch are examples of competitions that use this kind of Judge.

The LowWins class is a realization of the Judge interface that awards the win to the participant with the lowest score. Golf is an example of a competition that uses this kind of Judge.

Standing¶

The Standing class is an encapsulation of a competitor's performance in a tournament.

The default constructor must initialize all attributes to 0.

The increaseLosses(), increaseWins(), and increaseTies() methods must increase the associated attribute by 1.

The toString() method must return a String representation of the team's standing, including the wins, losses, and ties (in that order), delimited by " - " (i.e., a dash with a space on each side). Each value must be right-justified in a field of width three.

The Analyst Class¶

The Analyst class is a utility class for performing calculations on tournaments.

In addition to the specifications included in the UML diagram, this class must comply with the following specifications. Note that when a specification says that a method must be recursive, it must be recursive in a meaningful/non-trivial way (i.e., it must use recursion to solve the problem).

totalPointDifferential(Tournament, Matchup, String)¶

This method is the publicly visible method for calculating the total point differential in all games involving the given team, ending with the given Matchup. This method need not be recursive. In other words, it is possible (indeed relatively easy) to calculate the point differential for a particular team iteratively, without recursion.

buildSchedule(RoundRobinTournament)¶

This method is the publicly visible method that builds a schedule containing each competitor in a RoundRobinTournament (the key of the Map) and a List of all of its opponents (the value of the Map). The opponents must be included in the List in the order in which the competitions occurred (i.e., with the earliest round first).

The public method must call a private method that does most of the work. The private method need not be recursive, though it can be. Because of the structure of RoundRobinTournament objects, the schedule can be built iteratively, without recursion. Keep in mind that a RoundRobinTournament has multiple matchups in each round, including the final round.

totalPointDifferential(SingleEliminationTournament)¶

This method is the publicly visible method for calculating the total point differential of all matchups in a SingleEliminationTournament. It must call a private method that does most of the work. The private method must be recursive.

buildSchedule(SingleEliminationTournament)¶

This method is the publicly visible method that builds a schedule containing each competitor in a SingleEliminationTournament (the key of the Map) and an ordered List of all of its opponents (the value of the Map). It must call a private method that does most of the work. The private method must be recursive.

calculateStandings(Tournament, Judge)¶

This method is the publicly visible method for calculating the standings of all competitors in a Tournament. It must call a private method that does most of the work. The private method must be recursive.

Submission and Grading¶

At this point in the semester, you should be able to both implement and test your code. Hence, it is your responsibility to submit correct code. Hence, though you do not need to submit any tests, you will almost certainly need to write tests.

One way to think about this is that perspecTV does not have testers (either in-house alpha testers or external beta testers). The code you submit will be given to clients to use in a production environment. If the code contains defects, the clients will not provide details, they will just stop using the product (which will cost perspecTV revenue). If you find yourself in a situation in which your code passes all of your tests but the client (i.e., Gradescope) says it didn't work properly, you will need to re-think your tests.

Your grade will be based on the "official" tests your code passes/fails (though, as before, your code must not contain any style defects). The instructor code reviews are worth 0 additional points. However, points may be deducted if your code is difficult to understand. Ex: confusing variable names, too few or too many comments, etc.

Part A: Collections¶

Submit all five files: Judge.java, HighWins.java, LowWins.java, Standing.java, and Analyst.java. Only the first two methods (the non-recursive methods) of Analyst are required for Part A.

Criteria	Points
`Judge`, `HighWins`, `LowWins`, `Standing`	15
`totalPointDifferential(Tournament, Matchup, String)`	10
`buildSchedule(RoundRobinTournament)`	15
Instructor Code Review	0*

You may submit up to 10 times without penalty. Additional submissions (if any) will receive a penalty of -5 points each. Be sure to use all the development tools offline: Checkstyle, JUnit, coverage analysis, and the debugger.

Part B: Recursion¶

Submit only Analyst.java. Gradescope will compile your Analyst with the reference solutions for Judge, HighWins, LowWins, and Standing.

Criteria	Points
`totalPointDifferential(SingleEliminationTournament)`	20
`buildSchedule(SingleEliminationTournament)`	20
`calculateStandings(Tournament, Judge)`	20
Instructor Code Review	0*

You may submit up to 10 times without penalty. Additional submissions (if any) will receive a penalty of -5 points each. Be sure to use all the development tools offline: Checkstyle, JUnit, coverage analysis, and the debugger.

Hints and Suggestions¶

A Recommended Process¶

You should certainly start by implementing and testing the Judge interface, HighWins and LowWins classes, and Standing. After that, you should probably work on the methods in the Analyst class in increasing level of difficulty.

The totalPointDifferential(Tournament, Matchup, String) method is the easiest in the Analyst class. It needn't involve recursion.

The buildSchedule(RoundRobinTournament) method is the next-easiest (because you need only consider regular round robin tournaments). It also needn't involve recursion, though you need to think carefully about how you can use iteration because the last round in such a tournament includes multiple Matchup objects.

The totalPointDifferential(SingleEliminationTournament) method does involve recursion (i.e., the private method it calls must use recursion), but the recursion is fairly straightforward (i.e., similar to many examples that you've seen).

The buildSchedule(SingleEliminationTournament) method must work backwards from the last Matchup to construct a complete schedule. The base case should be fairly obvious, and you should also be able to figure out how to refine the other cases fairly quickly. What may take some time is figuring out how to keep track of the results.

The calculateStandings(Tournament, Judge) method is pretty challenging because it must work on any Tournament. Hence, though the base case is pretty obvious, you will need to spend time thinking about how to refine the other cases. Also, you will need to think carefully about how to avoid "double counting".

Using Your Code¶

You should test your code using JUnit. However, you may also want to write a small application just because it is sometimes more satisfying than just writing tests. For example, the following application can be used to print the standings of each team in the lacrosse championship.

package hws.hw9;

import java.util.Map;

public class Results {

    public static void main(String[] args) throws Exception {
        SingleEliminationTournament lacrosse;
        Map<String, Standing> standings;

        lacrosse = SingleEliminationTournament.read(
            "src/hws/hw9/data/lacrosse-women_d3_2017.set");
        standings = Analyst.calculateStandings(lacrosse, new HighWins());

        System.out.println(lacrosse.getDescription());
        for (String team : standings.keySet()) {
            Standing standing = standings.get(team);
            System.out.printf("%25s:\t%s\n", team, standing);
        }
    }
}

If you're actually interested in these kinds of analyses, you might also want to write an application that compares the point differential for all of the matchups in the lacrosse tournament with the point differential for the winner, in order to evaluate the winner's "dominance" in the tournament.