CSSE2310 - 2014 Assignment 1

ass1.c

#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;
}