Problem Set 12 - Exceptions and I/O
Assigned: April 15, 2026
Due: April 22, 2026 at 11:59 PM EST
Assigned: April 15, 2026
Due: April 22, 2026 at 11:59 PM EST
Design classes with the given specification in each problem, along with the appropriate test suite. Each method in a class, excluding mutators, accessors, and constructors, must include proper Javadoc comments describing the (1) purpose of the method, (2) parameters, and (3) return value.
Do not round your solutions. For example, do not use
Math.round or float your output to, e.g.,
2 decimal places, unless specified.
You may not use anything beyond Chapter 5. This includes but is not limited to:
ArrayDeque/DequeSystem.arraycopy, Arrays.copyOf.seek().Any violation results in a score of 0 on the problem set.
Please contact a staff member if you are unsure as to whether you're allowed to use something.
Warning 1: This problem set involves file I/O and exceptions, and it is extremely easy to tell when a solution has been generated by an LLM. This is considered an academic integrity violation, and you will be reported. This is not to deter you from getting help - this is to ensure that you get help from a human, who can guide you through the problem set and help you learn, rather than an LLM, which will just give you the answer.
Seriously, just do your work honestly and ask us for help when you need it. You're on the last problem set - why risk it?
This is very important to read, and I will redirect anyone that asks questions about how to write unit tests for file I/O to this section!
The way to write unit tests involving file I/O is, unfortunately, not very straightforward.
Suppose we are testing a method called fact(int n, String outFile). This method
receives an integer \(n\) and the name of an output file. The
method will compute \(n!\) and write it out to the file of the
given name. Below are the steps for how to write one unit test:
fact001.exp, where .exp means “expected
output.” This file will contain what you expect your file to output. For example, suppose we
want to test fact(5, "fact001.out"). The generated output file
"fact001.out" would, therefore, contain 120.
class FactTest {
@Test
void testFact001() {
Fact.fact(5, "fact001.out");
}
}.exp extension) and the actual output file (denoted by the
.out extension). Read the lines into two separate lists.
class FactTester {
@Test
void testFact001() {
Fact.fact(5, "fact001.out");
List<String> expLines = ...; // Read from "fact001.exp"
List<String> actLines = ...; // Read from "fact001.out"
assertEquals(expLines, actLines);
}
}Again, I said that these are the steps for writing one unit test. You need to do these multiple times to write comprehensive tests. It might be helpful to break the logic into smaller methods so as to avoid duplicating logic. Do not get lazy and simply omit tests because you don't want to write them. If you do, you will lose a substantial number of points!
(15 points) Design the RowNumbering class, which contains one method: static void outputRowNumbering(String filename). When given a file name containing an extension that is not out, this method should create a new file of the same name with the out extension, where each line from the original file is prefaced with the line number containing padded zeroes.
For example, suppose a file test.in contains 473 lines of text. The generated output file should be named test.out, with its contents as follows:
001 ... 002 ... ... 471 ... 472 ... 473 ...
So, the number of leading zeroes of each line depends on what the line number is, as well as how many lines are in the original input file.
Files to Submit:RowNumbering.java, RowNumberingTest.java
(35 points) A stack-based programming language is one that uses a stack to keep track of variables, values, and the results of expressions. These types of languages have existed for several decades, and in this exercise you will implement such a language.
Design the StackLanguage class, whose constructor receives no parameters. The class contains two instance methods: void readFile(String f) and double interpret().
The readFile method reads a series of “stack commands” from the file. These can be stored however you feel necessary in the class, but you should not interpret anything in this method, nor should you throw any exceptions.
Hint: You may want to create a private static class to represent commands and their arguments.
The interpret method interprets the stored list of instructions. If no instructions have been received by a readFile command, throw an IllegalStateException. Here are the possible instructions:
DECL v X declares that v is a variable with value X.PUSH X pushes a number X to the stack.POP v pops the top-most number off the stack and stores it in a variable v. If v has not been declared, an IllegalArgumentException is thrown.PEEK v stores the value at the top of the stack in the variable v. If v has not been declared or the stack is empty, an IllegalArgumentException is thrown.ADD X adds X to the top-most number on the stack. If the stack is empty, throw an IllegalArgumentException.SUB X subtracts X from the top-most number on the stack. If the stack is empty, throw an IllegalArgumentException.XCHG v swaps the value on the top of the stack with the value stored in variable v. If v has not been declared as a variable or the stack is empty, an IllegalArgumentException is thrown.DUP duplicates the value at the top of the stack.If the command is none of these, throw an UnsupportedOperationException. You may assume that all commands, otherwise, are well-formed, i.e., all numbers are double values, they contain the correct number of arguments, and the types thereof are correct.
After interpreting all instructions, the value that is returned is the top-most value on the stack. If there is no such value, throw a NoSuchElementException.
Hint: Use a Map to associate variable names to values.
StackLanguage.java, StackLanguageTest.java
(30 points) A maze is a grid of cells, each of which is either open or blocked. We can move from one free cell to another if they are adjacent and non-diagonal.
The start of the maze is the top-left cell, and the goal is to move to the bottom-right. For example, below is a maze, and below that is an example of a solved maze.
.######## ........# #.###.### #...#...# ###.###.# #...#...# ###.#.### #...#...# #######..
*######## ******..# #.###*### #...#***# ###.###*# #...#***# ###.#*### #...#***# #######**
In this exercise, you will design a maze-solving program that can path-find its way through a maze.
Design the IMazeSolverStrategy interface, which contains the char[][] solve(char[][] maze) method. This interface represents a strategy for solving a maze.
In any implementation, the solve method should return a char[][] that represents the solution to the maze, where the path from the start to the end is marked with '*' characters. This method should not modify the input maze, and should return a new char[][] that contains the solution. If there is no solution, the method should return null.
Design the BacktrackingMazeSolver class, which implements the IMazeSolverStrategy interface using a backtracking algorithm:
Start at a cell and mark it as visited. Then, recursively try to move to each of its neighbors, marking the path with a '*' character. If you reach the maze exit, then return true. Otherwise, backtrack and try another path. By “backtrack,” we mean that you should remove the '*' character from the path. If you have tried all possible paths from a cell and none of them lead to the exit, then return false.
(20 extra credit points) Design the BfsMazeSolver class, which implements the IMazeSolverStrategy interface using a breadth-first search (BFS) algorithm.
Unfortunately, a breadth-first search approach is a bit more involved than the backtracking alternative, but where it loses in complexity it makes up for in its benefits: it always finds the shortest path for any maze and it is much, much, much faster!
Here's the algorithm at a high level: instantiate a queue \(Q\), a visited set of positions \(V\), and a map of positions to positions called "pred". Add the starting position, i.e., \((0, 0)\) to both \(Q\) and \(V\). While the \(Q\) is not empty, poll the next-available element off of the queue, which we will call \(e\). We now have a case analysis:
If \(e\) is not the maze exit, then we compute all four possible free neighbors of \(e\), and for each of the neighbors, if it has not been visited yet, add it to \(V\) and \(Q\). Additionally, add to the "pred" map \(\langle{V, e\rangle}\).
If \(e\) is at the maze exit, then we need to use the predecessor map to build the path.
In the backtracking algorithm, we simply visit the path and, if that leads to a dead end, undo the visit.
For the BFS algorithm, we have to be a bit smarter by keeping track of what cells, in what order, got us to the exit, hence the "pred" map, which stands for "predecessor."
It might be helpful to design the private buildSolutions method, which receives the predecessors map and returns a list of positions, in order, from the starting position to the exit.
Then, use this list to fill in the char[][] for the path.
Hint: In addition to the helper method that we suggest, you should also design a private and static class to represent positions in the maze, which can be used as elements in the visited set and keys/values in the predecessor map.
Note: In CSCI-C 343 (Data Structures), you'll learn more about how breadth-first search works, but at a high level, the idea is that you explore the maze in "layers," where you first explore all cells that are one step away from the starting position, then all cells that are two steps away, and so on. We can contrast this with another approach called "depth-first search", which explores the maze by going as deep as possible down one path before backtracking and trying another path. Consider the advantages and disadvantages of each approach!
Warning: Even if you don't complete the extra credit, you still need to submit a file called BfsMazeSolver.java with the class header. If you don't, your code will not compile in the autograder.
Now, design the MazeSolver class, which has the following methods:
MazeSolver(String fileName) is the constructor, which reads a description of a maze from a file. The file contains a grid of characters, where '.' represents an open cell and '#' represents a blocked cell. The file is formatted such that each line is the same length.
Read the data into a char[][] instance variable. Assume that the maze dimensions, i.e., the number of rows and the number of columns, are on the first line of the file, separated by a space.
Design the char[][] solveMaze(IMazeSolverStrategy strategy) method, which takes in a maze-solving strategy and returns the solution to the maze using that strategy. Note that this method should be one line of code: it should call the solve method of the given strategy, passing in the maze instance variable.
void output(String fileName, char[][] soln) outputs the given solution to the maze to a file specified by the parameter. Refer to the above description for the format of the output file and the input char[][] solution. (You should output the number of rows, followed by a space, followed by the number of columns, followed by a new line, then the maze grid with the solution marked.)
Note: For some added context, in this problem, we leveraged a design pattern called the "Strategy" pattern.
Files to Submit:IMazeSolverStrategy.java, MazeSolver.java, BacktrackingMazeSolver.java, BfsMazeSolver.java MazeSolverTest.java
(20 points) Design the SpellChecker class, which contain the static void spellCheck(String dict, String in) method. The spellCheck method reads two files: a "dictionary" and a content file. The content file contains a single sentence that may or may not have misspelled words. Your job is to check each word in the file and determine whether or not it is spelled correctly, according to the dictionary of line-separated words. If a word is not spelled correctly, wrap it inside brackets [].
Output the modified sentence to a file of the same name, just with the out extension. You must remove whatever extension existed previously. You may assume that words are space-separated and that no punctuation exists.
Assuming dictionary.txt contains a list of words, if we invoke the method with spellCheck("dictionary.txt", "file3a.in"), and file3a.in contains the following:
Hi hwo are you donig I am dioing jsut fine if I say so mysefl but I will aslo sya that I am throughlyy misssing puncutiation
Then file3a.out is generated containing the following:
Hi [hwo] are you [donig] I am [dioing] [jsut] fine if I say so [mysefl] but I will [aslo] [sya] that I am [throughlyy] [misssing] [puncutiation]
Hint 1: Use a Set!
Hint 2: Words differing only in case should not be considered misspelled; for example, "Hello" is spelled the same as "hello". How can your program check this?
Files to Submit:
SpellChecker.java, SpellCheckerTest.java