Homework 8

Objectives

The goal of this assignment is to gain experience working with:

• for loops:
  • iterating over a collection
  • iterating over a range of integers
  • nested loops

Note: Your code for these exercises must use for loops, not while loops. Code that uses a while loop will receive no credit.

Docstrings

For this homework, and all of the remaining homeworks, all of your modules and functions must exhibit correct documentation. Submissions that don’t pass docstring checks will receive no credit.

You should read the Docstring Requirements carefully to see how it should be done.

Exercise 8.1 Intervals

For this exercises you will write a function that takes a list of floats and returns a new list containing only the numbers from that list that are within a designated interval. The file must be named interval.py and it must contain a single function named in_interval with four parameters:

• The first is a list of floats.
• The second is the lower bound of the interval.
• The third is the upper bound of the interval.
• The fourth is a Boolean indicating whether this is a closed interval. This parameter should have a default value of True indicating that the interval is closed.

The numbers in the returned list must be in the same order as they appeared in the original list. You may assume that the provided lower and upper values represent a valid interval.

Here are some examples illustrating the expected behavior:

Exercise 8.2 Street Addresses

For this exercise you will write a function to help with generating street addresses in new housing developments. Create a file named addressing.py with a single function named generate_addresses. This function must take four arguments:

• The name of the street
• The initial numerical address
• The upper bound of numerical address values (exclusive)
• The interval between numerical addresses

The function must return a list of street addresses formatted with the number of the address, followed by a single space, followed by the name of the street. For example:

Exercise 8.3 Shift Cipher

One of the simplest forms of encryption is the shift cipher, also known as the Caesar cipher. In this technique, each letter in the plaintext is replaced by a letter a fixed distance away in the alphabet, wrapping around at the end (or beginning) as necessary.

For example, if you encoded “dog” by shifting two to the right, “d” would be replaced by “f”, “o” would be replaced by “q”, and “g” would be replaced by “i”, so the final encoded text would be “fqi”. “zoo” would be encoded as “bqq”, because the “z” would wrap around to the beginning of the alphabet again.

Create program called shift_cipher.py containing the function encode. The function should take as parameters the text to encode (in all lower case), and the number of letters to shift (guaranteed to be between -26 and 26). It should return the encoded text, and leave spaces and punctuation as-is, without changing them.

Hint: You will need to use ord() and chr() to convert letters to numbers and back again in order to shift them. You might also use the modulo operator (%), although you do not have to.

Going Further: Shift ciphers are famously insecure. It is easy to break the code by using brute force to check every possible shift. If you want a challenge, try writing a function named decrypt that takes a single argument containing an encoded message and returns the decoded version. You may find it helpful to have access to a list of common English words that can be used to check if you have found the correct decoding: 1000-most-common-words.txt.

Here is an example of the desired behavior:

Exercise 8.4 More Image Manipulations

As mentioned in HW 6 computer images are organized into a two-dimensional grid of pixels. The usual convention is to place pixel (x=0, y=0) at the upper-left corner of the image, with x increasing as we move to the right and y increasing as we move down. The following code snippet shows an example of using the Pillow image library to create a small image and set the color of several individual pixels:

from PIL import Image

# Create some color tuples
red = (255, 0, 0)
green = (0, 255, 0)
blue = (0, 0, 255)
black = (0, 0, 0)

# Create a white image 30 pixels wide by 10 tall
img = Image.new('RGB', (30, 10), color='white')

# Color the upper-left pixel red
img.putpixel((0, 0), red)

# Color the lower-left pixel green
img.putpixel((0, 9), green)

# Color the upper-right pixel blue
img.putpixel((29, 0), blue)

# Color the lower-right pixel black
img.putpixel((29, 9), black)

# Display the resulting image
img.show()

Try running this code to confirm that it works as expected. If you haven’t done so already, you will need to install the Pillow (Python Imaging Library) package through the Thonny package manager. Keep in mind that individual pixels are tiny, so you may need to zoom in on the image or use a magnifying glass to see the colored pixels.

We can use nested for-loops to iterate over all of the pixels in an image. For example, this code creates a white image and then randomly sets half of the pixels to be black:

from PIL import Image
import random

img = Image.new('RGB', (640, 480), color='white')

