Assignment 3 COMP 208 Winter 2020
posted: Friday, March 13, 2020
due: Friday, March 27, 2020 at 23:59
Primary Learning Objectives
By the end of this assignment, students should be able to…
• perform operations on lists of lists
• guard functions against invalid argument values and raise exceptions in such cases • plot simple graphs in Matplotlib
• reason with objects and have an understanding of computer simulations
• read documentation of a class and its methods and use them appropriately
• apply problem-solving to a geometric problem
Submission instructions
• This file is accompanied by a .zip file called Assignment3.zip. Unzip this file to produce a directory called Assignment3 containing several Python code files. You will write the solutions to this assignment in these files.
• When ready to submit, zip up the Assignment3 folder and submit the resulting Assign- ment3.zip file to myCourses. Before zipping, make sure that the folder is still named As- signment3 and that the four Python code files inside are still named as follows:
– snowflake.py – vink.py
– wonkavator.py – student ai.py
Any deviation from these requirements will result in deduction of points.
• You can submit multiple times on myCourses, so don’t worry if you realize that your current submission contains an error.
• Submit early, submit often! (Computer crashes do occur, and myCourses may be overloaded during rush hours.)
1
Coding instructions
Please read the following instructions carefully; non-compliance will result in point deductions.
• You must include your name and McGill ID number at the top of each .py file that you submit. By doing so, you are certifying that the code file is entirely your own, and represents the result of your sole effort.
• You are expected to comment your code to explain what is going on, on average 1 comment for every 5-6 lines.
• You are expected to use descriptive variable names whenever possible. Do not use variable names like x, y or z (unless you are dealing with a mathematical function). Instead, use names like user input, sum of numbers, or average value.
• Some questions will ask you to define a function. The function you define must have the same name, parameters and return value as specified. Further, questions may have examples to show the output that your program is required to produce. Make sure that the output of your program exactly matches the output of the examples. (Input values are highlighted in gray, as they should be input by the user.)
• Those with prior programming knowledge may be able to solve a question with advanced Python concepts. Although it may be more efficient to do so, it defeats the purpose of the assignment as we are testing on specific language constructs. Therefore, please only use concepts discussed in class up to and including March 13 (the day Assignment 3 was posted). Solutions that use Python concepts seen after March 13 will be penalized). Further, third-party modules (except those explicitly specified) are not permitted.
Policies
• Late assignments will be accepted up to 2 days (48 hours) after the due date and will be penalized by 10 points per day. Note that submitting one minute late is the same as submitting 23 hours late. We will deduct 10 points for any student who submits or resubmits after the due date irrespective of the reason, be it wrong file submitted, wrong file format submitted or any other reason. This policy will hold regardless of whether or not the student can provide proof that the assignment was indeed “done” on time.
• If your program does not work at all, e.g., gives an error and does not produce any output, zero points will be given for that question. If your program executes without errors but produces incorrect output, partial marks may be awarded based on the correctness of the code.
• If anything is unclear, it is up to you to seek clarification by either directly asking a TA during office hours or making a post on the myCourses discussion board.
• Work submitted in this course must represent your own efforts. Assignments must be done individually; you must not work in groups (except for Question 4, where you can work in teams of two). Do not ask friends or tutors to do this assignment for you. You must not copy any other person’s work in any manner (electronically or otherwise), nor give a copy of your work to any other person. Code similarity detection software will be run on all assignments.
2
Question 1 [25 points]
Dr. Sno F. Lake of McGill Atmospheric Sciences is starting a study on the properties of snowflakes. To begin the study, a computerized representation of a snowflake must be developed. We will help Dr. Lake by writing the following function which represents a snowflake inside a square matrix (list of lists).
Name: make snowflake
Parameters: A positive, non-zero, odd integer n and a list of tuples regions, with each tuple con-
taining two positive, non-zero integers. The regions parameter has a default value of None.
Return value: A square matrix (list of lists) of size nxn filled with dots (’.’), and with snowflakes in the given regions. At the start of the function, you can call the given function make dot matrix to create an empty nxn matrix filled with dots.
A snowflake of a given region is defined by the middle row of the region filled with ‘*’, the middle column of the region filled with ‘*’, and the two diagonals of the region (top-left to bottom-right and top-right to bottom-left) filled with ‘*’. Furthermore, the middle of each snowflake should have the ‘@’ character, and the ends of each arm of the snowflake should have the ‘+’ character.
A region is specified by a tuple containing two positive integers: the first specifying at what row and column to start the snowflake on, and the second specifying the size of the snowflake (width and height of a snowflake will be the same). For example, a region defined by the tuple (0, 6) will have the top-left corner of the snowflake be (0, 0), and the bottom-right corner of the snowflake be (6, 6). A region defined by the tuple (3, 4) will have the top-left corner of the snowflake be (3, 3), and the bottom-right corner be (7, 7). If the regions parameter is None, the function should instead use a region of (0, n-1), where n is the first parameter of the function (i.e., the snowflake would span the entire matrix). Hint: Try writing this function only for the case where the snowflake spans the entire matrix, then extend it to work on any specified region.
Finally, we will harden our function against invalid parameter values. If any of the following condi- tions are met, then the function must raise a ValueError with an appropriate error message.
• nisnotoftypeint
• nisnotodd
• n is less than or equal to zero
• regions is of a type other than list or NoneType
• regions is an empty list
• a tuple in the regions list has a value that would put the bottom-right corner of the snowflake out of the bounds of the given matrix size
Further, there are a couple of other kinds of invalid parameters that are not listed here. You must think of them on your own and raise a ValueError in those cases as well.
Note: snowflake regions can overlap. Do not raise a ValueError in this case.
3
Filename
You must write this program in a file called snowflake.py. Some utility functions are already in the file which you may find useful. The example cases (below) are also in the file, near the bottom in comments. You can un-comment each example to test your code, but make sure to re-comment the line and/or delete the examples before you submit.
Examples (as executed in Thonny)
Example 1:
Example 2:
Example 3:
Example 4:
>>> print_snowflake(make_snowflake(1))
@
>>> print_snowflake(make_snowflake(3))
+*+
*@*
+*+
>>> print_snowflake(make_snowflake(5))
+.*.+
.***.
**@**
.***. +.*.+
>>> print_snowflake(make_snowflake(13))
+…..*…..+
.*….*….*.
..*…*…*..
…*..*..*…
….*.*.*….
…..***…..
******@******
…..***…..
….*.*.*….
…*..*..*…
..*…*…*..
.*….*….*.
+…..*…..+
4
Example 5:
>>> print_snowflake(make_snowflake(11, regions=[(0, 2), (4, 4)]))
+*+……..
*@*……..
+*+……..
………..
….+.*.+..
…..***…
….**@**..
…..***…
….+.*.+..
………..
………..
Example 6:
Example 7:
>>> print_snowflake(make_snowflake(2))
ValueError: n must be odd.
>>> print_snowflake(make_snowflake(5, regions=[(100, 5)]))
ValueError: A region had a starting point outside the bounds of the matrix.
5
Question 2 [20 points]
In this question, we will do further analysis of the conjectured ‘Vink sequence’ introduced in As-
signment 1. Recall that each term of the Vink sequence for k > 0 and starting term n > 0 is
n if n is even, or 3n + k if n is odd. We have already implemented the Vink sequence in A1, so 2
the function vink sequence is provided for you in the accompanying code. (Note that in A1 the function returned the number of terms until a 1 is reached – for this question, the provided function instead returns a list of the terms found until a 1 was reached; if 1 is not reached after j terms, then an empty list is returned. This modification will allow us to do more analysis of the sequence. Further, the parameter j is given the default value of 1000 and should not be modified.)
We will make three graphs using Matplotlib to analyze the Vink sequence. The code for each graph will be in its own function. At the start of each function, we will call plt.figure() to start a new graph. At the end of each function, we will return the special value plt.axes() – returning this value is usually not done when graphing, but it is necessary for our grading process, so please keep it there (it is already written for you).
Each graph has a specific title, label for y-axis, and label for x-axis. Further, after plotting, instead of showing the graphs tot the screen after plotting, they should instead be saved to a file, with the filename as specified below.
The three functions should be implemented as follows. Examples of how the graphs should look can be found on the next page.
Name: graph time to convergence
Parameters: A positive, non-zero integer max n.
What it should do: Plot a graph showing the number of terms it takes for the Vink sequence to converge to 1 for values of n in the range [1, max n] (inclusive). On the x-axis, we will have the values of n in said range, and on the y-axis, we will have the number of terms until a 1 is reached for that value of n. The graph title should be ‘Number of terms until convergence to 1 for n in [1, max n]’ where max n is replaced by the argument value. The y-label should be ‘Number of terms until convergence to 1’ and x-label should be ‘n’. The graph should be saved to the file ‘convergence maxn=max n.png’ where max n is replaced by the argument value.
Name: graph convergence of ks
Parameters: A positive, non-zero integer max k.
What it should do: Make a bar chart showing the number of values of n (in the range [0, 10000]) that converge to 1 (within 1000 terms) for odd values of k in the range [1, max k] (inclusive) (i.e., 1, 3, 5, …, max l). On the x-axis, we will have the values of k in said range, and the y-axis (height of each bar) will be the amount of values of n that converge to 1. The graph title should be ‘Convergence for values of k’, y-label ‘Number of n that converged to 1’ and x-label ‘k’. The graph should be saved to the file ‘convergence maxk=max k.png’ where max k is replaced by the argument value. Further, the k-value for each bar should be displayed under the bar.
6
Name: graph nums to 1
Parameters: A positive, non-zero integer max n.
What it should do: Make a plot showing the values of the terms of the Vink sequence until a 1 is reached, for every power of 2 in the range [2, max n] (inclusive), with k=1 and j=1000. That is, there should be one line plotted for each value of n, showing how the terms change until 1 is reached. The graph title should be ‘Convergence of n over time’, y-label ‘Term’ and x-label ‘Step number’. The graph should be saved to the file ‘numsto1 maxn=max n.png’ where max n is replaced by the argument value. Further, each line should have a different color, and a legend should show which line color corresponds to which value of n.
Filename
You must write this program in a file called vink.py.
Examples (as executed in Thonny)
Note that we show the image below each command, but your code should save each image to a file, not show it on-screen. You can then open the file (which will be in the same folder as your Python code file) to check if it resembles the figures below.
Example 1:
>>> graph_time_to_convergence(1000)
7
Example 2:
>>> graph_convergence_of_ks(8)
Example 3:
>>> graph_nums_to_1(2**10)
8
Question 3 [30 points]
Programming can be very useful because it can simulate real-world environments. In this question we will write some code to complete a Python simulation of a Wonkavator. A Wonkavator is like an elevator, but an elevator can only go up and down. A Wonkavator can go sideways, and slantways, and longways, and backways, amongst other things. In fact, it can take you to any room in an entire building.
We will simulate a building in which the Wonkavator will move around. The building will be represented by a 3D grid, where each coordinate in the grid represents a room. The Wonkavator can travel from room to room by moving at most 1 unit in any direction. For example, it could move from point (2, 3, 4) to point (2, 4, 5), by making a movement of (0, 1, 1). However, it is illegal to make a move from (1, 1, 1) to (3, 1, 1), as we can move a maximum of 1, not 2, in any direction. A move of (0, 0, 0) (i.e., staying in place) is also invalid. Further, it is invalid to move beyond the bounds of the grid (i.e., out of the building). If the Wonkavator is at coordinate (5, 5, 4), and the grid is of size 6x6x6, then it is invalid to move in the direction (1, 0, 0), as that would bring the Wonkavator out of the grid.
In the code provided to you, three classes are defined: Person, Factory and Wonkavator:
• The Person class defines a person inside the building. At the start of the simulation, each Person will be located at one particular (x, y, z) coordinate in the grid, and will want to travel to some other (x, y, z) coordinate. The Person class contains four attributes: the person’s name, their current position in the grid (represented as a Point3D object), their destination position in the grid (represented as a Point3D object), and finally a boolean variable indicating whether or not they have arrived at their destination yet.
• The Wonkavator class contains methods to move the Wonkavator and maintain the list of people currently inside. The Wonkavator must travel to each person’s (x, y, z) coordinate, moving by at most 1 in any dimension at a time (as described above). After picking up a person, it must deliver them to their destination (x, y, z) coordinate. (Note: The Wonka- vator doesn’t have to deliver a person right after picking them up; it could pick up multiple people before delivering all of them to their destinations.) Once a person has reached their destination, they remain there for the rest of the simulation. The Wonkavator class contains three attributes: its current position in the grid (represented as a Point3D object), the size of the factory (represented as a Point3D object), and a list of the people currently in the Wonkavator.
• The Factory class contains methods to run the simulation and display it to the screen. It also contains four attributes: the size of the factory (a Point3D object), a list of the people in the simulation (i.e., a list of Person objects), one object of type Wonkavator for the actual elevator, and finally an attribute relating to the Matplotlib visualization.
Much of the code for these three classes has already been provided to you in the given wonkavator.py file. Your job is to write one incomplete method of each of the three classes, as listed on the next page.
9
Name: init method of Person class
Parameters: In addition to self, a string name, Point3D object cur pos and Point3D object
dst pos.
What it should do: Create four attributes: name, cur pos, dst pos and arrived. The first three attributes should be assigned the values of the respective parameters, while the arrived attribute should be set to False.
Name: run method of Factory class
Parameters: No parameters (just self).
What it should do: This method is the main loop for the simulation. It checks to see if the elevator is currently in a room where there are people who want to enter the elevator, and/or if there are people in the elevator whose destination point is the current room and who thus want to leave the elevator.
If there is a person(s) who are in the same room as the elevator and need to be picked up, then, for each such person, the person enters method of the elevator attribute should be called, with the person passed as argument to the method. However, make sure that the person does need to be picked up and has not already arrived at their destination room (you can check the arrived method of the person – if it is True, then they should not be picked up as they have already arrived).
If there is a person(s) who are in the elevator and whose destination is the current room, and thus need to be dropped off in the room, the person leaves method of the elevator attribute should be called, with the person passed as argument to the method.
(Hint: Whenever writing a new method for a class, consider what attributes of the class you might need to use in the method. There may be many attributes, so it’s good to focus only on the ones you need. For example, here you may need to access the people attribute, perhaps using a for loop to go through each Person object in that list. You may also need to use in some way the people in elevator and cur pos attributes of the elevator attribute.)
Finally, the method should call the move method of the elevator attribute, and pass the list of people (self.people) as argument. (This line is already done for you.)
Name: choose direction method of Wonkavator class
Parameters: In addition to self, people: a list of Person objects
What it should do: This method tells the elevator in which direction to move, by returning a Point3D object with the direction to move in each dimension. The elevator can only move a maximum of 1 unit in any dimension, so each component of the direction must be either -1, 0, or 1. (Note that a direction of (0, 0, 0) is invalid as the elevator cannot stay in the same place, but a direction of (1, 1, -1) is fine.)
There is no constraint in how this method should be designed, but the simulation must end with all people taken to their destinations. Thus, the method should return a direction such that it moves
10
closer either to picking up a person or dropping off a person, so that in the end, the simulation can finish. (Hint: The get direction vector method of the Point3D class may be useful to you here. Given two Point3D objects x and y, calling x.get direction vector(y) will return a direction vector of one unit in each dimension from x moving towards y.)
Filename
You must write these methods in a file called wonkavator.py. The three methods are already defined for you, as are all the other methods of the classes – do not alter any code except for the three methods listed.
Examples (as executed in Thonny)
Once you complete the first method (the init method of the Person class), you will be able to run the code file in Thonny. When you run, you will see a visualization of the 3D grid on-screen. (This visualization uses Matplotlib!) The elevator will appear as a green dot and the people will appear as blue dots. As you write code for the other methods, you will see the elevator (green dot) begin to move around the grid. Once the elevator picks up a person, a red dot will appear on the grid, indicating the person’s destination. The red dot will disappear when the elevator travels to that location and drops off the person.
Here is a sample visualization:
(To stop the simulation and close the visualization window, press the Stop button in the Thonny toolbar.)
11
Question 4 [25 points]
The time has come for the first annual COMP 208 Pong AI tournament.
For this question, you will work on an AI for the game of Pong. You may work in teams of two for this question (and only this question) if you like, or you can work alone if you prefer. If you are looking for a teammate for this question, feel free to post on the course discussion boards. (If you decide to work with a partner, feel free to communicate through online methods like Skype.) However, please do not use this as an opportunity to code the other questions together. We will be running plagiarism detection software on all other assignment questions.
Requirements
This question asks you to write a method pong ai inside the PongAI class. This method will be repeatedly called for you in the provided Pong game. The method must return either the string ‘up’ or the string ‘down’, in order to move your AI’s paddle up or down, respectively. Your AI will be on the right-hand side of the board.
The pong ai method has three parameters.
• paddle rect: An object of type Rectf, which contains the attributes pos and size. pos is a tuple representing the upper-left (x, y) coordinate of your AI’s paddle (that is, paddle rect.pos[0] and paddle rect.pos[1]). size is also a tuple, representing the dimensions of your AI’s pad-
dle along the x and y-axis, respectively (that is, paddle rect.size[0] and paddle rect.size[1]).
• other paddle rect: An object of type Rectf, which contains the same attributes pos and size as above, but for your opponent’s paddle.
• ball rect: An object of type Rectf containing the attributes pos and size for the ball. Further, the class PongAI has one attribute that is already set for you in its initializer:
• table size: A tuple containing the dimensions of the table (board) along the x and y-axis, respectively (that is, table size[0] and table size[1]).
12
Pong is a real-time game, that is, the ball moves in real time. Thus, your pong ai method will also be called in real-time, every few milliseconds. The method must finish (return) in at most 0.3 ms after it was called; otherwise, your movement for those three milliseconds will be skipped. (You can measure the time it takes for your method to run by using the time module as seen in class.) Also, recall that third-party modules are not allowed (except pygame here).
The other player in the game (playing on the left-hand side) will be controlled by a simple AI called Chaser, whose code is also provided to you. The Chaser AI simply follows the y-coordinate of the ball: if the ball is higher than the paddle, the paddle will move down; if the ball is lower than the paddle, the paddle will move up. Your AI must make a demonstrable improvement over the Chaser AI in order to obtain full marks for this question. A demonstrable improvement is any win over the Chaser AI in at least 55 out of 100 games.
Hints
• With the parameters listed above, you can get an idea of where to move the paddle. For example, as described above, the Chaser AI uses the current paddle position and ball position to determine whether to move the paddle up or down. However, recall that the pong ai method is called every few milliseconds, each time with the updated location of the ball (and paddles). By storing a history of ball locations, you may be able to infer properties of the ball’s movement that can help your choice of whether to move the paddle up or down.
• Itmayalsobehelpfultoconsiderthepositionoftheopponent’spaddle(thesecondparameter).
• Try sketching out on paper a diagram of a Pong game and how different ball trajectories
might impact the optimal paddle position.
• It would be helpful to look through the given Pong game code (PongAIvsAI.py) to get a better understanding of the physics of the game (specifically, the get angle method of Paddle class and move method of Ball class. However, it is not necessary to read or understand the full game code.
How to test your AI
The first time you test your AI, you must do the following:
• Install the pygame third-party library, following the steps we saw in class regarding installation of third-party libraries
• Edit the file PongAIvsAI.py by commenting out line 437, and un-commenting line 449. This change will make the right-side paddle use the AI in your file. Or, you can un-comment line 443 instead of 449. This change will make a human able to control the right-side paddle instead of an AI (using the up and down arrow keys), which may be useful to get experience with the game before starting on your AI.
After doing these two steps, you may then test your AI by opening the PongAIvsAI.py file and running it in Thonny to start a new game.
13
Tournament format
If your AI performs better than the Chaser AI, it will be entered into the round-robin tournament. Each AI will face against each other using the original Pong game as given to you. Game settings (speed, etc.) will not be altered by default, but may change at our discretion for breaking ties.
Filename
You must write this program in a file called student ai.py. Other code is also provided to you: the pong game in PongAIvsAI.py and the Chaser AI in chaser ai.py. You do not have to include these two files in your submission. When we test your AI, we will use the original copies of these files, so please do not make any changes to them as they will not be used.
If you are working with a partner, you must each submit the same student ai.py file.
14