This problem is similar to SneakyQueens, but the solution requires a bit of a twist that will push you to employ your knowledge of data structures in clever ways. It has more restrictive runtime and space complexity requirements, as well: Your program needs to have an average-case / expected runtime complexity that does not exceed O(n) (where n is the number of knights), and a worst-case space complexity that does not exceed O(n).
The assignment also has a different board size restriction: The maximum board size is now Integer.MAX_VALUE Integer.MAX_VALUE.
Please feel free to seek out help in office hours if youre lost, and remember that its okay to have conceptual discussions with other students about this problem, as long as youre not sharing code (or pseudocode, which is practically the same thing). Just keep in mind that youll benefit more from this problem if you struggle with it a bit before discussing it with anyone else.
You will be given a list of coordinate strings for knights on an arbitrarily large square chess board, and you need to determine whether any of the knights can attack one another in the given configuration.
In the game of chess, knights can move two spaces vertically (up or down) and one space to the side (left or right), or they can move two spaces horizontally (left or right) and one space vertically (up or down). For example, the knight on the following board (denoted with a letter N, since the letter K is traditionally reserved for the king in formal chess notation systems) can move to any position marked with an asterisk (*), and no other positions:
Figure 1: The knight at position d3 can move to any square marked with an asterisk. see image.
Thus, on the following board, none of the knights (denoted with the letter N) can attack one another:
Figure 2: A 4x4 board in which none of the knights can attack one another. see image.
In contrast, on the following board, the knights at c6 and d8 can attack one another, as can the knights at c6 and d4:
Figure 3: An 8x8 board in which some of the knights can attack one another. see image.
This program uses the same coordinate system given in the SneakyQueens assignment.
In order to pass all test cases, the average-case / expected runtime of your solution cannot exceed O(n), and the worst-case space complexity cannot exceed O(n) (where n is the number of coordinate strings to be processed).
As with SneakyQueens, this O(n) figure assumes that the length of each coordinate string is bounded by some constant, which means you neednt account for that length in your runtime analysis, provided that each string is processed or examined only some small, constant number of times (e.g., once or twice). Equivalently, you may conceive of all the string lengths as being less than or equal to k, in which case the average-case runtime complexity and worst-case space complexity that your solution cannot exceed would be expressed as O(nk).
Implement the following methods in a class named SneakyKnights. Please note that they are all public and static. You may implement helper methods as you see fit.
public static boolean allTheKnightsAreSafe(ArrayList
Description: Given an ArrayList of coordinate strings representing the locations of the knights on a boardSize boardSize chess board, return true if none of the knights can attack one another. Otherwise, return false.
Parameter Restrictions: boardSize will be a positive integer less than or equal to Integer.MAX_VALUE. boardSize describes both the length and width of the square board. (So, if boardSize = 8, then we have an 8 8 board.) coordinateStrings will be non-null, and any strings within that ArrayList will follow the format described above for valid coordinates on a boardSize boardSize board. Each coordinate string in the ArrayList is guaranteed to be unique; the same coordinate string will never appear in the list more than once.
Output: This method should not print anything to the screen. Printing stray characters to the screen (including newline characters) is a leading cause of test case failure.
public static double difficultyRating()
Return a double indicating how difficult you found this assignment on a scale of 1.0 (ridiculously easy) through 5.0 (insanely difficult).
public static double hoursSpent()
Return an estimate (greater than zero) of the number of hours you spent on this assignment.