Spider-Verse – 98 course points -The purpose of this assignment is to practice your understanding of Undirected Graphs and Adjacency Lists. 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.

Spider-Verse – 98 course points

The purpose of this assignment is to practice your understanding of Undirected Graphs and Adjacency Lists.

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.

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

The assignment has two components:

Coding (95 points) submitted through Autolab.
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! ([email protected])
- You cannot resubmit reflections but you can edit your responses before the deadline by clicking the Google Form link, signing in with their netid, and selecting “Edit your response”

Overview

Welcome to the Spider-Verse!

In the Spider-Verse there are many different Dimensions and just as many Spider-People. As you would’ve guessed, with great power comes great responsibility and these Spiders are tasked with protecting their Dimension from any threat that may hurt anyone.

To help visualize the Spider-Verse, we can make a graph of all the different Dimensions, with some holding any number of Spiders and any number of anomalies. Anomalies are people (mainly villains) who have been sent to a different Dimension as the result of the mob boss named Kingpin running dangerous Particle Collider experiments in Dimension 1610.

Dimension 1610 is home to Miles Morales, one of the many Spider-men, and is also the source of the anomalies. We need to set them straight along with finding out some useful information about graphs along the way. In each method you will learn some backstory for the method, which will be implemented by you.

You DO NOT need to be familiar with Spider-Man or the Marvel Cinematic Universe in order to complete this assignment.

Implementation

Overview of Files

We provide one Java class for each of the tasks you need to complete. Update these files with your code for each task (see Implementation Notes).
We provide StdIn and StdOut.
We provide one input file for each task. You are free to edit them, as well as create new input files with the correct format to help test your code.

Implementation Notes

The structure of this assignment is quite different from the previous assignments.

DO NOT use static variables on your code.
In each given Java class, you will read from a given set of input files (passed in as command line arguments), and write to a given output file (passed in as a command line argument).
DO NOT change the names of any of the given Java files, or the project structure itself (do not change directory names or create new directories).
DO NOT remove the package statement from any of the given input files.
DO NOT use System.exit() in your code.
Unlike any previous assignment, YOU MAY (and should) create your own classes in the src/spiderman folder. YOU MAY import “java.util.*”, but DO NOT import anything else. Make sure any new classes have a package statement: package spiderman;
The classes that you create MAY NOT have spaces in their names.
In order to grade a problem, we run the corresponding Java class and verify the output file. This means you have full freedom in your project structure, as long as our provided classes output the correct answer to the correct output file. Take this opportunity to practice your project design skills, and write clean code that avoids redundancy.
DO NOT remove the package statement from the provided classes.

Using StdIn and StdOut

Use StdIn.setFile(fileName) to set the current input file you want to read from.
You can now use methods like StdIn.readInt(), StdIn.readString() and StdIn.readLine() to operate on the input file as if it was standard input.
The methods StdIn.readInt() and StdIn.readString() actually leave the newline character unread, so if you use StdIn.readLine() after one of these methods, it will read this character rather than the next line. If you want to read the next line with StdIn.readLine(), you will need to call StdIn.readLine() once to read the newline character and then again to read the next line. StdIn.readInt() and StdIn.readString() ignore spaces and newlines by default.
Use StdOut.setFile(fileName) to set the current output file you want to write to. It creates the file if it doesn’t already exist.
You can now use methods like StdOut.print() and StdOut.println() to operate on the output file as if it was standard output.

Autolab ignores empty lines and extra spaces that your output files may have.

Check out this SpiderVerse Video Guide! (Timestamps in Video Comments)

Files to be implemented by you:

1. Clusters.java

Kingpin is up to no good, and is making a Particle Collider to bridge the gap between the dimensions so he can find his lost wife and child. However, Kingpin is reckless, and his collider is merging all the dimensions towards his own in the form of a chain of dimensions stemming from his. This will destroy not only the dimension he, Miles, and yourself reside in, but will also destroy the other dimensions. To prevent Kingpin’s Collider from destroying the Spider-Verse, Miles has tasked you with exploring the dimensional connections, and determining where they may be linked. We will find which are connected by inserting into a separate chaining hash table, creating clusters of dimensions.

