Assignment U5

Assignment U5#

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, or annotate methods with a throws clause, except where explicitly permitted
• Catch exceptions outside of the allowed pattern for reading/writing files (see Slides of Workshop 6B).
• 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).
• Interact with the environment outside of the file system operations described on the Slides of Workshop 6B.
• Write to or read from files other than described in the assignment.

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 6B To see roughly how this assignment will be marked, check out the Skeleton Rubric.

You still need to follow the Design Recipe and write appropriate documentation and tests. In particular, the (minor) adjustments to the Design Recipe for class definitions were covered in workshop 6B. Do not write code that is overly complicated.

Formalities#

This assignment is submitted via GitLab.

Access to Your Repository#

In order for us to be able to collect and mark it, you need to satisfy the following conditions:

• Your repository’s name must be comp1110-2025s1-u5 (exactly), placed directly in your user namespace (the default). That is, if your uid is u1234567, the address of your GitLab project should read as https://gitlab.cecs.anu.edu.au/u1234567/comp1110-2025s1-u5.
• Your repository must have our marker bot (comp1110-2025-s1-marker) added as a Maintainer.

You can achieve both these points by creating your project through forking our template repository and not changing the name, or by just using the correct name when creating the project and then manually adding the bot.

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 this 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 that 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 (remove the brackets!), 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 have the following structure:

• notebook.yml - your Notebook
• soo.txt - your signed Statement of Originality
• src - a folder containing your source files:
  • Vertex.java - the given interface for vertices
  • Edge.java - the given interface for edges
  • DirectedGraph.java - the given interface for graphs
  • MazeCell.java - containing part of your work for parts 1 and 2
  • Maze.java - containing part of your work for parts 1 and 2
  • GraphExplorer.java - containing your work for part 3
  • RotationMazeCell.java - containing part of your work for part 4
  • RotationMaze.java - containing part of your work for part 4
  • PathTranslator.java - containing part of your work for part 4
  • CostMazeCell.java - containing part of your work for part 5
  • CostMaze.java - containing part of your work for part 5
  • MinCostPath.java - containing part of your work for part 5
  • any additional files for other data types you created
• tests - a folder containing your test files:
  • separate your tests at least by parts of the assignment, but also possibly into more files

You may have additional files in src for additional classes, and additional files in tests for additional tests.

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.

Special Comment Requirement: Complexity#

Some methods you are required to implement for this assignment require you to analyse the worst-case time complexity of your code. Such a requirement is typically phrased as follows:

Analyse the worst-case time complexity of your implementation in terms of |V| as the number of vertices and |E| as the number of edges in the graph.

A prompt may include different variables, depending on the particular inputs. You may be given more variables than are needed to express the complexity of your method - if a particular variable does not factor into the worst-case bound, omit it.

Where you are required to analyse the worst-case time complexity of your code, do so and document your finding in the comments of your method, right below the design strategy. For example:

/**
 * Creates a new copy of the given list.
 * Examples:
 * - Given: []
 *   Expect: [] as a different object from given list
 * - Given: [1,2,3]
 *   Expect: [1,2,3] as a different object from given list
 * Strategy: Iteration
 * Time Complexity: O(n), where n is the size of the given list
 * @param list - the list of which to create a copy
 * @return a new copy of the given list
 */
public static <T> List<T> copyList(List<T> list) { ... }

Steep mark penalties apply if you omit the time complexity documentation where required.

Tasks#

As a 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 to decide to internally layout data inside your class implementations, you may indeed have some “get” methods with some logic inside.

We will be working with directed graphs, which should be based on the following interfaces:

In src/Vertex.java

/**
 * Represents a vertex in a graph, associated
 * with some data.
 * Any implementation of this interface should
 * override toString to return the result of
 * calling toString on its data value.
 * @implSpec Invariant: every edge returned by
 * getOutgoingEdges returns this vertex as its
 * "from" vertex. The outgoing edges and the
 * associated data never change.
 */
