Assignment A4

Assignment A4#

NEW: Make sure you have the latest A4Compliance.jar. Its version is 1.10 and you can find the version of your A4Compliance.jar by looking at the first line of its output.

This assignment uses regular Java 23, and JUnit Jupiter 5.9.0. You may optionally import the Functional Java Standard Libraries. Do not import other libraries into your project. Your code may not:

• Explicitly throw exceptions.
• Use concurrency (if you do not know what that is, you will not be using it so long as you write the code on your own).
• Use reflection (if you do not know what that is, you will not be using it so long as you write the code on your own).

In everything you do, you must follow the Design Recipe. The minor adjustments to the Design Recipe for class definitions are available in Slides of Workshop 7B. Do not forget both the adjustments of the Design recipe for stateful (imperative) programs and iteration, covered in Week 6. To see roughly how this assignment will be marked, check out the Skeleton Rubric.

The deadline for registering to participate in code walks is Friday, 17 October 2025, 18:00. You need to do this in order for your assignment submission to get marked!

You still need to follow the Design Recipe for all class definitions. In particular, the (minor) adjustments to the Design Recipe for class definitions were covered in workshop 7B. However, for class methods (either instance or static ones) you only need to follow the design recipe for the definition of those methods listed in the sections below and any helper methods directly called by them. Besides, you do not need to come up with examples or write tests for methods whose name starts with "get", except if you have any sort of complicated logic in them. You may of course use them in your tests of other methods. Not following the Design Recipe means that you do not have to write documentation nor tests (at your own risk!) for those methods that do not fall into this category. However, you still have to write methods for which only a single design strategy applies (methods must only do ONE thing!!!), with some relaxations covered in the workshop slides. Do not write code that is overly complicated.

Formalities#

This assignment is submitted via GitLab.

Access to Your Repository#

To start your assignment, go to the GitLab repository of Assignment 4 and follow these steps:

1. Click the Fork button at the top right of the page.
2. Do not change the project name, that is, it must still be comp1110-2025s2-a4
3. If asked for a namespace, choose your university ID.
4. Do not change the project slug.
5. Make sure the visibility of the project (bottom of the page) is set to private.
6. Click the Fork project button at the bottom of the page.

To double check that we can access your assignment, make sure that:

• your assignment 4 project is reachable through the address https://gitlab.cecs.anu.edu.au/XXXXXXXX/comp1110-2025s2-a4 where XXXXXXXX is your uid in the format u1234567.
• your repository includes our marker bot (comp1110-2025-s2-marker) as a Maintainer member (click on Manage on the right side of your project page, then Members and you should see the marker bot in the list on the right).

Notebooks and Push Requirement#

You need to keep a notebook file as explained on the Git and Notebooks page. You need to commit and push the current state of your files:

• at the end of every session where you work on the assignment
• at least once per hour (our checks implement that no two pushes during sessions recorded in the notebook are more than 70 minutes apart).
• at least once per major part of the assignment (i.e. for this assignment, at least four times). You are absolutely free to commit and/or push more often than that.

You need to write informative commit messages, and informative notes for each session in your notebook, which describe what it is what you did for this particular commit or session, respectively.

Statement of Originality#

Your submission (and therefore your git repository) needs to include a signed statement of originality. This must be a text file named soo.txt. That file must contain the following text, with the placeholders [your name here] and [your UID here] replaced with your name and UID, respectively:

I declare that this work upholds the principles of academic
integrity, as defined in the University Academic Misconduct
Rule; is entirely my own work; is produced for the purposes
of this assessment task and has not been submitted for
assessment in any other context, except where authorised in
writing by the course convener; gives appropriate
acknowledgement of the ideas, scholarship and intellectual
property of others insofar as these have been used; in no part
involves copying, cheating, collusion, fabrication, plagiarism
or recycling.

I declare that I have not used any form of generative AI in
preparing this work.

I declare that I have the rights to use and submit any assets
included in this work.

