Skip to Main Content

Data Structures

Computer Science Department

RU Hunger Games – 100 course points

In this assignment, you will practice implementing binary search trees. 

READ the assignment as soon as it comes out! You need time to understand the assignment and to answer the many 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.

Overview

The goal of this assignment is to simulate the Hunger Games (a modified from the original). You do not have to be familiar with the Hunger Games novels or movies in order to complete the assignment.

The Hunger Games is a fictional annual event where one pair of people is chosen from each district by lottery to compete in a battle Royale to the death. The goal of this assignment is to use Binary Search Trees (BSTs) to run your own version of the games through the input files of People and Districts provided to you.

Districts are similar to states. They contain two types of population based on each person’s birth month.

  • odd population were born in odd months of the year. January (01), March (03), and so on. 
  • even population were born in even months of the year. February (02), April (04), and so on.

Districts are defined by an identification (ID) value and all districts are stored in a BST using ID’s as the key (used for comparisons). People are placed into districts and assigned into odd or even population within each district. 

In other words, we can represent the Hunger Games districts as a Binary Search Tree (BST), assigning identifiers (district ID’s) to each district in order to make comparisons.

Implementation

Overview of files provided

DO NOT edit or submit to Autolab any of these files EXCEPT for HungerGames.java.

  • District class: Represents a district in the Hunger Games. Contains two ArrayLists that store the odd and even population for a single district. 
  • 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. 
  • HungerGames class: Contains provided methods as well as methods you are responsible for completing. Moves players from input files to districts, eliminates districts and players, and determines a winner of a given round of the Hunger Games. Write your solutions in this file and submit this file to Autolab.
  • Person class: Represents a dueler within the Hunger Games. Duelers have a first name, last name, age, district ID for the district they belong to, an effectiveness property that represents their effectiveness in a duel, a Tessera property that indicates the person has volunteered for the game, and a birthMonth property that indicates whether they will be placed in the odd or even population for their district. 
  • DuelPair class: Stores a pair of duelers in the Hunger Games. 
  • TreeNode class: Represents a BST Node in the Hunger Games. It holds a District as well as the left and right subtrees of the node.
  • StdIn and StdOut classes: Used by the driver, provided methods, and some of your implemented methods as well.
  • StdRandom class: Used by retrievePlayers to generate random numbers. 
  • 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.

HungerGames.java

  • DO NOT add new import statements.
  • DO NOT change any of the method’s signatures.
  • You are allowed (encouraged, even) to make helper methods in your HungerGames.java file to be used in your graded methods. Just make sure that they are created with the private keyword.

This class contains:

  • districts: an ArrayList of Districts that is used to store the districts that are read from an input file. It is not used except in setupPanem and the Driver. This array contains all the districts that are part of Panem.
  • game: a reference to the root node of the Binary Search Tree (BST). Each TreeNode contains one district. The BST contains all the districts that are still competing in the game.
  • Provided methods that are used by the driver and empty methods you are expected to write your code in.

Methods to be implemented by you:

setupPanem

The Hunger Games is set in Panem, a totalitarian dictatorship, where the population is distributed between Districts subject to the Capitol due to the failed insurrection, where the Hunger Games is played to remind the Districts about it.

This method simulates the commencement of the Hunger Games. Districts are established (using an ArrayList of districts) and people (players) are populated into their respective districts. This method is provided to you. It calls setupDistricts and setupPlayers in that order; complete setupDistricts and setupPeople to make this method work.

  • setupDistricts reads districts from the input file in order to add them to an ArrayList of Districts.
  • setupPeople reads people from the same input file after districts have been read and inserts players into districts.

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

  • A number n on the first line specifies the amount of districts.
  • n lines containing district ID’s. 
  • A number p on the next line specifies the amount of players
  • p lines containing people data, consisting of first name, last name, birth month, age, district ID, and effectiveness (in this order, space-separated). 

While you may test these methods incrementally, Autolab will test setupPanem and expects the following two methods to be completed.

  • Submit HungerGames.java with setupDistricts and setupPeople completed under Early Submission to receive extra credit.

1. setupDistricts

