CS1027 ASSIGNMENT 2 Computer Science Fundamentals II This assignment is due on Thursday, March 4th, 2021 by 11:55pm. See the bottom of this document for submission details. Learning Outcomes To gain experience with • Solving problems with the stack data type • The design of algorithms in pseudocode and their implementations in Java • Handling exceptions Introduction Valentines Day is fast approaching, and the hero of our story, Cupid, is trying his best to spread some platonic love and friendship in these gloomy times. If you didn’t know, Cupid is an archer, and archers often prefer staying still and spending their time taking good shots with their bow. Cupid is no different in this regard, but he’s heard you’ve been learning about stacks and algorithm design and was wondering if you could help him simulate some scenarios so that he’s in tip-top shape (He hasn’t been getting out much with the pandemic). He also understands that your assignment isn’t due until the 4th of March, but he’s happy to have it for future years anyways. You are given a map that describes Cupid and the targets for his arrows, which is divided into rectangular cells to simplify the task of computing the required path. There are different types of map cells: • The starting point that Cupid wants to use • Map cells where the target is located, • Map cells indicating roadblocks or other barriers • Map cells containing pathways. There are 3 types of pathways: o Cross paths. A cross path located in cell L can be used to interconnect all the neighbouring map cells of L. A cell L has at most 4 neighbouring cells that we denote as the north, south, east, and west neighbours. The cross path can be used to interconnect all neighbours of L; o Vertical paths. A vertical path can be used to connect the north and south neighbours of a map cell; and o Horizontal paths. A horizontal path can be used to connect the east and west neighbours of a map cell. CS1027 ASSIGNMENT 2 Computer Science Fundamentals II Figure 1 shows an example of a map divided into cells. Each map cell has up to 4 neighbouring cells indexed from 0 to 3. Given a cell, the north neighbouring cell has index 0 and the remaining neighbouring cells are indexed in clockwise order. For example, in Figure 1 the neighbouring cells of cell 8 are indexed from 0 to 3 as follows: neighbour with index 0 is cell 1, neighbour with index 1 is cell 9, neighbour with index 2 is cell 13, and neighbour with index 3 is cell 7. Some cells have fewer than 4 neighbours and the indices of these neighbours might not be consecutive numbers; for example, cell 4 in Figure 1 has 2 neighbours indexed 1 and 2 (no 0 or 3 neighbours). A path from Cupid (cell number 12 in the figure) to a target (cell number 0) is the following: 12, 7, 2, 1, 0. A path from Cupid to another target (cell number 4) is the following: 12, 7, 2, 3, 4. Note that in some other maps, cells will be inaccessible because they are walls, or because the path is horizontal and the only way is vertical, or vice versa. Valid Paths When looking for a path the program must satisfy the following conditions: • The path can go from Cupid, a cross path cell, or a target cell to the following neighbouring cells: o A target cell, o A cross path cell, o The north cell or the south cell, if such a cell is a vertical path, or o The east cell or the west cell, if such a cell is a horizontal path. • The path can go from a vertical path cell to the following neighbouring cells: o The north cell or the south cell, if such a cell is either Cupid, a cross path cell, a target cell, or a vertical path cell. • The path can go from a horizontal path cell to the following neighbouring cells: o The east cell or the west cell, if such a cell is either Cupid, a cross path cell, a target cell, or a horizontal path cell. CS1027 ASSIGNMENT 2 Computer Science Fundamentals II Figure 1. A sample of one of Cupid’s maps represented as a grid of cells Limitation: If while looking for a path the program finds that from the current cell there are several choices as to which adjacent cell to use to continue the path, your program must select the next cell for the path in the following manner: CS1027 ASSIGNMENT 2 Computer Science Fundamentals II • An object in motion in motion will stay in motion unless acted on by an unbalanced force. The arrows will continue in the same direction they were heading if the path is available. • The program prefers a target cell over the other cells. • If there is no target cell adjacent to the current cell, then the program must prefer the cross path cell over the other cells; and • If there is no cross-path cell, then the program chooses the smallest indexed cell that • satisfies the conditions described above. • While Cupid’s arrows are magic, they are only so magical. The arrows Cupid uses can backtrack up to 3 times before they are unable to do so again. • Cupid’s arrows can only turn so much as well. Keep track of the inertia of the arrow by tracking how many times it has traveled in the same direction. After it has taken 3 steps in the same direction, it can no longer turn. For simplicity, it may take 2 steps and turn as many times as needed for the pathfinding. Note: The initial step required to pick a direction does not count for inertia. • Importantly, Cupid will only shoot an arrow down the same path once. • Cupid’s arrows should stop when they hit a target, and the stack should be popped until empty. • The distance Cupid can shoot an arrow is configurable and provided as an argument to the program. • Lastly, Cupid fires arrows one at a time. Provided files The following is a list of files provided to you for this assignment. You do not need alter these files in any way and should assume we will mark them with unmodified ones. Studying these will help improve your understanding of Java. • Map.java – This class represents the map of the neighbourhood, including Cupid’s starting location and the target houses. The public methods from this class you might use include: o Map (String inputFile) throws InvalidMapException, FileNotFoundException, IOException. This method reads the input file and displays the map on the screen. An InvalidMapException is thrown if the inputFile has the wrong format. o MapCell getStart(). Returns a MapCell object for the cell that Cupid starts in. o Int quiverSize(). Returns the number of targets that can fit in Cupid’s quiver. o Note: Lines 45-47 set the delay times for showing the path. You may wish to enable line 47 when testing many maps to have it go quicker. CS1027 ASSIGNMENT 2 Computer Science Fundamentals II • MapCell.java – This class represents the cells of the map. Objects of this class are created inside the class Map when its constructor reads the map file. The methods that you might use from this class are: o MapCell neighbourCell(int i) throws InvalidNeighbourIndexException. As explained in Section 1, each cell of the map has up to four neighbouring cells, indexed from 0 to 3. This method returns either a MapCell object representing the i-th neighbour of the current cell or null if such a neighbour does not exist. Remember that if a cell has fewer than 4 neighbouring cells, these neighbours do not necessarily need to appear at consecutive index values. So, it might be, for example, that this.getNeighbour(2) is null, but this.getNeighbour(i) for all other values of i are not null. An InvalidNeighbourIndexException exception is thrown if the value of the parameter i is negative or larger than 3. o boolean methods: isBlocked(), isCrossPath(), isVerticalPath(), isHorizontalPath(), isCupid(), isTarget(), return true if this MapCell object represents a cell corresponding to a blocked path, a cross path, a vertical path, a horizontal path, Cupid, or a target respectively. o boolean isMarked() returns true if this MapCell object represents a cell that has been marked as inStack or outOfStack. o void markInStack() marks this MapCell object as inStack. o void markOutStack() marks this MapCell object as outOfStack. • Other classes provided: o ArrayStackADT.java, CellColors.java, CellComponent.java, InvalidNeighbourIndexException.java, CellLayout.java, InvalidMapException.java, IllegalArgumentException.java. Classes to implement A description of the classes that you are required to implement for full marks in this assignment are given below. You may implement more classes if you want; you must submit the code for these with your assignment. CS1027 ASSIGNMENT 2 Computer Science Fundamentals II In all these classes, you may implement more private (helper) methods as desired, but you may not implement more public methods. You may not add static methods or instance variables. Penalties will be applied if you implement these. For this assignment, you may not use Java’s Stack class, although reading and understanding the code there may help you better understand stacks. You also may not use any other premade Java collections libraries. The data structure required for this assignment is an array, described below: ArrayStack.java This class implements a stack using an array. The header for this class must be this: public class ArrayStack implements ArrayStackADT This class will have the following private instance variables: • T[] stack. o This array stores the data items of the stack. • int top. o This variable stores the position of the last data item in the stack. In the constructor this variable must be initialized to -1, this means the stack is empty. o Note that this is different from the way in which the variable top is used in the lecture notes. This class will have the following public static variable: • public static String sequence; o Used for tracking the arrow path. This class needs to provide the following public methods: • ArrayStack() o Creates an empty stack. o The default initial capacity of the array used to store the items of the stack is 14 (for Valentine’s day) • ArrayStack(int initialCapacity). o Creates an empty stack using an array of length equal to the value of the parameter. • void push(T dataItem) CS1027 ASSIGNMENT 2 Computer Science Fundamentals II o Adds dataItem to the top of the stack. If the array storing the data items is full, you will increase its capacity as follows: ▪ If the capacity of the array is smaller than 50, then the capacity of the array will be increased by 10. ▪ Otherwise, the capacity of the array will increase by doubling the initial size. So, if, for example, the size of the array is 225 and the array is full, when a new item is added the size of the array will increase to 450. At the end of this method, add the following. This is used in TestSearch to make sure you are following a correct path: if (dataItem instanceof MapCell) { sequence += "push" + ((MapCell)dataItem).getIdentifier(); } else { sequence += "push" + dataItem.toString(); } • T pop() throws EmptyStackException o Removes and returns the data item at the top of the stack. An EmptyStackException is thrown if the stack is empty. o If after removing a data item from the stack the number of data items remaining is smaller than one fourth of the length of the array you need to shrink the size of the array by one half, to a minimum of 14; o To do this create a new array of size equal to half of the size (to a minimum of 14) of the original array and copy the data items there. o For example, if the stack is stored in an array of size 100 and it contains 25 data items, after performing a pop operation the stack will contain only 24 data items. Since 24