Gladiators - 107 Course Points

The goal of this assignment is to simulate a game of duels in a Coliseum amongst warriors to become Gladiators, using Binary Search Trees.

This assignment will take longer to complete than any of the labs. Start your assignment early! You need time to understand the assignment and to answer any questions that will arise as you read the description and the code provided.

Refer to our Programming Assignments FAQ for instructions on how to install VSCode, how to use the command line, and how to submit your assignments. 

  • See this video on how to import the project into VSCode and how to submit to Autolab.

The assignment has two components:

  1. Coding (107 points) submitted through Autolab.
  2. Reflection (3 points) submitted through a form.
    • Submit the reflection AFTER you have completed the coding component.
    • Be sure to sign in with your RU credentials! (netid@scarletmail.rutgers.edu)
    • You cannot resubmit reflections, but you can edit your responses before the deadline by clicking the Google Form link, signing in with your NetID, and selecting “Edit your response.”

Overview

In this game mode, warriors are selected from each city by lottery and compete in a battle royale. The goal of this assignment is to use Binary Search Trees to run your own version of the games through the input files of People and Cities provided to you in this assignment.

People are populated into cities and put into odd and even populations within each city. Cities are defined by an ID value and all cities can be stored through a binary search tree using IDs as key values for comparisons. Odd and even populations are based on whether each person’s birth month is odd or even. For example, January (01) birth months would be odd, while December (12) birth months would be even.

In other words, we can represent the cities as a binary search tree, assigning identifiers (city IDs) to each City in order to make comparisons.

Implementation

Overview of Files

  • City class: Represents a city that is participating in the duels. Contains two ArrayLists that store the odd and even population for a single City. Do not edit or submit.

  • Driver class: You can run the Driver to test any of your methods interactively. Feel free to edit this class, as it is provided only to help you test. It is not submitted and it is not used to grade your code. Do not submit.

  • Coliseum class: Contains provided methods as well as methods you are responsible for completing. Moves players from input files to Cities, eliminates Cities and players, and determines a winner of a given round of the battle. Write your solutions in this file and submit this file.

  • Person class: Represents a player within a city. Players have a first name, last name, age, city ID for the City they belong to, an effectiveness property that represents their effectiveness in combat, a youngWarrior property that indicates their eligibility for resources, and a birthMonth property that is used to determine if they will be placed in the odd or even population for their City. Do not edit or submit.

  • DuelPair class: Stores a pair of players in the duels. Do not edit or submit.

  • StdIn and StdOut classes: Used by the driver, provided methods, and some of your implemented methods as well. Do not edit these classes or submit them.

  • StdRandom class: Used by selectDuelers() to generate random numbers. Do not edit or submit.

  • Multiple text files that contain input data and can be read by the driver as test cases. All provided input files, including those used as grading test cases, are correctly formatted. Feel free to edit them or even make new ones to help test your code. They are not submitted.

Coliseum.java

NOTE: You are allowed (encouraged, even) to make helper methods in your Coliseum.java file to be used in your graded methods. Just make sure that they are created with the private keyword. Do not add new imports. 

This class contains:

  • cities, which is an ArrayList of Cities that is used to store the Cities read from an input file. It is not used except in setupGladiators and the Driver.
  • game, which is a BSTNode that refers to the root node of the binary search tree.
  • Provided methods that are used by the driver and empty methods you are expected to write your code in.

Working with BSTNode<> objects

For assignments/labs in CS112, we will use a cs112.jar file containing useful classes. This includes the BSTNode<> class, which implements a binary tree node. You’ve previously worked with the LLNode<> class to create linked lists. Many aspects of the BSTNode are similar:

  • The BSTNode class takes in a generic type, which means it can store any type of data. In this assignment you will be working with nodes that have City objects as their data – to have nodes with City data we can use BSTNode 

  • Making a node: BSTNode newNode = new BSTNode(data) — replace T with a type

    • Note that the data must be passed in for the constructor, and the data a node holds can not be changed later (aka it is immutable). The data may not be null.

      • For this assignment, the City objects WILL be mutable, to allow for easier BST deletion.

  • Methods: 

    • getLeft() – returns the left child of the node
    • setLeft(BSTNode left) – sets the left child of the node
    • getRight() – returns the right child of the node
    • setRight(BSTNode right) – sets the right child of the node
    • getData() returns the data object a node holds