Read the districts from the input file in order to add them to Panem, the world in which the Hunger Games takes place. Create District objects and insert them into the districts ArrayList in order of appearance.

Here is the expected output for this method given by the Driver using input1.in – use the setupPanem method to test:

2. setupPeople

Now, you will add people into Panem.

Read the people from the input file and insert them in order of appearance into their respective districts in the districts ArrayList. People between ages 12 and 18 (age is greater than or equal to 12, but less than 18) will have the Tessera property (set tessera = true);  this means that they have volunteered for the games.

Assume districts have already been created and inserted into the districts ArrayList. Insert people into their districts (each person is assigned to a district) – people born in odd months go into the oddPopulation list and people born in even months go into the evenPopulation list. 

Use the StdIn library to read from a file:

  • StdIn.setFile(filename) opens a file to be read. This is already done for you on setupPanem.
  • 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.

To test this method, use setupPanem, which calls setupDistricts and setupPlayers in sequence. Here is the expected output for this method given by the Driver using input1.in:

3. addDistrictToGame

In the Hunger Games, there are districts that are competing against each other. In the novel and film, there are 12 districts, but our version of the Hunger Games game allows for an arbitrary number of districts to be added to the game. When we have a large number of districts, we can add/remove a single district more efficiently using a BST in O(log n) than an Array O(n). Do you understand why is this?

  • The reference variable game is the root of the BST.
  • The BST node is called TreeNode. Each TreeNode has a district associated with it.
  • The BST then, holds all the districts that are still competing in the Hunger Games.

To initialize the game all districts must be added to the BST. Once all districts are added, they will officially be competing against each other as opposed to simply being in Panem.

This method inserts a SINGLE district into the BST.

  • District ID’s are unique, no district will share the same ID.
  • Follow BST ordering when inserting a district. Use the district ID’s as the key to insert the district into the tree – TreeNodes with district ID’s greater than a root of a subtree go to the right of the root, otherwise they will go to the left.  
  • Remove the newly inserted district from the districts ArrayList upon insertion.

This method has a TreeNode “root” as a parameter. The driver ALWAYS calls this method on the game instance variable, and we expect that only the tree rooted at game will be updated.

  • While you may use this parameter to implement a recursive solution, you are not required to. We expect that this method inserts a single district to the BST rooted at game in all cases.

When testing this method, the Driver will allow you to pick a district from the districts ArrayList or insert all districts in the order they appeared in setupPanem.

Changes to the game from previous methods will be reflected when testing individual methods.

This is the expected output after running setupPanem and adding all districts in input1.in:

4. findDistrict

This method searches for a district in the Hunger Games game BST given its district ID. Return the District that matches the target ID; return null if the district ID isn’t found in the BST. 

Later on in the assignment, you will call findDistrict in the eliminateDueler method to access populations and return the winner back to their district.

  • Implement this method recursively.

If you need help with BST search, review Learning Objective 5.2c.

Here is the output when trying to find district 1 using input1.in:

5. selectDuelers

In the Hunger Games, a lottery ceremony is conducted in which two people, one female and one male, both from the same district, are chosen and added onto the list of duelers.

  • This assignment is a simplified version of the Hunger Games – instead of having two people from the same district duel another pair, we have one person duel another person from a different district.
  • Tesserae is a system in which children between the ages of 12-18 (greater than or equal to 12 but less than 18) may submit their name to the lottery extra times in exchange for a year’s supply of food and oil for one person. In this simplified version ALL children (ages 12-17) have volunteered, so they have their tessera set to true (see the setupPeople method).

This method selects two duelers from DISTINCT districts in the game tree to duel in the game. The two duelers form a DuelPair and will duel against one another in the Hunger Games. Follow these rules when selecting duelers:

  • Investigate each district (to select people to duel) by traversing through the game tree, starting at the root then go to that node’s left and right children, in that order.
  • The two selected people must be from DISTINCT districts, one person is selected from the odd population and the other person is selected from the even population.
  • Choose the FIRST person that matches the criteria: 
    • Children (tessera = true) are selected first.
    • If there are no children (tessera = true) then select a person randomly. Use StdRandom.uniform(x) where x is the respective population size to obtain a random player.
  • Stored them into a DuelPair. The person from the odd population will be person1 and the person from the even population will be person2 within the pair. Return this pair.
    • Note: Person 1 and person 2 cannot be from the same district.
  • Remove the Persons from their district. They are now dueling in the Hunger Games.