[your name here]
[your UID here]

Files Summary#

Your repository must be accessible to us and must contain the following files in its root directory:

• notebook.yml - your Notebook
• soo.txt - your signed Statement of Originality

The source Java files of the assignment should be placed in the src/ directory, with a single class per Java source file. The tests should be written using JUnit, and placed in the tests/ directory, with one test class in tests/ per corresponding class in src/. You must have the classes and Java source files listed below in each section. You may also add additional helper source files/Java classes as you see fit. Finally, you may also add pure text files in your tests/ directory to support your tests.

Compliance Tests#

To assist you with all the formalities above and the required classes and methods defined in the following sections, use the A4Compliance.jar checker. Save the compliance checker to the same folder as your assignment and execute the following in the terminal to check your assignment: java -jar --enable-preview A4Compliance.jar .

The current version of the A4 compliance checker is 1.00. Always ensure that you have the latest version of it by verifying that the version displayed in the first output line matches the previously mentioned one.

Keep in mind that passing the compliance tests does not imply that you will get a good grade because the compliance checker does not evaluate the logic of your functions.

The compliance checker does not check the Distinction-Level Part (Parts 6 and 7).

Project Configuration and Running Programs#

We recommend that you use IntelliJ IDEA for this assignment. However, you do not have to. If you do, the standard settings that result from following the IntelliJ Project Setup Guide should make your project work with our testing environment.

If you do not want to (or cannot) use IntelliJ IDEA, or if you want to make sure you can run your program like our automated testing framework, then you can follow the guide available here. This will allow you to trigger your tests directly from the console, in a similar way we did in the first half of the course with the functional Java library support for tests.

Info: Java Standard Libraries#

Part of this assignment asks you to do things for which there are operations in the Java Standard Libraries. Consider particularly looking at the following pages:

• Collections

Info: Functional Java Library#

If you wish to use the functional Java library, you will need to copy the Functional Java Jar File into a folder called library. For more details, see the IntelliJ Project Setup page.

Tasks#

As a general rule in this assignment, you do not need to come up with examples or write tests for methods whose name starts with get, except if you have some logic in them beyond just returning a field variable of the class. You may of course use them in your tests of other methods. We note that depending on how you decide to internally lay out data inside your class implementations, you may indeed have some get methods with some logic inside.

This assignment follows the theme of Assignment 3 but does not require its solution. This time, we will be developing tools to help game designers create dungeon quests. Dungeons are undirected graphs: vertices are locations and edges are corridors. The edges have non-negative weights associated to them representing the time to traverse them. We will also have an inventory of items that can help the players during their quest.

The representation of dungeon’s locations and corridors is based on the following two interfaces, respectively:

In src/Vertex.java

You cannot change this file

/**
 * Represents a vertex in an undirected graph, associated with some data.
 * Any implementation of this interface should override toString to return
 * the result of calling toString on its data value, in the format 
 * "Vertex Data=data". For example, if a vertex has as data the String "CSIT",
 * toString() should return the String "Vertex Data=CSIT".
 * If the data associated to a vertex is null, then the generated String should be
 * "Vertex Data=null".
 *
 * @param <T> the type of data stored in the vertex
 * @param <L> the type of labels used on incident edges
 */
public interface Vertex<T, L> {
  /**
   * @return the edges incident to this vertex
   */
  Collection<Edge<T, L>> getIncidentEdges();

  /**
   * @return the data associated with the vertex
   */
  T getData();
}

In src/Edge.java

You cannot change this file

/**
 * Represents an undirected edge between two vertices with a label of some kind.
 * Any implementation of this interface should override toString to return
 * the result of calling toString on its label value concatenated with the edge's
 * weight, in the format "Edge Label=label Weight=weight". For example, if an edge
 * is labeled with the String "University Avenue" and its weight its the value 2,
 * toString() should return the String "Edge Label=University Avenue Weight=2".
 * If the label associated to an edge is null, then the generated String should be
 * "Edge Label=null Weight=weight".
 *
 * @param <T> the type of vertex data
 * @param <L> the type of this edge's label
 */
