Skip to Main Content

Data Structures

Computer Science Department

Minecraft Linear Probing - 10 Course Points

The purpose of this lab is to learn how to implement a resizeable linear probing hash table. 

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. Players have an inventory that consists of 9 main slots as well as 27 more that are accessible through an inventory menu. You can have up to 64 of a single item in a slot. You don’t need any knowledge of the game in order to understand or complete this assignment. 

We’re creating an inventory system based on Minecraft that uses linear probing – the real game doesn’t actually use linear probing; it’s a fixed 4×9 array. In our implementation we’ll start with nine slots and then expand our inventory using resizing. We’ll also use rehashing and resizing to readjust our inventory and reduce unnecessary spaces. 

If you’ve played Minecraft before, here’s how this differs from real Minecraft:

  • We will not enforce the 64-item constraint per slot. In Minecraft, if you pick up an item and you have 64 of it, it’ll take up another spot. In our inventory, it’ll be added to the same spot.
  • We will use linear probing to resize the inventory and insert items, as opposed to simply having a 4×9 array. Normally, the last row of your inventory has the items you carry, with the first three rows accessible via a menu.
  • ALL items can stack (you can have multiple of an item in the same slot, with no upper bound). 
  • Not all items in the real game are included in the provided asset files, so unfortunately this doesn’t represent all possible items.  

Structure + Implementation

  • The Item class stores an item that would take up a slot: it has an item name and a count of how many items are in its corresponding slot. Don’t edit or submit.
  • The MinecraftLinearProbing class is where you’ll write your solution: it implements the inventory system using linear probing. Submit this to Autolab.
  • 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.

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.

 

Using the Driver

The driver provides you with an interactive menu through which you can modify your inventory. When you first open up the driver, it should look like this:

Use the buttons (the ones with up/down arrows) in the search and add/drop fields to select an item from the list of items. Then hit a button to confirm your action.

To drop an item, either click the item in its inventory to drop one item OR use the Add/Drop menu to drop one or more. If you have more than 18 items you might need to use the scrollbar to view all items.

If you receive a “STOP!” message, you may have opened the wrong folder in VSCode. Open up the MinecraftLinearProbing folder – the one that directly contains the bin, src, assets and lib folders. DO NOT open a CS112 folder that contains MinecraftLinearProbing, or a MinecraftLinearProbing folder that contains another. The driver WILL NOT WORK if you do this. 

If you’re having issues with the Minecraft font, uncheck the box in the top right. 

search [PROVIDED]

This method will search for an item in the table, given an item name. It uses the following hash function: Math.abs(itemName.hashCode()) % st.length. Remember that no duplicates are allowed.
 
You don’t need to modify this method – but it’s provided as an example of how to traverse a linear probing hash table. Note that this method WILL NOT WORK until you implement put. 

put

In this method, you’ll insert an item into the hash table st. Use the hash function in search to traverse through the hash table starting at the position it returns – ie. the value returned from Math.abs(itemName.hashCode()) % st.length. 

  • If the item exists, increment its count by the parameter count.
  • Otherwise, you would back out at the first empty index you see, and insert the item there by creating a new item containing the parameter name and count. YOU MAY need to wrap around the array to find an available space; the provided method search is an example of how to traverse.
  • Increase slotsFilled by 1 IF an item is inserted (not just a count being updated). Resize the array and double its size by calling resize() if the following load factor is met: (double) slotsFilled / table size >= 0.5. The provided loadFactor() method returns a double calculated by (double) slotsFilled / table size. 
This is the output after adding 1 Diamond, 3 Diamonds, 1 Diamond Axe, 1 Diamond Boots, 1 Diamond Chestplate and 1 Diamond Helmet in that order.

If you’re on Windows, it’s best to wait two seconds before hitting “add”, “drop” or “search” again as popups stay for about two seconds. 

resize [PROVIDED – DO NOT EDIT]

We’ll need to grow (or possibly decrease) our inventory, and we’ll do that by resizing the table. Here’s how we’ve implemented this:

  • Create a temporary MinecraftLinearProbing variable that has the capacity specified in parameters. 
  • For each item in the OLD hash table (start from index 0), call .put on the temporary table using the old item’s name and count. 
  • Once that’s done, reassign the instance variables st and slotsFilled by accessing the temporary table’s st and slotsFilled values.

rehash [PROVIDED – DO NOT EDIT]

This rehashes the table starting from index i until the first empty space past that index. The method wraps around the table to find the first empty space. It fixes item positions when we delete items – for instance, if we delete an item at index 4 and an item hashes to index 4, we’ll run into issues. 
 
This is used in the delete() method, so that items are fixed if we delete an item at a particular index.

delete 

Given a name and count, search the table to see if you have the item AND the count of items you’re deleting is less than or equal to the number you currently have. Remember, our hash function is Math.abs(itemName.hashCode()) % st.length. 

  • Decrement the item’s count by however many you’re deleting, IF the desired count to delete is less than or equal to what you currently have.
    • If the desired count to delete is GREATER than what you currently have, don’t do anything. If you’re attempting to delete 64 diamonds and you have 2 diamonds, do nothing. 
  • If after decrementing the count, you have zero of the target item:
    • Delete the item from the current index by setting the value at its index to null in the instance variable st.
    • Decrement slotsFilled by 1.
    • Call rehash on the index that comes after this item, to fix the table: (i + 1) % st.length.
    • If the current table length is greater than 9 AND slotsFilled / table size <= 0.25 (the table is at most 25% full), call the resize method to the table to half its current size (use integer division; round down). 
DO NOT decrease the table size if the table length is smaller than 9.
 
Using the example from before (insert 1 Diamond, 3 Diamond, 1 Diamond Axe, 1 Diamond Boots, 1 Diamond Chestplate and 1 Diamond Helmet in that order), here’s the output after deleting all four diamonds, one at a time, and then deleting a diamond chestplate:

If you’re on Windows, it’s best to wait two seconds before hitting “add”, “drop” or “search” again as popups stay for about two seconds. 

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 MinecraftLP object.
  • Call .put() repeatedly to add one or more items.
  • Verify that the table has all items as intended, and that the table resizes accordingly.
  • Call .delete() repeatedly after putting items. 

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 MinecraftLP.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 MinecraftLP: javac -d bin src/*.java and java -cp bin inventory.Driver 
  • NOTE: if you have MinecraftLP (2) -> MinecraftLP or CS112 -> MinecraftLP in VS Code, open the INNERMOST MinecraftLP through File -> Open Folder.
To run JUnit tests: right click test/MinecraftLPTest.java in VS Code and select Run Tests. 

Before submission

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

Collaboration policy. Read our collaboration policy here.

Submitting the assignment. Submit MinecraftLP.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