MCS 275 Spring 2024 Homework 8 Solutions¶

Course Instructor: Emily Dumas

Problem 2:¶

Work in hwk8prob2.py.

You will need to save the following PNG file in the directory where you do your work. All the links below take you to the same PNG file, so use whichever one makes it easiest for you to save it to a known location on your computer.

Link to the file: hwk8-campus-circle.png
Directory where you can find it on github: worksheets/images/
The image itself (which you may be able to right-click and "save as"):

UIC circle logo

This is an image of the UIC campus logo, a red circle with "UIC" written inside it in bold white sans-serif letters.

Write a Python program that uses Pillow (i.e. the PIL module) to open this image file, analyze it, and print a report that answers these questions:

Exactly what RGB color is the shade of red used in this UIC logo image? Many colors are used in this image because of blending between red and white at the edges. But there are only two "popular" colors, used in tens of thousands of pixels: white (i.e. (255,255,255)) and one other color (that we're asking for).
How many pixels in the image have the exact color that was the answer to question #1? (Let's call these "UIC red pixels".)
What fraction of the area of this image is accounted for by UIC red pixels? Assume the pixels are square. Print the answer as a percentage, with one digit after the decimal point.

Here's an example of what the output should look like, but using different colors and numbers than the actual answer:

UIC red is: (105,21,17)
Number of pixels of that color: 28055
Fraction of the area they account for: 38.5%

ALSO, please run your program and paste its output as a series of comment lines at the bottom of hwk8prob2.py. That way we can see its output while reading the code during grading.

from PIL import Image
from collections import defaultdict

# Make a histogram of the image (dict mapping color to # pixels)
hist = defaultdict(int)
img = Image.open("images/hwk8-campus-circle.png")
for x in range(img.size[0]):
    for y in range(img.size[1]):
        hist[img.getpixel((x,y))] += 1

# Convert this to a list of tuples (# pixels, color)
pairs = [ (v,k) for k,v in hist.items() ]
# Sort to put in order of increasing freq
pairs.sort()

# Last color should be white
most_common_color_pixels, most_common_color = pairs[-1]
assert most_common_color == (255,255,255)

# Second last is "UIC red"
uic_red_pixels, uic_red = pairs[-2]

# Convert this info into the output requested
print("UIC red is: ",uic_red)
print("Number of pixels of that color:",uic_red_pixels)
print("Fraction of the area they account for: {:.1f}%".format(100.0 * uic_red_pixels / (img.size[0]*img.size[1])))

UIC red is:  (213, 31, 53)
Number of pixels of that color: 31046
Fraction of the area they account for: 42.6%

Problem 3: Save tree as CSV file¶

Work in hwk8prob3.py. You'll need to import and use trees.py, and I suggest you download a fresh copy because it has been updated include the methods you were asked to write in Worksheets 7 and 8. (You don't necessarily need to use those new methods, but their code may be a handy source of inspiration.)

Write a function save_tree_as_csv that takes two arguments:

T, a Node or BST object that is the root of a tree
filename, a string specifying the name of the desired output file

This function should create a CSV file with two columns: location and key. After the header row, there should be one row for each node in the tree. In the row corresponding to a node, the value in column key should be the key of the node, and the value in column location should be a string containing only the letters L and R that, when read from left to right, indicates how to get to the node from the root (T). For example, the string "LRL" would mean: "To get to this node, start at the root, go to its Left child, then the Right child of that, then the Left child of that." The empty string "" would be the location of the root node itself.

For example, the tree

-           <True>
-           /    \
-    <"Alice">  <False>
-     /     \
-  <5.8>   <5.5>

might generate a CSV file with the following contents:

location,key
,True
L,Alice
LL,5.8
LR,5.5
R,False

Use the following function definition line:

def save_tree_as_csv(T,filename):

Notes:

After the header row, the other rows are allowed to appear in any order. What's important is that there is exactly one row for each node in the tree.
Feel free to write and use helper functions if you like.
You can do this by recursion or iteration according to your preference. If you're not sure I'd try recursion.

import csv

def tagged_preorder(T,prefix=""):
    """
    Perform a preorder traversal of tree with root T,
    returning a list of pairs (tag, key) where tag
    is a string consisting of L and R characters
    indicating how to get to the node from the root
    """
    if T is None:
        return []
    return [(prefix,T.key)] + tagged_preorder(T.left,prefix+"L") + tagged_preorder(T.right,prefix+"R")

def save_tree_as_csv(T,filename):
    "Export tree as CSV with one node position code and key on each line"
    with open(filename,"w",newline="",encoding="UTF-8") as fp:
        writer = csv.writer(fp)
        writer.writerow(["location","key"])
        for location,key in tagged_preorder(T):
            writer.writerow([location,key])

Why don't we test that it works on a random tree?

import treeutil
import treevis
T = treeutil.random_bst(6)
print("The tree:")
treevis.treeprint(T)
save_tree_as_csv(T,"test_tree_to_csv.csv")
print("\nAs a CSV:\n")
with open("test_tree_to_csv.csv","r") as fp:
    for line in fp:
        print(line,end="")

The tree:
              <11>

      <6>             <14>

  <4>     <8>      .       .

<3>  .   .   .   .   .   .   .


As a CSV:

location,key
,11
L,6
LL,4
LLL,3
LR,8
R,14

Revision history¶

2024-04-01 Initial publication