public interface Edge<T, L> {
  /**
   * @return a collection containing exactly the two endpoints (i.e. vertices) 
   * of this edge. That is, the returned collection must contain only 2 items.
   */
  Collection<Vertex<T, L>> getVertices();

  /**
   * @return the label value for the edge (may be used by policies; 
   *         see Part 3 below for more details)
   */
  L getLabel();

  /**
   * @return the non-negative weight (cost) of traversing the edge
   */
  int getWeight();
}

You cannot assume that the data stored in a Vertex uniquely identifies a vertex. That is, two different vertices may store the same data value (i.e., two data values for which the equals method returns true). The same applies to Edges and their labels.

Click here for more information about the Collection interface in the Java standard library.

Besides, a dungeon (undirected graph) is represented via the following interface:

In src/UndirectedGraph.java

You cannot change this file

/**
 * Represents an undirected graph as a collection of vertices and edges.
 *
 * @param <T> the type of vertex data
 * @param <L> the type of edge labels
 */
public interface UndirectedGraph<T, L> {
  /**
   * @return the vertices of the graph
   */
  Collection<Vertex<T, L>> getVertices();

  /**
   * @return the edges of the graph
   */
  Collection<Edge<T, L>> getEdges();
}

Part 1 – Modelling a Dungeon#

In the files src/DungeonVertex.java, src/DungeonEdge.java, and src/DungeonGraph.java (and possibly additional files for additional data types)

Design concrete classes that implement the three graph interfaces above for undirected graphs (i.e., Vertex, Edge, UndirectedGraph, respectively). Each of these concrete classes must also be generic and parameterised with <T, L>. They should have appropriately typed fields to represent the data. You may add convenient (helper) methods in your concrete classes but do NOT add abstract methods to the provided interfaces.

Additional requirements and hints:

• Vertex data may have the null value.
• Edge labels may have the null value. They also may have values of user-defined reference types that we will later specify (e.g., a terrain type or a door). In other words, they are not necessarily numbers or Strings.
• Edges are undirected. Represent each connection as a single Edge<T,L> object whose getVertices() returns exactly the two endpoints (i.e., vertices), and ensure each endpoint includes that edge in its getIncidentEdges().
• Edge weights are non-negative integers (they can be zero) representing the time to traverse the edge.
• You should carefully read the documentation of the interfaces above to better understand the expected behaviour of the methods and meaning of the generic parameters. For example, do not forget to overload toString for your Vertex and Edge interface implementations.

In order to be able to construct and populate instances of your DungeonGraph<T,L> concrete implementation, you also need to implement the following constructor and instance methods of DungeonGraph<T,L> (they are not additions to the interfaces):

public DungeonGraph();

/**
 * Adds a new vertex to the graph with given data value.
 * Returns the newly created vertex.
 */
public Vertex<T, L> addVertex(T data);

/**
 * Adds a new edge connecting vertices u and v to the graph, with given
 * weight and label. You can asume that both u and v are non-null. You
 * can also assume that u and v are different vertex instances (i.e., 
 * self-edges/self-loops are not allowed), and that they are already present in the
 * graph. If an edge that already connects u and v exists in the graph, this method 
 * should replace it. As a consequence, there cannot be duplicated edges in DungeonGraph.
 * Returns the newly created edge.
 */
public Edge<T, L> addEdge(Vertex<T, L> u, Vertex<T, L> v, int weight, L label);

Follow the Design Recipe!

Document any invariants and pre/postconditions you consider relevant for your concrete classes.

Part 2 – Computing Paths and their Costs#

To help our game designers to decide if the exit of a dungeon is reachable as well as to evaluate the cost of given paths in the dungeon, we will create a class Path. Implement the following constructor, instance methods, and static method for Path:

In the file src/Path.java

import java.util.List;
import java.util.Optional;

/**
 * Constructs a path from an ordered sequence of locations (vertices) in the given 
 * graph, i.e., the Vertex instances in the list must correspond to Vertex instances 
 * in the graph for the path to be considered a valid path. The list must contain at 
 * least one vertex. The ordered sequence  provided as first argument may or may not 
 * correspond to a path in the graph (i.e., path validity is not a pre-condition for the 
 * constructor). use isValid() to check for validity once the Path class has been 
 * instantiated.  
 *
 * @param vertices the ordered sequence of vertices (size ≥ 1)
 * @param graph    the undirected graph for which we want to determine
 *                 whether there is a path matching the sequence of vertices
 *                 given in the first argument
 */
public Path(List<Vertex<T, L>> vertices, UndirectedGraph<T, L> graph);

/**
 * @return true if and only if every consecutive pair of vertices in this 
 *         path appears as endpoints of some edge in the graph.
 *         A single-vertex path is valid (as far as the vertex is in the graph).
 */
public boolean isValid();

/**
 * @return the sum of the weights of edges traversed by this path in order.
 *         If the path is invalid, return -1. A single-vertex path has cost 0.
 */
public int cost();

/**
 * Returns a path from start to goal if one exists.
 * The path does not need to be optimal neither in the number
 * of edges nor the total traversal time. If no path exists, 
 * returns Optional.empty().
 *
 * @param graph the undirected graph
 * @param start the start vertex
 * @param goal  the goal vertex
 * @return an Optional containing a Path from start to goal, or empty if unreachable
 */
public static <T, L> Optional<Path<T, L>> computePath(
    UndirectedGraph<T, L> graph,
    Vertex<T, L> start,
    Vertex<T, L> goal);

Optional is the regular Java version of Maybe and you can read more about it here. See also the example in workshop demo 8a. Note that computePath must return a Path (optimal or not) if one exists or Optional.empty() if no path exists from start to goal.

Part 3 – Policies#

In this part, you will modify Part 2 to allow us introduce modifiers to the dungeon’s corridors. As good Object-Oriented programmers, we want to give our game designers a lot of freedom on how they can modify a dungeon’s base user requirements (e.g., easy, normal and hard mode) and design choices (e.g., required items to reach the exit).

In order to do this, we will consider the Inventory of a player, i.e., a set of items uniquely identified by their names that a given player carries while traversing the dungeon. A class to represent a player’s Inventory is already provided to you in the file src/Inventory.java. You may add instance methods to this class, but you cannot change the signature of the instance methods already provided.

The new bit in this part is the ability to perform inventory-aware traversal of edges via policies. A policy is an implementation of the interface TraversalPolicy (src/TraversalPolicy.java) and represents the different modifiers for a dungeon. These modifiers will allow our game designers to implement different difficulty modes for the same dungeon. In particular, the interface looks like (you cannot modify this file):

In src/TraversalPolicy.java

/**
 * Selects which edges may be traversed and with what cost, given an inventory.
 * Policies enable changing a dungeon in different ways and still reuse the same
 * pathfinding algorithm.
 *
 * @param <T> the type of vertex data
 * @param <L> the type of edge labels
 */
public interface TraversalPolicy<T, L> {
  boolean traversable(Edge<T, L> e, Inventory inv);
  int weight(Edge<T, L> e, Inventory inv);
}

Add the following methods in your Path class:

/**
 * Computes a path under a caller-provided traversal policy.
 * The policy determines which edges are traversable and their effective costs.
 * The path need not be optimal. If no policy-compliant path exists, return empty.
 *
 * @param graph  the undirected graph
 * @param start  the start vertex
 * @param goal   the goal vertex
 * @param policy the traversal policy to apply
 * @param inv    the inventory
 * @return an Optional containing a Path from start to goal, or empty if unreachable
 */
