From 442a49ad5a48d417345959b903ae6a6d32d55759 Mon Sep 17 00:00:00 2001 From: Haidong Ji Date: Fri, 15 Apr 2022 15:51:30 -0500 Subject: Great C programming fun Excellent fundamentals and displine training, many tools and techniques exercises: gdb, emacs, valgrind, git --- 31_minesweeper/Makefile | 3 + 31_minesweeper/README | 80 +++++++++++ 31_minesweeper/grade.txt | 24 ++++ 31_minesweeper/minesweeper.c | 335 +++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 442 insertions(+) create mode 100644 31_minesweeper/Makefile create mode 100644 31_minesweeper/README create mode 100644 31_minesweeper/grade.txt create mode 100644 31_minesweeper/minesweeper.c (limited to '31_minesweeper') diff --git a/31_minesweeper/Makefile b/31_minesweeper/Makefile new file mode 100644 index 0000000..7c65731 --- /dev/null +++ b/31_minesweeper/Makefile @@ -0,0 +1,3 @@ +CCFLAGS=-Wall -pedantic -std=gnu99 -Werror -ggdb3 +minesweeper: minesweeper.c + gcc -o minesweeper $(CCFLAGS) minesweeper.c diff --git a/31_minesweeper/README b/31_minesweeper/README new file mode 100644 index 0000000..14b4bfa --- /dev/null +++ b/31_minesweeper/README @@ -0,0 +1,80 @@ + +********************************************************************* +** REMINDER: your programs MUST valgrind cleanly for full credit! ** +********************************************************************* + +For this problem, you will be completing a partially written +minesweeper game. This game will be played on a text interface +(not a GUI---we haven't learned anything about those). + +If you are not familiar with the game of minesweeper, you might +take a minute to read up about it on the internet, but you don't +need much game expertise to do this assignment. + +I have provided code for an almost working minesweeper, except +that I have deleted the code for 4 functions: + +board_t * makeBoard(int w, int h, int numMines) +int countMines(board_t * b, int x, int y) +int checkWin(board_t * b) +void freeBoard(board_t * b) + + +Your job is to implement each of these functions (which all have a +//WRITE ME comment to make them easy to find). A brief description +of each follows: + + + - makeBoard: this function should malloc and initialize a board_t + representing the board. The parameters specify the width + and height of the board, as well as the number of mines. + You will also need to call malloc (multiple times) + to allocate space for the 2D array "board". + This function should fill in all squares on the board with + UNKNOWN, then call addRandomMine an appropriate number of times + (i.e., numMines) to "randomly" place mines on the board. + Note that the fields of your board_t must be initailzed before + you call addRandomMine. + Also note that the mine generation is pseudo random and will not + change if you re-run the program multiple times with the same + parameters. + + Note that the layout of b->board should be such that it is indexed + b->board[y][x] + where y is between 0 and the height and x is between 0 and the width. + + - countMines: this funciton takes a board_t, and an (x,y) coordinate. + It should count the mines in the 8 squares around that (x,y) + coordinate, and return that count. Note that a mine may be + indicated by a square on the board either being HAS_MINE or + KNOWN_MINE. You can use the IS_MINE macro to test both cases: + IS_MINE(b->board[ny][nx]) + (where b is the board_t, and (nx,ny) are the coordinates you + want to check). Be careful not to go out of bounds of the array. + + - checkWin: this funciton takes a board_t and see if the game has + been won. The game is won when no squares are UNKNOWN. Return 0 + if the game has not been won, 1 if it has. + + - freeBoard: This function takes a board_t and frees all memory + associated with it (including the array inside of it). That is, + freeBoard should undo all the allocations made by a call to makeBoard. + +Note: You should NOT change any of the other provided functions! + + +Once you have these all working, you should have a playable game of +minesweeper. Note that there are a few differences in game play +from the "standard" game: + + - You select a square by entering its x (column) and y (row) coordinate. + The x coordinates are listed across the top and the y are listed + down the left side to reduce counting. + + - The game will automatically figure out the "obvious" squares: + both mines and non-mined spaces. It will reveal these too you + as soon as it considers them trivial to figure out. + + - You cannot manually mark a square that you suspect has a mine + +Once your code is complete, submit minesweeper.c diff --git a/31_minesweeper/grade.txt b/31_minesweeper/grade.txt new file mode 100644 index 0000000..b4cf79d --- /dev/null +++ b/31_minesweeper/grade.txt @@ -0,0 +1,24 @@ +Grading at Sun 19 Dec 2021 12:56:12 AM UTC +Attempting to compile minesweeper.c +################################################# +testcase1: +Your output is correct + - Valgrind was clean (no errors, no memory leaks) +valgrind was clean +################################################# +testcase2: +Your output is correct + - Valgrind was clean (no errors, no memory leaks) +valgrind was clean +################################################# +testcase3: +Your output is correct + - Valgrind was clean (no errors, no memory leaks) +valgrind was clean +################################################# +testcase4: +Your output is correct + - Valgrind was clean (no errors, no memory leaks) +valgrind was clean + +Overall Grade: A diff --git a/31_minesweeper/minesweeper.c b/31_minesweeper/minesweeper.c new file mode 100644 index 0000000..3ea9490 --- /dev/null +++ b/31_minesweeper/minesweeper.c @@ -0,0 +1,335 @@ +#include +#include +#include +#include + +#define CLICK_KNOWN_MINE -2 +#define CLICK_INVALID -1 +#define CLICK_CONTINUE 0 +#define CLICK_LOSE 1 + +#define KNOWN_MINE -3 +#define HAS_MINE -2 +#define UNKNOWN -1 + +#define IS_MINE(x) ((x) == HAS_MINE || (x) == KNOWN_MINE) + + +struct _board_t { + int ** board; + int width; + int height; + int totalMines; +}; + +typedef struct _board_t board_t; + +void addRandomMine(board_t * b) { + int x; + int y; + //we could have a board too small for the number + //of mines that we request. try w*h*10 times before + //we give up + int limit = b->width * b->height * 10; + do { + x = random() % b->width; + y = random() % b->height; + assert(limit > 0); + limit--; + } while(b->board[y][x] == HAS_MINE); + b->board[y][x] = HAS_MINE; +} + +board_t * makeBoard(int w, int h, int numMines) { + board_t * b = malloc(sizeof(board_t)); + b->width = w; + b->height = h; + b->totalMines = numMines; + + b->board = malloc(h*sizeof(int *)); + for (int i = 0; i < h; i++) { + b->board[i] = malloc(w * sizeof(int)); + } + + for (int i = 0; i < h; i++) { + for (int j = 0; j < w; j++) { + b->board[i][j] = UNKNOWN; + } + } + + for (int i = 0; i < numMines; i++) { + addRandomMine(b); + } + return b; +} + +void printBoard(board_t * b) { + int found = 0; + printf(" "); + for (int x = 0; x < b->width; x++) { + printf("%d",x/10); + } + printf("\n "); + for (int x = 0; x < b->width; x++) { + printf("%d",x%10); + } + printf("\n----"); + for (int x = 0; x < b->width; x++) { + printf("-"); + } + printf("\n"); + for (int y = 0; y < b->height; y++) { + printf("%2d: ", y %100); + for (int x = 0; x < b->width; x++) { + if (b->board[y][x] == KNOWN_MINE) { + printf("*"); + found++; + } + else if (b->board[y][x] < 0) { + printf("?"); + } + else if (b->board[y][x] == 0) { + printf(" "); + } + else { + printf("%d", b->board[y][x]); + } + } + printf("\n"); + } + printf("\n----"); + for (int x = 0; x < b->width; x++) { + printf("-"); + } + printf("\n"); + + printf(" "); + for (int x = 0; x < b->width; x++) { + printf("%d",x/10); + } + printf("\n "); + for (int x = 0; x < b->width; x++) { + printf("%d",x%10); + } + printf("\nFound %d of %d mines\n", found, b->totalMines); +} +int countMines(board_t * b, int x, int y) { + int count = 0; + + for (int i = -1; i < 2; i++) { + for (int j = -1; j < 2; j++) { + if (x + i >=0 && x+i <= b->width-1) { + if (y + j >=0 && y+j <= b->height-1) { + if (IS_MINE(b->board[y+j][x+i])){ + count++; + } + } + } + } + } + return count; +} +int click (board_t * b, int x, int y) { + if (x < 0 || x >= b->width || + y < 0 || y >= b->height) { + return CLICK_INVALID; + } + if (b->board[y][x] == KNOWN_MINE) { + return CLICK_KNOWN_MINE; + } + if (b->board[y][x] == HAS_MINE) { + return CLICK_LOSE; + } + if (b->board[y][x] != UNKNOWN) { + return CLICK_CONTINUE; + } + + b->board[y][x] = countMines(b,x,y); + return CLICK_CONTINUE; +} + +int checkWin(board_t * b) { + for (int i = 0; i < b->width; i++) { + for (int j = 0; j < b->height; j++) { + if (b->board[j][i] == UNKNOWN) { + return 0; + } + } + } + return 1; +} + +void freeBoard(board_t * b) { + for (int i = 0; i < b->height; i++) { + free(b->board[i]); + } + free(b->board); + free(b); +} + +int readInt(char ** linep, size_t * lineszp) { + if (getline (linep, lineszp, stdin) == -1) { + fprintf (stderr,"End of file from keyboard reading a number. Quitting\n"); + exit(EXIT_FAILURE); + } + char * endptr = NULL; + long int x = strtol (*linep, &endptr, 10); + if (endptr == *linep) { + fprintf (stderr,"You did not enter any valid number\n"); + printf ("Please try again\n"); + return readInt (linep, lineszp); + } + if (*endptr != '\n') { + fprintf( stderr, + "Input was not entirely a number (junk at end)\n"); + printf ("Please try again\n"); + return readInt (linep, lineszp); + } + if (x > INT_MAX) { + fprintf(stderr,"%ld is too big for an int!\n", x); + printf("Please try again\n"); + return readInt(linep, lineszp); + } + return x; +} + +void doReveal(board_t * b, int x, int y, int revealMines){ + for (int dy = -1; dy <=1 ; dy++) { + for (int dx = -1; dx <=1 ; dx++) { + int nx = x + dx; + int ny = y + dy; + if (nx >= 0 && nx < b->width && + ny >= 0 && ny < b->height) { + if (revealMines) { + assert(b->board[ny][nx] != UNKNOWN); + if (b->board[ny][nx] == HAS_MINE){ + b->board[ny][nx] = KNOWN_MINE; + } + } + else { + assert(b->board[ny][nx] != HAS_MINE); + if (b->board[ny][nx] == UNKNOWN) { + b->board[ny][nx] = countMines(b,nx,ny); + } + } + } + } + } +} + +int maybeReveal(board_t * b, int x, int y) { + int unknownSquares = 0; + int knownMines = 0; + for (int dy = -1; dy <=1 ; dy++) { + for (int dx = -1; dx <=1 ; dx++) { + int nx = x + dx; + int ny = y + dy; + if (nx >= 0 && nx < b->width && + ny >= 0 && ny < b->height) { + if (b->board[ny][nx] == UNKNOWN || + b->board[ny][nx] == HAS_MINE) { + unknownSquares++; + } + else if(b->board[ny][nx] == KNOWN_MINE) { + knownMines++; + } + } + } + } + assert(knownMines + unknownSquares >= b->board[y][x]); + assert(knownMines <= b->board[y][x]); + if (unknownSquares > 0) { + int revealMines = (knownMines + unknownSquares == + b->board[y][x]); + int allKnown = knownMines == b->board[y][x]; + if(revealMines || allKnown) { + assert(!revealMines || !allKnown); + doReveal(b,x,y, revealMines); + return 1; + } + } + return 0; +} +void determineKnownMines(board_t * b) { + int foundMore = 0; + for (int y = 0; y < b->height; y++) { + for (int x = 0; x < b->width; x++) { + if (b->board[y][x] >= 0) { + foundMore = maybeReveal(b,x,y) || foundMore; + } + } + } + if (foundMore) { + determineKnownMines(b); + } +} + +void revealMines(board_t * b) { + for (int y = 0; y < b->height; y++) { + for (int x = 0; x < b->width; x++) { + if (b->board[y][x] == HAS_MINE) { + b->board[y][x] = KNOWN_MINE; + } + } + } +} +int playTurn(board_t * b, char ** linep, size_t *lineszp) { + printf("Current board:\n"); + printBoard(b); + printf("x coordinate:\n"); + int x = readInt(linep, lineszp); + printf("y coordinate:\n"); + int y = readInt(linep, lineszp); + int result = click(b,x,y); + determineKnownMines(b); + if (result == CLICK_LOSE) { + printf("Oh no! That square had a mine. You lose!\n"); + revealMines(b); + printBoard(b); + return 1; + } + else if (result == CLICK_INVALID) { + printf("That is not a valid square, please try again\n"); + } + else if (result == CLICK_KNOWN_MINE) { + printf("You already know there is a mine there!\n"); + } + else if(checkWin(b)) { + printBoard(b); + printf("You win!\n"); + return 1; + } + return 0; +} + + +int main(int argc, char ** argv) { + if (argc != 4) { + fprintf(stderr,"Usage: minesweeper width height numMines\n"); + return EXIT_FAILURE; + } + int width = atoi(argv[1]); + int height = atoi(argv[2]); + int numMines = atoi(argv[3]); + if (width <= 0 || height <= 0 || numMines <= 0) { + fprintf(stderr, + "Width, height, and numMines must all be positive ints\n"); + return EXIT_FAILURE; + } + char * line = NULL; + size_t linesz = 0; + + do { + board_t * b = makeBoard (width, height, numMines); + int gameOver = 0; + while (!gameOver) { + gameOver = playTurn(b, &line, &linesz); + } + freeBoard(b); + do { + printf("Do you want to play again?\n"); + } while(getline(&line, &linesz, stdin) == -1); + } while(line[0] == 'Y' || line[0] == 'y'); + free(line); + return EXIT_SUCCESS; +} -- cgit v1.2.3