This is a warm-up assignment to get you thinking mathematically, algorithmically, and cleverly. It will encourage you to think in terms of implementing efficient solutions to problems, since your program needs to have a worst-case runtime that does not exceed O(m + n) (linear runtime). Its also a fairly gentle return to Java for those who havent used it in a while, and involves a direct application of the base conversion knowledge you gained in Computer Science 1 (albeit with a minor twist).

You might find this problem very tricky at first. Its important to struggle with it. Dont be discouraged if you dont solve it right away. Maybe walk away, take a break, and come back to it later (perhaps even the following day). You might be amazed by what your brain can do if you let it work on a problem in the background and/or if you come back to a problem well-rested, with a fresh perspective.

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.

Deliverables

SneakyQueens.java

Note! The capitalization and spelling of your filename matter!

Note! Code must be tested on Eustis, but submitted via Webcourses.

1. Problem Statement

You will be given a list of coordinate strings for queens on an arbitrarily large square chess board, and you need to determine whether any of the queens can attack one another in the given configuration.

In the game of chess, queens can move any number of spaces in any of eight directions: up, down, left, right, or any of four possible diagonal directions (up-left, up-right, down-left, or down-right). For example, the queen on the following board (denoted with a letter Q) can move to any position marked with an asterisk (*), and no other positions:

Figure 1: The queen at position d3 can move to any square marked with an asterisk.

Thus, on the following board, none of the queens (denoted with the letter Q) can attack one another:

Figure 2: A 44 board in which none of the queens can attack one another.

In contrast, on the following board, the queens at c6 and h6 can attack one another, as can the queens at f4 and h6:

Figure 3: An 88 board in which some of the queens can attack one another.

2. Coordinate System

One standard notation for the location of a chess piece on an 88 board is to give its column, followed by its row, as a single string with no spaces. In this coordinate system, columns are labeled a through h (from left to right), and rows to be numbered 1 through 8 (from bottom to top).

So, for example, the board in Figure 2 (above, on pg. 2) has queens at positions a3, b1, c4, and d2.

Because youre going to be dealing with much larger chess boards in this program, youll need some sort of notation that allows you to deal with boards that have more than the 26 columns we can denote with the letters a through z. Heres how that will work:

Columns will be labeled a through z (from left to right). After column z, the next 26 columns will be labeled aa through az. After column az, the next 26 columns will be labeled ba through bz, and so on. After column zz, the next 26 columns will be labeled aaa through aaz.

Essentially, the columns are given in a base 26 numbering scheme, where digits 1 through 26 are represented using a through z. However, this counting system is a bit jacked up since theres no character to represent the value zero. (Thats part of the fun.)

All the letters in these strings will be lowercase, and all the strings are guaranteed to be valid representations of board positions. They will not contain spaces or any other unexpected characters.

For example:

1. In the coordinate string a1, the a tells us the piece is in the first column (from the left), and the 1 tells us the piece is in the first row (from the bottom).
2. Similarly, the string z32 denotes a piece in the 26^th column (from the left) and 32^nd row (from the bottom).
3. The string aa19 represents a piece in the 27^th column (from the left) and 19^th row (from the bottom).
4. The string fancy58339 would represent a piece in the 2,768,999^th column (from the left) and the 58,339^th row (from the bottom). (However, as youll see below, 2,768,999 exceeds the maximum width of the chess boards youll be required to handle.)

Converting these strings to their corresponding numeric coordinates is one of a few key algorithmic / mathemagical challenges you face in this assignment. You might want to write a separate helper method that does that for you.

3. Runtime Requirements

In order to pass all test cases, the worst-case runtime of your solution cannot exceed O(m + n), where m is both the length and width of the square chess board, and n is the number of coordinate strings to be processed. This 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 the entire length of 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 worstcase runtime that your solution cannot exceed would be expressed as O(m + nk).

Note! O(m + n) is just another way of writing O(_MAX{m, n}), meaning that your runtime can be linear with respect to m or n whichever one happens to be the dominant term for any individual test case.

4. Method and Class Requirements

Implement the following methods in a class named SneakyQueens. Please note that they are all public and static. You may implement helper methods as you see fit.

public static boolean allTheQueensAreSafe(ArrayList<String> coordinateStrings, int boardSize)

Description: Given an ArrayList of coordinate strings representing the locations of the queens on a boardSize boardSize chess board, return true if none of the queens can attack one another. Otherwise, return false.

Parameter Restrictions: boardSize will be a positive integer, with boardSize 60,000, describing 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.

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.

5. Compiling and Testing SneakyQueens on Eustis (and the test-all.sh Script!)

Recall that your code must compile, run, and produce precisely the correct output on Eustis in order to receive full credit. Heres how to make that happen:

1. To compile your program with one of my test cases:

javac SneakyQueens.java TestCase01.java

2. To run this test case and redirect your output to a text file:

java TestCase01 > myoutput01.txt

3. To compare your programs output against the sample output file Ive provided for this test case:

diff myoutput01.txt sample_output/TestCase01-output.txt

If the contents of myoutput01.txt and TestCase01-output.txt are exactly the same, diff wont print anything to the screen. It will just look like this:

[email protected]:~$ diff myoutput01.txt sample_output/TestCase01-output.txt [email protected]:~$ _

Otherwise, if the files differ, diff will spit out some information about the lines that arent the same.

4. Ive also included a script, test-all.sh, that will compile and run all six test cases for you. You can run it on Eustis by placing it in a directory with java and all the test case files and typing:

bash test-all.sh