public static <T, L> Optional<Path<T, L>> computePath(
    UndirectedGraph<T, L> graph,
    Vertex<T, L> start,
    Vertex<T, L> goal,
    TraversalPolicy<T, L> policy,
    Inventory inv);

/**
 * @return true if and only if this path is policy-valid under the given inventory:
 * for every step, there exists at least one incident edge between
 * consecutive vertices that is traversable(policy, inv).
 */
public boolean isValid(TraversalPolicy<T, L> policy, Inventory inv);

/**
 * @return the policy-adjusted cost of this path, computed as the sum over
 * steps of policy.weight(chosenEdge, inv). If the path is not
 * policy-valid, you must return -1. A single-vertex path has cost 0.
 */
public int cost(TraversalPolicy<T, L> policy, Inventory inv);

Also, in src/TrivialPolicy.java, implement a simple “do nothing” policy, named TrivialPolicy. Such a policy allows all edges to be traversed and does not modify the edge costs. Do not add any constructor to TrivialPolicy. You can use TrivialPolicy and an empty Inventory to test your new methods against the methods from Part 2.

Part 4 – Terrains (Time-to-traversal Modifiers)#

In this part, we will design dungeons such that their corridors are associated a terrain. Terrains may increase the time required for a player to traverse a dungeon corridor, unless the player has a terrain-specific item in their inventory. Not all corridors have a terrain associated to them.

To give freedom to game designers, you need to create an interface Terrain that they can later implement to create terrains with different characteristics.

Here are some examples of terrains, associated time-to-traversal modifiers, and special items:

• The Swamp terrain, which increments the time to traverse a corridor by 2 units unless the player’s inventory has "SwampBoots".
• The Lava terrain, which increments the time to traverse a corridor by 4 units unless the player’s inventory has "FireCloak".
• The Water terrain, which increments the time to traverse a corridor by 3 units unless the player’s inventory has "Flippers".
• The Normal terrain, which does not modify the time to traverse a corridor regardless of the player’s inventory.

Recall that item names are case-sensitive (e.g., "SwampBoots" and "swampboots" are considered to be different items).

In the file src/Terrain.java, create the interface Terrain with the following methods (you cannot modify this file):

/**
 * @return the case-sensitive name of the item that avoids the penalty,
 * or Optional.empty() if no item can avoid it.
 */
Optional<String> requiredItem();

/**
 * @return the non-negative extra time penalty to add for traversing an 
 * edge with this terrain.
 */
int penalty();

In separated files, with one class per file, provide concrete implementations for the examples of terrain given above. In order to facilitate the construction of classes implementing the Terrain interface, design a class, TerrainFactory in src/TerrainFactory.java, with the following single static method:

/**
 * 
 * Creates an instance of a class implementing the Terrain
 * interface.
 * 
 * @param terrainName the name of the terrain to be created.
 *        Currently supported terrain names are "Swamp", "Lava", 
 *        "Water" and "Normal".
 * @return the instance of the class implementing the Terrain 
 *         interface corresponding to terrainName
 */ 
public static Terrain makeTerrain(String terrainName);

In the file src/TerrainPenaltyPolicy.java, design a class named TerrainPenaltyPolicy that implements the generic TraversalPolicy<T, L> interface, with the following behavior:

• traversable always returns true (this policy never blocks).
• weight adjusts an edge’s weight by adding a terrain penalty when the edge label represents a Terrain; otherwise it adds 0.

NEW: Do not add any constructor to TerrainPenaltyPolicy.

Design tests showing how different terrains and inventory items change the cost of a given path.

Part 5 – Doors (Traversable Modifiers)#

In this part, we will introduce doors to our dungeons. Doors can be opened if the player has the right key in their inventory. We will model this as a TraversalPolicy in which a player can only traverse a hallway marked as a door, regardless of the direction they are travelling, if the key specified in that hallway is present in the player’s inventory. In other words, the key is necessary to go through the door in both directions. Not all corridors have doors necessarily.

