Skip to content

Instantly share code, notes, and snippets.

@joeladdison
Created August 26, 2014 03:27
Show Gist options
  • Save joeladdison/294e0a898697194429b9 to your computer and use it in GitHub Desktop.
Save joeladdison/294e0a898697194429b9 to your computer and use it in GitHub Desktop.
CSSE2310 - 2014 Assignment 1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Bounds of grid */
#define MIN_HEIGHT 2
#define MIN_WIDTH 2
#define MAX_HEIGHT 999
#define MAX_WIDTH 999
/* Exit status codes */
#define EXIT_GOOD 0
#define EXIT_USAGE 1
#define EXIT_DIMS 2
#define EXIT_FILE 3
#define EXIT_GRID 4
#define EXIT_END_INPUT 10
#define EXIT_COMPLETE 11
#define EXIT_NO_MOVES 12
/* Grid status */
#define STATUS_COMPLETE 1
#define STATUS_NO_MOVES 2
/* Other constants */
#define MAX_INPUT 79
/**
* Details for the current game
* - height: Height of the grid
* - width: Width of the grid
* - grid: The grid itself
* - border: The top and bottom border, stored for efficiency
* - workingHeight: Upper bound on area known to not be empty
* - workingWidth: Right bound on area known to not be empty
* The working area will shrink towards the bottom left corner,
* as this is how the collapsing happens.
*/
struct Game {
int height;
int width;
char **grid;
char *border;
int workingHeight;
int workingWidth;
};
/**
* Node for searching grid for matches
* - row: Row of position to check
* - col: Column of position to check
* - next: The next node in the list
*/
struct Node {
int row;
int col;
struct Node *next;
};
/**
* Free the malloc'd variables within the game struct.
* @param g Game struct
*/
void free_game(struct Game *g) {
int r;
if (g != NULL) {
if (g->grid != NULL) {
for (r = 0; r < g->height; ++r) {
free(g->grid[r]);
}
free(g->grid);
}
if (g->border != NULL) {
free(g->border);
}
free(g);
}
}
/**
* Exit the program with the provided code. Free memory as appropriate.
* @param g Game struct
* @param code The exit status to use.
*/
void exit_prog(struct Game *g, int code) {
/* Free memory for grid */
free_game(g);
switch(code) {
case EXIT_USAGE:
fprintf(stderr, "Usage: match height width filename\n");
exit(EXIT_USAGE);
case EXIT_DIMS:
fprintf(stderr, "Invalid grid dimensions\n");
exit(EXIT_DIMS);
case EXIT_FILE:
fprintf(stderr, "Invalid grid file\n");
exit(EXIT_FILE);
case EXIT_GRID:
fprintf(stderr, "Error reading grid contents\n");
exit(EXIT_GRID);
case EXIT_END_INPUT:
fprintf(stderr, "End of user input\n");
exit(EXIT_GOOD);
case EXIT_COMPLETE:
printf("Complete\n");
exit(EXIT_GOOD);
case EXIT_NO_MOVES:
printf("No moves left\n");
exit(EXIT_GOOD);
default:
break;
}
}
/**
* Parse the arguments given to the program and populate the game struct.
* @param g Game struct
* @param argv The arguments provided to the program.
*/
void parse_args(struct Game *g, char *argv[]) {
/* Temporary variables for use with strtol (arg parsing) */
char *inputEnd;
long tempNum;
tempNum = strtol(argv[1], &inputEnd, 10);
if (inputEnd == argv[1] || *inputEnd != '\0' ||
tempNum > MAX_HEIGHT || tempNum < MIN_HEIGHT) {
exit_prog(g, EXIT_DIMS);
}
g->height = (int) tempNum;
tempNum = strtol(argv[2], &inputEnd, 10);
if (inputEnd == argv[2] || *inputEnd != '\0' ||
tempNum > MAX_WIDTH || tempNum < MIN_WIDTH) {
exit_prog(g, EXIT_DIMS);
}
g->width = (int) tempNum;
/* Set working area to be entire grid */
g->workingHeight = -1;
g->workingWidth = g->width;
}
/**
* Read the grid file and store the contents to the grid array.
* Exit the program if the grid file is found to be invalid.
* @param g Game struct
* @param filename The path to the grid file.
*/
void read_grid(struct Game *g, char *filename) {
int i, j, c, failed = 0;
FILE *f = fopen(filename, "r");
if (f == NULL) {
exit_prog(g, EXIT_FILE);
}
/* Create the grid */
g->grid = malloc(sizeof(*g->grid) * g->height);
for (i = 0; i < g->height; ++i) {
g->grid[i] = malloc(sizeof(*g->grid[i]) * (g->width + 1));
}
/* Read in the grid */
for (i = 0; i < g->height; ++i) {
for (j = 0; j < g->width; ++j) {
c = fgetc(f);
if (c == EOF || c == '\n' || c == '\0') {
/* End of file reached unexpectedly, line too short or
invalid char */
failed = 1;
break;
}
g->grid[i][j] = (char) c;
}
if (failed || fgetc(f) != '\n') {
/* End of file reached unexpectedly, or line too long */
failed = 1;
break;
}
g->grid[i][j] = '\0';
}
if (failed || fgetc(f) != EOF) {
/* Additional lines in the grid file */
fclose(f);
exit_prog(g, EXIT_GRID);
}
fclose(f);
/* Generate top/bottom row */
g->border = malloc(sizeof(*g->border) * (g->width + 3));
g->border[0] = g->border[g->width + 1] = '+';
memset(g->border + 1, '-', g->width);
g->border[g->width + 2] = '\0';
}
/**
* Print the grid to the given stream. A border will be added to the grid.
* @param g Game struct
* @param stream The stream to print the grid to.
*/
void print_grid(struct Game *g, FILE *stream) {
int i;
/* Print top border */
fprintf(stream, "%s\n", g->border);
/* Print rows */
for (i = 0; i < g->height; ++i) {
fprintf(stream, "|%s|\n", g->grid[i]);
}
/* Print bottom border */
fprintf(stream, "%s\n", g->border);
fflush(stream);
}
/**
* Save the grid to a file. A border will be added to the grid.
* @param g Game struct
* @param filename The path to save the file to.
*/
void save_grid(struct Game *g, char *filename) {
FILE *f;
f = fopen(filename, "w");
if (f == NULL) {
fprintf(stderr, "Can not open file for write\n");
return;
}
print_grid(g, f);
fprintf(stderr, "Save complete\n");
fclose(f);
}
/**
* Check if a position is within the bounds of the grid.
* @param g Game struct
* @param row The row of the position.
* @param col The column of the position.
* @return 1 if inside grid bounds, 0 otherwise.
*/
int in_bounds(struct Game *g, int row, int col) {
return row < g->height && row >= 0 && col < g->width && col >= 0;
}
/**
* Check whether a move can occur at the given position.
* @param g Game struct
* @param row The row of the position.
* @param col The column of the position.
* @return 1 for valid move, 0 otherwise.
*/
int valid_move(struct Game *g, int row, int col) {
char c;
return (in_bounds(g, row, col) &&
(c = g->grid[row][col]) != '.' &&
((row - 1 >= 0 && g->grid[row - 1][col] == c) ||
(row + 1 < g->height && g->grid[row + 1][col] == c) ||
(col - 1 >= 0 && g->grid[row][col - 1] == c) ||
(col + 1 < g->width && g->grid[row][col + 1] == c)));
}
/**
* Create a node for use with finding matches within the grid.
* @param row A row of the grid.
* @param col A column of the grid.
* @return A new node with the row and column set.
*/
struct Node *create_node(int row, int col) {
struct Node *n = malloc(sizeof(*n));
n->row = row;
n->col = col;
n->next = NULL;
return n;
}
/**
* Update the grid, removing all matches found. If grid is updated,
* collapse the grid and then print it out.
* @param g Game struct
* @param row The row to start from.
* @param col The column to start from.
*/
void update_grid(struct Game *g, int row, int col) {
char c;
struct Node *n = NULL, *last = NULL, *temp = NULL;
int i = 0;
n = last = create_node(row, col);
c = g->grid[row][col];
/* Search for grid positions that match, and update them */
while (n != NULL) {
if (g->grid[n->row][n->col] != '.') {
for (i = -1; i < 2; i += 2) {
if (in_bounds(g, n->row + i, col) &&
g->grid[n->row + i][n->col] == c) {
last = last->next = create_node(n->row + i, n->col);
}
if (in_bounds(g, row, n->col + i) &&
g->grid[n->row][n->col + i] == c) {
last = last->next = create_node(n->row, n->col + i);
}
}
g->grid[n->row][n->col] = '.';
}
temp = n;
n = n->next;
free(temp);
}
}
/**
* Collapse columns within the grid. Move all completely empty columns within
* the grid to the right side of the grid.
* @param g Game struct
*/
void collapse_columns(struct Game *g) {
int r = 0, c = 0;
short *colStatus = calloc(g->workingWidth, sizeof(*colStatus));
int count = 0, nonEmpty = 0, empty = 0, nextCol = 0;
/* Find all completely empty columns */
for (c = 0; c < g->workingWidth; ++c) {
for (r = 0; r < g->height; ++r) {
if (g->grid[r][c] != '.') {
colStatus[c] = 1;
++nonEmpty;
break;
}
}
}
empty = g->workingWidth - nonEmpty;
/* Fill the empty columns with the contents of the non-empty colums */
for (c = 0; c < nonEmpty; ++c) {
if (count == 0 && colStatus[c] == 1) {
continue;
}
/* Find the next non-empty column to copy from */
while ((c + count) < g->workingWidth &&
colStatus[c + count] == 0) {
++count;
}
/* Move columns to the right */
for (r = 0, nextCol = c + count; r < g->height; ++r) {
g->grid[r][c] = g->grid[r][nextCol];
}
}
/* Move the collapsed columns to the end */
for (r = g->height - 1; empty > 0 && r > g->workingHeight; --r) {
memset(g->grid[r] + nonEmpty, '.', empty);
}
free(colStatus);
/* Store the new bounds for the area that is not empty */
g->workingWidth -= empty;
}
/**
* Collapse all of the rows within the grid. All partially empty rows will
* be collapsed towards the bottom of the grid.
* @param g Game struct
*/
void collapse_rows(struct Game *g) {
int r = 0, c = 0;
int count = 0, rowHeight = 0;
int upperBound = g->height - 1;
/* Collapse rows column by column */
for (c = 0; c < g->workingWidth; ++c) {
count = 0;
rowHeight = g->workingHeight;
/* Work from the bottom of the column to the top of the working box */
for (r = g->height - 1; r > g->workingHeight; --r) {
if (count == 0 && g->grid[r][c] != '.') {
continue;
} else if (r <= g->workingHeight + count) {
/* Fill in empty spaces */
g->grid[r][c] = '.';
continue;
}
/* Find the next non-empty row to copy from */
while ((r - count) > g->workingHeight &&
g->grid[(r - count)][c] == '.') {
++count;
}
if ((r - count) <= g->workingHeight) {
/* From this row up we just have dots */
g->grid[r][c] = '.';
rowHeight = r;
} else if (count > 0) {
/* Shift the chars to fill empty spaces */
g->grid[r][c] = g->grid[r - count][c];
}
}
if (rowHeight < upperBound) {
upperBound = rowHeight;
}
}
/* Store the new bounds for the area that is not empty */
g->workingHeight = upperBound;
}
/**
* Checks the status of the grid. If grid is complete or has no possible moves,
* exit the program with the appropriate status.
* @param g Game struct
* @param initial Whether this is the start of game check.
*/
void check_status(struct Game *g, int initial) {
int r = 0, c = 0;
int colBound = g->width - 1;
int status = STATUS_COMPLETE;
for (r = g->height - 1; r > g->workingHeight; --r) {
for (c = 0; c < g->workingWidth; ++c) {
if (g->grid[r][c] == '.') {
continue;
} else if (status == STATUS_COMPLETE) {
/* Not complete, as there is something other than a '.' */
status = STATUS_NO_MOVES;
}
if ((c < colBound && g->grid[r][c] == g->grid[r][c + 1]) ||
(r > 0 && g->grid[r][c] == g->grid[r - 1][c])) {
/* Two identical chars next to each other, so move possible */
return;
}
}
}
/* End of program, as grid complete or no moves left. */
if (!initial && status == STATUS_COMPLETE) {
exit_prog(g, EXIT_COMPLETE);
} else {
exit_prog(g, EXIT_NO_MOVES);
}
}
/**
* Play a game of match.
* @param g Game struct
*/
void play_game(struct Game *g) {
char input[MAX_INPUT + 2], *in;
int c, row, col, count, length, initial = 1;
print_grid(g, stdout);
while (1) {
/* Check the grid status */
check_status(g, initial);
initial = 0;
/* Print the prompt */
printf("> ");
fflush(stdout);
/* Read input */
in = fgets(input, MAX_INPUT + 2, stdin);
if (in == NULL) {
exit_prog(g, EXIT_END_INPUT);
}
length = strlen(input);
if (input[length - 1] != '\n') {
/* Consume remaining characters */
while ((c = fgetc(stdin)) != '\n' && c != EOF);
}
/* Remove newline character / ensure only MAX_INPUT chars in buffer */
input[length - 1] = '\0';
if (input[0] == 'w') {
/* Attempt to save grid */
save_grid(g, input + 1);
} else {
/* Attempt to make move */
count = sscanf(input, "%d %d", &row, &col);
if (count == 2 && valid_move(g, row, col)) {
update_grid(g, row, col);
collapse_columns(g);
collapse_rows(g);
print_grid(g, stdout);
}
}
}
}
int main(int argc, char *argv[]) {
struct Game *g = NULL;
if (argc != 4) {
exit_prog(g, EXIT_USAGE);
}
g = malloc(sizeof(*g));
g->grid = NULL;
g->border = NULL;
parse_args(g, argv);
read_grid(g, argv[3]);
play_game(g);
return EXIT_GOOD;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment