CPSC 217: Assignment 4 (The Game Of Life)

Due at 4 PM. For assignment due dates see the main schedule on the course webpage. The program must be written and run under python version 3.X and run on the computers in the tutorial labs.

Sections for this assignment

• Program writing portion
• Short answer portion

Program writing portion: New Concepts to be applied for the assignment (worth a max of 4.15 GPA)

• 2D lists
• Solving a more challenging and larger problem (although not mandatory, studying the "Problem solving" lecture material would help for this assignment)
• File input: reading text information into a 2D list
• Exception handling
• Decomposing a program into functions properly (this time you must decide what functions to implement).
• If you want credit for your work: Do not use any pre-created functions/methods unless you are given explicit permission to do so.  [Information about allowable pre-created code in the form of python libraries] Additional functions allowed for this assignment: len, append, open, readline, close. Also, you can use the string methods that were taught in lecture or tutorial although their use is not mandatory.

Assignment difficulty

Students may find assignments more challenging than they first thought. It's best to start work as early as possible. Tips in the [very first lecture] were provided but here's two reminders: 1) work through the lecture and tutorial material before looking in detail at the assignments 2) start work as soon as possible. If you find you cannot complete an assignment before the due date then you will not be granted an extension. For this specific assignment: most students will find it to be quite challenging (so if you are in this boat then that's perfectly normal). Most students in introductory programming courses complete most-all functional requirements so it is a challenge that you have a reasonable chance of meeting if you have approached this course (and assignment) properly. (In some other post-secondary institutes the instructor may not require file input to be implemented but typically less information is provided i.e. just the 'rules' for the births and deaths). Peptalk speech: If it helps, this assignment has been completed by grade 11 students in a Calgary high school. That definitely indicates that it is a 'doable' challenge for you.

Note: it is not sufficient to just implement a working program and expect full credit. This requirement exists so you implement your solution in the correct way using good design principles and you apply the necessary concepts. Even if your program is fully working and the program is not designed or implemented as specified in the assignment description (e.g. poor variable names used, named constants, functions not implemented appropriately or insufficiently etc.) then you will not be awarded full credit.

Critical design requirements

All instructions must be enclosed within the body of a function¹, you must write at least 5 functions (JT's solution to A4 including 10 functions) of your own. Of course the functions must follow good design principles for functions. Functions that I have created in the starting code isn't included in the count. The functions you write must be properly implemented.   No global variables  may be employed. The exceptions to having statements outside of a function could include: import statements (not really needed for this assignment), the creation of global constants (e.g. ATTIC = 1), a global debugging flag (which is a variable) and the call to the initial start or main function.

• You will be penalized heavily if functions are not used or improperly used.

  • No functions or a single function employed then the max assignment grade = 1.0 grade points
  • Two functions properly implemented then the max assignment grade = 1.5 grade points
  • Three functions properly implemented then the max assignment grade = 2.5 grade points
  • Four functions properly implemented then the max assignment grade = 3.0 grade points
  • In order to qualify as properly implemented the function must include instructions (functionality) that are appropriate to that function (e.g. anything related to the attic should not be implemented in a function that includes functionality for the bedroom) and the functions should not be 'empty' (e.g. it just includes a pass instruction) or a token implementation (e.g. a few output statements or declarations).

• In a similar fashion you will be penalized heavily if you define or use global variables (global constants are okay, if you don't know the difference refer to the "Intro programming" lectures covered at the start of the term). If you don't know the difference between constants and variables then refer to the "Intro programming" lectures covered at the start of the term).

  • When any global identifiers (excluding a debugging flag and constants) are employed then you will be penalized a full grade point (1.0). To rephrase: This penalty applies if you declare one or more global variable(s) aside from the debugging flag.

  • Example:
    location = "bedroom"  #Global declared
    def processBedroom():
        if (location == "bedroom"):  #Global referred to in the function.
            #Etc.

• What happens if you ignore both of these requirements (sufficient/proper use of functions and the prohibition on the use of global variables).
• If you define no functions or just a single function and your program includes any global variables then you will be awarded no credit for this assignment. (It might seem 'harsh' but the main learning objective of this assignment is to learn how to implement a program with functions so really aren't getting anything out of this assignment by just writing yet another program that doesn't properly employ functions.)
• The function-related & global variable penalties are applied before other style penalties but the lowest grade that may be awarded is a GPA of 0 (no negative scores will be awarded).

This time around you won't be given a list of specific functions that you need to implement. There's two reasons for this:

1. Providing a pre-created design will constraint students who may think of a different (but still perfectly valid) design.

2. To give you practice decomposing a program into functions. If you aren't required to do this on your own at least once then you will never be able to do this on your own which makes all the other lessons on functional decomposition rather useless because you won't be able to apply them when writing programs.

If you are having trouble coming up with candidate functions then try reviewing the lessons on functional decomposition in lecture (the initial decomposition exercise was very simple because it was covered early in the semester) As well you should attend tutorial and try out the more advanced version of the decomposition exercise TAs will cover for finding the candidate functions. Since you are more experienced now, the Teaching Assistants can cover a more advanced example sometime after they have gone over lists. As mentioned you should have been attending class and taking note of the lessons on a regular basis but this is a hint about the important material for those who haven't always been in attendance. A direct link isn't provided here because requiring you to go through all the material will help you catch up on important concepts that you should have studying.

Summary:

You are to implement a text-based biological simulation: Conway's "Game of Life". Given a starting pattern of life forms that comes either from: 1) one of the 6 hard-coded (fixed) starting patterns in the starting code OR 2) read in from file your program will apply the [rules of births and deaths] on a turn-by-turn basis. At the end of each turn the before and after state of the simulation will be displayed to the user. There will then be an option to continue the simulation or quit the program. If the 'hidden' option is selected then [debugging mode] will be toggled.

Functional requirements (working features of your program, for the marks allocated for each feature see the marking spreadsheet: 
 

• Program displays a menu to the user that will allow the starting pattern to be one chosen from of the hard-coded starting patterns provided in the [starting program].  The code in the starting program is extremely simple and just initializes the references to the lists ('newWorld' and 'oldWorld') to an empty world and displays the result for these lists. The program that you submit will not do things this way. Your program must apply the [rules of births and deaths] on the starting pattern during the first turn. Then the rules are applied on the updated pattern during the second turn and so on until the user quits the simulation.

  • Hard-coded/fixed starting patterns for the lists used in the simulation: are specified in these functions: oneEmpty(), twoSingleCritter(), threeSingleBirth(), fourthSimpleBirth(), fifthCreateListEdgeCases()and sixthComplexCases(). The more of the initial six cases that your program can correctly process, the higher will be your grade. Each of the functions will initialize a 10x10 list. Programs that only utilize this hard-coded method of initialization does not have to handle lists of other sizes. You can write additional functions with different initial patterns but your program must handle the 6 starting cases. Although additional test cases won't increase your grade it may reduce the likelihood of bugs in your program. What you can't do is modify the starting patterns in the above six functions so the marker can tell exactly what cases your program can handle.

  • Starting patterns are read in from a file: A 7th menu option should be added that allows the user the option to specify the name of the file containing the starting pattern.

    • File input option 1 (fixed pattern for a 10x10 list only): Reading the starting patterns from a text file (10x10 world) into the 2D list (worth fewer marks). [Directory containing the input files for the 6 hard-coded cases]
      • The starting patterns of critters will be in square pattern (10 rows, 10 columns). Similar to the last mini-assignment the name of the input file can be chosen by the user.
      • Prompt the user for the name of the input file & if the file is empty it will display an error message.
      • Open the input file and read the starting pattern of stars and empty spaces into the world.
      • If there is any problems associated with the file (cannot open, file is empty, or there is an error during the actual read process) then the program will display an appropriate error message and repeatedly prompt the user for the name of the input file and begin the file read process anew.
    • File input option 2 (variable sized pattern for a list of any size): Reading the starting information from any arbitrarily sized rectangular file into a variable size 2D list (worth a greater number of marks) [One example input file]

      • The starting pattern of critters will be from any sized rectangular sized grid (minimum of 1 row or column to a maximum of 20 rows x 30 columns. (Theoretically your program should be handle a larger input file but there may be problems displaying the results in a reasonable fashion). The size of your 2D lists will vary depending upon the information in the file specified by the user.

      • To help you visualize the layout of the starting input files you may want to view an example starting input file with [formatting marks turned on in Word]. Note: the tutorial example only illustrates the use of a debugging mode in one function just to give you an idea of how this mode works, your program really should take full advantage of the flag and use it throughout (every function). Also you might want to create test files of various sizes using Word (but making sure you save them as .txt files). Of course to be able to check if your program has completed the above tasks successfully the program needs to display the state of the simulation.

      • If implement this option of file input then you will likely have to make some minor modifications to the display function. (That's because the starting display function assumes a fixed size list and you have to figure out how to display a variable sized list). But even with the modifications the grid and layout should appear the same (e.g. the before and after state displayed side by side, the correct pattern and turn number appears etc.)

  • In both cases (hard-coded or file initialization):
    • Your program still must use the display function so the marker can see consistent output.
    • Important grading point: Your program functionality marks will only be awarded if your program produces the same results as the outputs as shown in the [output files]. For example, function "oneEmpty()" starts out empty and should never contain a Critter in the pattern. Function "sixthComplexCases()" will produce a stable pattern of 4 Critters in a square by turn 20. Partial marks will not be awarded if your pattern of Critters is 'close' to the pattern produced by my program. In addition you need to correctly and comprehensively document which starting patterns that your program will handle. Both of these requirements (producing the same patterns in your output and documenting which cases that your program correctly handles are necessary to make the marking process reasonable - don't expect the marker to expend time hand tracing code to figure out if things are working). However, providing the results that your program must display is also an advantage for you. You will know if your program is "working or not" based on the pattern match (immediate and continuous feedback about your progress). But just looking at the patterns is not a substitute for implementing and employing a debugging mode. The debugging mode can be very useful for helping you determine why and how your program is malfunctioning (if you have good debugging output messages).

• The pattern read in is a biological simulation ('biosphere') whose state is stored as a pair of 2D lists 'newWorld' and 'oldWorld'. Each location in a biosphere (element in a 2D list) either contains: a space character or a the life form ("Critter" which appears as a star).

• The rules of births and deaths] are determined by the pattern in the 'before' list (oldWorld) and the actual births and deaths occur in the 'after' list (newWorld).

• These rules are applied simultaneously for each element as a time unit (a 'turn') passes in the simulation. That's because the check of neighbors occurs in the oldWorld list and births/deaths occur in the newWorld list.

• There will be a main loop in the program that runs until the user quits the program:

  get the initial starting pattern from the 6 hard-coded choices or from file

  run a turn in the simulation

  do while (user has not quit)

      display the state of the world

      run a turn in the simulation

      prompt the user (quit or continue to the next turn: the option to toggle debugging won't be displayed but the program will react to this selection)

      copy the new world biosphere into the old world biosphere (write the code yourself, don't use pre-created python function/method)

  end loop

• User input at the end of each turn:

  • If the user wants to run another turn: allow the user to just hit enter (your prompt should that the user just pressed 'enter' to continue). Don't force the user to type in any other characters e.g. ('c' and enter to run another turn because the extra character just needlessly forces the user to enter more keystrokes).

  • If the user wants to end the simulation: The user then they should type in 'q' or 'Q' and press enter. (This option should also be specified in the prompt).

  • (This option is not show in the prompt i.e. it's a hidden option): If the user types in 'd' or 'D' and then pressed enter the this toggles the [debugging mode] on/off.

• Copying the data from oldWorld to newWorld. In order to learn how to write basic code for a list you cannot use pre-created function/method to perform the copy but you can refer to examples provided. Although all the examples dealing with lists can help you with the assignment there is [one particular lecture example] that shows how to properly copy lists. Also it illustrates the difference between list variables and the list it refers to which you (this point is illustrated by showing the correct and incorrect way to copy a list)

• To complete this assignment: you can (and really must) change the code in the start() function. As well you must implement several other functions that include the above program functionality.

Debugging mode

Entering 'd' or 'D' will toggle debugging mode (False becomes True, True becomes False). The flag 'debugOn' will track whether debugging message are to appear or not and by default the mode is 'off'.

    debugOn = False

When the flag is set to 'True' debugging messages will appear, otherwise they will not:

    if(debugOn == True):
        print("<<<Some debugging message>>>")

The exact content of the debugging messages is left to your discretion. As the name implies the debugging tool should be used to help you test and debug your program. Here are examples of debugging messages: 1) Display greater details: the neighbor count as well as births and deaths for each square  2) More sparse announcements specifying only where births and deaths have occurred. Again you are not bound to produce these exact messages in order to get credit for the debugging feature but they are provided to give you an idea of how you can use this feature to test your program.

This global variable for the debugging flag is the sole exception on the prohibition on the use of global variables in your program. No penalty will be applied for using this debugging flag but the usual penalty will be applied for other global variables e.g.

turn= 1

def display(oldWorld,newWorld):

    print("Turn #%d" %turn)

If you are still having trouble figuring out how a debug flag can be used in your assignment an was covered in tutorial but linked here for your convenience [example program: 8boardGameSolution_with_DEBUGGING].

Global constants (e.g. SIZE = 10) should be used when appropriate. Penalties for lack of constants may be applied when it's appropriate to define one and one hasn't been defined for that program.

Rules of births and deaths

The births and deaths of critters is based solely upon the number of neighbors in adjacent/neighboring squares. For each of the squares in the biosphere a count of the neighbors must be performed and based on the count the following rules will be applied.
 

If the an existing square in the old world is empty then a birth may occur in the corresponding location in the new world if:

• There are exactly three neighbors in the old world.

If the an existing square in the old world contains a critter then a death will occur in that corresponding location in the new world if:

• The critter is too lonely: it has zero or one neighbors in the old world.

• The critter has been over crowded: it has four or more neighbors in the old world.

If the an existing square in the old world contains a critter then the critter will continue living in the corresponding location in the new world if:

• There are either 2 or 3 neighbors.

Each square will have from 3 - 8 neighboring squares (inner squares have 8 neighbors, outer squares can have 3 at the corners or 5 on the top/bottom/left/right edges).

? = the square to check for a birth or death

N = a neighboring (adjacent) location in the list

Inner squares (1,1) to (7,7): 8 neighbors

N	N	N
N	?	N
N	N	N

Four corners (0,0), (0,9), (9,0), (9,9): 3 neighbors

(0,0)	(0,9)	(9,0)	(9,9)
? N N N	N ? N N	N N ? N	N N N ?

Left, top, right and bottom

Hint for reading the pattern from file (how to see the invisible characters in a text document).

Open the input file using Word (you should be able to access Word via the student license for Office 365 without charge while you are U of C student) and here's how you turn toggle the display of 'Formatting marks':

• Home ribbon -> (Paragraph group) and click on the Show/Hide icon

Characters that aren't visible such as spaces, tabs and the newline (enter) appear in this display mode. Here's how to see formatting marks in MS-Word on an Apple computer (because the university is unable to provide a MAC to the course instructor the correctness of the contents of this link could not be verified): [Viewing formatting marks on a MAC]

Links to online web-based executable versions of the Game of Life to allow you to see how the simulation progresses.

• [Using pre-determined starting patterns]
• [The starting pattern may be edited]

In addition to grading on whether the above functionality was correctly implemented TAs will also look at documentation and style.

Naming the file containing your program

Implement a program with the features listed under the functional requirements. You must save your program in a file called "gol.py" (short for "game of life"). Failing to use this exact name will affect your grade.

In addition to grading on whether the above functionality was correctly implemented TAs will also look at documentation and style.

Non -functional assignment requirements (style and documentation).

General programming style requirements (-0.1 penalty for each  violation of a category, for this assignment there is no maximum cap on the number of style penalties that may be applied (8 categories of penalties means a penalty of -0.8 will be applied)

• Naming conventions: You should employ good naming conventions for identifiers (variables, constants and even the name of the file containing the program) as covered in the "Intro to programming" section of the course.
• Named constants should be used as appropriate (and if they aren't a penalty will be incurred).

	Yes do it this way!	No. Not this way!
	LEFT = 0 RIGHT = 1 CENTER = 2 if (silverLockPosition == RIGHT):	if (silverLockPosition == 0): #What does 0 stand for???

• The program code should have appropriate white space (specified in the "Intro to programming lecture') and alignment (specified throughout the lecture notes).
• Code is self documenting e.g. Clear expressions (e.g. mathematical, Boolean). Expressions should be clear and simple (break up or restructure complex expressions). Good variable names and the use of named constants are examples of writing self documenting code but specifying clear expressions is important enough to be included in a separate category.
• Your program should follow the 5 rules of thumb for designing user friendly software (distilled from Jakob Nielsen's 10 usability heuristics) which were included at the notes on 'Repetition' e.g. good error handling (such as prompts to the user to enter the required information clearly indicate what is required, good error messages should be provided for erroneous input) minimizing the user's memory load, being consistent, providing clearly marked exits & providing feedback as appropriate. This includes but is not limited to having the menu selections for choosing the action for each room being intuitive intuitive.
• Of course if a student implements an extreme case of inefficient code (e.g. multiple loops or branches are used when one will do) then penalties may be applied but this is generally rare.
• Looping structures should not employ abnormal termination mechanisms i.e. a 'break' instruction
• Having at least one violation in one of the above general style requirements will result in -0.1 penalty to marking. Multiple violations in one category still results in a single penalty (e.g. 3 bad variable names will still result in a -0.1 penalty). However violations between categories will result in cumulative penalties (e.g. a program that includes poor variable names, messy program layout and poor error handling will receive a -0.3 penalty)

Function specific style requirements (principles of good design for functions) -0.2 penalty will be applied for each of the 3 function specific style requirements that have been violated.

• Functions are one screen in length (normal screen 40 lines max of code (the count excludes whitespace and documentation).
• Functions implement one well defined task (e.g. processLivingRoomCommands vs. processlivingRoomRunIntroductionRunConclusion).
• Code in one function is not duplicated in another function (not in the notes but this is just common sense that you don't write two functions where there's overlapping code - the overlap should likely be taken out of both functions and moved to another separate function). In this assignment there may appear to be some overlap (e.g. each room displays a menu of options but the specific options displayed will not be identical so the latter is not a case of overalaping code.
• Violating any of the function specific style requirements will result in a -0.2 penalty for a violation in each of the 3 categories. E.g. a program that includes a function that exceeds the maximum length and implements two or more tasks would incur a -0.4 penalty.

Documentation requirements:

• Header documentation: This should be specified in the header of the program (very top of your program in the form of Python documentation). The basics of documentation were covered in the "Intro to programming" section of the course. Later lectures may specify additional information that needs to be provided in the documentation.

  • Identifying information: All assignments should include contact information (full name, student ID number and tutorial section [Here's a link if you don't know how to find this information]) at the very top of your program.
  • Program version. (version date or version number).
    • Under the version you should specify which assignment features were implemented in that version as specified in the "Intro to programming section"
  • Any program limitations or weaknesses.
• New documentation requirement starting with A3 and applies to all successive assignments: [Inline documentation] (provided just before each function is defined): list the features of each room that were implemented in a particular function, the return type(s) as well as the type(s) of the arguments.

How to do determine 'how you did' on an assignment?

Program functionality (implementing working program features)

• Test your program: Because the [marking key] is posted ahead of time if you test your program thoroughly before submitting the final version then you should get a pretty clear idea of "how you will do".

Marking and grading

• What to submit: Submitted programs must run on the computer science network (i.e. the computer rooms were your tutorials are conducted) running Python 3.x. If you choose to install Python on your own computer then it is your responsibility to ensure that your program will run properly on the computer science network. Options for doing this remotely were detailed in the [getting started as a computer science student help link]. It's up to you if you wish use the graphical program builder other than IDLE (or another development environment rather than a simple text editor) to write/run your programs but if you do you submit your program in the form of text ".py" file or files. Windows users: take care that you don't accidentally submit a shortcut to a file instead of the actual file. (Check the file name and compare the file size to your original file. Simply downloading the shortcut file as a test won't work because that shortcut will work on your computer but not on anyone else's machine and your work won't be graded.).
• Late assignments or components of assignments: Extensions may be granted for reasonable cases by the course instructor with the receipt of the appropriate documentation (e.g., a statutory declaration with a commissioner of oaths). Location of the online form: [PDF file]. Alternate submission mechanisms (non exhaustive list of examples: email, uploads to cloud-based systems such as Google drive, time-stamps, TA memories) cannot be used as alternatives if you have forgotten to submit work or otherwise have not properly submitted into D2L. Only files submitted into D2L by the due date is what will be marked, everything else will be awarded no credit. The final cut off date after which full assignments will not be accepted is after the maximum progressive penalty (listed below) can be applied.
• Assignment extensions (before the assignment is due): may be granted for reasonable cases by the course instructor with the receipt of the appropriate documentation (e.g., a sworn declaration with a commissioner of oaths). Typical examples of reasonable cases for an extension include: illness or a death in the family. Example cases where extensions will not be granted include situations that are typical of student life: having multiple due dates, work commitments, forgetting or mixing up due date etc. Tutorial instructors (TAs) will not be able to provide extension on their own and must receive permission from the course instructor first. If you request an extension from me let me know the name of your tutorial instructor and the tutorial number [link to : tutorial and TA information) because the markers won't accept late submissions without directly getting an email from me and I need to know who to contact.  Also extensions need to be requested before the due date and not afterward.
• How you will be graded for full assignments. As mentioned, as well as being marked on whether "your program works" you will also be marked on non-functional requirements such as style and documentation. Consequently this assignment will include a separate [marking checklist]. Besides seeing your grade point in D2L you can also see the detailed feedback that your TA will enter for each student. You can access the grading sheet in D2L under Assessments->Dropbox and then clicking on the appropriate assignment link. If you still cannot find the grading sheet then here is a [help link]
• Questions or concerns about grades after they have been released: Assignments will be marked by your tutorial instructor (the "Teaching Assistant" or "TA") for your tutorial section. When you have questions about marking this is the first person that you should be directing your questions towards.  If you still have question after you have talked to your TA, then you can talk to your course (lecture) instructor but please indicate in your email that you first contacted your TA before going into your concerns.

Collaboration:

Assignments must reflect individual work; group work is not allowed in this class nor can you copy the work of others. Some "do nots" for your solution: don't publically post it, don't email it out, don't show it to other students.  For more detailed information as to what constitutes academic misconduct (i.e., cheating) for this course please read the following [link].

Method of submission:

You are to submit your assignment using D2L [help link]. Make sure that you [check the contents of your submitted files] (e.g., is the file okay or was it corrupted, is it the correct version etc.). It's your responsibility to do this! (Make sure that you submit your assignment with enough time before it comes due for you to do a check). If don't check and there were problems with the submission then you should not expect that you can "learn your lesson" and simply resubmit.

D2L configuration for this course

• Do not use compression utilities (such as zip) or archiving utilities (such as tar) otherwise your submission may not be marked. The space savings in D2L is not worth the extra time required by the marker to process each submission.
• How often can you submit: Multiple submissions are allowed for this assignment: You can (and really should) submit work as many times as you wish before the due date. However only the latest file submitted is the one that will be marked, everything else will be ignored (because it is not fair to your marker to sort through multiple versions of your files).

Late submissions for full assignments  when there is no extension granted: Make sure you give yourself enough time to complete the submission process so you don't get cut off by D2L's deadline (or your submission will be automatically flagged as late by D2L and it will be graded appropriately)..

Use of pre-created Python libraries:

Unless otherwise told you are to write the code yourself and not use any pre-created functions (or methods). For most assignments the usual acceptable functions include: print(), input() and the 'conversion' functions such as int(), float(), str(). Look at the particular assignment description for a list of other functions/methods that you are allowed to use and still get credit in an assignment submission. If it's not listed then you should assume that you won't be able use the function and still be awarded credit. You cannot use a pre-created method (e.g. those specified in the copy module) to copy one list to another.