辅导案例-A4
CSE30, Fall 2019 A4: Life Check Point Due: Fri Nov 1, 2019 @ 11:59PM Final Assignment Due: Wed Nov 6, 2019 @ 11:59PM Please read over the entire assignment before starting to get a sense of what you will need to get done in the next week. REMEMBER: Everyone procrastinates but it is important to know what you are procrastinating and still leave yourself enough time to finish. This assignment must be run on ieng6. We are using custom libraries that are only available on ieng6 for this assignment. Go to the lab or ssh: You will not be able to compile or run the assignment otherwise. Table of Contents 1. Getting Started 2. The Game of Life 3. How the Program Works a. Arguments b. Interactive Commands c. The Input Files d. The boards_t Struct 4. Part 1: Checkpoint [Due Fri Nov 31 @ 11:59pm] 5. Part 2: Final Submission [Due Wed Nov 6 @11:59pm] 6. Submission, Style, and Grading Learning Goals ● Dynamic memory allocation and deallocation ● Array processing ● Structs and Pointers ● File I/O CSE30, Fall 2019 1. Getting Started We’ve provided you with a Makefile and starter code at this repo. You can either clone the repo or download the zip. (if you are sshing into ieng6, you can git clone in ssh.) 1. Clone or download the repo to get the starter code and README 2. Fill out the fields in the README before turning in 3. If you plan on using the Graphics mode while working remotely: ○ Windows - install MobaXterm and then ssh into ieng6. ○ Mac - Install XQuartz from a terminal window, ssh -X into ieng6. 1 ○ Linux - You already have it!! ssh -X into ieng6. Makefile: The Makefile provided will create a swlife executable from the source files provided. Compile it by typing make into the terminal. By default, it will run with warnings turned on. To compile without warnings, run make no_warnings instead. Run make clean to remove files generated by make . Starter Code: We have provided you with some starter code. There are a few initial config files that you can load into the program. The main function that handles optional/interactive commands is provided. You’ll notice that main calls many extern functions that are not defined in any of your .c files. We’ve included those functions as a library on ieng6. Solution Executable: We have also provided you with swLife_sol executable. You may run this executable to see what the expected output is. gdb: To run with gdb, the command is gdb [executable] to start gdb with your executable. r [arguments] will run your executable with [arguments] valgrind: to run with valgrind, the command is valgrind ./[executable] [arguments] 1 We have found that the X11 tunneling doesn’t always stay active so you might need to log out and log back in. For example, we have found that swLife -g will work and then fail to open the display sometime later. If you see this, log out and log back in to reestablish the X11 connection. CSE30, Fall 2019 2. The Game of Life Developed by John Conway, the Game of Life is a mathematical simulation of a simplified evolution process. The simulation occurs on a two-dimensional grid of cells over a series of discrete timesteps. At any given timestep, each cell will either be “alive” or “dead” (encoded as 1 and 0 respectively), and each cell’s value for the next timestep will be computed based on the current values of its 8 direct neighbors. The next-state rules are defined as follows: For an alive cell: If 0 or 1 neighbors are alive, it will die in the next timestep from loneliness. If 2 or 3 neighbors are alive, it will remain alive in the next timestep. If 4+ neighbors are alive, it will die in the next timestep from overpopulation. For a dead cell: If exactly 3 neighbors are alive, it will become alive in the next timestep. Otherwise, it will remain dead in the next timestep. See this site for an interactive example of the Game of Life. See the Wikipedia page on Example Patterns to see moving gifs of common patterns (toad, glider, etc). The original life algorithm assumes an infinite plane of cells. However, we are working with limited memory and will simplify the game by working with a finite board and assuming that all the board edges can never sustain life. For example, for a board of 100 x 200 cells, only the inner 98 x 198 active cells could potentially support life. Thus the boards you implement will schematically look like the figure below: CSE30, Fall 2019 3. How the Program Works ● This program loads an input file, defining the initial board layout of dead/alive cells. ● You are able to interactively step through the program to see how the board evolves through each timestep. ● It can also be run in both ASCII and graphical mode. ● All argument processing is handled by the provided main.c . Please do not edit main.c as we will be testing with our own copy of the file. See arguments and interactive commands below for details. Arguments Format for calling this executable with arguments: ./life filename [-g#] Arguments Description filename (required) The name of the input file to initialize the dead/alive cells of the array. See below for details on the format. -g# (optional) -g specifies the graphics option with a # scale factor. If -g is not specified, the game will print ASCII output to the terminal. If -g is specified, the game will show in a pop up window. Note: Graphics mode requires ssh-ing with ssh -X Interactive Commands After running the executable in either mode, interact with it by entering the following commands: Command Description s N Simulate N steps, displaying the intermediate results. Note: use of -g recommended as intermediate steps may display too quickly to be visible in ascii mode. n N Simulate N steps without displaying intermediate results. d filename Dump the current state of the board to filename . The file can then be as input when running the executable. q Quit the program. CSE30, Fall 2019 The Input File The input file for generating a board has the following format: [numRows] [numCols] [row col] ← only lists row-col coordinates of alive cells ... [row col] Ex: A file that contains the following 2 3 0 1 2 0 produces a 2 x 3 game board with the cells at (1,0) and (0,2) starting out alive. Note: Remember row is the y coordinate and col is the x coordinate and by convention (0,0) is upper left corner. See stater code config.small , config.big , config.fancy to see examples of input files. The boards_t Struct You will be using a boards_t struct, defined in boards.h . Read the following carefully: 1. belem - Each cell is represented with a custom belem type, which we have defined to be an unsigned char. 2. bufferA / bufferB - Pointers to contiguous blocks of memory that we will treat as arrays of belem ’s. These buffers represent the board state. You will need to allocate memory for these on the heap using either malloc() or calloc() . CSE30, Fall 2019 Hint: Dynamically allocating memory returns a 1D contiguous block, yet we think of game boards as 2D grids. We can index into a 1D array using 2D row-column notation. Notice that for any 2-dimensional position on the board given a 2D location as (row, column). you can access it in the 1D array at . (For more ndex row numCols oli = * + c details, refer to this link.) 3. currentBuffer - A pointer to the buffer representing the “current” board state nextBuffer - A pointer to the buffer representing the “next” board state Hint: We want to store a cell’s next value separately from its current value so the cell’s neighbors can be computed correctly. So you will need two game buffers and a way to differentiate between the “current” and “next” board. (Why do you think this is? What would happen if we updated each cell as we went only using one buffer?) After computing the “next” buffer, you only need to swap the currentBuffer and nextBuffer pointers to “advance” to the next generation. 4. numRows /numCols /gen - the number of rows, number of columns, and current generation (timestep) respectively [ stored as 32-bit unsigned integer type uint32_t ] CSE30, Fall 2019 4. Part 1: Checkpoint [Due Fri, Nov 1, 2019] This checkpoint is meant to encourage you to keep making progress on the assignment. Please implement the functions below. We will be testing functions individually. Do not change the function headers. In addition, we ask that you fill out this bi-weekly survey for the checkpoint. Part 1 Board.c Functions clearBoard void clearBoard(boards_t *self) clearBoard() takes a pointer to a boards_t struct and zeroes-out both buffers in the struct. getIndex int getIndex(boards_t *self, int row, int col) The 2D game board is represented using a 1D array buffer. getIndex() takes in a particular row and column. It then calculates and returns the index value of that row-col in the 1D array. Remember: . (For more details, refer to link.)ndex row numCols oli = * + c createBoard boards_t * createBoard(char *initFileName) createBoard() allocates memory for a boards_t struct on the heap (malloc) and initializes the struct elements. It returns a boards_t struct pointer. See boards.h for details on the struct. To initialize the struct, createBoard() must do the following: ● Allocate memory for the boards_t struct on the heap. What size should the struct be? ● Read in the number of columns and number of rows from the input file initFileName and populate the struct values. Hint: use fopen() and fscanf() to open the file. See example below. ● Allocate memory for and initialize the struct’s bufferA and bufferB . What size should the buffers be? ● Initialize struct’s currentBuffer and nextBuffer and clear the buffers ● Read in each line of the input file and initialize the appropriate cells in currentBuffer to be alive. [Hint: Use fscanf() see example below] ● Set gen the generation number to 0 CSE30, Fall 2019 Example: deleteBoard void deleteBoard(boards_t **bptr) deleteBoard() takes a pointer to a pointer to a boards_t struct and deallocates (frees) all the memory associated with the struct. Then it sets the pointer to the boards_t struct to null. Testing Checkpoint To test that your checkpoint works as expected, try running the executable with an input file A. If it runs, try dumping the contents of the board to a seperate file B. The contents of A and B should be identical. We have provided a few initial files for you to test with. Run valgrind to check for memory leaks. Bi-Weekly Survey Take this bi-weekly survey as part of your checkpoint. CSE30, Fall 2019 5. Part 2: Final Submission [Due Wed Nov 6, 2019] Please implement the functions below. We will be testing functions individually. Do not change the function header. Board.c Functions swapBuffers void swapBuffers(boards_t *self) swapBuffers() takes a boards_t struct pointer and swaps the current buffer with the next buffer. Sim.c Functions: doRow static void doRow(belem *dest, belem *srcStart, belem *srcEnd, uint32_t cols) Parameters: - belem *dest - pointer to the first destination cell in the next buffer - belem *srcStart - pointer to the first cell to process in the current buffer - belem *srcEnd - pointer to the last cell to process in the current buffer - uint32_t cols - number of columns in the board doRow() processes one row of a board. At a high level the algorithm is as follows: For each cell in the row, calculate whether that cell is going to be dead or alive in the next time step based on the rules outlined above in Section 2: The Game of Life. Put the value that the cell will be in the next iteration into nextBuffer . A 0 value indicates “dead” and a 1 value indicates “alive”. Note: doRow can be completed without calling any other functions. We recommend not using any other functions within doRow() since the next assignment will involve translating this C code into assembly. However we will not be enforcing this. CSE30, Fall 2019 simLoop void simLoop(boards_t *self, uint32_t steps) Parameters: - boards_t *self - pointer to the boards_t struct for processing - uint32_t steps - the number of steps to take simLoop() performs the simulation for running the game boards through each “step.” It should advance the board through steps number of generations. At each step, it should call doRow() enough times to process all rows in the board and calculate cells of the next generation. (Remember that the edges of the board are always dead!) Then it should call swapBuffer() to swap the current and next buffers and finally increment the generation count in the boards_t struct. Hints and Tips ● This assignment deals with malloc and frees so there is the potential for memory leaks. It’s highly recommended for you to run valgrind to check for memory leaks. ● We have provided a library for some of the boilerplate code. You can see their function headers in cse30life.h . ● To test, we recommend that you write a small example input file, and step through it to see if it functions as expected. CSE30, Fall 2019 6. Submission, Style, and Grading Style Guidelines No points are given for style, but teaching staff won't be able to provide assistance or regrades unless code is readable. Please take a look at the following Style Guidelines. Submitting: Checkpoint [6 points] 1. Make sure to fill out the survey [1 point] 2. Submit your files to Gradescope under the assignment titled Assignment 4: Life - Checkpoint. You will submit the following files: ● board.c ● README To upload multiple files to Gradescope, zip all of the files and upload the zip to the assignment, or you can multi-select all files and drag and drop. Ensure that the files you submit are not in a nested folder.. 3. After submitting, the autograder will run a few tests [5 points]: a. Checks that all required files were submitted b. Checks that your source code compiles c. Runs test input on your program and compares your output to ours d. Runs valgrind to check for memory leaks Note: The checkpoint is worth a total of 6 points. 5 points for the code, 1 for the survey. However, we will also run additional tests on the checkpoint code at the final submission (not necessarily the exact same tests). These tests are worth an additional 5 points. So if you receive 0/5 on the checkpoint for your code, you can still earn 5/10 points for the checkpoint code by turning in a correct implementation for the final submission. CSE30, Fall 2019 Submitting: Final Submission 1. Submit your files to Gradescope under the assignment titled Assignment 4: Life - Final. You will submit the following files: ● sim.c ● board.c ● README To upload multiple files to Gradescope, zip all of the files and upload the zip to the assignment, or you can multi-select all files and drag and drop. Ensure that the files you submit are not in a nested folder. 2. After submitting, the autograder will run a few tests [15 points]: e. Checks that all required files were submitted f. Checks that your source code compiles g. Runs test input on your program and compares your output to ours h. Runs valgrind to check for memory leaks Grading Breakdown Make sure to check the autograder output after submitting! We will be running additional tests after the deadline passes to determine your final grade. Checkpoint : 6 Points ● getIndex - 1 point ● createBoard - 2 points ● Correct memory allocation/deallocation - 2 points ● Survey - 1 point Final submission: 15 Points ● Checkpoint Tests - 5 points (we retest checkpoint functions, but not necessarily the same tests) ● doRow - 5 points ● simLoop - 5 points Make sure your assignment compiles correctly through the provided Makefile on the ieng6 machines. Any assignment that does not compile will receive 0 credit.
