ASSIGNMENT #4: POLYMORPHISM AND DESIGN PATTERNS CS246, SPRING 2022
Assignment #4: Polymorphism and Design Patterns
Due Date 1: Monday , July 4th, 2022, 5:00 pm EST
Due Date 2: Friday, July 8th, 2022, 5:00 pm EST
• Relationships, Inheritance, and Polymorphism in C++
• STL vectors
• Decorator and Observer design patterns
• Questions 1, 2a, and 3a are due on Due Date 1; questions 2b, 3b, and 4 are due on Due Date 2.
• On this and subsequent assignments, you will take responsibility for your own testing. This assignment is designed to
get you into the habit of thinking about testing before you start writing your program. If you look at the deliverables
and their due dates, you will notice that there is no C++ code for Q2 and Q3 due on Due Date 1. Instead, you will be
asked to submit test suites for C++ programs that you will later submit by Due Date 2.
Test suites will be in a format compatible with that of the latter questions of Assignment 1, so if you did a good job
writing your runSuite script, that experience will serve you well here.
• Design your test suites with care; they are your primary tool for verifying the correctness of your code. Note that test
suite submission zip files are restricted to contain a maximum of 40 tests. The size of each input (.in) file is also
restricted to 500 bytes. This is to encourage you not to combine all of your testing eggs in one basket. There is also a
limit for each output file (.out), but none of your tests should be able to create such a large output file that you would
normally encounter it.
• You must use the standard C++ I/O streaming and memory management (MM) facilities on this assignment; you may
not use C-style I/O or MM. More concretely, you may #include the following C++ libraries (and no others!) for the
current assignment: iostream, fstream, sstream, iomanip, string, utility, stdexcept, and vector.
Marmoset will be set to reject submissions that use C-style I/O or MM, or libraries other than the ones specified above.
• For this assignment, you are not allowed to use the array (i.e., []) forms of new and delete. Further, the CXXFLAGS
variable in your Makefile must include the flag -Werror=vla. This means that you must use vectors instead of
variable-length arrays.
• We will manually check that you follow a reasonable standard of documentation and style, and to verify any assignment
requirements that are not automatically enforced by Marmoset. Code to a standard that you would expect from someone
else if you had to maintain their code. Further comments on coding guidelines can be found here:
https://www.student.cs.uwaterloo.ca/˜cs246/S22/codingguidelines.shtml
• We have provided some code and sample executables in the subdirectory a4. These executables have been compiled
in the CS student environment and will not run anywhere else.
Note: We suggest creating the directory ˜/cs246/s22/a4 and creating all of your assignment solutions in this directory.
Practice Question
Question 1 is a coding practice question and may be publicly discussed on Piazza. Students can publicly discuss solution
strategies so long as solutions are not revealed. Publicly sharing any part of your code is not allowed.
Page 1 of 8
ASSIGNMENT #4: POLYMORPHISM AND DESIGN PATTERNS CS246, SPRING 2022
Question 1
(20% of DD1) In this exercise you will write a C++ program that can mutate and update a number sequence composed of
addition, multiplication, subtraction, and division operations. Your program should define the sequence to have an initial value
of 0 and be defined by the following function (known as the identity function):
f(x) = x
Your program should read characters from standard input, where each of the following characters defines a command telling
your program to do something:
• ’s’ - if the character ’s’ is read your program should next read an int from the stream and reset the sequence being
maintained to the identify function with an initial value of the int read from stream.
• ’n’ - if the character ’n’ is read your program should update the sequence to the next number in the sequence and
print that value out.
• ’+’ - if the character ’+’ is read your program should next read an int readIn from the stream and add a new
operation to function that defines the sequence of adding readIn to the value. That is if your old sequence defining
function was f(x) then your new sequence defining function becomes g(x) = f(x) + readIn.
• ’*’ - if the character ’*’ is read your program should next read an int readIn from the stream and add a new
operation to function that defines the sequence of multiplying the value by that readIn. That is if your old sequence
defining function was f(x) then your new sequence defining function becomes g(x) = f(x) ∗ readIn.
• ’-’ - if the character ’-’ is read your program should next read an int readIn from the stream and add a new
operation to function that defines the sequence of subtracting readIn from the value. That is if your old sequence
defining function was f(x) then your new sequence defining function becomes g(x) = f(x) − readIn.
• ’/’ - if the character ’/’ is read your program should next read an int readIn from the stream and add a new
operation to function that defines the sequence of dividing the value by readIn. That is if your old sequence defining
function was f(x) then your new sequence defining function becomes g(x) = f(x)/readIn.
All arithmetic is done on integers. For example given the following input:
you would generate the following output:
Because after the command s 1 the function is set to f(x) = x and the current value is set to 1. The two n commands say to
apply f to the current value, update the current value to the result, and print it. However these each print 1 because f(1) = 1,
and thus f(f(1)) = f(1) = 1. Then after the command + 5 the function now becomes f(x) = x + 5 so the next two n
Page 2 of 8
ASSIGNMENT #4: POLYMORPHISM AND DESIGN PATTERNS CS246, SPRING 2022
commands produce 6 and 11. Then after the * 10 command the function becomes f(x) = (x + 5) ∗ 10 so the next two n
commands produces 160 and 1650.
Submission:
Due on Due Date 1: Submit a4q1.zip to Marmoset with all the source code files needed to build your program and a
Makefile that builds your program and names it a4q1.
Assessment Questions
Questions 2 to 4 are part of the coding assessment and may be publicly discussed on Piazza only for general clarifications.
Solutions cannot be publicly discussed nor revealed.
Question 2
(30% of DD1; 40% of DD2)
In this question you will be building a version of Conway’s Game of Life. The game of life is not really a “game”, but
rather an automaton that simulates the “life” and “death” of cells as they progresses between “generations” according to a set
of rules. In the game of life cells in a grid are either “alive” or “dead”, a given state of the grid is called a “generation”. Then
to progress to the next generation a set of rules for which cells will become alive or dead the next generation are followed and
the next generation is computed. In Conway’s Game of Life the rules are:
1. Any cell with fewer than two living neighbours dies (due to underpopulation).
2. Any cell with more than three living neighbours dies (due to overpopulation).
3. Any dead cell with exactly three live neighbours becomes a live cell (due to reproduction).
However, in our version of the Game Of Life not every cell in the grid must follow the exact same rules. Instead rules
can be added onto a cell at run time, and we will have some extra rules we can add to cells as well. Our rules will function
as follows, rule 1 applies to all cells, the rest have to be added on to cells at run time. That is, all cells in the grid follow
the underpopulation rule, all other rules are applied individually to cells. However, for convienience your program will also
provide the option to default all the cells to one type (and then additional rules can be added onto cells individually)
1) Only rule that applies to ALL cells: Any dead cell with exactly three live neighbours becomes a live cell, unless
another rule says it would die.
2) Any cell with fewer than two living neighbours dies.
3) Any cell with more than three living neighbours dies.
4) A periodic cell - this rule takes an additional integer parameter N denoting the period. When applied to the cell every N
generations it will flip its state (if it is dead on the Nth generation it will become alive, if it is alive it will become dead).
5) A friendly cell - this rule takes an additional integer parameter N denoting how many friends this cell likes to have. If
this cell is surrounded by exactly N neighbours then it will become (or stay) alive into the next generation.
The order the rules are added onto a cell matter. For example the “Friendly Cell” rule can directly conflict with the rules
about overpopulation and underpopulation. In the case of a conflict, whichever rule was more recently added takes precedence.
Since the rules can be added at runtime to change the behaviour of the cells, you are required to implement this using
the Decorator pattern. The test harness a4q2.cc simply instantiates a LifeGame object with a given width and height,
and calls the play() method on it. You must implement this class, as well as any other classes you need to properly design
your solution to match the behaviour required by the spec/sample executable. The play() method does the job of reading
input from the user. As such a skeleton for the method has been given, which you will need to fill in to make it work with
your implementation of the game. The comments in the skeleton explain the command structure for the game. However, the
commands are also listed below.
Page 3 of 8
ASSIGNMENT #4: POLYMORPHISM AND DESIGN PATTERNS CS246, SPRING 2022
• update command — if the user inputs the character u as a command this should update your Game of Life to the next
generation. That is, each cell in the game should become either dead or alive based on the rules applied to that cell.
• on command — if the user inputs the character o as a command then two integers x and y are read in and the the cell
located at (x, y) on the grid is turned on. The upper left corner of the grid represents (0,0) and the x-coordinates get
larger as you move right while the y-coordinates get larger as you move down. That is, the coordinate (2, 5) represents
the cell in the third column (x-coordinate of 2), and the sixth row (y-coordinate of 5).
• Rule two command — if the user inputs the character l as a command then two integers x and y are read in and the cell
located at (x, y) on the grid has rule two applied to it (it is decorated with a rule two object).
• Rule three command — if the user inputs the character a as a command then two integers x and y are read in and the
cell located at (x, y) on the grid as rule three applied to it (it is decorated with a rule three object).
• Rule four command — if the user inputs the character t as a command then two integers x and y are read in and the
cell located at (x, y) on the grid as rule four applied to it (it is decorated with a rule four object).
• Rule five command — if the user inputs the character f as a command then three integers x, y, and N are read in and
the cell located at (x, y) on the grid as rule five parameterized by N applied to it (it is decorated with a rule five object).
• default command — if the user inputs the character d as a command then you must read in characters until anything
other than a l, a, p, or f is read in (or an integer only if it immediately follows an f). Then, all cells in the grid must be
set to off and have the rules read in applied to them. That is, if the user inputes dla*, then all cells in the game are set
to dead and now follow rules 1, 2, and 3. Similarly, if the user inputs daf7-, then all cells in the game are set to dead
and now follow rules 1, 3, and 5 (parameterized with 7).
• print command — if the user inputs the character p as a command then the grid will be printed out as a 2D grid of
characters. Living cells should be printed as the character “X”, while dead cells should be printed as the period character
“.”.
• quit command — if the user inputs the character q as a command then the function will end.
Important: As the point of this assignment is to use the Decorator pattern, if your solution is found in handmarking to
not employ the decorator pattern your correctness marks will be reduced to a maximum of 50
Hints: Create a Cell abstract base class and have Decorator extend from that. As per the decorator pattern create a
BaseCell class which implements the basic behaviour (and also stores the variables you need). Include a Grid class that
stores your grid of Cells.
Note: Your program should be well documented and employ proper programming style. It should not leak memory.
Markers will be checking for these things.
Due on Due Date 1: Submit your test suite (suiteq2.txt and all necessary files) in the file a4q2a.zip.
Due on Due Date 2: Submit your solution in the file a4q2b.zip. You must include a Makefile, such that issuing the
command make will build your program. The executable should be called a4q2.
Page 4 of 8
ASSIGNMENT #4: POLYMORPHISM AND DESIGN PATTERNS CS246, SPRING 2022
Question 3
(50% of DD1; 50% of DD2)
In this problem, you will use C++ classes to implement the game of Reversi. (https://en.wikipedia.org/
wiki/Reversi). An instance of Reversi consists of an n × n-grid of cells, each of which can be either empty, black, or
white. When the game begins the middle 4 cells are populated following the pattern Black-White-Black-White. Reversi is a
two-player game where players take turns placing a piece of their colour in a cell. Black plays first. The goal of Reversi is to
have the most cells holding pieces of your colour at the end of the game. If a new piece A would form a line segment with
an existing piece B of the same colour, such that all of the cells in between are occupied and of the opposite colour, those
in-between pieces are flipped to the same colour as A and B. There is one slight difference from standard Reversi: whereas a
legal move in standard Reversi must cause at least one flip, your program is not required to enforce this rule. This means that
on any turn players can play a piece on any cell, so long as that cell is within the grid and not currently occupied by another
piece.
To implement the game, you will use the following classes:
• class Subject — abstract base class for subjects (see provided subject.h);
• class Observer — abstract base class for observers (see provided observer.h);
• class Cell — implements a single cell in the grid (see provided cell.h);
• class Grid — implements a two-dimensional grid of cells (see provided grid.h);
• struct State — provides a representation of a cells state (see provided state.h);
• class TextDisplay — keeps track of the character grid to be displayed on the screen (see provided textdisplay.h);
• file info.h structure definition for queries issued by the observer on the subject.
Note: you are not allowed to change the public interface of these classes (i.e., you may not add public fields or methods),
but you may add private fields or methods if you want.
Your solution to this problem must employ the Observer pattern. Each cell of the grid is an observer of all of its neighbours
(that means that class Cell is its own observer). Thus, when the grid calls notifyNeighbours on a given cell, that cell
must then call the notify method on each of its neighbours (each cell is told who its neighbours are when the grid is
initialized). Moreover, the TextDisplay class is an observer of every cell (this is also set up when the grid is initialized).
A subject’s collection of observers does not distinguish what kinds of observers are actually in the collection (so a cell could
have arbitrary cells or displays subscribed to it). When the time comes to notify observers, you just go through the collection
and notify them.
As a hint for implementation, consider how the rules of the game above can be replicated using an observer pattern where
a notification can either be a notification of a new piece, a relay of that new piece message, or a reply to that new piece being
found. A cell that receives a new piece can notify its observers (adjacent cells) that it has received a new piece of a certain
colour. The cells notified of a new piece by their neighbour can relay that message along the line. When a message is received
by a cell that contains the same colour piece as the new piece, it can reply back in a similar fashion. Hence, when a piece
matching the colour of the new piece is reached, the message stops relaying and instead replies back. Similarly if there are no
pieces in a cell to relay a message then it should stop. Since the observer pattern doesn’t distinguish what observers are in the
collection the cell receiving a new piece can’t send out specific information about the direction of each line to its appropriate
neighbours. However, when a neighbour receives a notification of a new piece they can check the information passed along
and determine what direction they are from the original piece, and relay that information along. For more information on these
messages see the state.h file provided to you.
You are to overload operator<< for the text display, such that the entire grid is printed out when this operator is invoked.
Each empty cell prints as - and a cell with a white or black piece prints as W or B respectively. Further, you are to overload
operator<< for grids, such that printing a grid invokes operator<< for the text display, thus making the grid appear on
the screen.
When you run your program, it will listen on stdin for commands. Your program must accept the following commands:
• new n Creates a new n × n grid,where n ≥ 4 ∧ n ≡ 0 (mod 2). If there was already an active grid, that grid is
destroyed and replaced with the new one. When setting up the new grid your program should intialize the middle 4
squares following the Black-White-Black-White pattern.
Page 5 of 8
ASSIGNMENT #4: POLYMORPHISM AND DESIGN PATTERNS CS246, SPRING 2022
• play r c Within a game, plays a piece at row r, column c of the colour corresponding to the player who’s move it
is. If the row and column entered correspond to a cell that already has a piece, or a position outside the grid, then the
input is ignored and nothing is done.
The program ends when the input stream is exhausted, or when the game is over. The game is over when there are no more
empty cells on the grid.,
When the game is over, if the black player wins the program should display Black Wins! to stdout before terminating;
if the white player wins it should display White Wins!; otherwise it should display Tie!. If input was exhausted before
the game was won or lost, it should display nothing. A sample interaction follows (responses from the program are in italics):
Note: Your program should be well documented and employ proper programming style. It should not leak memory.
Markers will be checking for these things.
Due on Due Date 1: Submit your test suite (suiteq3.txt and all necessary files) in the file a4q3a.zip.
Due on Due Date 2: Submit your solution. You must include a Makefile, such that issuing the command make will build
your program. The executable should be called a4q3.
Page 7 of 8
ASSIGNMENT #4: POLYMORPHISM AND DESIGN PATTERNS CS246, SPRING 2022
Question 4
(10% of DD2) Note: there is no sample executable for this problem, and no Marmoset tests. This problem will be
entirely hand-marked. In this problem, you will adapt your solution from problem 3 to produce a graphical display. You are
provided with a class Xwindow (files window.h and window.cc), to handle the mechanics of getting graphics to display.
Declaring an Xwindow object (e.g., Xwindow xw;) causes a window to appear. When the object goes out of scope, the
window will disappear (thanks to the destructor). The class supports methods for drawing rectangles and printing text in five
different colours. For this assignment, you should only need black, white, and blue rectangles. In the graphical representation
let blue represent an empty cell, black represent a cell containing a piece from the black player, and white represent a cell
containing a piece from the white player. To do so you must complete the following tasks:
• Create a GraphicsDisplay class as a subclass of the abstract base class Observer, and register it as an observer
of each cell object.
• The class GraphicsDisplay will be responsible for mapping the row and column numbers of a given cell object to
the corresponding coordinates of the squares in the window.
• Your GraphicsDisplay class should have a composition relationship with Xwindow. So your constructor for
GraphicsDisplay should also create a Xwindow object which is a member of the GraphicsDisplay class.
Each time a new game is created you should create a new GraphicsDisplay to set up an appropriate window for
the game size.
• Your cell objects should not have to change at all.
The window you create should be of size 500×500, which is the default for the Xwindow class. The larger the grid you
create, the smaller the individual squares will be.
Note: to compile this program, you need to pass the option -lX11 to the compiler at link time. Note that is a hyphen,
lowercase L, uppercase X, and 11. For example:
g++ -std=c++14 *.o -o a4q4 -lX11
This option is not relevant during compilation, so it should not be put in your CXXFLAGS variable. You should only use it
during the linking stage, i.e., the command that builds your final executable.
Note: Your program should be well documented and employ proper programming style. It should not leak memory (note,
however, that the given Xwindow class leaks a small amount of memory; this is a known issue). Markers will be checking
for these things.
Due on Due Date 2: Submit your solution. You must include a Makefile, such that issuing the command make will build
your program. The executable should be called a4q4.