微信客服：xiaoxionga100
微信客服：ITCS521
A2-csc148代写
时间：2023-03-30
2023/3/29 20:56 A2 — Treemaps: CSC148H1S 20231 (All Sections): Introduction to Computer Science
https://q.utoronto.ca/courses/292974/pages/a2-treemaps 1/14
A2 — Treemaps
Due date: Tuesday, April 4th, at 1:00 pm sharp.
You may complete this assignment individually or with a partner, who can be from any section of
the course.
FAQ
Please make sure to check the A2 FAQ post on piazza
(https://piazza.com/class/lci0mq5wy287iw/post/1192) . Clarifications and answers to common
questions will be posted there.
Grade Breakdown
Category Weight
python TA 10
self tests 20
hidden
tests
70
Learning goals
After completing this assignment, you will be able to:
model different kinds of real-world hierarchical data using trees
implement recursive operations on trees (both non-mutating and mutating)
implement an algorithm to generate a geometric tree visualisation called a treemap
use the os library to write a program that interacts with your computer’s file system
use inheritance to design classes according to a common interface
Introduction
As we’ve discussed in class, trees are a fundamental data structure used to model hierarchical
data. Often, a tree represents a hierarchical categorization of a base set of data, where the leaves
represent the data values themselves, and internal nodes represent groupings of this data. Files
on a computer can be viewed this way: regular files (e.g., PDF documents, video files, Python
source code) are grouped into directories, which are then grouped into larger directories, etc.
Sometimes the data in a tree has some useful notion of size. For example, in a tree representing
the departments of a company, the size of a node could be the dollar amount of all sales for that
department, or the number of employees in that department. Or in a tree representing a
computer’s file system, the size of a node could be the size of the file.
2023/3/29 20:56 A2 — Treemaps: CSC148H1S 20231 (All Sections): Introduction to Computer Science
https://q.utoronto.ca/courses/292974/pages/a2-treemaps 2/14
A treemap (http://en.wikipedia.org/wiki/Treemapping) is a visualisation technique to show a
tree’s structure according to the weights (or sizes) of its data values. It uses rectangles to show
subtrees, scaled to reflect the proportional sizes of each piece of data.
Treemaps are used in many contexts. Among the more popular uses are news headlines, various
kinds of financial information, and computer disk usage. Some free programs use treemaps to
visualize the size of files on your computer; for example:
WinDirStat (http://portableapps.com/apps/utilities/windirstat_portable) for Windows
Disk Inventory X (http://www.derlien.com/) for MacOS
KDirStat (http://kdirstat.sourceforge.net/) for Linux
For this assignment, you will write an interactive treemap visualisation tool that you can use to
visualize hierarchical data.
It will have a general API (implemented with inheritance, naturally!) and you will define specific
subclasses that will allow you to visualize different kinds of data.
And with that, let’s get started on your final CSC148 assignment!
Task 0: Getting started
1. Download and unzip the starter code (a2_starter_files.zip
(https://q.utoronto.ca/courses/292974/files/25399282?wrap=1)
(https://q.utoronto.ca/courses/292974/files/25399282/download?download_frd=1) ) into your
directory for Assignment 2.
2. With tm_trees.py open, take the time to read through the tasks below to get a sense of what
code you’ll be writing throughout this assignment.
3. Familiarize yourself with the following coding guidelines:
You may NOT define any new public or private attributes.
You are always free to define private helpers (functions or methods).
Complete docstrings are not required for any helpers that you define or for methods that
you override or extend, but you are encouraged to take the time to write them.
Task 1: TMTree basics
In this task, you will implement:
TMTree.__init__
TMTree.is_displayed_tree_leaf
TMTree.get_path_string
In order to use a treemap to visualize data, we first need to define our tree structure and be able
to initialize it. For this program, you will develop a TMTree class to define the basic functionality
required by the provided treemap visualizer. To visualize any specific hierarchical dataset, we
simply need to define a subclass of TMTree , which we will do later.
2023/3/29 20:56 A2 — Treemaps: CSC148H1S 20231 (All Sections): Introduction to Computer Science
https://q.utoronto.ca/courses/292974/pages/a2-treemaps 3/14
The TMTree class is similar to the basic Tree class that you have already worked with, but with
some differences. A few of the most conceptually important ones are discussed here.
First, the class has a data_size instance attribute that is used by the treemap algorithm to
determine the size of the rectangle that represents this tree. data_size is defined recursively
as follows:
If the tree is a single leaf, its data_size is some measure of the size of the data being
modelled. For example, it could be the size of a file.
If the tree has one or more subtrees, its data_size is equal to the sum of the data_size s of
its subtrees, plus some additional size of its own.
Second, the class not only stores its subtrees, but it also stores its parent as an attribute. This
allows us to traverse both up and down the tree, which you will see is necessary when we
want to mutate the tree.
Third, we’ll also track some information inside our tree related to how to display it. More on
this shortly.
Fourth, we don’t bother with a representation for an empty TMTree , as we’ll always be
visualizing non-empty trees in this assignment.
To get started, you should do the following:
1. Complete the initializer of TMTree according to its docstring. This will get you familiar with the
attributes in this class.
2. Implement the is_displayed_tree_leaf method according to its docstring and the definition of
the displayed-tree (see below).
3. Implement the get_path_string method according to its docstring.
In the subsequent parts of this assignment, your program will allow the user to interact with the
visualizer to change the way the data is displayed to them. At any one time, parts of the tree will
be displayed and others not, depending on what nodes are expanded.
We’ll use the terminology displayed-tree to refer to the part of the data tree that is displayed in
the visualizer. It is defined as follows:
The root of the entire tree is in the displayed-tree.
For each “expanded” tree in the displayed-tree, its children are in the displayed-tree.
The trees whose rectangles are displayed in the visualization will be the leaves of the displayed-
tree. A tree is a leaf of the displayed-tree if it is not expanded, but its parent is expanded. Note
that the root node is a leaf of the displayed-tree if it is not expanded.
We will require that (1) if a tree is expanded, then its parent is expanded, and (2) if a tree is not
expanded, then its children are not expanded. Note that this requirement is naturally encoded as
a representation invariant in the TMTree class.
Note: the displayed-tree is not a separate tree! It is just the part of the data tree that is displayed.
2023/3/29 20:56 A2 — Treemaps: CSC148H1S 20231 (All Sections): Introduction to Computer Science
https://q.utoronto.ca/courses/292974/pages/a2-treemaps 4/14
Progress check!
After this step is done, you should be able to instantiate and print a TMTree , as is done in the
provided main block of tm_trees.py .
In the next task, you will implement the code required for the treemap algorithm.
Task 2: The Treemap algorithm
In this task, you will implement:
TMTree.update_rectangles
TMTree.get_rectangles
The next component of our program is the treemap algorithm itself. It operates on the data tree
and a 2-D window to fill with the visualization, and generates a list of rectangles to display, based
on the tree structure and data_size attribute for each node.
For all rectangles in this program, we’ll use the pygame representation of a rectangle, which is
a tuple of four integers (x, y, width, height) , where (x, y) represents the upper-left corner of the
rectangle. Note that in pygame, the origin is in the upper-left corner and the y-axis points down.
So, the lower-right corner of a rectangle has coordinates (x + width, y + height). Each unit on both
axes is a pixel on the screen. Below, we show a grid representing the rectangle (0, 0, 8, 4) :
We are now ready to see the treemap algorithm.
Note: We’ll use “size” to refer to the data_size attribute in the algorithm below.
Input: An instance of TMTree , which is part of the displayed-tree, and a pygame rectangle (the
display area to fill).
Output: A list of pygame rectangles and each rectangle’s colour, where each rectangle
corresponds to a leaf in the displayed-tree for this data tree, and has area proportional to the
leaf’s data_size .
Treemap Algorithm:
Note I: Unless explicitly written as “displayed-tree”, all occurrences of the word “tree” below refer
to a data tree.
Note II: (Very Important) The overall algorithm, as described, actually corresponds to the
combination of first calling TMTree.update_rectangles to set the rect attribute of all nodes in the
2023/3/29 20:56 A2 — Treemaps: CSC148H1S 20231 (All Sections): Introduction to Computer Science
https://q.utoronto.ca/courses/292974/pages/a2-treemaps 5/14
tree and then later calling TMTree.get_rectangles to actually obtain the rectangles and colours
corresponding to only the displayed-tree’s leaves.
1. If the tree is a leaf in the displayed-tree, return a list containing just a single rectangle that
covers the whole display area, as well as the colour of that leaf.
2. Otherwise, if the display area’s width is greater than its height: divide the display area into
vertical rectangles (by this, we mean the x-coordinates vary but the y-coordinates are fixed),
one smaller rectangle per subtree of the displayed-tree, in proportion to the sizes of the
subtrees (don’t use this tree’s data_size attribute, as it may actually be larger than the sizes of
the subtrees because of how we defined it!)
Example: suppose the input rectangle is (0, 0, 200, 100), and the displayed-tree for the input
tree has three subtrees, with sizes 10, 25, and 15.
The first subtree has 20% of the total size, so its smaller rectangle has width 40 (20% of
200): (0, 0, 40, 100).
The second subtree should have width 100 (50% of 200), and starts immediately after the
first one: (40, 0, 100, 100).
The third subtree has width 60, and takes up the remaining space: (140, 0, 60, 100).
Note that the three rectangles’ edges overlap, which is expected.
3. If the height is greater than or equal to the width, then make horizontal rectangles (by this, we
mean the y-coordinates vary, but the x-coordinates are fixed) instead of vertical ones, and do
the analogous operations as in step 2.
4. Recurse on each of the subtrees in the displayed-tree, passing in the corresponding smaller
rectangle from step 2 or 3.
Important: To ensure that you understand the treemap algorithm, complete the A2 release
activity (https://q.utoronto.ca/courses/292974/assignments/963601) , double-check your answers
(https://q.utoronto.ca/courses/292974/files/25397463?wrap=1)
(https://q.utoronto.ca/courses/292974/files/25397463/download?download_frd=1) , and ask clarifying
questions as needed.
Note about rounding: because you’re calculating proportions here, the exact values will often be
floats instead of integers. For all but the last rectangle, always truncate the value (round down to
the nearest integer). In other words, if you calculate that a rectangle should be (0, 0, 10.9, 100),
“round” (or truncate) the width down to (0, 0, 10, 100). Then a rectangle below it would start at (0,
100), and a rectangle beside it would start at (10, 0).
However, the final (rightmost or bottommost) edge of the last smaller rectangle must always be
equal to the outer edge of the input rectangle. This means that the last subtree might end up a bit
bigger than its true proportion of the total size, but that’s okay for this assignment.
2023/3/29 20:56 A2 — Treemaps: CSC148H1S 20231 (All Sections): Introduction to Computer Science
https://q.utoronto.ca/courses/292974/pages/a2-treemaps 6/14
Important followup to Note II above: You will implement this algorithm in the
update_rectangles method in TMTree . Note that rather than returning the rectangles for only
the leaves of the displayed-tree, the code will instead set the rect attribute of each node in
the entire tree to correspond to what its rectangle would be if it were a leaf in the
displayed-tree. Later, we can retrieve the rectangles for only the leaf nodes of the
displayed-tree by using the get_rectangles method.
Note: Sometimes a TMTree will be sufficiently small that its rectangle has very little area (it has a
width or height very close to zero). That is to be expected, and you don’t need to do anything
special to deal with such cases. Just be aware that sometimes you won’t be able to actually see
all the displayed rectangles when running the visualizer, especially if the window is small.
Tips: For the recursive step, a good stepping stone is to think about when the tree has height 2,
and each leaf has the same data_size value. In this case, the original rectangle should be
partitioned into equal-sized rectangles.
Warning: make sure to follow the exact rounding procedure in the algorithm description above. If
you deviate from this, you might get slightly incorrect rectangle bounds.
Important: The docstring of the get_rectangles method refers to the displayed-tree. For now, the
whole tree is the displayed-tree, as all trees start expanded. Make sure that you come back later
and further test this method on trees where the displayed-tree is a subset of the full data tree to
ensure that your code is fully correct.
Progress check!
Note that the basic treemap algorithm does not require pygame or the visualizer at all! You can
check your work simply by instantiating a TMTree object, calling update_rectangles on it, then
calling get_rectangles to see the list of rectangles returned.
This is primarily how we’ll be testing your implementation of the treemap algorithm!
At this point, you can now run treemap_visualiser.py and see your treemap. By default, it will
display the example from the worksheet, which should look something like below (with random
colours of course). Note: the bar across the bottom is where the path string of the selected
rectangle will appear once you complete the next task.
2023/3/29 20:56 A2 — Treemaps: CSC148H1S 20231 (All Sections): Introduction to Computer Science
https://q.utoronto.ca/courses/292974/pages/a2-treemaps 7/14
Next, you will implement the method necessary to enable the selection of rectangles in the
visualizer.
Task 3: Selecting a tree
In this task, you will implement:
TMTree.get_tree_at_position
The first step to making our treemap interactive is to allow the user to select a node in the tree. To
do this, complete the body of the get_tree_at_position method. This method takes a position on
the display and returns the displayed-tree leaf corresponding to that position in the treemap.
IMPORTANT: Ties should be broken by choosing the rectangle on the left for a vertical boundary,
or the rectangle above for a horizontal boundary. That is, you should return the first leaf of the
displayed-tree that contains the position, when traversing the tree in the natural order.
In the visualizer, the user can click on a rectangle to select it. The text display updates to show
two things:
the selected leaf’s path string returned by the get_path_string method.
the selected leaf’s data_size
Clicking on the same rectangle again unselects it. Clicking on a different rectangle selects that
one instead.
Reminder: Each rectangle corresponds to a leaf of the displayed-tree, so we can only select
leaves of the displayed-tree.
Progress check!
Try running the program and then click on a rectangle on the display. You should see the
information for that displayed-tree leaf shown at the bottom of the screen, and a box appear
around the selected rectangle. Click again to unselect that rectangle, and try selecting another
one. Note that you will also see a thinner box appear around any rectangle that you hover over in
the display.
For the worksheet example, it should look something like the below, if you have selected
rectangle “d” and are not hovering over any rectangle:
2023/3/29 20:56 A2 — Treemaps: CSC148H1S 20231 (All Sections): Introduction to Computer Science
https://q.utoronto.ca/courses/292974/pages/a2-treemaps 8/14
Note: As you run the visualizer, you will see output in the python console in PyCharm. This output
is to help you see what events are being executed. You may find this information useful when
debugging your code. Feel free to modify anything that is being printed in treemap_visualiser.py if
you find it helpful to do so.
Task 4: Making the display interactive
In this task, you will implement:
TMTree.expand
TMTree.expand_all
TMTree.collapse
TMTree.collapse_all
TMTree.move
TMTree.change_size
Note: Unless explicitly written as “displayed-tree”, all occurrences of the word “tree” below refer to
a data tree.
Now that we can select nodes, we can move on to making the treemap more interactive.
In addition to displaying the treemap, the pygame graphical display responds to a few different
events (by event, we mean the user presses a key, hovers, or clicks on the window). The first
such event was actually clicking on a rectangle to select it, which we implemented in the previous
task. We will now implement the rest of the actions associated with events, by implementing
methods in the TMTree class which the visualizer calls:
a. The user can close the window and quit the program by clicking the X icon (like any other
window).
No additional code required.
b. The user can resize the window by clicking and dragging a corner or side of the window (like
any other resizable window).
No additional code required.
The next four events change which rectangles are included in the displayed-tree.
2023/3/29 20:56 A2 — Treemaps: CSC148H1S 20231 (All Sections): Introduction to Computer Science
https://q.utoronto.ca/courses/292974/pages/a2-treemaps 9/14
c. If the user selects a rectangle, and then presses e , the tree corresponding to that rectangle is
expanded in the displayed-tree. If the tree is a leaf in the data tree, nothing happens, since we
can’t expand a leaf. When a tree is expanded, the visualization will make the first subtree of
the newly expanded tree the new selected tree.
implement TMTree.expand
d. If the user selects a rectangle, and then presses c , the parent of that tree is unexpanded (or
“collapsed”) in the displayed-tree. (Note that since rectangles correspond to leaves in the
displayed-tree, it is the parent that needs to be unexpanded.) If the parent is None because
this is the root of the whole tree, nothing happens. When a tree is collapsed, the visualization
will make its parent tree the new selected tree, as it is now a leaf of the displayed-tree.
implement TMTree.collapse
e. If the user selects a rectangle, and then presses a , the tree corresponding to that rectangle,
as well as all of its subtrees, are expanded in the displayed-tree. If the tree is a leaf, nothing
happens. When a tree is expanded in this way, the visualization will make the “last” subtree of
the newly expanded trees the new selected tree. Note: The docstring for the relevant method
clarifies what we mean by “last”.
implement TMTree.expand_all
f. If the user selects any rectangle, and then presses x , the entire displayed-tree is collapsed
down to just a single tree node. If the displayed-tree is already a single node, nothing
happens. When a tree is collapsed in this way, the visualization will make this single tree node
the new selected tree, as it is now the only leaf of the displayed-tree.
implement TMTree.collapse_all
The following two events allow the user to actually mutate the data tree, and see the changes
reflected in the display.
g. If the user presses the Up Arrow or Down Arrow key when a rectangle is selected, the
selected node’s data_size increases or decreases by 1% of its current value, respectively.
Note: This affects the data_size of its ancestors as well, given our definition of data_size !
implement TMTree.change_size
Details:
A node’s data_size cannot decrease below 1. There is no upper limit on the value of
data_size . Just keep in mind that if a node is too large, then other nodes will appear relatively
small in the visualization!
If a node has children, its data_size cannot decrease below the sum of its child data sizes.
The 1% amount is always “rounded up” before applying the change. For example, if a leaf’s
data_size value is 140, then 1% of this is 1.4, which is “rounded up” to 2. So its value could
increase up to 152 142, or decrease down to 148 138. (Note: the docstring for the relevant
method provides similar clarification.)
h. If the user selects a rectangle, then hovers the cursor over another rectangle and presses m ,
the selected node should be moved to be the last subtree of the node being hovered over.
Remember: we can only select and hover over leaves of the displayed-tree.
2023/3/29 20:56 A2 — Treemaps: CSC148H1S 20231 (All Sections): Introduction to Computer Science
https://q.utoronto.ca/courses/292974/pages/a2-treemaps 10/14
implement TMTree.move
Very Important: Whenever you modify a tree’s data_size , the data_size attributes of all its
ancestors need to be updated too! You must make use of the parent_tree attribute to do this: it’s
a widely-used technique for traversing up a tree (this should feel a lot like traversing a linked list!).
Progress check!
At this point, your visualizer should be fully functional!
One of the nice things about code with an interactive display is that it’s usually pretty
straightforward to test basic correctness.
Try running the treemap visualizer, and see if you can resize, move rectangles, and manipulate
the displayed-tree as outlined above.
Of course, you can also write pytests to check the correctness of the methods you have written
too!
Next, we’ll write code to allow us to visualize the files on your computer!
Task 5: File System Data
In this task, you will implement:
path_to_nested_tuple
dir_tree_from_nested_tuple
You will also:
override any methods necessary for your subclasses of TMTree to behave as specified below.
decide on an appropriate inheritance hierarchy for the FileTree and DirectoryTree classes.
Consider a directory on your computer (e.g., the assignments directory you have in your csc148
directory). It contains a mixture of other directories (“subdirectories”) and some files; these
subdirectories themselves contain other directories, and even more files! This is a natural
hierarchical structure, and can be represented by a tree.
The _name attribute will always store the name of the directory or file (e.g. preps or prep8.py ), not
its path; e.g., /Users/courses/csc148/preps/prep8/prep8.py .
The data_size attribute of a file is simply how much space (in bytes) the file takes up on the
computer. Note: to prevent empty files from being represented by a rectangle with zero area, we
will always add a +1 to file sizes. The data_size of a directory corresponds to the size of all files
contained in the directory, including its subdirectories. As with files, we’ll also add a +1 to directory
sizes for this assignment.
In our code, we will represent this filesystem data using the FileTree and DirectoryTree classes.
1. Complete the path_to_nested_tuple function according to its docstring.
2023/3/29 20:56 A2 — Treemaps: CSC148H1S 20231 (All Sections): Introduction to Computer Science
https://q.utoronto.ca/courses/292974/pages/a2-treemaps 11/14
2. Complete the dir_tree_from_nested_tuple function. This function is the public interface for how
we will create DirectoryTree objects to test your code for correctness.
3. Override or extend methods from TMTree , as appropriate, in the FileTree and DirectoryTree
classes. You will need to decide if you can just use the inherited methods as they are or not
(see additional requirements below).
To complete step 1, you will need to read the Python os module documentation
(https://docs.python.org/3/library/os.html) to learn how to get data about your computer’s files in a
Python program. You may also find the provided print_dirs.py to be a useful example to base
your implementation on.
We recommend using the following functions:
os.path.isdir
os.path.join
os.path.getsize
os.path.basename
os.listdir (see note below)
Note: Since the order that os.listdir returns file names is dependent on your operating
system, we have provided a helper, ordered_listdir which you MUST use in your
implementation. You MUST add the subtrees in the order they are produced from
ordered_listdir .
You may NOT use the os.path.walk function — it does a lot of the recursive work for you, which
defeats the purpose of this part!
Warning: Make sure to either use os.path.join (recommended) or make use of string
concatenation and the os.sep string to build larger paths from smaller ones, because different
operating systems use different separators for file paths.
Requirements for step 3:
FileTree objects can be resized in exactly the same way as TMTree objects, while
DirectoryTree objects can NOT be resized. Attempting to change the size of a directory should
raise an OperationNotSupportedError .
We can only move files and directories into a directory. Attempting to move a file or directory
into a file should raise an OperationNotSupportedError , as demonstrated in the doctests for the
DirectoryTree class. Also note that, since every event is designed for use with the visualizer,
you can only perform moves between leaves of the displayed-tree.
Ensure your code is consistent with any other behaviour demonstrated in the provided
doctests for the DirectoryTree class.
If you decide you would like an additional class in your hierarchy, you are free to define a new
class.
Progress check!
2023/3/29 20:56 A2 — Treemaps: CSC148H1S 20231 (All Sections): Introduction to Computer Science
https://q.utoronto.ca/courses/292974/pages/a2-treemaps 12/14
You should now be able to instantiate a DirectoryTree by first calling path_to_nested_tuple on a
path and then calling the dir_tree_from_nested_tuple function on the result. You can then inspect
the tree’s contents in the debugger or print it, as is done in the main block.
You can also try running the treemap visualizer and confirm that it works as expected for the file
system version. In the main block, you can toggle which visualizer is run by changing which of the
RUN_OPTIONS is chosen.
One more dataset to go!
Task 6: Chess!
In this task, you will implement:
moves_to_nested_dict
ChessTree.__init__
You will also:
override or extend any methods necessary for ChessTree to behave as specified below.
Our last dataset consists of games extracted from a database of chess games played by
WGMs. While you don’t have to know the exact rules of chess for this part, there are a few
important things to note:
a game consists of a sequence of moves
“white” goes first and “black” goes second, with the two players continuing to take alternating
turns until the game ends.
Each move can be represented by a code indicating which piece was moved and where it
moved to.
the games can potentially end at any time, with some games taking less than 10 moves and
others taking 100 or more.
For those interested, moves are represented as strings in the format ‘{from square}{to square}’
e.g. ‘e2e4’ is the move from square e2 to square e4. This format is known as algebraic notation
(https://en.wikipedia.org/wiki/Algebraic_notation_(chess)) if you are interested, but you don’t
need to know anything about the format to complete the assignment.
Note: you should assume the games consist of only valid moves, so do not attempt to do
any verification of this yourself.
Below is an example of what the data (a list of a list of games) looks like. This is a subset of the
games in the provided wgm_10.json , with … denoting omitted moves / games for purposes of
conciseness.
[
['e2e4', 'e7e6', 'd2d4', 'd7d5', 'b1d2', ..., 'f5f7'],
['d2d4', 'g8f6', 'g1f3', 'g7g6', 'c2c4', ..., 'd7d6'],
...
['e2e4', 'c7c6', 'd2d4', 'd7d5', 'e4e5', ..., 'd5f7']
]
2023/3/29 20:56 A2 — Treemaps: CSC148H1S 20231 (All Sections): Introduction to Computer Science
https://q.utoronto.ca/courses/292974/pages/a2-treemaps 13/14
Similar to the filesystem data initialization process, we will again have you do this in two steps:
1. Implement the moves_to_nested_dict function according to its docstring.
2. Implement the initializer for ChessTree according to its docstring.
A few important notes about the structure:
The root node should be the string '-'
The children of the root node should be all moves that occur as the first move of at least one
game.
The children of all deeper moves should be the moves that follow the move represented by
the parent move in at least one game.
We also need to update the functionality of our ChessTree class to reflect what events should be
ignored for this new kind of data. In particular, given the interpretation of the nodes, we don’t want
to support either changing the sizes of nodes or moving nodes. As you did with the file system
related subclasses, appropriately override the relevant methods in a way consistent with the
provided code.
Progress check!
You should now be able to instantiate a ChessTree as is done in the main block.
You should also be able to run the visualizer on one of the three provided json files containing
games of chess. In the visualizer code, you can choose which data file to open.
For example, if you visualize the games from wgm_200.json , fully collapse the displayed-tree,
expand once, and then select the largest rectangle (which should correspond to 145 games), the
treemap should look something like the below. Note, depending on how exactly you read in the
games and construct the tree, the rectangles may appear in a different order, which is perfectly
fine.
You can also try using the ‘o’ key on a selected ChessTree . This should open a website with the
chess position shown corresponding to the move sequence of the selected tree!
And that’s it!
2023/3/29 20:56 A2 — Treemaps: CSC148H1S 20231 (All Sections): Introduction to Computer Science
https://q.utoronto.ca/courses/292974/pages/a2-treemaps 14/14
Submission instructions
1. Login to MarkUs and create a group for the assignment (or specify that you’re working alone).
2. Run your code one more time locally to ensure that it runs.
3. Upload tm_trees.py to MarkUs.
4. Run the self-tests on MarkUs and read through the test output to avoid any silly
mistakes.
5. Congratulations, you are finished with your last assignment in CSC148! Go have some
chocolate or do a cartwheel. :)
https://q.utoronto.ca/courses/292974/pages/a2-treemaps 1/14
A2 — Treemaps
Due date: Tuesday, April 4th, at 1:00 pm sharp.
You may complete this assignment individually or with a partner, who can be from any section of
the course.
FAQ
Please make sure to check the A2 FAQ post on piazza
(https://piazza.com/class/lci0mq5wy287iw/post/1192) . Clarifications and answers to common
questions will be posted there.
Grade Breakdown
Category Weight
python TA 10
self tests 20
hidden
tests
70
Learning goals
After completing this assignment, you will be able to:
model different kinds of real-world hierarchical data using trees
implement recursive operations on trees (both non-mutating and mutating)
implement an algorithm to generate a geometric tree visualisation called a treemap
use the os library to write a program that interacts with your computer’s file system
use inheritance to design classes according to a common interface
Introduction
As we’ve discussed in class, trees are a fundamental data structure used to model hierarchical
data. Often, a tree represents a hierarchical categorization of a base set of data, where the leaves
represent the data values themselves, and internal nodes represent groupings of this data. Files
on a computer can be viewed this way: regular files (e.g., PDF documents, video files, Python
source code) are grouped into directories, which are then grouped into larger directories, etc.
Sometimes the data in a tree has some useful notion of size. For example, in a tree representing
the departments of a company, the size of a node could be the dollar amount of all sales for that
department, or the number of employees in that department. Or in a tree representing a
computer’s file system, the size of a node could be the size of the file.
2023/3/29 20:56 A2 — Treemaps: CSC148H1S 20231 (All Sections): Introduction to Computer Science
https://q.utoronto.ca/courses/292974/pages/a2-treemaps 2/14
A treemap (http://en.wikipedia.org/wiki/Treemapping) is a visualisation technique to show a
tree’s structure according to the weights (or sizes) of its data values. It uses rectangles to show
subtrees, scaled to reflect the proportional sizes of each piece of data.
Treemaps are used in many contexts. Among the more popular uses are news headlines, various
kinds of financial information, and computer disk usage. Some free programs use treemaps to
visualize the size of files on your computer; for example:
WinDirStat (http://portableapps.com/apps/utilities/windirstat_portable) for Windows
Disk Inventory X (http://www.derlien.com/) for MacOS
KDirStat (http://kdirstat.sourceforge.net/) for Linux
For this assignment, you will write an interactive treemap visualisation tool that you can use to
visualize hierarchical data.
It will have a general API (implemented with inheritance, naturally!) and you will define specific
subclasses that will allow you to visualize different kinds of data.
And with that, let’s get started on your final CSC148 assignment!
Task 0: Getting started
1. Download and unzip the starter code (a2_starter_files.zip
(https://q.utoronto.ca/courses/292974/files/25399282?wrap=1)
(https://q.utoronto.ca/courses/292974/files/25399282/download?download_frd=1) ) into your
directory for Assignment 2.
2. With tm_trees.py open, take the time to read through the tasks below to get a sense of what
code you’ll be writing throughout this assignment.
3. Familiarize yourself with the following coding guidelines:
You may NOT define any new public or private attributes.
You are always free to define private helpers (functions or methods).
Complete docstrings are not required for any helpers that you define or for methods that
you override or extend, but you are encouraged to take the time to write them.
Task 1: TMTree basics
In this task, you will implement:
TMTree.__init__
TMTree.is_displayed_tree_leaf
TMTree.get_path_string
In order to use a treemap to visualize data, we first need to define our tree structure and be able
to initialize it. For this program, you will develop a TMTree class to define the basic functionality
required by the provided treemap visualizer. To visualize any specific hierarchical dataset, we
simply need to define a subclass of TMTree , which we will do later.
2023/3/29 20:56 A2 — Treemaps: CSC148H1S 20231 (All Sections): Introduction to Computer Science
https://q.utoronto.ca/courses/292974/pages/a2-treemaps 3/14
The TMTree class is similar to the basic Tree class that you have already worked with, but with
some differences. A few of the most conceptually important ones are discussed here.
First, the class has a data_size instance attribute that is used by the treemap algorithm to
determine the size of the rectangle that represents this tree. data_size is defined recursively
as follows:
If the tree is a single leaf, its data_size is some measure of the size of the data being
modelled. For example, it could be the size of a file.
If the tree has one or more subtrees, its data_size is equal to the sum of the data_size s of
its subtrees, plus some additional size of its own.
Second, the class not only stores its subtrees, but it also stores its parent as an attribute. This
allows us to traverse both up and down the tree, which you will see is necessary when we
want to mutate the tree.
Third, we’ll also track some information inside our tree related to how to display it. More on
this shortly.
Fourth, we don’t bother with a representation for an empty TMTree , as we’ll always be
visualizing non-empty trees in this assignment.
To get started, you should do the following:
1. Complete the initializer of TMTree according to its docstring. This will get you familiar with the
attributes in this class.
2. Implement the is_displayed_tree_leaf method according to its docstring and the definition of
the displayed-tree (see below).
3. Implement the get_path_string method according to its docstring.
In the subsequent parts of this assignment, your program will allow the user to interact with the
visualizer to change the way the data is displayed to them. At any one time, parts of the tree will
be displayed and others not, depending on what nodes are expanded.
We’ll use the terminology displayed-tree to refer to the part of the data tree that is displayed in
the visualizer. It is defined as follows:
The root of the entire tree is in the displayed-tree.
For each “expanded” tree in the displayed-tree, its children are in the displayed-tree.
The trees whose rectangles are displayed in the visualization will be the leaves of the displayed-
tree. A tree is a leaf of the displayed-tree if it is not expanded, but its parent is expanded. Note
that the root node is a leaf of the displayed-tree if it is not expanded.
We will require that (1) if a tree is expanded, then its parent is expanded, and (2) if a tree is not
expanded, then its children are not expanded. Note that this requirement is naturally encoded as
a representation invariant in the TMTree class.
Note: the displayed-tree is not a separate tree! It is just the part of the data tree that is displayed.
2023/3/29 20:56 A2 — Treemaps: CSC148H1S 20231 (All Sections): Introduction to Computer Science
https://q.utoronto.ca/courses/292974/pages/a2-treemaps 4/14
Progress check!
After this step is done, you should be able to instantiate and print a TMTree , as is done in the
provided main block of tm_trees.py .
In the next task, you will implement the code required for the treemap algorithm.
Task 2: The Treemap algorithm
In this task, you will implement:
TMTree.update_rectangles
TMTree.get_rectangles
The next component of our program is the treemap algorithm itself. It operates on the data tree
and a 2-D window to fill with the visualization, and generates a list of rectangles to display, based
on the tree structure and data_size attribute for each node.
For all rectangles in this program, we’ll use the pygame representation of a rectangle, which is
a tuple of four integers (x, y, width, height) , where (x, y) represents the upper-left corner of the
rectangle. Note that in pygame, the origin is in the upper-left corner and the y-axis points down.
So, the lower-right corner of a rectangle has coordinates (x + width, y + height). Each unit on both
axes is a pixel on the screen. Below, we show a grid representing the rectangle (0, 0, 8, 4) :
We are now ready to see the treemap algorithm.
Note: We’ll use “size” to refer to the data_size attribute in the algorithm below.
Input: An instance of TMTree , which is part of the displayed-tree, and a pygame rectangle (the
display area to fill).
Output: A list of pygame rectangles and each rectangle’s colour, where each rectangle
corresponds to a leaf in the displayed-tree for this data tree, and has area proportional to the
leaf’s data_size .
Treemap Algorithm:
Note I: Unless explicitly written as “displayed-tree”, all occurrences of the word “tree” below refer
to a data tree.
Note II: (Very Important) The overall algorithm, as described, actually corresponds to the
combination of first calling TMTree.update_rectangles to set the rect attribute of all nodes in the
2023/3/29 20:56 A2 — Treemaps: CSC148H1S 20231 (All Sections): Introduction to Computer Science
https://q.utoronto.ca/courses/292974/pages/a2-treemaps 5/14
tree and then later calling TMTree.get_rectangles to actually obtain the rectangles and colours
corresponding to only the displayed-tree’s leaves.
1. If the tree is a leaf in the displayed-tree, return a list containing just a single rectangle that
covers the whole display area, as well as the colour of that leaf.
2. Otherwise, if the display area’s width is greater than its height: divide the display area into
vertical rectangles (by this, we mean the x-coordinates vary but the y-coordinates are fixed),
one smaller rectangle per subtree of the displayed-tree, in proportion to the sizes of the
subtrees (don’t use this tree’s data_size attribute, as it may actually be larger than the sizes of
the subtrees because of how we defined it!)
Example: suppose the input rectangle is (0, 0, 200, 100), and the displayed-tree for the input
tree has three subtrees, with sizes 10, 25, and 15.
The first subtree has 20% of the total size, so its smaller rectangle has width 40 (20% of
200): (0, 0, 40, 100).
The second subtree should have width 100 (50% of 200), and starts immediately after the
first one: (40, 0, 100, 100).
The third subtree has width 60, and takes up the remaining space: (140, 0, 60, 100).
Note that the three rectangles’ edges overlap, which is expected.
3. If the height is greater than or equal to the width, then make horizontal rectangles (by this, we
mean the y-coordinates vary, but the x-coordinates are fixed) instead of vertical ones, and do
the analogous operations as in step 2.
4. Recurse on each of the subtrees in the displayed-tree, passing in the corresponding smaller
rectangle from step 2 or 3.
Important: To ensure that you understand the treemap algorithm, complete the A2 release
activity (https://q.utoronto.ca/courses/292974/assignments/963601) , double-check your answers
(https://q.utoronto.ca/courses/292974/files/25397463?wrap=1)
(https://q.utoronto.ca/courses/292974/files/25397463/download?download_frd=1) , and ask clarifying
questions as needed.
Note about rounding: because you’re calculating proportions here, the exact values will often be
floats instead of integers. For all but the last rectangle, always truncate the value (round down to
the nearest integer). In other words, if you calculate that a rectangle should be (0, 0, 10.9, 100),
“round” (or truncate) the width down to (0, 0, 10, 100). Then a rectangle below it would start at (0,
100), and a rectangle beside it would start at (10, 0).
However, the final (rightmost or bottommost) edge of the last smaller rectangle must always be
equal to the outer edge of the input rectangle. This means that the last subtree might end up a bit
bigger than its true proportion of the total size, but that’s okay for this assignment.
2023/3/29 20:56 A2 — Treemaps: CSC148H1S 20231 (All Sections): Introduction to Computer Science
https://q.utoronto.ca/courses/292974/pages/a2-treemaps 6/14
Important followup to Note II above: You will implement this algorithm in the
update_rectangles method in TMTree . Note that rather than returning the rectangles for only
the leaves of the displayed-tree, the code will instead set the rect attribute of each node in
the entire tree to correspond to what its rectangle would be if it were a leaf in the
displayed-tree. Later, we can retrieve the rectangles for only the leaf nodes of the
displayed-tree by using the get_rectangles method.
Note: Sometimes a TMTree will be sufficiently small that its rectangle has very little area (it has a
width or height very close to zero). That is to be expected, and you don’t need to do anything
special to deal with such cases. Just be aware that sometimes you won’t be able to actually see
all the displayed rectangles when running the visualizer, especially if the window is small.
Tips: For the recursive step, a good stepping stone is to think about when the tree has height 2,
and each leaf has the same data_size value. In this case, the original rectangle should be
partitioned into equal-sized rectangles.
Warning: make sure to follow the exact rounding procedure in the algorithm description above. If
you deviate from this, you might get slightly incorrect rectangle bounds.
Important: The docstring of the get_rectangles method refers to the displayed-tree. For now, the
whole tree is the displayed-tree, as all trees start expanded. Make sure that you come back later
and further test this method on trees where the displayed-tree is a subset of the full data tree to
ensure that your code is fully correct.
Progress check!
Note that the basic treemap algorithm does not require pygame or the visualizer at all! You can
check your work simply by instantiating a TMTree object, calling update_rectangles on it, then
calling get_rectangles to see the list of rectangles returned.
This is primarily how we’ll be testing your implementation of the treemap algorithm!
At this point, you can now run treemap_visualiser.py and see your treemap. By default, it will
display the example from the worksheet, which should look something like below (with random
colours of course). Note: the bar across the bottom is where the path string of the selected
rectangle will appear once you complete the next task.
2023/3/29 20:56 A2 — Treemaps: CSC148H1S 20231 (All Sections): Introduction to Computer Science
https://q.utoronto.ca/courses/292974/pages/a2-treemaps 7/14
Next, you will implement the method necessary to enable the selection of rectangles in the
visualizer.
Task 3: Selecting a tree
In this task, you will implement:
TMTree.get_tree_at_position
The first step to making our treemap interactive is to allow the user to select a node in the tree. To
do this, complete the body of the get_tree_at_position method. This method takes a position on
the display and returns the displayed-tree leaf corresponding to that position in the treemap.
IMPORTANT: Ties should be broken by choosing the rectangle on the left for a vertical boundary,
or the rectangle above for a horizontal boundary. That is, you should return the first leaf of the
displayed-tree that contains the position, when traversing the tree in the natural order.
In the visualizer, the user can click on a rectangle to select it. The text display updates to show
two things:
the selected leaf’s path string returned by the get_path_string method.
the selected leaf’s data_size
Clicking on the same rectangle again unselects it. Clicking on a different rectangle selects that
one instead.
Reminder: Each rectangle corresponds to a leaf of the displayed-tree, so we can only select
leaves of the displayed-tree.
Progress check!
Try running the program and then click on a rectangle on the display. You should see the
information for that displayed-tree leaf shown at the bottom of the screen, and a box appear
around the selected rectangle. Click again to unselect that rectangle, and try selecting another
one. Note that you will also see a thinner box appear around any rectangle that you hover over in
the display.
For the worksheet example, it should look something like the below, if you have selected
rectangle “d” and are not hovering over any rectangle:
2023/3/29 20:56 A2 — Treemaps: CSC148H1S 20231 (All Sections): Introduction to Computer Science
https://q.utoronto.ca/courses/292974/pages/a2-treemaps 8/14
Note: As you run the visualizer, you will see output in the python console in PyCharm. This output
is to help you see what events are being executed. You may find this information useful when
debugging your code. Feel free to modify anything that is being printed in treemap_visualiser.py if
you find it helpful to do so.
Task 4: Making the display interactive
In this task, you will implement:
TMTree.expand
TMTree.expand_all
TMTree.collapse
TMTree.collapse_all
TMTree.move
TMTree.change_size
Note: Unless explicitly written as “displayed-tree”, all occurrences of the word “tree” below refer to
a data tree.
Now that we can select nodes, we can move on to making the treemap more interactive.
In addition to displaying the treemap, the pygame graphical display responds to a few different
events (by event, we mean the user presses a key, hovers, or clicks on the window). The first
such event was actually clicking on a rectangle to select it, which we implemented in the previous
task. We will now implement the rest of the actions associated with events, by implementing
methods in the TMTree class which the visualizer calls:
a. The user can close the window and quit the program by clicking the X icon (like any other
window).
No additional code required.
b. The user can resize the window by clicking and dragging a corner or side of the window (like
any other resizable window).
No additional code required.
The next four events change which rectangles are included in the displayed-tree.
2023/3/29 20:56 A2 — Treemaps: CSC148H1S 20231 (All Sections): Introduction to Computer Science
https://q.utoronto.ca/courses/292974/pages/a2-treemaps 9/14
c. If the user selects a rectangle, and then presses e , the tree corresponding to that rectangle is
expanded in the displayed-tree. If the tree is a leaf in the data tree, nothing happens, since we
can’t expand a leaf. When a tree is expanded, the visualization will make the first subtree of
the newly expanded tree the new selected tree.
implement TMTree.expand
d. If the user selects a rectangle, and then presses c , the parent of that tree is unexpanded (or
“collapsed”) in the displayed-tree. (Note that since rectangles correspond to leaves in the
displayed-tree, it is the parent that needs to be unexpanded.) If the parent is None because
this is the root of the whole tree, nothing happens. When a tree is collapsed, the visualization
will make its parent tree the new selected tree, as it is now a leaf of the displayed-tree.
implement TMTree.collapse
e. If the user selects a rectangle, and then presses a , the tree corresponding to that rectangle,
as well as all of its subtrees, are expanded in the displayed-tree. If the tree is a leaf, nothing
happens. When a tree is expanded in this way, the visualization will make the “last” subtree of
the newly expanded trees the new selected tree. Note: The docstring for the relevant method
clarifies what we mean by “last”.
implement TMTree.expand_all
f. If the user selects any rectangle, and then presses x , the entire displayed-tree is collapsed
down to just a single tree node. If the displayed-tree is already a single node, nothing
happens. When a tree is collapsed in this way, the visualization will make this single tree node
the new selected tree, as it is now the only leaf of the displayed-tree.
implement TMTree.collapse_all
The following two events allow the user to actually mutate the data tree, and see the changes
reflected in the display.
g. If the user presses the Up Arrow or Down Arrow key when a rectangle is selected, the
selected node’s data_size increases or decreases by 1% of its current value, respectively.
Note: This affects the data_size of its ancestors as well, given our definition of data_size !
implement TMTree.change_size
Details:
A node’s data_size cannot decrease below 1. There is no upper limit on the value of
data_size . Just keep in mind that if a node is too large, then other nodes will appear relatively
small in the visualization!
If a node has children, its data_size cannot decrease below the sum of its child data sizes.
The 1% amount is always “rounded up” before applying the change. For example, if a leaf’s
data_size value is 140, then 1% of this is 1.4, which is “rounded up” to 2. So its value could
increase up to 152 142, or decrease down to 148 138. (Note: the docstring for the relevant
method provides similar clarification.)
h. If the user selects a rectangle, then hovers the cursor over another rectangle and presses m ,
the selected node should be moved to be the last subtree of the node being hovered over.
Remember: we can only select and hover over leaves of the displayed-tree.
2023/3/29 20:56 A2 — Treemaps: CSC148H1S 20231 (All Sections): Introduction to Computer Science
https://q.utoronto.ca/courses/292974/pages/a2-treemaps 10/14
implement TMTree.move
Very Important: Whenever you modify a tree’s data_size , the data_size attributes of all its
ancestors need to be updated too! You must make use of the parent_tree attribute to do this: it’s
a widely-used technique for traversing up a tree (this should feel a lot like traversing a linked list!).
Progress check!
At this point, your visualizer should be fully functional!
One of the nice things about code with an interactive display is that it’s usually pretty
straightforward to test basic correctness.
Try running the treemap visualizer, and see if you can resize, move rectangles, and manipulate
the displayed-tree as outlined above.
Of course, you can also write pytests to check the correctness of the methods you have written
too!
Next, we’ll write code to allow us to visualize the files on your computer!
Task 5: File System Data
In this task, you will implement:
path_to_nested_tuple
dir_tree_from_nested_tuple
You will also:
override any methods necessary for your subclasses of TMTree to behave as specified below.
decide on an appropriate inheritance hierarchy for the FileTree and DirectoryTree classes.
Consider a directory on your computer (e.g., the assignments directory you have in your csc148
directory). It contains a mixture of other directories (“subdirectories”) and some files; these
subdirectories themselves contain other directories, and even more files! This is a natural
hierarchical structure, and can be represented by a tree.
The _name attribute will always store the name of the directory or file (e.g. preps or prep8.py ), not
its path; e.g., /Users/courses/csc148/preps/prep8/prep8.py .
The data_size attribute of a file is simply how much space (in bytes) the file takes up on the
computer. Note: to prevent empty files from being represented by a rectangle with zero area, we
will always add a +1 to file sizes. The data_size of a directory corresponds to the size of all files
contained in the directory, including its subdirectories. As with files, we’ll also add a +1 to directory
sizes for this assignment.
In our code, we will represent this filesystem data using the FileTree and DirectoryTree classes.
1. Complete the path_to_nested_tuple function according to its docstring.
2023/3/29 20:56 A2 — Treemaps: CSC148H1S 20231 (All Sections): Introduction to Computer Science
https://q.utoronto.ca/courses/292974/pages/a2-treemaps 11/14
2. Complete the dir_tree_from_nested_tuple function. This function is the public interface for how
we will create DirectoryTree objects to test your code for correctness.
3. Override or extend methods from TMTree , as appropriate, in the FileTree and DirectoryTree
classes. You will need to decide if you can just use the inherited methods as they are or not
(see additional requirements below).
To complete step 1, you will need to read the Python os module documentation
(https://docs.python.org/3/library/os.html) to learn how to get data about your computer’s files in a
Python program. You may also find the provided print_dirs.py to be a useful example to base
your implementation on.
We recommend using the following functions:
os.path.isdir
os.path.join
os.path.getsize
os.path.basename
os.listdir (see note below)
Note: Since the order that os.listdir returns file names is dependent on your operating
system, we have provided a helper, ordered_listdir which you MUST use in your
implementation. You MUST add the subtrees in the order they are produced from
ordered_listdir .
You may NOT use the os.path.walk function — it does a lot of the recursive work for you, which
defeats the purpose of this part!
Warning: Make sure to either use os.path.join (recommended) or make use of string
concatenation and the os.sep string to build larger paths from smaller ones, because different
operating systems use different separators for file paths.
Requirements for step 3:
FileTree objects can be resized in exactly the same way as TMTree objects, while
DirectoryTree objects can NOT be resized. Attempting to change the size of a directory should
raise an OperationNotSupportedError .
We can only move files and directories into a directory. Attempting to move a file or directory
into a file should raise an OperationNotSupportedError , as demonstrated in the doctests for the
DirectoryTree class. Also note that, since every event is designed for use with the visualizer,
you can only perform moves between leaves of the displayed-tree.
Ensure your code is consistent with any other behaviour demonstrated in the provided
doctests for the DirectoryTree class.
If you decide you would like an additional class in your hierarchy, you are free to define a new
class.
Progress check!
2023/3/29 20:56 A2 — Treemaps: CSC148H1S 20231 (All Sections): Introduction to Computer Science
https://q.utoronto.ca/courses/292974/pages/a2-treemaps 12/14
You should now be able to instantiate a DirectoryTree by first calling path_to_nested_tuple on a
path and then calling the dir_tree_from_nested_tuple function on the result. You can then inspect
the tree’s contents in the debugger or print it, as is done in the main block.
You can also try running the treemap visualizer and confirm that it works as expected for the file
system version. In the main block, you can toggle which visualizer is run by changing which of the
RUN_OPTIONS is chosen.
One more dataset to go!
Task 6: Chess!
In this task, you will implement:
moves_to_nested_dict
ChessTree.__init__
You will also:
override or extend any methods necessary for ChessTree to behave as specified below.
Our last dataset consists of games extracted from a database of chess games played by
WGMs. While you don’t have to know the exact rules of chess for this part, there are a few
important things to note:
a game consists of a sequence of moves
“white” goes first and “black” goes second, with the two players continuing to take alternating
turns until the game ends.
Each move can be represented by a code indicating which piece was moved and where it
moved to.
the games can potentially end at any time, with some games taking less than 10 moves and
others taking 100 or more.
For those interested, moves are represented as strings in the format ‘{from square}{to square}’
e.g. ‘e2e4’ is the move from square e2 to square e4. This format is known as algebraic notation
(https://en.wikipedia.org/wiki/Algebraic_notation_(chess)) if you are interested, but you don’t
need to know anything about the format to complete the assignment.
Note: you should assume the games consist of only valid moves, so do not attempt to do
any verification of this yourself.
Below is an example of what the data (a list of a list of games) looks like. This is a subset of the
games in the provided wgm_10.json , with … denoting omitted moves / games for purposes of
conciseness.
[
['e2e4', 'e7e6', 'd2d4', 'd7d5', 'b1d2', ..., 'f5f7'],
['d2d4', 'g8f6', 'g1f3', 'g7g6', 'c2c4', ..., 'd7d6'],
...
['e2e4', 'c7c6', 'd2d4', 'd7d5', 'e4e5', ..., 'd5f7']
]
2023/3/29 20:56 A2 — Treemaps: CSC148H1S 20231 (All Sections): Introduction to Computer Science
https://q.utoronto.ca/courses/292974/pages/a2-treemaps 13/14
Similar to the filesystem data initialization process, we will again have you do this in two steps:
1. Implement the moves_to_nested_dict function according to its docstring.
2. Implement the initializer for ChessTree according to its docstring.
A few important notes about the structure:
The root node should be the string '-'
The children of the root node should be all moves that occur as the first move of at least one
game.
The children of all deeper moves should be the moves that follow the move represented by
the parent move in at least one game.
We also need to update the functionality of our ChessTree class to reflect what events should be
ignored for this new kind of data. In particular, given the interpretation of the nodes, we don’t want
to support either changing the sizes of nodes or moving nodes. As you did with the file system
related subclasses, appropriately override the relevant methods in a way consistent with the
provided code.
Progress check!
You should now be able to instantiate a ChessTree as is done in the main block.
You should also be able to run the visualizer on one of the three provided json files containing
games of chess. In the visualizer code, you can choose which data file to open.
For example, if you visualize the games from wgm_200.json , fully collapse the displayed-tree,
expand once, and then select the largest rectangle (which should correspond to 145 games), the
treemap should look something like the below. Note, depending on how exactly you read in the
games and construct the tree, the rectangles may appear in a different order, which is perfectly
fine.
You can also try using the ‘o’ key on a selected ChessTree . This should open a website with the
chess position shown corresponding to the move sequence of the selected tree!
And that’s it!
2023/3/29 20:56 A2 — Treemaps: CSC148H1S 20231 (All Sections): Introduction to Computer Science
https://q.utoronto.ca/courses/292974/pages/a2-treemaps 14/14
Submission instructions
1. Login to MarkUs and create a group for the assignment (or specify that you’re working alone).
2. Run your code one more time locally to ensure that it runs.
3. Upload tm_trees.py to MarkUs.
4. Run the self-tests on MarkUs and read through the test output to avoid any silly
mistakes.
5. Congratulations, you are finished with your last assignment in CSC148! Go have some
chocolate or do a cartwheel. :)