Implementation Notes

  • YOU MAY only update the methods: setupCities(), setupPeople(), addCityToGame(), findCity(), selectDuelers(), eliminateCity(), and eliminateDueler()

  • DO NOT add any instance variables to the Coliseum class.

  • DO NOT add any public methods to the Coliseum class.

  • DO NOT use System.exit() in your code.

  • DO NOT remove the package statement from Coliseum.java
  • YOU MAY add private helper methods to the Coliseum.java. 

To Compile/Run: run the following commands from the innermost Gladiators directory, containing the src and bin folders.

  • Compile:
    • javac -d bin -cp lib/cs112.jar src/games/*.java
  • Run:
    • Windows: java -cp “lib/cs112.jar;bin” games.Driver
    • Mac/Linux: java -cp bin:lib/cs112.jar games.Driver

setupGladiators [PROVIDED]

Let the games begin! This method simulates the commencement of the Gladiators games. The duels are set in a Coliseum where the population is distributed between Cities subject to the duels to uphold their traditions and values in order to give the strongest the title of a Gladiator.

Cities are established (using an ArrayList of Cities) and players are populated into their respective Cities. This is a provided method that calls setupCities and setupPeople in that order; complete setupCities and setupPeople to make this method work. setupCities reads Cities from the input file in order to add them to an ArrayList of Cities, and setupPeople reads players from the same input file after Cities have been read and inserts players into Cities.

Complete both setupCities and setupPeople and submit to Autolab under early submission for 5 points extra credit.

You have been provided with input files to test this method. Each input file is formatted as follows:

  • A number, n, on one line specifies the amount of Cities

  • n lines containing city IDs. 

  • A number, p, on one line specifies the amount of players

  • p lines containing player data, consisting of first name, last name, birth month, age, City ID, and effectiveness (in this order, space-separated). 

How to Test:

First, run the Driver (see the How to open + run section):

Enter the name of the input file.

Then, select 1 to call setupGladiators (calls setupCities and setupPeople). This is the expected output using input1.in:

1. setupCities 

Read Cities from the input file in order to add them to the Coliseum as participating cities. Insert into the Cities ArrayList in order of appearance.

Use the StdIn library to read from a file:

  • StdIn.readInt() reads the next integer value from the opened file (whether the value is in the current line or in the next line)
  • StdIn.readString() reads the next String value from the opened file

The part of the file that you need to read for this method includes:

  • A number, n, on one line specifies the amount of Cities
  • n lines containing city IDs (ints), use these to create City objects  

Note: the input file was already opened using StdIn.setFile() in the setupGladiators() method, so you do not need to set the input file in this method. 

To test this method, select the setupGladiators option in the driver after also completing setupPeople – see above.

Complete this method and the next one for early submission

2. setupPeople

Now, you will add players into cities.

Read players from the input file and insert them in order of appearance into their respective Cities in the Cities ArrayList. Those between ages 12 and 17 (age is greater than or equal to 12, and less than or equal to 17) will have the youngWarrior property equal to true, the Person.java constructor will do this for you. Assume Cities have already been inserted into the Cities ArrayList. Insert players into the proper Cities – odd people go into the oddPopulation list and even people go into the evenPopulation list. 

  • DO NOT call StdIn.setFile in this method – you’re using the same input file as setupCities, picking up where that method left off. The input file will continue being read from where it stopped reading in setupCities. 

The part of the file that you need to read for this method includes:

  • A number, p, on one line specifies the amount of players
  • p lines containing player data, consisting of first name, last name, birth month, age, City ID, and effectiveness (in this order, space-separated). 
    • The first and last name are Strings, the rest are ints
    • Use these to create a Person object, and add this Person to the even or odd population in the correct City

Hint: StdIn.readString() will read the next String up to but not including the space. The entire file can be read using only readString() and readInt() with nothing fancy to ignore the spaces. 

To test this method, select the setupGladiators option in the driver – see above.

  • Complete setupCities BEFORE setupPeople.

Submit this method and setupCities on Autolab under early submission for 5 points extra credit

3. addCityToGame

This method inserts a single City into the Coliseum City Tree (rooted at the instance variable called “game”). Follow Binary Search Tree rules using City IDs as comparisons – BSTNodes with City IDs greater than a root of a subtree go to the right of the root, otherwise they will go to the left. IDs are unique to each City and no City will share the same ID. Remember that the instance variable “game” refers to the root node of the tree.

When testing this method, the Driver will allow you to pick from the Cities in the Cities ArrayList or insert all Cities in the order they appeared in setupGladiators. Changes from previous actions will be reflected when testing individual methods.

Complete setupCities and setupPeople first in order to test this method.

How to Test:

Call setupGladiators in the driver first. Immediately afterward, select option 2 to use the same input file to test another method and select “addCityToGame”.

Select the option to add all cities. This is the expected output when adding all cities in order of appearance using input1.in:

IMPORTANT: Note that this tree and any modifications you make by testing/calling other methods will carry over to other method tests/calls in the driver. You don’t need to start over if you’ve called the required methods in order without modifying the tree.

4. findCity

This method allows you to find the City in which a person is located so you can update and access their population values – later on in the assignment, you will call findCity in the eliminateDueler method to access populations and return the winner back to their City.

This method searches for a City in the Coliseum City Tree given its City ID. Return the City if a City with the target ID is found; otherwise return null. 

  • You should not modify values or nodes in the BST itself.

Complete all previous methods before starting this method.

In the driver, test setupGladiators and addCityToGame on all cities first. Immediately after that, use option 2 to test with the same input file, and test findCity.

Here is the output when trying to find City 3 using input1.in:

5. selectDuelers

This method will obtain two players from unique Cities in the City tree that will fight against each other in the Coliseum. Follow these rules when selecting duelers, so you uphold the game’s integrity:

  • This requires FOUR passes through the BST in this order: one to find an odd young warrior, one to find an even young warrior, another to find an odd warrior (if needed), and another to find an even warrior (if needed).
  • You’ll draft duelers by storing one odd person and one even person into a DuelPair object. The odd person will be person1 and even will be person2 within the pair. Return this pair.
  • When you select a person, put them into the DuelPair and remove them from their City 

To complete this method, we heavily suggest you write four recursive helper methods. These should follow the preorder traversal route (first visit the current node, then the left and right children in that order).

  • First, one which attempts to select a youngWarrior from the odd populations (youngWarrior property is true for that person)
  • Second, one which attempts to select a youngWarrior from the even populations
    • If your first method successfully picked a young odd dueler, then ensure you do not select from the same city
  • Third, one which attempts to select a random dueler from the odd populations if needed
    • If the first helper method populated Person1 with a odd youngWarrior, then do not override them
    • Use StdRandom.uniform(x) where x is the respective population size to obtain a random player
      • Only call StdRandom.uniform(x) IF Person1 is null, and the City has not already been chosen from
    • Remember Person1 and Person2 can not be from the same city
  • Fourth, one which attempts to select a random dueler from the even populations, if needed
    • If the second helper method populated Person2 with an even youngWarrior, then do not override them
    • Use StdRandom.uniform(x) where x is the respective population size to obtain a random player
      • Only call StdRandom.uniform(x) IF Person2 is null, and the City has not already been chosen from
    • Again, make sure Person2 is not from the same city as Person1

In the driver, test in this order using the same input file –  no need to start over unless you’ve called selectDuelers, eliminateCity, or eliminateDueler in between:

  • setupGladiators
  • addCityToGame on ALL cities
  • selectDuelers

Here is the expected output for input1.in – the driver will store this pair for use in eliminateDueler:

6. eliminateCity

Once a City is eliminated, they are turned into ruins and must be removed from the game. 

This method deletes a City from the binary search tree given the ID of the City to eliminate. To delete a node from a BST, find the node containing the ID.

  • If a deleted node has no children, simply unhook it from its parent.
  • If a deleted node has one child, replace it with that child.
  • If a deleted node has two children, replace it with its in-order successor
    • An in-order successor is the next node in sequence. i.e. the smallest node greater than the current node (aka the smallest node in the target’s right subtree)
    • To find the inorder successor of a node: move once to the right, then as far left as possible.

In the driver, test in this order using the same input file –  no need to start over unless you’ve tested eliminateCity or eliminateDueler in between:

  • setupGladiators
  • addCityToGame on ALL cities
  • eliminateCity

Here is the expected output after eliminating City 3 from the tree created using the steps above (uses input1.in):

7. eliminateDueler

As the game starts, people are fighting for glory, thus eliminating opponents they have to face as they roam around the setting they are put in. It does not matter how strong, skilled, astute a person was, one simple mistake could lead to elimination. In this case, our players occasionally meet others and fight each other.

The fight starts now! This method takes in a DuelPair as parameters. If the pair is incomplete, return the player in the pair (if there is one) back to the City they came from and add them to their respective population. Do nothing else if this is the case.

If the pair is complete:

  • You can use the duel() method built into the Person class to have two players fight against each other. For example, calling person1.duel(person2) will return a winner and the other person will be the loser. 
  • Return the winner back to their City, to their respective odd or even population.
  • If either the winner or loser city’s odd or even population sizes are 0, call eliminateCity on the City ID to remove that City from the BST.

In the driver, test in this order using the same input file –  no need to start over unless you’ve tested eliminateCity in between:

  • setupGladiators
  • addCityToGame on ALL cities
  • selectDuelers
  • eliminateDueler

Here is the expected output after running eliminateDueler using input1.in:

 

How to open + run

First things first, make sure you have VS Code installed, a Java Development Kit (JDK) installed, and the Java Extension Pack enabled on VS Code. If you don’t, the FAQ tab of this site has download links.

Afterward, open the Gladiators folder in VS Code using File -> Open Folder. Open the Gladiators folder that directly contains the bin, src, and lib folders. If you have a Gladiators folder inside Gladiators, or you have CS112 Code -> Gladiators, you must open the innermost Gladiators folder. 

Next, when you’re ready to run your program, you can use either the terminal or the VS Code run option. 

If you use the terminal, run the following commands in order from the Gladiators directory that contains the bin, src and lib folders. If you’re having issues, please ensure that you’re in the right directory in VS Code and that you’ve typed the commands correctly and in order.

To Compile/Run: run the following commands from the innermost Gladiators directory, containing the src and bin folders.

  • Compile:
    • javac -d bin -cp lib/cs112.jar src/games/*.java
  • Run:
    • Windows: java -cp “lib/cs112.jar;bin” games.Driver
    • Mac/Linux: java -cp bin:lib/cs112.jar games.Driver

You can also use the “Run” option in VS Code to run your program by right-clicking Driver.java and selecting “Run Java”. 

JUnit Testing

The “test” folder in the project directory contains a GladiatorsTest.java class which contains an empty JUnit test for each of the methods. You can fill out these tests to test the correctness of your methods, by comparing your output to hardcoded reference output. 

Since most methods can be tested via the Driver, this is most useful to test setupCities and setupPeople individually, as the Driver tests both at once using setupGladiators.

Once you fill in a JUnit test, remove the fail() statement at the bottom of it. If you do not do this, the test will never pass.

Before submission

REMOVE all print statements you have written in Coliseum.java.

Collaboration policy. Read our collaboration policy on the course syllabus.

Submitting the assignment. Submit Coliseum.java separately via the web submission system called Autolab. 

Getting help

If anything is unclear, don’t hesitate to drop by office hours or post a question on Piazza.

  • Find instructors and Lead TAs office hours here
  • Find tutors office hours on Canvas -> Tutoring
  • In addition to office hours we have the Coding and Social Lounge (CSL), a community space staffed with lab assistants which are undergraduate students further along the CS major to answer questions.

By Kal Pandit, Maksims Kurjanovics Kravcenko, and Pranay Roni

White RU Logo

Rutgers is an equal access/equal opportunity institution. Individuals with disabilities are encouraged to direct suggestions, comments, or complaints concerning any
accessibility issues with Rutgers websites to accessibility@rutgers.edu or complete the Report Accessibility Barrier / Provide Feedback form.

Copyright © , Rutgers, The State University of New Jersey. All rights reserved. Contact webmaster