The dimensions that collide (this happens because of the hash function used) will be at the same cluster (same array index).

This Java class will take two command line arguments in the following order: a dimensions list input file name and an output file name.
The dimensions input file will be formatted as follows:
- The first line consists of three numbers, space-separated:
  - An integer a (the number of dimensions)
  - An integer b (the initial size of the hash table prior to rehashing)
  - A double c (the capacity or threshold used to determine when to rehash the hash table)
- a lines, each with
  - The dimension number (an integer)
  - The number of canon events (an integer)
  - The dimension weight (an integer)

To complete this task, you will:

1) Create a separate-chaining hash table to represent clusters. The initial size of the table is b, but this size will change later.

Our goal is to insert each dimension into the cluster hash table based on its hash function and our algorithm below. Then, we will use these clusters similar to an edge list to fill in our adjacency list later in Collider.java
The dimensions that collide will be at the same cluster (same hash table index).

2) For each of the a dimensions:

Add the dimension to the cluster table: the index of the list it will be placed in can be calculated by taking DimensionNumber % TableSize. When inserting items into their table index, add to the front of the list.
IF the current load of the cluster table (dimensions added so far / number of clusters so far) meets or exceeds the dimension threshold c, you need to rehash to prevent the Collider and Kingpin from destroying the Spider-Verse!
1. The size of the cluster table is doubled to accommodate the increase in dimensions.
2. Because we are rehashing the table, items must be re-indexed to your new list according to the new list size.
Once the cluster table is finished, you and Miles need to ensure that these dimensions are connected between different clusters:
1. For every cluster in the table, you will take the first dimension of the previous two clusters, and add them to the end of the current cluster.
2. For the first two clusters, their “previous” clusters wrap around to the end of the list.

The following two diagrams show Step 1 and Step 2 of the algorithm above. This shows the cluster table after each rehash (4 rehashes, blank line separating them), and each cluster has x cluster indices.

The following diagram shows examples of the algorithm from Step 3 being applied to different dimensions.

Output file format for clusters.out is as follows:

n lines containing the first dimension of each cluster followed by all other dimensions in order, space separated