public interface Vertex<T,L> {
   /**
    * @return the edges that originate from this vertex
    * and point to some other vertex.
    */
   Collection<Edge<T,L>> getOutgoingEdges();

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

In src/Edge.java

/**
 * Represents an edge between two vertices
 * in a graph, with a Label value of some
 * kind.
 * Any implementation of this interface should
 * override toString to return the result of
 * calling toString on its label value.
 * @implSpec Invariant: the vertex returned
 * by getFrom contains this edge in its
 * outgoing edges. Neither result of getFrom,
 * getTo, or getLabel ever changes for the 
 * same edge.
 */
public interface Edge<T,L> {
   /**
    * @return the vertex from which the edge originates.
    */
   Vertex<T,L> getFrom();
   /**
    * @return the vertex to which the edge points.
    */
   Vertex<T,L> getTo();
   /**
    * @return the label value for the edge.
    */
   L getLabel();
}

In src/DirectedGraph.java

/**
 * Represents a graph as a collection
 * of vertices and edges. 
 * @implSpec Invariant: Edges in the graph
 * connect vertices contained in the graph,
 * and no two vertices or edges in the
 * graph are equal. Edges and Vertices
 * in a graph do not change.
 */
public interface DirectedGraph<T,L> {
   /**
    * @return the vertices of the graph
    */
   Collection<Vertex<T,L>> getVertices();
   /**
    * @return the edges of the graph
    */
   Collection<Edge<T,L>> getEdges();
}

You may not add additional abstract instance methods to these interfaces. You may add default methods, if appropriate.

Our primary application for this graphs exercise will be Mazes, which are encoded in files as follows:

• Each line contains the same number of characters, which is always an odd number greater than or equal to 3
• Valid characters are:
  • ‘W’, indicating a wall
  • ‘S’, indicating the start position
  • ‘G’, indicating the goal position
  • ’ ‘, indicating a free path
• The first and last lines consist of all ‘W’s, and the first and last character of each line is a ‘W’, with the exception of one character in either the first or last line, or at the start or end of some line, which is an ‘S’
• Each row/line and column has a non-negative, 0-based index
• Where both the row and column index are even, the character is always ‘W’
• Where both the row and column index are odd, the character is never ‘W’
• ‘S’ must be in either the first or last line, or at the start or end of some row.
  • If it is in the first or last line, its column index must be odd
  • If it is at the start or end of some line, its row index must be odd
• ‘G’ can only occur where both the row and column index are odd
• There is exactly one occurrence of ‘S’ and exactly one occurence of ‘G’
• There is a newline character immediately in front of the end of the file.

An example file may look as follows:

WWWWWWWWW
W       W
W WWWWW W
W  GW   W
WWWWW W W
S     W W
WWWWWWWWW

Part 1#

In the files src/MazeCell.java and src/Maze.java (and possibly additional files for additional data types)

Part 1 is a regular part of the assignment and will be included in marking it. However, it is designed as an on-ramp. Tutors may help you with the code here if you ask for help - though you should still try to do as much as possible yourself.

Design a class that represents a cell in the maze, which is a location that corresponds to an odd row and column position in the above file format, or a special virtual start cell.

Cells represent locations in the maze where someone navigating it may make a turn. Cells may have neighbours, which are cells with coordinates that are equal in one dimension, and have a difference of exactly 2 in the other dimension, provided there is no wall between them. One special neighbour is the virtual start cell, which is a neighbour of whatever cell is directly adjacent to the “S” in the maze encoding.

It should have at least the following members:

/**
 * Returns the neighbouring maze cell that is above this cell,
 * if it exists
 * @return the MazeCell above this cell, or null if none exists
 */
public MazeCell getUpNeighbour()
/**
 * Returns the neighbouring maze cell that is below this cell,
 * if it exists
 * @return the MazeCell below this cell, or null if none exists
 */
public MazeCell getDownNeighbour()
/**
 * Returns the neighbouring maze cell that is to the left of
 * this cell, if it exists
 * @return the MazeCell left of this cell, or null if none exists
 */
public MazeCell getLeftNeighbour()
/**
 * Returns the neighbouring maze cell that is to the right of
 * this cell, if it exists
 * @return the MazeCell right of this cell, or null if none exists
 */
public MazeCell getRightNeighbour()
/**
 * Returns the coordinates of this cell within the maze.
 * The components of the coordinate are always positive odd numbers,
 * except for the special starting cell, where one component is even.
 * @return the coordinates of this cell
 */
public |C| getCoordinates()

The coordinates of the cell should be represented with a type |C|, which should have the following members:

/**
 * Returns the row index of the coordinate
 * @return the row index of the coordinate
 */
public int getRow()

/**
 * Returns the column index of the coordinate
 * @return the column index of the coordinate
 */
public int getColumn()

MazeCell should implement the Vertex interface, where getData returns the coordinates of the cell, just like getCoordinates does, and there should be an Edge from the cell to each of its neighbours that exist, labelled with the corresponding direction, expressed as some data type |D|, which, when toString is called, returns the “UP”, “DOWN”, “LEFT”, or “RIGHT”, as appropriate for the direction.

Based on the above types, design a class Maze, implementing the DirectedGraph interface with MazeCells as vertices, and the edges created by their neighbour relations as edges. Besides the methods required by the interface, it must have at least the following members:

/**
 * @return the width of the maze in characters, i.e.
 *         [number of cells in a row]*2 + 1
 */
public int getWidth()
/**
 * @return the height of the maze in characters, i.e.
 *         [number of cells in a column]*2 + 1
 */
public int getHeight()

/**
 * Returns the cell with the given coordinates.
 * row/column are always odd and within bounds,
 * i.e. the starting cell cannot be returned
 * by this method.
 * @param row - the row of the cell, >0, <height, odd
 * @param column - the column of the cell, >0, <width, odd
 * @return the cell at the given coorinates
 */
public MazeCell getCell(int row, int column)

/**
 * Returns the special starting cell of the maze
 * @return the starting cell of the maze
 */
public MazeCell getStart()

/**
 * Returns the goal cell of the maze
 * @return the goal cell of the maze
 */
public MazeCell getGoal()

/**
 * Parses a maze file and returns a new object representing the maze
 * @param file a path to an existing file containing
 *    well-fromed maze data as described in the assignment
 * @return The maze represented by the file
 */
public static Maze readMaze(File file)

Follow the Design Recipe! In particular, take care to write correct invariants about all the types you are defining here, and corresponding pre/postconditions, i.e. how do the values of their various fields and thus the return values of various methods relate to each other?

Part 2#

In the files src/MazeCell.java and src/Maze.java (and possibly additional files for additional data types)

Implement equality reasoning for your graph data types by overriding the equals method and everying else that is needed:

• Coordinates |C| should be considered equal if both the row and column components are equal.
• Vertices should be considered equal if the data they carry is equal - for MazeCells, that means coordinates |C|.
• Edges should be considered equal if they point from equal vertices to equal vertices. Their label does not affect equality.
  • make sure that in all likelihood, to edges going in opposite directions between the same objects have different hash codes.
• Graphs should be considered equal if they contain equal vertices and edges.

Follow the Design recipe and Java’s requirements for overriding equals!

For each method that you write/override for this part, analyse the worst-case time complexity of your implementation in terms of |V| as the number of vertices and |E| as the number of edges in the graph. Do so following the instructions above.

Part 3#

In the file GraphExplorer.java

Since trees are essentially a restricted form of graphs, we can represent trees using our graph nodes. Write down a type definition for trees using graph nodes, following the Design Recipe, and use this definition in your human signatures where appropriate.

Design the class GraphExplorer. It must have at least the following members:

/**
 * Given a start vertex in an arbitrary graph, produces a tree
 * represented using graph nodes that contains a matching vertex
 * for every vertex reachable from the given one, via edges
 * equal to edges in the graph of the original vertex.
 * 
 * Analyse the worst-case time complexity of your implementation
 * in terms of |V| as the number of vertices, |E| as the number
 * of edges in the graph.
 */
public static <T, L> Vertex<T, L> computeDfsTree(Vertex<T, L> startVertex)

/**
 * Given two vertices in an tree, return the single path to
 * the given descendant node as a list of edges from
 * the root vertex to the goal vertex.
 * 
 * Analyse the worst-case time complexity of your implementation
 * in terms of |V| as the number of vertices, |E| as the number
 * of edges in the graph.
 * 
 * @param tree - the root node of a tree represented as graph nodes
 * @param goal - a descendant node of the above root node
 * @return A list of edges that form a path from the root
 *         to the goal
 */
public static <T, L> List<Edge<T, L>> computePathFromTree(
   Vertex<T, L> tree, Vertex<T, L> goal)

/**
 * Given two vertices in an arbitrary graph, return the the shortest
 * path (in number of edges), as a list of edges from
 * the start vertex to the goal vertex.
 * 
 * Analyse the worst-case time complexity of your implementation
 * in terms of |V| as the number of vertices, |E| as the number
 * of edges in the graph.
 * 
 * @param start - a vertex in a graph
 * @param goal - a vertex in the same graph as start, reachable
 *               via some number (possibly 0) of edges
 * @return A list of edges that form a path from the start
 *         to the goal
 */
public static <T, L> List<Edge<T, L>> computeShortestPath(
   Vertex<T, L> start, Vertex<T, L> goal)

/**
 * Given a list of Graphs and a pair of functions that for any given
 * Graph select a start vertex and a goal vertex, return a map
 * from graphs to the shortest paths (as lists of edges along
 * the path) from the start vertex to the goal vertex within them.
 * If two graphs in the list are equal, only the path for the first
 * graph in the should be calculated; any subsequent equal graph
 * should be skipped.
 * 
 * Analyse the worst-case time complexity of your implementation
 * in terms of |V| as the maximum number of vertices, |E| as the maximum 
 * number of edges in the graphs, |L| as the length of the list of graphs.
 * 
 * @param graphs - a list of graphs for which to find shortest paths
 * @param getStart - a function that, given a graph, selectes a start
 *                   vertex from it
 * @param getGoal - a function that, given a graph, selects a goal
 *                  vertex from it, which is reachable from the 
 *                  vertex that getStart selects
 * @return a map from Graphs to shortest paths between the selected
 *         start and goal nodes.
 */
public static <T, L> Map<DirectedGraph<T,L>, List<Edge<T,L>>> computePaths(
   List<DirectedGraph<T,L>> graphs, 
   Function<DirectedGraph<T,L>, Vertex<T,L>> getStart,
   Function<DirectedGraph<T,L>, Vertex<T,L>> getGoal)

Follow the Design recipe!

For each method that you write/override for this part, analyse the worst-case time complexity of your implementation in terms of |V| as the number of vertices and |E| as the number of edges in the graph. Do so following the instructions above.

Part 4 (Distinction-Level)#

In the files src/RotationMazeCell.java, src/RotationMaze.java, and src/PathTranslator.java (and possibly additional files for additional data types)

Design two new classes RotationMazeCell and RotationMaze, which work mostly like the original MazeCell and Maze. You should use the same direction type |D| as before, but may use a different coordinate type |Z|.

RotationMazeCell, RotationMaze, and |Z| should have the same methods as MazeCell, Maze, and |C|, respectively, except adjusted to use the three new types in the signatures (e.g. RotationMaze.readMaze(File file) returns a RotationMaze). Use as much abstraction as possible to limit the amount of duplicated code while respecting Liskov Substitutability.

The key difference is the notion of equality. Two mazes that only differ in being rotated by 90 degrees some number of times should be considered equal, and so the corresponding vertices that would match if the mazes were rotated to line up should be equal. Adjust all notions of equality involved here to make this true.

Design a class PathTranslator. It should have at least the following member:

/**
 * Translates a path of edges from one graph to
 * a path consisting of equal edges in an equal 
 * other graph.
 * 
 * Analyse the worst-case time complexity of your implementation
 * in terms of |V| as the number of vertices, |E| as the 
 * number of edges in the graphs, |P| as the length of the Path.
 * 
 * @param path a path through a graph
 * @param originalGraph the graph that contains 
 *   the edges of the given path
 * @param targetGraph a graph that is equal to
 *   originalGraph
 * @return a list of edges that represent the
 *   same path in targetGraph as the given path
 *   in originalGraph
 */
public static <T, L> List<Edge<T,L>> translatePath(
   List<Edge<T,L>> path,
   DirectedGraph<T,L> originalGraph,
   DirectedGraph<T,L> targetGraph)

For each method that you write/override for this part and which either specified here that you should analyse the worst-case time complexity of your function or did so in a previous part, do so following the instructions above.

Follow the Design Recipe!

Part 5 (Distinction-Level)#

In the files src/CostMazeCell.java and src/CostMaze.java, src/MinCostPath.java (and possibly additional files for additional data types)

Design two new classes CostMazeCell and CostMaze, which work mostly like the original MazeCell and Maze. You may use a different coordinate type |Y|, and edges now use Integer as the label type.

Edges are now labeled with costs, between 0 and 10. This changes the file format for mazes a bit, in that characters at row/column indices where one index is odd and the other is even can be one of ‘ ‘, ‘0’, ‘1’, ‘2’, … ‘9’, with ‘ ‘ standing for cost 10, and every decimal character standing for their respective cost value.

CostMazeCell, CostMaze, and |Y| should have the same methods as MazeCell, Maze, and |C|, respectively, except adjusted to use the three new types in the signatures (e.g. RotationMaze.readMaze(File file) returns a RotationMaze). Use as much abstraction as possible to limit the amount of duplicated code while respecting Liskov Substitutability.

The notion of equality for these paths should be the same as in Part 2.

Design a class MinCostPath. It should have at least the following member:

/**
 * Given two vertices in an arbitrary graph, return the the
 * minimum-cost path (sum of edge labels), as a list of edges from
 * the start vertex to the goal vertex.
 * 
 * Analyse the worst-case time complexity of your implementation
 * in terms of |V| as the number of vertices, |E| as the number
 * of edges in the graph.
 * 
 * @param start - a vertex in a graph
 * @param goal - a vertex in the same graph as start, reachable
 *               via some number (possibly 0) of edges
 * @return A list of edges that form a path from the start
 *         to the goal, whose label sum is the lowest of possible
 *         such paths
 */
public static <T> List<Edge<T, Integer>> computeMinCostPath(
   Vertex<T, Integer> start, Vertex<T, Integer> goal)

/**
 * Given a list of Graphs and a pair of functions that for any given
 * Graph select a start vertex and a goal vertex, return a map
 * from graphs to the minimum-cost paths (as lists of edge labels along
 * the path) from the start vertex to the goal vertex within them.
 * If two graphs in the list are equal, only the path for the first
 * graph in the should be calculated; any subsequent equal graph
 * should be skipped.
 * 
 * Analyse the worst-case time complexity of your implementation
 * in terms of |V| as the maximum number of vertices, |E| as the maximum 
 * number of edges in the graphs, |L| as the length of the list of graphs.
 * 
 * @param graphs - a list of graphs for which to find shortest paths
 * @param getStart - a function that, given a graph, selectes a start
 *                   vertex from it
 * @param getGoal - a function that, given a graph, selects a goal
 *                  vertex from it, which is reachable from the 
 *                  vertex that getStart selects
 * @return a map from Graphs to minimum cost paths between the selected
 *         start and goal nodes.
 */
public static <T> Map<DirectedGraph<T,Integer>, List<Edge<T, Integer>>> 
  computeMinCostPaths(
    List<DirectedGraph<T,Integer>> graphs, 
    Function<DirectedGraph<T,Integer>, Vertex<T,Integer>> getStart,
    Function<DirectedGraph<T,Integer>, Vertex<T,Integer>> getGoal)

For each method that you write/override for this part and which either specified here that you should analyse the worst-case time complexity of your function or did so in a previous part, do so following the instructions above.

Follow the Design Recipe!

Updates#