Skip to Main Content

Data Structures

Computer Science Department

Minecraft Separate Chaining - 10 Course Points

The purpose of this lab is to learn how to implement a separate chaining hash table without rehashing. 

Start your assignment early! 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.

The assignment has one component: Coding (10 points) submitted through Autolab.

Overview

Minecraft is a popular sandbox game where you can place blocks, mine or collect items, or create anything from small shelters to complex structures. Items like wood, diamonds, apples, etc are the core of the game — you can make structures out of items, store them in other places, and craft items to make others. You don’t need any knowledge of the game in order to understand or complete this assignment.

In Minecraft, you can craft items by assembling items inside a crafting table – you have a 2×2 crafting table by default, but by creating a crafting table you can use it to work with a 3×3 grid. Here’s an example of putting diamonds in a 3×3 grid to create a diamond block:

In this assignment, we will use a separate chaining hash table without rehashing to store “how” we can craft items. Names will be the keys, and recipes will be the values. You will be given the key-value pair needed, so you don’t have to worry about parsing recipes at all. Instead of a traditional hash function like id % size, we will map letters to indices (A is at index 0, B index 1, C index 2) so that we can search for items based on their first letter (A for Apple, D for Diamond). Because letters are fixed (there are only 26 letters in the English alphabet), we don’t need to rehash. 

If you’ve played Minecraft before, this differs from real Minecraft in that:

  •  We will only test you on craftable items: that is, items that do have recipes. If you try to add a non-craftable item or an item whose ingredients are missing, the driver will give you an empty recipe grid. 
  • You can assume that the only correct way to make an item is by having all ingredients in the exact same position (only one recipe to craft an item). 
  • The actual recipe book in Minecraft arranges items in categories; we’re using the first letter of the item name to define a “cluster” and store items at a given index. 

Structure + Implementation

  • The Driver class is used to test your methods interactively. Feel free to edit this file, as it is provided only to help you test your code. It is not submitted and it is not used to grade your code. Do not submit to Autolab.
  • The Item class is our node in the separate-chaining table. stores an item name (which will be used as the key), a Recipe object (containing the crafting recipe, which will be used as the value), and a “next” reference to another item. 
  • The Recipe class stores a 3×3 grid of item names in an instance variable called items, whose positions represent how to make an item. We also store the number of items that a recipe can generate (you can get two sticks through its recipe) in an instance variable called resultingCount. 
  • The MinecraftSC class is your overall solution class; you’ll implement code to put and delete items. It also has code to read input files. Submit this class to Autolab.
  • Multiple input files, which are formatted as follows (you don’t need to work with this!):
    • A number of items in this table, we’ll call this n
    • For each of n items:
      • On the same line: The resulting count (how many items this recipe can generate), followed by the item name as a string
      • Another line containing the # of items needed in the recipe
      • For each needed item: an x coordinate, a y coordinate, and the item name
    • Example of the number of items + a single recipe:
    • 47
1 Activator Rail
9
0 0 Iron Ingot
0 1 Stick
0 2 Iron Ingot
1 0 Iron Ingot
1 1 Redstone Torch
1 2 Iron Ingot
2 0 Iron Ingot
2 1 Stick
2 2 Iron Ingot

Directions:

  • DO NOT add new import statements.
  • DO NOT add any new class attributes
  • DO NOT change any of the method’s signatures.
  • DO NOT modify the given constructor.

 

search [PROVIDED]

DO NOT change or update this method. This method does an existence check in the instance variable table to see if an item is present in the table, given the name. It calls the provided hash() function to get the index the item should go in, given its name (it assigns hash values based on the first letter of the item name, ex: A maps to 0). 

Then, it traverses the linked list rooted at that table to see if that item is present, and returns the item if it’s there or null otherwise. 

Use the search bar in the driver to search for an item; you’ll see a popup that shows whether or not the item is found.

put

