Due date: 周二中午需要有结果InstructionsBefore writing any code, read Gardner's article on Conway's Game of Life and this entire document.Work with your assigned partner or partners (and only with them).Unless otherwise indicated, use only the Python operations and commands we have been using thus far inclass and lab.You will need to download and unzip the starter archive. (See the section on the starter archive.)Write all your code in the supplied hw4.py and keep it named that way. In that file, replace with your names. Work in areas indicated by the comments marked with ... and onceyou have completed work on that area, remove those ... comments.Include a concise, proofread and edited comment at the top of your file that indicates how much of theassignment you were able to complete and any known bugs or limitations of your code.Submit by replying to the email officially announcing the assignment and attach only your hw4.py file.Submit only once per partnership, but CC your partners when submitting.You are encouraged to experiment with the runnable solution module (hw4x.py) which is included in thestarter archive. (See the section on making use of the runnable solution.)DetailsConway's Game of LifeYour goal for this assignment is to implement Conway's Game of Life. You are encouraged to familiarize yourselfwith the game and its history. In particular, you should read "The fantastic combinations of John Conway's newsolitaire game 'life'" by Martin Gardner from the October 1970 issue of Scientific American. (The final set ofdiagrams is not included in this version of the article, but that should not prevent you from understanding how the"game" works.) You are strongly encouraged to experiment with an existing implementation of the game such asthis JavaScript version runnable in your Web browser or Golly (a very powerful downloadable version of thegame).grids v. boards2/9For purposes of this assignment, we need to distinguish between two related ideas: A grid is a list of lists of thesame kinds of items (so a list of lists of Booleans, or of numbers, or really anything) where each interior list (row)is the same length (has the number of columns). If we refer to the dimensions of a grid as being "m by n" we meanit consists of n lists each of which consist of m values (i.e., the grid is m columns by n rows).On the other hand, for this project, we define a board as a grid of numbers where the numbers are all either 1 or 0and where the borders (the top and bottom rows and the leftmost and rightmost columns) are all 0. Because theborder is not designed to change, we describe the dimensions of the board as ignoring the borders. So if theunderlying grid is 7x5 (inclusive of the borders) then that is describing a 5x3 board. The overall grid might be:00000000101110011001000101000000000but conceptually the inside of the board is just this 10111 11001 01010and the user would think there are active cells at these (column, row) coordinates:(0, 0), (2, 0), (3, 0), (4, 0)(0, 1), (1, 1), (4, 1)(1, 2), (3, 2)The choice to use 1 and 0 instead of True and False and use the extra border of 0 values is motivated by thesimplicity it offers for counting how many active neighbors a cell has (see the count_neighbors function describedbelow).columns v. rowsIt is important to remember that when specifying the total number of columns and rows in a board, each is just aninteger, but the order matters. Likewise, when specifying the coordinate the specific column and row of a cell inthe board both are integers and order matters. (3, 4) is not the same as (4, 3).When using the paint method, the coordinates are specified as an ordered pair (a tuple of length two) where thefirst item in the pair is the horizontal (x) coordinate (the column number) and the second item is the vertical (y)coordinate (the row number).However, the standard convention for representing a twodimensional array is as a list of lists and thinking of thatas a list of rows. This means we specify the row number first when accessing the elements directly in an array. Soif we have a grid g, and wanted to refer to what is at position (3, 4) i.e., column 3 (counting from 0) and row 4(counting from 0), we would write:3/9 g[4][3]This can lead to hard to find bugs where a value intended to specify a column number is instead used as a rowindex and vice versa. To combat that problem: 1) be aware of the potential problem; 2) test as you go; and 3) usenonsquare grids (usually we use more columns than rows because most computer screens are wider than they aretall) so that you either receive an index error (for instance if accidentally referring to an outofbounds row numberwhen you intended it to be a column number), or the visual display of the grid seems rotated by 90 degrees.ordered pairsOrdered pairs in Python are tuples (immutable lists) of length two. In this assignment, the only ordered pairs weuse will consist of two integers.When passing dimensions into a function (how wide, how high), the arguments will be separate integers. Forexample, to create an empty grid, gol_repl calls:gol_aux.make_empty_grid(columns + 2, rows + 2)When referring to a coordinate pair, we use a tuple. For example, to fill the cell at column 7, row 4 with the colorblue, we would write:gol_graphics.paint((7, 4), 'blue')Occasionally, it will be convenient to use tuples for the overall dimensions most notably in functions that returnsthe dimensions of a board (since we can only return one value; but one tuple can contain two values). For example(columns, rows) = gol_aux.get_dimensions(board)graphics in SpyderNot all of the functions you write for this assignment will be fruitful (meaning they do not all require a returnstatement), but they will all be independent of the details of using graphics in Python. The only two functions youshould ever need from the supplied graphics module (gol_graphics.py) are paint and update (which forces theunderlying graphics system to update the graphics on the screen a quirk of the underlying system, but a quirk thatallows us to control how fast our graphics are painted).In many implementations of Conway's Game of Life, the user can interact with the board directly to activate ordeactivate cells (for example, by clicking on cells). Later this semester we will learn how to do that, but it is a bitbeyond our capabilities just now. Instead, a textbased REPL allows us to load patterns of cells into and out of theGame of Life board, to randomly configure the board, and more.In Spyder, graphics windows open as a separate window from the main Spyder IDE window. In particular, thedisplayed grid for this assignment runs in a separate window from the iPython console. This means that if youhave limited screen real estate (like on a normal sized laptop display), you may have to bring one or or the other ofthe windows (the graphics window or the main IDE window) into focus in order to interact with an executing4/9Python graphics program. For instance, in the console there will be our usual style of textbased REPL, while inthe graphics window you can see the evolution of an instance of Conway's Game of life. Examples:Spyder: iPython console in front of graphics window5/9Spyder: graphics window in front of iPython consoleDepending on your computer's Spyder configuration, when you quit running an instance of the assignment(gol_repl), the graphics window may not close. If that happens, simply restart the console from within Spyder.loading and saving GameofLife patternsThe supplied Game of Life REPL (gol_repl) allows the user to load and save text files that represent gameboardconfigurations. There are two different styles that can be used:full boards: This text file is an example file showing a "glider" that can be loaded as a GOL board. When loading afull board (the load option), the current board is replaced entirely with the configuration represented in the file.Entire boards can be saved in this format using the save option.activecell patterns: This text file is an example showing another way a glider can be represented (as a list ofactive cells on a board, rather than as an entire board). When loading a pattern (the pattern option), only thespecified coordinate pairs are turned "on". All other parts of the board remain as they were prior to loading thepattern. Likewise, saving the current configuration (the xtract option) creates a files consisting only of thecoordinate pairs of cells that are "on".starter archiveThe starter archive is a zip file that represents a folder (hw4) which contains a collection of Python files and textfiles. The Python files are:hw4.py: the only file which you need to modifygol_graphics.py: uses Python's graphics to create a window for painting colored squaresgol_aux.py: helpful functions for a variety of assignmentspecific tasksgol_repl.py: the REPL for playing Conway's Game of Lifehw4x.py: the runnable solution version of hw4.py.The text files are:glider.grid.txt a full grid representation of a gliderglider.list.txt a list of cells representation of a gliderblinker.list.txt a list of cells representation of a vertical blinkerblinker.grid.txt a partial grid representation of a horizontal blinker.runnable solutionYou are welcome (and encouraged) to experiment with the runnable solution module (hw4x.py) that is included inthe starter archive. If you import that file in your working file (hw4.py) as in:import hw4x 6/9then you can use it to (temporarily!) use my solutions if you get stuck on a problem so that you can proceed. Forexample, to make randomize_board work you could use:def randomize_board(board, density): hw4x.randomize_board(board, density)You can also run my full solution by temporarily modifying your gol_repl.py file so that instead of havingimport hw4 as gol you use:import hw4x as golThe assignment itself0. Unpack the starter archive. That should create a folder called hw4 within the folder where you performedthe extraction. Work entirely within the file hw4.py. Other than the first two problems, to test your work, runthe gol_repl.py module.1. Complete fill_grid(grid, fill_item) so that it sets every cell of grid to be fill_item. You can test this in theshell using the supplied grid_to_string as in this example:>>> import gol_aux>>> g = gol_aux.make_empty_grid(9, 5)>>> print(gol_aux.grid_to_string(g))_____________________________________________>>> fill_grid(g, 1)>>> print(gol_aux.grid_to_string(g))*********************************************2. Complete set_grid_border(grid, border_item) so that it sets the all the border cells of grid to be border_item.Keep your code simple, but also try to avoid redundant work (i.e., setting the same cell more than once).You should be able to test set_grid_border in the shell like this (continuing from previous example):>>> fill_grid(g, 1)>>> set_grid_border(g, 0)>>> print(gol_aux.grid_to_string(g))_________7/9_*******__*******__*******__________3. Complete paint_board(board) so that it draws the cells from within board onto the canvas via the suppliedpaint function. The board's "border" cells should not be drawn. Use nested loops. Completing this functionshould have an immediate impact when running the game REPL because we are using three distinct colorsfor the window's background color (BG_COLOR), the color of active cells (ACTIVE_COLOR) andinactive cells (INACTIVE_COLOR). Furthermore, the clear and fill options work by using fill_grid andset_grid_border so you can now visually test your solutions to the previous two problems by using theREPL.4. Complete set_cell(board, crp, active=True) so that it sets the cell at rowcolumn pair crp in board to be "on"if active is True and "off" if not. You can assume column and row are integers. However, your code shouldcheck that they are within the range of the board. This is a sideeffecting function that returns nothing.When successful it modifies board; when not (if the position is out of range), it indicates the invalidcoordinates using print. Remember to take into effect the invisible "borders" of the board. In other words,calling set_cell(b, (5, 7)) should make the value of b[8][6] be 1. You can test this function by using theactivate and deactivate options of the REPL.5. Complete toggle_cell(board, crp) so that it inverts the cell at rowcolumn pair crp in board. This should bethe same as activate_cell (i.e, its side effecting, it should check that the coordinates are within the range ofthe board, and, if not, should print a warning). Again, remember to take into effect the invisible "borders" ofthe board. Remember that the board consists of 1's and 0's, not Boolean values. Test this using the toggleaction in the REPL.6. Complete randomize_board(board, density) so that it sets every nonborder cell of the board to be a 1 withthe probability indicated by density (which should be an integer between 0 and 100 indicating the percentchance that any cell is to be filled). randomize_board(board, 0) is equivalent to clearing the board;randomize_board(board, 100) is equivalent to filling the board. randomize(board, 50) sets each cell as activeor inactive with equal likelihood. Test using the randomize action in the REPL.7. Complete set_cells(board, pairs, active=True) so that it sets all the cells in board indicated by pairs whichshould be a list of rowcolumn pairs to be active or inactive. Complete paint_list(color, pairs) so that itpaints a colorcolored square at each valid rowcolumn pair in pairs. (Hint: These are meant to be simpleexercises in looping over lists; call set_cell and paint.) When these are complete you can test them by usingthe pattern option in the REPL which will load a pattern from a text file consisting of a list of rowcolumnpairs of active cells. For instance, if you start with a clear board and then load the glider.list.txt (included inthe starter archive) you should see a glider pattern appear on the board. (Note: I have already supplied thecode to read this sort of file and parse a string that represents a list of pairs.)8. Complete extract_cells(board) so that it returns a list of rowcolumn coordinate pairs of the active cells inboard. The coordinates should reflect their apparent positions (not their literal coordinates within thebordered grid); so, for example: if board[5][7] is 1 then the corresponding pair returned in the list should be(4, 6). Once completed that will make the xtract option of the REPL work correctly.8/9These next three problems combine together to play Conway's Game of Life's for one generation. Namely,for every nonborder cell in board: if a cell is currently active and has 2 or 3 active neighbors than it remainsactive; otherwise it becomes inactive. If a cell is currently inactive and has exactly 3 active neighbors itbecomes active.9. Complete count_neighbors(board, crp) so that it returns the number of active cells that "touch" the specifiedlocation in board. For example, if board looks like:0 0 0 0 00 0 0 1 00 1 1 0 00 0 1 0 00 1 0 1 00 0 0 0 0then>>> count_neighbors(board, (0, 0))2>>> count_neighbors(board, (2, 1))3but count_neighbors(board, (3, 5)) should result in an error. (Since the coordinates are apparent, not actual.)10. Complete compute_changes(board) so that it returns a pair of lists: the first is a list of the apparent rowcolumncoordinates of newly active cells (those that are "born"), the second is a list of apparent rowcolumncoordinates of newly inactive cells (those they have just "died"). For the example above, the result mightlook like:>>> compute_changes(board)([(1, 0), (2, 1), (2, 2), (1, 3)], [(2, 0), (1, 2), (0, 3), (2, 3)])(It might be different in exact form because the order of the the newly active cells within the first list andlikewise the order of the newly deactivated cells in the second list depends on the exact order determinedby your algorithm.)11. Complete evolve_once(board) so that it plays Conway's Game of Life for one generation. (Hint: usecompute_changes, set_cells, and paint_list.) Test using the evolve once option in the REPL.12. Complete evolve_n(board, n) so the game is played for n generations. (This is meant to be almost trivialonce the previous problems are complete. However, if you choose to do the challenge exercises you mayeventually revisit this function.) Test using the go option in the REPL.13. Complete read_gridfile(columns, rows, filename) so that it reads filename (which can be assumed to be thevalid name of readable text file) and returns a columns x rows board that corresponds to the contents of thefile. The format of the file is: a description of the file (so it can be ignored, or printed out to the shell); the9/9second line consists of the singlecharacter symbol used in the remainder of the file to signify active cells inthe grid. For example, see blinker.grid.txt and glider.grid.txt from the archive. You can assume that each rowis specified on its own line; any character (including spaces) other than the active character representinactive cells; each line is up to specified column width then everything else ignored on that line; if the lineends before the column width is reached, the row is padded to that width using 0s. Only the specifiednumber of rows are read (anything after is ignored); if fewer than the specified number of lines are included,remaining rows are padded with 0s. Test the function by reading either of the example grid files using theload gridfile option in the REPL.14. Complete write_gridfile(filename, desc, board) so it writes the board as a gridfile using the sameconventions outlined in the previous problem where the first line of the desc string is the used in thedescription line, and the dimensions of the board are determined in their usual way (using len). The writtengrid should exclude the 0border of the underlying grid.Challenge problemsConsider these problems only after completing all of the numbered problems above.Modify evolve_once so that in addition to being side effecting (modifying the board and painting squares inthe graphics window) it also returns the number of cells that have changed.Modify evolve_n so that it stops before n generations have elapsed if it hits a stable configuration meaningthat no changes occur between two successive generations.Print messages in the shell (that appear during normal use in the REPL) to indicate how much time elapseswhile evolving one generation.Challenging: modify evolve_n so that is also stops if a pattern emerges: that is if one generation that itevolves is identical to some previous generation (but not necessarily the immediately previous one). If itstops it should indicate (by printing a message) how long (how many generations) form the "cycle".