Hint: you may have to do several passes through the BST. First search for a person with tessera = true from the odd population, then search for a person with tessera = true from the even population. If you still don’t have the two duelers, then you need more passes to find people with tessera = false.

Here is the expected output using input1.in:

6. eliminateDistrict

Once all people from a district are eliminated, the district must be removed from the game.

Given the ID of the district to eliminate, this method deletes the district from the game tree.  To delete a node from a BST, search for the node containing the district’s ID.

If the TreeNode containing the district:

  • has no left or right children, delete the node by setting it’s parent’s link to null.
  • has only one child, replace it’s parent’s link with the child.
  • has two children, find the inorder successor of the node, delete the inorder successor from the tree (don’t lose the node), and put the inorder successor in the node’s spot.
    • the inorder successor of a node is the minimum node in its right subtree.

Hint: this is similar to the BST delete seen in class.

Here is the expected output after eliminating district 3 from the tree created by adding all districts in putDistrict (uses input1.in):

7. eliminateDueler

As the game starts, people are dueling for their lives, thus “eliminating” opponents they face as they roam around the setting they are put in. It did not matter how strong, skilled, astute a person was, one simple mistake could lead them to their death. In this case, all people occasionally meet others and fight for their lives.

This method will make a pair of duelers duel! This method takes in a DuelerPair as parameter.

If the pair is INcomplete (there is only one person in the pair):

  • return the person in the pair back to the district they came from, to their respective odd or even population.
  • Do nothing else if this is the case.

If the pair is complete:

  • Use the duel() method built into the Person class to have two duelers fight against each other. For example, calling person1.duel(person2) will return a winner; the other person will be the loser. 
  • Return the winner back to their district, to their respective odd or even population.
  • If a district’s population reaches 0 (zero), the district is limited. Check the winner’s and the loser’s district’s populations size.
    • If district’s odd or even population sizes are 0 (zero), call eliminateDistrict on the district ID to remove their district from the BST.

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

Implementation Notes

  • YOU MAY only update the methods commented with WRITE YOUR CODE HERE.
  • COMMENT all printing statements from HungerGames.java
  • DO NOT add any instance variables to the HungerGames class.
  • DO NOT add any public methods to the HungerGames class.
  • DO NOT add/rename the project or package statements.
  • DO NOT change the class HungerGames name.
  • YOU MAY add private methods to the HungerGames class.
  • YOU MAY use any of the libraries provided in the zip file.
  • DO NOT use System.exit()

VSCode Extensions

You can install VSCode extension packs for Java. Take a look at this tutorial. We suggest:

Importing VSCode Project

  1. Download HungerGames.zip from Autolab Attachments.
  2. Unzip the file by double clicking.
  3. Open VSCode
    • Import the folder to a workspace through File > Open

Executing and Debugging

  • You can run your program through VSCode or you can use the Terminal to compile and execute. We suggest running through VSCode because it will give you the option to debug.
  • How to debug your code
  • If you choose the Terminal:
    • first navigate to HungerGames directory/folder
      • to compile:  javac -d bin src/games/*.java
      • to execute: java -cp bin games.Driver

Before submission

COMMENT all printing statements from HungerGames.java

Collaboration policy. Read our collaboration policy here.

Submitting the assignment. Submit HungerGames.java separately via the web submission system called Autolab. To do this, click the Assignments link from the course website; click the Submit link for that assignment.

Getting help

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

  • Find instructors office hours here
  • Find tutors office hours on Canvas -> Tutoring, RU CATS
  • Find head TAs office hours here
  • In addition to office hours we have the CAVE (Collaborative Academic Versatile Environment), a community space staffed with lab assistants which are undergraduate students further along the CS major to answer questions.

Problem by Maksims Kurjavonics Kravacenko, Kal Pandit, Pranay Roni