In this method, you will be given an item name, recipe array (a 3×3 string array), and resulting item count. You’ll insert items if they don’t already exist, to the front of a list given hash table ordering rules.

  • Place the recipe array and resulting item count into a Recipe object using the Recipe constructor.
  • USE hash(itemName) to find the index you should insert at. (remember, it uses the first letter which differs from class. “Apple” goes to index 0, “Beacon” index 1). 
  • At that index, add an Item containing the recipe object and item name to the END of the linked list at that index ONLY IF that item doesn’t exist in the list – if you’re attempting to insert a duplicate, do nothing. 

The “Put All” button will add multiple items in an input file in one click – see putAllCraftableItems (provided). Here’s the result after putting all items in small_input.txt – hover over an item to see its name, click to view its recipe if one exists:

NOTE: IF the dropdowns don’t work for you, replace the driver with a new one from Autolab. This mostly affects Windows users.

delete

In this method, you’ll remove an item from the separate chaining table — the item could be anywhere within a list or not at all. Remember how we delete items in a singly linked list — you’ll have to apply the same logic to delete an item if it exists.

  • Use the provided hash function to find the index you should search for, given the item name. 
  • That gives you the corresponding index at which you should search: afterward, identify the item and then delete it if you found the item.
    • Recall the different cases for deletion: deleting from the front, middle, and end as well as the only node in the list. table[i] refers to the front of a linked list of nodes. 

Use the dropdown box to select the item you want to remove. The below image shows the result when attempting to remove “Diamond Helmet” after putting all items in small_input.txt:

NOTE: IF the dropdowns don’t work for you, replace the driver with a new one from Autolab. This mostly affects Windows users.

putAllCraftableItems [PROVIDED]

This method mainly is meant for the driver and Autolab, and puts all items from an input file into the table by calling put repeatedly on each item it reads. DO NOT CHANGE this method.

findUnknownRecipe [PROVIDED]

This method mainly is meant for the driver, and it finds the item’s recipe in an input file given its name. This lets you add a single item if you are trying to do so. DO NOT CHANGE this method.

Writing JUnit Tests

You do not have to submit this, this is for you to test your own code.

In the main project folder, there exists a “test” folder next to the “src” folder. This contains a JUnit test class, which can run and test pieces of your code. To compile and run these tests, you must install the Test Runner extension. See the Programming FAQ for more info on VScode extensions.

You must fill the insertion and deletion test in. Once you do, remove the fail() statements at the bottom and run. 

You are provided with a premade JUnit test class. You can finish writing the test methods, by using JUnit test methods (assertTrue(), assertFalse(), assertEquals()) in order to test your code.

If you’d like to use unit tests, you can:

  • Instantiate a new MinecraftSC object.
  • Call .put() repeatedly to add one or more items (use findUnknownRecipe to get the recipe given a name), OR call putAllCraftableItems on the MinecraftSC object.
  • Verify that the table has all items as intended. 
You can use findUnknownRecipe to find a recipe in an input file.

Tests not running? 

First, make sure you’re in the right folder and the tests are implemented. Next, if you have the “Code Runner for Java” or Oracle “Java” extension, make sure you uninstall those extensions. Remember that you must fill in the tests yourself.

VSCode Extensions

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

Importing VSCode Project

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

Executing and Debugging

  • Use the run option in VS Code to run this program – right click Driver.java and select Run Java.To use the terminal, run the following commands from the innermost folder named MinecraftSC: javac -d bin src/*.java and java -cp bin inventory.Driver 
  • NOTE: if you have MinecraftSC (2) -> MinecraftSC or CS112 -> MinecraftSC in VS Code, open the INNERMOST MinecraftSC through File -> Open Folder.
To run JUnit tests: right click test/MinecraftSCTest.java in VS Code and select Run Tests. 

Before submission

COMMENT all printing statements you have written from MinecraftSC.java.

Collaboration policy. Read our collaboration policy here.

Submitting the assignment. Submit MinecraftSC.java separately via the web submission system called Autolab. To do this, click the Labs and 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
  • Find head TAs office hours here
  • In addition to office hours we have the Coding and Social Lounge (CSL) , a community space staffed with community managers who are undergraduate students further along the CS major to answer questions.

By Kal Pandit