summaryrefslogtreecommitdiff
path: root/31_minesweeper
diff options
context:
space:
mode:
authorHaidong Ji2022-04-15 15:51:30 -0500
committerHaidong Ji2022-04-15 15:51:30 -0500
commit442a49ad5a48d417345959b903ae6a6d32d55759 (patch)
treec7127bb497e5e439018b1915e0136eec2c9cb124 /31_minesweeper
Great C programming funHEADmaster
Excellent fundamentals and displine training, many tools and techniques exercises: gdb, emacs, valgrind, git
Diffstat (limited to '31_minesweeper')
-rw-r--r--31_minesweeper/Makefile3
-rw-r--r--31_minesweeper/README80
-rw-r--r--31_minesweeper/grade.txt24
-rw-r--r--31_minesweeper/minesweeper.c335
4 files changed, 442 insertions, 0 deletions
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 <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+#include <limits.h>
+
+#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;
+}