for x in range(img.width):
    for y in range(img.height):
        if random.random() < .5: # True 50% of the time
            img.putpixel((x, y), (0, 0, 0)) # set to black
            
img.show()

Here the outer loop iterates over all of the columns of the image grid, while the inner loop iterates over all of the rows. This access pattern: starting with the first column, then moving to the second column, etc. is referred to as column-major order.

Download the file drawing.py and complete following two functions:

• draw_rectangle(img, x_pos, y_pos, width, height, color) - This function must modify the provided image by adding a rectangle of the color specified in the fifth argument. The parameters x_pos and y_pos indicate the upper left coordinate of the rectangle, while the parameters height and width specify the size of the rectangle. If this is the initial image:

  

  Then calling draw_rectangle(img, 0, 0, 100, 120, (255, 0, 0)) will have the following result:

  

  Be Careful! Your submission will only pass the automated tests if the rectangle is exactly the right size and in exactly the right location. This will be difficult to confirm visually, so you’ll need to think carefully about your implementation.

• draw_triangle(img, x_pos, y_pos, width, color) - This function must modify the provided image by adding an isosceles right-triangle with the indicated width. The upper-left corner of the triangle must be at the position indicated by the x_pos and y_pos arguments.

  Calling draw_triangle(img, 0, 0, 100, (255, 0, 0)) on the image above will have the following result:

  

  Hint: The logic for this function will be similar to the logic for draw_rectangle. The difference is that the inner loop must be modified so that it stops one pixel earlier every time it is reached.

Exercise 8.5 Book Cipher

As mentioned above, shift ciphers are easy to break. Book ciphers provide a more secure alternative. In a book cipher we encode each word of the plaintext by replacing it with the location where that word can be found in a particular book. As long as our correspondent has the same edition of the book, they can decode our message by looking up the words in their copy.

For this exercise, you will implement a book cipher using books downloaded from Project Gutenberg.

As a starting point, download the file book_cipher.py. This file includes the following functions. The first is finished for you, the rest are stubs that you will need to implement.

• get_book(url) - This function takes the web address of a book and returns a list containing all of the words from that book, in order. For example:

  >>> %Run book_cipher.py
  >>> print(get_book('https://www.gutenberg.org/files/84/84-0.txt'))
  ['\ufeffthe', 'project', 'gutenberg', 'ebook', 'of', 'frankenstein', ...

• word_locations(words) - This function takes a list of words and returns a dictionary that maps from the words in the list to the index of their last appearance in the list. For example:

  >>> %Run book_cipher.py
  >>> word_locations(['i', 'think', 'therefore', 'i', 'am'])
  {'i': 3, 'think': 1, 'therefore': 2, 'am': 4}

• encode(plaintext, key) - The first argument to this function is a list of words that should be encoded. The second is the list of words from the book that will be used as the key. You may assume that the words in both lists will be lower-case. The return value is a list of integers representing the indices where each plaintext word appears in the key. Any word that does not appear in the key must be represented as -1.

  >>> encode(['i', 'am', 'done'], ['i', 'think', 'therefore', 'i', 'am'])
  [3, 4, -1]

  Your encode function should include a call to word_locations.

• decode(ciphertext, key) - The first argument to this function is a list of integers representing an encoded message. The second is the list of words from the book that will be used as the key. This function must return a list of words found at the corresponding indices in the key. For -1 entries in the ciphertext, the word should default to '---'. For example:

  >>> %Run book_cipher.py
  >>> decode([3, 4, -1], ['i', 'think', 'therefore', 'i', 'am'])
  ['i', 'am', '---']

As the adventuresome Sherlock Holmes once said: “107518, 93975, 107475, 103805, 107518, 82632, 107459, 107518, 95372, 96188, 11033, 69283, 107484, 95257, 103723”.

Going Further: Our book cipher would be more secure if we didn’t always use the same instance of a particular word in our ciphertext. For example, high frequency words like “the” are likely to appear multiple times in our message. The fact that the same number pops up multiple times in our ciphertext could give a code-breaker a clue that we are using some sort of substitution cipher. This weakness could be mitigated by randomly selecting matching indices each time we encode a particular word. For example, in our small example above, “i” could be encoded using either 0 or 3. If you want a challenge, make a copy of your solution and rewrite word_locations and encode to support this behavior. (The code you submit must match the original specification.)