You are free to model Doors as you wish and the only requirement is that each Door knows the key needed to open it. Besides, the key must be of a type that can be added to the player’s inventory. Place your Door in the file src/Door.java

NEW: In src/Door.java, add the following static method to be used by our tests (you are also allowed to used it in your own tests):

/**
 * 
 * Creates an instance of Door that can only be opened if the
 * provided key name is in the player inventory.
 * 
 * @param keyName the name of the key that opens this door. Keys
          are inventory items therefore are **case-sensitive**.
 * @return the object representing the desired Door.
 */ 
public static Door makeDoor(String keyName);

Design a class named DoorPolicy in src/DoorPolicy.java that implements TraversalPolicy<T, L> and only allows a player to traverse a hallway marked as a door if they have the right key in their inventory. DoorPolicy must not change the time to traverse the hallway.

NEW: Do not add any constructor to DoorPolicy.

Provide tests showing how the presence of doors in the dungeon and the inventory items can affect to the validity of a path.

Part 6 – Combining Policies (Distinction-Level)#

Sometimes game designers want to combine different features of the game, for instance, terrains and doors. To represent that, create a new Policy called CombinedPolicy in the file src/CombinedPolicy.java, that applies multiple TraversalPolicys. The logic of CombinedPolicy is as follows:

• An edge is traversable if only if all policies say it is.
• The edge weight returned should be the maximum over all the policies.

Your CombinedPolicy class should also implement TraversalPolicy<T, L>.

NEW: Moreover, you need to provide the following constructor for CombinedPolicy: public CombinedPolicy(Collection<TraversalPolicy<T, L>> policies)

Design tests that show that composing TerrainPenaltyPolicy and DoorPolicy changes cost paths and validity as expected. To this end, you also need to think about how to model an edge’s label able to represent a corridor of a given terrain that has a door.

NEW: To this end, you also need to think about how to model an edge’s label able to represent a corridor that is either a terrain or has a door but not both at the same time.

Such a label should be able to be combined with both TerrainPenaltyPolicy and DoorPolicy without modifying the implementation of the latter two resulting from Part 4 and 5, respectively.

Part 7 – Adding Keys to Dungeon Locations (Distinction-Level)#

In this part, we will model dungeon quests in which the player needs to find the keys within the dungeon in order to open some or all doors in the dungeon. To help our game designers, you will implement a method to decide if a given quest is solvable or not.

In the file src/DungeonVertex.java, modify your concrete vertex class so that some vertices may carry an item that is picked up upon arrival. Since this is specific to your implementation, add the following public instance method to your vertex class (not to the Vertex interface):

public Optional<String> getItemName(); // empty if none; case-sensitive when present

On the other hand, in the file src/DungeonGraph.java, overload the addVertex method with the following method:

/**
 * Adds a new vertex to the graph with given data value, and item's name.
 * Returns the newly created vertex.
 */
public Vertex<T, L> addVertex(T data, String itemName);

Picking up an item:

• Happens when your algorithm arrives at a dungeon location,
• Is free, i.e., does not cost any time, and
• Adds the item to the player’s current inventory for subsequent traversals.

Add to your Path class (in src/Path.java) the following generic static method:

/**
 * Returns true if and only if the goal can be reached from start by using the items present
 * in the initial inventory and by collecting any keys found on locations along
 * the way. Doors are enforced via DoorPolicy (you may compose with terrain in your tests).
 */
public static <T, L> boolean isQuestSolvable(
    UndirectedGraph<T, L> graph,
    Vertex<T, L> start,
    Vertex<T, L> goal,
    Inventory initialInventory);

Note that we do not require you to return a path, instead, we only require to check if a path exists.

Make sure to test cases such as:

• Unsolvable without the required items on the dungeon.
• Solvable when an item is picked up before reaching a matching door.
• Different inventories leading to different results on the same dungeon.

Follow the Design Recipe!

Updates#