You will be given a list of coordinate strings for rooks on an arbitrarily large square chess board, and you need to determine whether any of the rooks can attack one another in the given configuration.
In the game of chess, rooks can move any number of spaces horizontally or vertically (up, down, left, or right). For example, the rook on the following board (denoted with a letter 'R') can move to any position marked with an asterisk (*), and no other positions:
Figure 1: The rook at position d3 can move to any square marked with an asterisk. see image.
Thus, on the following board, none of the rooks (denoted with the letter 'R') can attack one another:
Figure 2: A 4x4 board in which none of the rooks can attack one another. see image.
In contrast, on the following board, the rooks at c6 and h6 can attack one another:
Figure 3: An 8x8 board in which two of the rooks can attack one another. see image.
One standard notation for the location of a chess piece on an 8x8 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 rooks at positions a3, b1, c4, and d2.
Because you're 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 there's 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:
Converting these strings to their corresponding numeric coordinates is one of a few key algorithmic / mathemagical challenges you face in this assignment. You will have to write a function that does that for you.
To store rook coordinates, you must use the struct definition we have specified in SneakyRooks.h without any modifications. You must #include the header file in your SneakyRooks.c source file like so:
#include "SneakyRooks.h"
Note that the capitalization of SneakyRooks.h matters! Filenames are case sensitive in Linux, and that is of course the operating system we'll be using to test your code.
The struct you will use to hold rook coordinates is defined in SneakyRooks.h as follows:
typedef struct Coordinate
{
int col; // The column where this rook is located (1 through board width).
int row; // The row where this rook is located (1 through board height).
} Coordinate;
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 needn't 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 worst- case 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.
In the source file you submit, SneakyRooks.c, you must implement the following functions. You may implement any auxiliary functions you need to make these work, as well. Please be sure the spelling, capitalization, and return types of your functions match these prototypes exactly. Please do not include a main() function in your submission.
int allTheRooksAreSafe(char **rookStrings, int numRooks, int boardSize);
Description: Given an array of strings, each of which represents the location of a rook on a square boardSize boardSize chess board, return 1 if none of the rooks can attack one another. Otherwise, return 0. You must do this in O(numRooks + boardSize) time. Be sure to avoid memory leaks.
Parameter Restrictions: boardSize will be a positive integer describing both the length and width of the square board. (So, if boardSize = 8, then we have an 8 8 board.) rookStrings will be a non-NULL (but possibly empty) array of strings. Any strings within that array will be unique (there will be no repeats), and all of those strings are guaranteed to follow the format described above for valid coordinates on a boardSize boardSize board. numRooks will be a non-negative integer indicating the number of strings in the rookStrings array.
Output: This function should not print anything to the screen.
Runtime Requirement: This function's runtime must be no worse than O(numRooks + boardSize). For details, see Section 4, "Runtime Requirements" (above). Note that repeated calls to Cs built-in pow() function (or a home-brewed pow() function) would be ill-advised, because that function will not have an O(1) runtime. Instead, use Horners Rule when calculating multiple powers of the same base.
Returns: 1 if all the rooks are safe, 0 otherwise.
void parseCoordinateString(char *rookString, Coordinate *rookCoordinate);
Description: Parse through rookString to determine the numeric row and column where the given rook resides on the chess board, and populate rookCoordinate with that information. You may assume that rookString is non-NULL, and that it contains a valid coordinate string using the format described above in Section 2, "Chess Board Coordinates." You may assume that rookCoordinate is non-NULL and is a pointer to an existing Coordinate struct.
Returns: Nothing. This is a void function.
double difficultyRating(void);
Returns: A double indicating how difficult you found this assignment on a scale of 1.0 (ridiculously easy) through 5.0 (insanely difficult).
double hoursSpent(void);
Returns: A reasonable and realistic estimate (greater than zero) of the number of hours you spent on this assignment.