Compile command: javac -d bin src/spiderman/*.java

Run command: java -cp bin spiderman.Clusters dimension.in clusters.out

Below is the expected output for Clusters.java when running with arguments “dimension.in clusters.out”

Submit the entire SpiderVerse directory with Clusters.java implemented under Early Submission to receive extra credit (see “Zipping the directory for submission” below).

DO NOT submit only Clusters.java to Autolab.

2. Collider.java

With the dimensional connections mapped out via our separate chaining hash table, we can use this to create a final Adjacency List in order to more efficiently navigate the Spider-Verse and track down anomalies.

This Java class will take three command line arguments in the following order: a dimensions list input file name, a spiderverse input file name, and an output file name.
The dimensions input file will be formatted the same as above.
The spiderverse input file will be formatted as follows:
- An integer d (the number of people in the file)
- d lines, each with
  - The dimension this person is currently at (an integer)
  - The name of the person (a String)
  - The dimensional signature of the person (an integer)

With the clusters being completed, you and Miles need to represent these connections between each Dimension as an adjacency list showing undirected links.

Let the first Dimension in a cluster be linked to every Dimension in its cluster and have a link going back to represent it being undirected. More formally, in the adjacency list there must exist an edge from first→ d and d → first for each dimension appearing in a cluster starting at first.
So edges exist from d1 → d2 and d2 → d1, d1 → d3 and d3 → d1, ………….. , d1 → dn and dn → d1 (where dn is the last dimension in the cluster)

2. Insert people from the Spiderverse input file into their corresponding dimensions. They belong to a dimension, they’re not connected via edges.

The output file will be formatted as follows:
- a lines, where each line starts with a dimension number, then lists all the dimensions linked to that dimension (space separated)
- The order in which you output the lines DOES NOT MATTER for grading.

Compile command: javac -d bin src/spiderman/*.java

Run command: java -cp bin spiderman.Collider dimension.in spiderverse.in collider.out

Below is one example of a correct “collider.out” file obtained from running the Collider.java file with the command line arguments “dimension.in” “spiderverse.in” and “collider.out” in that order.

Collider dimension.in spiderverse.in collider.out

3. TrackSpot.java

Gwen was tasked with stopping a villain known as The Spot, who has the power to jump across dimensions. Gwen got carried away spending time with Miles, and as a result, The Spot has jumped to a different unknown Dimension.

The Spot is trying to become stronger so he can defeat Miles and Gwen, and to do so he needs to find a Dimension with a Collider. Since he is still learning, The Spot can only naively use his powers to jump through dimensions. He does not know where a Collider may be, which results in a potentially long and sub-optimal route, as he jumps to the next immediate Dimension in the Dimensional Adjacency List. This means that his search path takes the form of a Depth First Search (DFS).

Once Gwen finds out The Spot has left the Dimension she is currently in, she uses an AI hologram named Lyla to track The Spot to his current Dimension.

This Java class will take four command line arguments in the following order: a dimension list input file name, a spiderverse input file name, a spot input file name and an output file name.
The dimension list input file and spiderverse input file will be formatted exactly as the ones from Collider.
The spot input file will be formatted as follows:

1 line containing the number for the initial dimension
1 line containing the number for the destination dimension

You will use the graph described by the Dimensional Adjacency List to recreate the route that Spot took from the initial dimension to get to the destination dimension via a depth-first search traversal.

Print the route that Spot takes to an output file:

The output file will be formatted as follows:
One line, listing the dimensional number of each dimension Spot has visited (space separated)
Here is the correct “trackspot.out” file obtained from running the TrackSpot.java file with the command line arguments “dimension.in”, “spiderverse.in”, “spot.in” and “trackspot.out” in that order.

4. CollectAnomalies.java

Because of Kingpin’s Collider experiments in Miles’ home dimension, anomalies are appearing in other Dimensions. An anomaly is someone who is in a Dimension that they do not belong to (in accordance with their dimensional signature and the Dimensions’ dimensional number).

The leader of the inter-dimensional Spider-Society, named Miguel O’Hara and known as Spider-man 2099, is trying to stop any anomalies who are wreaking havoc in the Dimensions they do not belong in. He believes it is his responsibility to protect these Dimensions, as enough damage from anomalies could cause the Dimension to cease to exist, or even the Spider-Verse as a whole.

For Miguel to accomplish his goal, he has created a hub in his home dimension, and recruits Spiders from other Dimensions to help him track down these anomalies, bring them back to the hub, and return them to their own Dimension.

This Java class will take four command line arguments in the following order: a dimension list input file name, a spiderverse input file name, a hub input file name and an output file name.
The dimension list input file and spiderverse input file will be formatted exactly as the ones from Collider.
The hub input file will be formatted as follows:
1 line, containing dimensional number of the starting hub

You and Miguel want to stop and bring in any anomalies you find, but are not sure which dimensions they may reside, or the best route to take. To solve this problem, you and Miguel have decided to use a Breadth First Search (BFS) to find the best routes which contain anomalies.

A Spider is someone whose Dimensional Signature matches the Dimension Number of where they are located.
An Anomaly is someone whose Dimensional Signature DOES NOT match the Dimension Number of where they are located.
- For this file, we will IGNORE Anomalies located at the hub.

Find the best route from the hub, to any anomaly, and back to the hub. You can do this for all anomalies in the Spider-Verse using BFS. If there is a Spider at that dimension with the anomaly, return ONLY the route going back to the hub (reverse of the route from hub –> anomaly). In both instances, the current Dimension of these anomalies and Spiders will be changed to the source where the hub is located to be sent back home in a later method. Recall that BFS finds the shortest path from a source vertex to every other vertex with respect to the number of edges (hops).

The output file will be formatted as follows:
e lines, listing the name of the anomaly collected and the name of the Spider who is at the same dimension (if one exists, space separated) followed by the dimensional number of each dimension in the route.
Here is one example of a correct “collected.out” file obtained from running the ColllectAnomalies.java file with the command line arguments “dimension.in”, “spiderverse.in”, “hub.in” and “collected.out” in that order.

Spiderverse.in

5. GoHomeMachine.java

With all of the anomalies collected and brought to the hub dimension, you are one step closer to fixing the mess Kingpin caused with the Collider. Now that you have them collected, Miguel wants to use a device called the Go Home Machine. Unlike when we were collecting the anomalies, this machine uses Dijkstra’s algorithm. With this Go Home Machine, we can identify each anomaly’s dimensional signature and use the sum of any two adjacent dimensions weights to find out how long it takes to travel between dimensions. With this additional info we can send the anomaly home as quickly as possible via the Go Home Machine.

While Miles was in the hub dimension, he was deemed as an anomaly. Thus, Miguel wanted to keep him there to prevent damage to the dimensional timelines. But Miles managed to escape and used the Go Home Machine to leave the hub. Miguel blames Gwen for this, and also sends her back to her own dimension.

This Java class will take five command line arguments in the following order: a dimension list input file name, a spiderverse input file name, a hub input file name, an anomalies input file name and an output file name.
The dimension list input file, spiderverse input file and hub input file will be formatted exactly as the ones from previous methods.
The anomalies input file will be formatted as follows:

An integer e (the number of anomalies in the file
e lines, each with
- The name of the anomaly which will go from the hub dimension to their home dimension
- The time allotted to return the anomaly home before a canon event is missed

A canon event is a critical point in a Spider’s history, which relies on certain events (often tragic) taking place. Anomalies can disrupt, and even break these canon events, putting the Spider-verse in danger. So, we need to get these anomalies home before the time allotted (if possible).

Remember, an anomaly is anyone whose Dimensional Signature DOES NOT match the Dimension Number of where they are currently located.

If the amount of time it takes to send the anomaly back home is greater than the time alotted, then the number of canon events will be decreased by one, signifying a canon event has been broken. To send these anomalies home:

BEFORE RUNNING GoHomeMachine: Run CollectAnomalies and make sure the current dimension of the Anomalies (and spiders, if applicable) are updated to the Hub before you run GoHomeMachine

Read each anomaly from the input file.
Use Dijkstra’s Algorithm to find the shortest path from the hub to every other Dimension. Each Dimension has a weight (given in the input file), and the weight of a connection between two adjacent Dimensions is the sum of both individual dimension weights.
For all anomalies:
1. If the hub dimension has the anomaly, remove them from the hub and add them home to their correct dimension (according to their dimensional signature).
2. If the time to get home is larger than the anomaly’s allotted time:
  1. Decrease canon events by 1 according to their Dimensional Signature and current canon events at that time.
    - NOTE: Canon event count will be ignored during grading, but must still exist and be updated.
  2. If dimension count is at or below 0, you should mark this dimension for deletion (for a later program).
  3. Getting this anomaly back home has unfortunately FAILED. This will be important when you create a report.
3. Otherwise, we were SUCCESSFUL in getting the anomaly home.

Dijkstra’s Algorithm finds the shortest path (minimal cost) from a source to every other vertex in a weighted graph. Here is pseudocode for Dijkstra’s Algorithm:

Here’s an example of the algorithm:

Algorithm

Create a report with your findings and write the report to an output file.

The output file will be formatted as follows:
e lines, each with

The number of canon events at that anomalies home Dimension after being returned
The name of the anomaly
SUCCESS or FAILED in relation to whether or not that anomaly made it back in time
The route the anomaly took to get home
Here is one example of a correct “report.out” file obtained from running the GoHomeMachine.java file with the command line arguments “dimension.in”, “spiderverse.in”, “hub.in”, “anomalies.in” and “report.out” in that order.

6. CHALLENGE: SaveMiles.java [0 points]

This file does NOT count towards your assignment grade.

After Miles’ escape and return home, Gwen wants to save him, and ends up going to Miles’ home Dimension (1610). There, she finds out that Miles is missing, and has actually been sent to the wrong Dimension. This is due to the fact that the spider which bit him and gave him superpowers is from Dimension 42, which overwrote Miles dimensional signature.

Gwen still plans on saving Miles, but since he is in a Dimension that never had a Spider-Man, there are many criminals and villains there left unchecked. Gwen contacts her group of Spider-friends, along with some new ones she has made along the way, and they gather at Miles’ home Dimension in preparation to travel to Dimension 42. To ensure no time is wasted, these Spiders make use of Dijkstras’ for maximum efficiency.

This Java class will take six command line arguments in the following order: a dimension list input file name, a spiderverse input file name, a hub input file name, an anomalies input file name, a meetup file name and an output file name.
The dimension list input file, spiderverse input file, hub input file and anomalies input file will be formatted exactly as the ones from previous methods.
The meetup input file will be formatted as follows:
- Same line:

An integer f (the number of Spiders in the file)
An integer g (the number of people being gathered)
An integer h (the time given for them to arrive)
An integer j (the Dimension they will gather at)
f lines, each with
- The name of the Spider

We need g Spiders who can make it to Dimension j within time h. Find out whether or not we can gather enough people to save Miles. To complete this task (complete ALL previous tasks before this):

Read all spiders from the input file
Use Dijkstra’s Algorithm starting from the gathering dimension in the input file.
For all spiders, investigate every dimension.
1. If the dimension has the spider, change their dimension to the meetup point and if their trip to their dimension is within time increase the number of people that can make it.

The output file will be formatted as follows:

One line, printing TRUE or FALSE: true if the number of people who can make the trip meets or exceeds the number of people needed, false otherwise.
Here is one example of a correct “rescue.out” file obtained from running the SaveMiles.java file with the command line arguments “dimension.in”, “spiderverse.in”, “hub.in”, “anomalies.in”, “meetup.in” and “rescue.out” in that order.

7. CHALLENGE: CanonEvent.java [0 points]

This file does NOT count towards your assignment grade.

Miguel, Miles and the Spider-society are trying their best to keep these dimensions from collapsing, but some cannot be saved. After some anomalies have been sent home, it’s possible they’ve already missed a canon event, causing a dimensional collapse.
This Java class will take six command line arguments in the following order: a dimension list input file name, a spiderverse input file name, a hub input file name, an anomalies input file name, a canon file name and an output file name.
The dimension list input file, spiderverse input file, hub input file and anomalies input file will be formatted exactly as the ones from previous methods.
The canon input file will be formatted as follows:

An integer f (the number of Dimension in the file)
f lines, each with:
- The Dimension number of the we will edit
- The number of canon events that will decrease at that Dimension

Previously, we sent anomalies home, and this may have their home dimension’s canon event count equal to zero or less. Along with reading in the Dimensions we are editing, these Dimensions may also be at risk (at or below zero). Make the necessary changes with this file and scan the Spider-Verse graph for any Dimensions that are to be deleted from the Dimensional Adjacency List that was crafted.
Any Dimension with a canon event count at or below zero will be marked for deletion, updating the links to show that Dimension is deleted. If a single Dimension is not connected to the Spider-Verse graph after a Dimension has been deleted then that single Dimension is deleted as well.
If the Spider-Verse graph results in a disconnected graph, the Spider-Verse will only be represented by the largest component (deemed by the number of Dimensions in the component) and the smaller component(s) will be deleted.
The output file will be formatted the same way as formatted from Collider.java output file for ”collider.out”.
Here is one example of a correct “deleted.out” file obtained from running the CanonEvent.java file with the command line arguments “dimension.in”, “spiderverse.in”, “hub.in”, “anomalies.in”, “canon.in” and “deleted.out” in that order.

canon.in

Helpful Java Classes

The following are some data structures which are automatically imported with “java.util.*” that can help make your code cleaner and more efficient. You are free to use (or not use) any of these, as well as any other class under “java.util.*”. These data structures do not have every method covered here, just some useful ones for this assignment. You can find more information about how to use these classes online.

ArrayList is an ordered array-like structure with no size limit, as it automatically resizes

You can initialize an empty ArrayList named “name” which holds objects of type “Type” with ArrayList name = new ArrayList<>();
For example, an ArrayList of integers named “arrList” is initialized with ArrayList arrList = new ArrayList<>();
You can add a new element of type “Type” to the end of your ArrayList in average case O(1) time with name.add(newElement);
You can get the element at some index of your ArrayList in O(1) time with name.get(index);
You can set some index to some new element in O(1) time with name.set(index, newElement);
You can check if the ArrayList contains some element (returns a boolean) in O(n) time with name.contains(element)

Queue implements a FIFO structure

You can initialize an empty Queue named “name” which holds objects of type “Type” with Queue name = new LinkedList<>();
For example, a Queue of integers named “q” is initialized with Queue q = new LinkedList<>();
You can add a new element of type “Type” to the back of your Queue in O(1) time with name.add(newElement);
You can get the element at the front of the Queue with name.peek()
You can get and delete the element at the front of the queue with name.remove()

HashMap is an unordered data structure which stores and retrieves key value pairs

You can initialize an empty HashMap named “name” that maps objects of type “Key” to objects of type “Value” with HashMap<Key, Value> name = new HashMap<>();
For example, a HashMap named “map” which maps strings to integers is initialized with HashMap<String, Integer> map = new HashMap<>();
You can add a new key value pair, or update an existing key with a new value in average case O(1) time with name.put(key, value);
You can check if the HashMap contains some key in average case O(1) time (returns a boolean) with name.containsKey(key)
You can check the value of some key in the HashMap in average case O(1) time with name.get(key)
You can iterate over all the keys in the HashMap with for (Key key : name.keySet()) where Key is the type of keys in the HashMap.

LinkedList is an ordered data structure

You can initialize an empty LinkedList named “name” which holds objects of type “Type” with LinkedList name = new LinkedList();
You can add an element to the end of your linked list with name.add(item); and to the front with name.addFirst(item).
You can get items using name.get(index), name.getFirst(), or name.getLast(), to get an item at a specific index, first index, or last index respectively.
name.remove() removes the first element from the list, name.remove(index); removes an item at a specific index.

VSCode Extensions

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

Importing VSCode Project

Download the zip file from Autolab Attachments.
Unzip the file by double clicking it.
Open VSCode
- Import the folder Spiderverse to a workspace through File > Open Folder

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 (general).
How to run the debugger on this assignment.
If you choose the Terminal, from Spiderverse directory/folder:
- to compile: javac -d bin src/spiderman/*.java
- to execute Clusters: java -cp bin spiderman.Clusters dimension.in clusters.out
- to execute Collider: java -cp bin spiderman.Collider dimension.in spiderverse.in collider.out
- to execute TrackSpot: java -cp bin spiderman.TrackSpot dimension.in spiderverse.in spot.in trackspot.out
- etc…

Zipping the directory for submission (READ THIS before submitting)

Video on how to zip the files.
Be careful when zipping the directory for submission.
Autolab is expecting the exact directory organization we provided to you.
Autolab is expecting the zip file to be named spiderverse.zip
All files that you have written MUST be in the Spiderverse/src/spiderman directory.

To zip the Spiderverse directory navigate to the parent directory:

zip -r spiderverse.zip Spiderverse

Inspect the zip by listing the files in zip without uncompressing it:

unzip -l spiderverse.zip

Your zip file MUST have the following structure:

Before submission

Collaboration policy. Read our collaboration policy here.

Submitting the assignment.

You will have to submit a zip file. See previous section on how to zip the directory.

Submit spiderverse.zip 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.

Edurite Writers