CS111 Matrix Operations

Problem 1: 2-D lists

This problem involves writing functions that create and manipulate two-dimensional lists of integers. Some of these functions will then be used in the next problem to implement John Conways Game of Life.

Getting started

Begin by downloading the following zip file: ps10pr1.py

In ps10pr1.py, we have given you the following function:

def create_row(width):
""" creates and returns a "row" with the specified width --
i.e., a list containing width zeros.
input width: a non-negative integer
"""
row = []

for col_num in range(width):
row += [0] # add one 0 to the end of the row

return row

This function creates and returns a row of the specified widthi.e., a 1-D list containing the specified number of zeros.

To see how it works, run the file in IDLE, and try entering the following function calls from the Shell:

>>> create_row(3)
[0, 0, 0]

>>> create_row(7)
[0, 0, 0, 0, 0, 0, 0]

Your tasks

Write a function create_grid(height, width) that creates and returns a 2-D list of height rows and width columns in which all of the cellsi.e., all of the elements of the sublistshave a value of 0. We strongly encourage you to make use of our create_row function to create each row of the grid. Make sure that your code calls create_row multiple times: once for each row of the grid. In addition, you can copy the structure of that function when constructing your create_grid function. Just as create_row gradually accumulates a list of zeros, create_grid should gradually accumulate a list of rows. Here is a template that you can use:

def create_grid(height, width):
""" put your docstring here
"""
grid = []

for row_num in _____________:
grid += _________________ # add a whole row

return grid

Try testing your function by re-running the file and entering the following from the Shell:

>>> grid = create_grid(3, 5)
>>> grid
[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

Two important tests:

• Make sure that you get a 2-D list! The test above should give you three rows/sublists within the overall list. If you get a 1-D list with 15 zeros, you need to rethink the expression that youre using in the body of your loop. Because were using concatenation to build up a 2-D list, the expression that you concatenate must itself be a 2-D listi.e., a list with a sublist.
• Make sure that your rows are independent! After performing the test above, try the following:

>>> grid[0][0] = 1
>>> grid
[[1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

• Note that only the first row/sublist should be modified; the second and third rows should be unchanged.
• If your create_grid function is failing to create independent rows, you will see the following result instead:

[[1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0]]

• This result in which all three rows have had their first element changed to 1 means that your create_grid is creating a single row and then making copies of the reference to that row, rather than creating multiple independent rows. Make sure to fix your function before proceeding, using our create_row function to create a separate list for each row.

When Python prints a 2-D list, it flattens the list into one long list (wrapping it onto subsequent lines as needed). To allow you to print your grids in 2-Dwith one row per linewere providing the following function, which you should copy into your ps10pr1.py file:

def print_grid(grid):
""" prints the 2-D list specified by grid in 2-D form,
with each row on its own line, and no spaces between values.
input: grid is a 2-D list. We assume that all of the cell
values are either 0 or 1.
"""
for row in grid:
for cell in row:
print(cell, end='') # don't print a newline or space at end
print() # at end of row, go to next line

Notice the statement that we use to print the value of a single cell:

print(cell, end='')

The argument end='' indicates that Python should print nothing after the value of cellnot a newline character (which is the default behavior), and not even a space. As a result, the values in a given row will appear right next to each other on the same line. (We can safely eliminate the spaces between values because were assuming that the individual cell values will be either 0 or 1.)

Make sure that your copy of print_grid is working by re-running the file and trying the following from the Shell:

>>> grid = create_grid(3, 5)
>>> print_grid(grid)
00000
00000
00000

To provide an example of using nested loops to manipulate a 2-D list, were also providing the following function, which you should copy into your ps10pr1.py file:

def diagonal_grid(height, width):
""" creates and returns a height x width grid in which the cells
on the diagonal are set to 1, and all other cells are 0.
inputs: height and width are non-negative integers
"""
grid = create_grid(height, width) # initially all 0s

for r in range(height):
for c in range(width):
if r == c:
grid[r][c] = 1

return grid

Notice that the function first uses create_grid to create a 2-D grid of all zeros. It then uses nested loops to set all of the cells on the diagonali.e., the cells whose row and column indices are the sameto 1.

Make sure that your copy of diagonal_grid is working by re-running the file and trying the following:

>>> grid = diagonal_grid(6, 8)
>>> print_grid(grid)
10000000
01000000
00100000
00010000
00001000
00000100

Based on the example of diagonal_grid, write a function inner_grid(height, width) that creates and returns a 2-D list of height rows and width columns in which the inner cells are all 1 and the cells on the outer border are all 0.

For example:

>>> grid = inner_grid(5, 5)
>>> print_grid(grid)
00000
01110
01110
01110
00000

Hint: Modify the ranges used by your loops so that they loop over only the inner cells.

Write a function random_grid(height, width) that creates and returns a 2-D list of height rows and width columns in which the inner cells are randomly assigned either 0 or 1, but the cells on the outer border are all 0.

For example (although the actual values of the inner cells will vary):

>>> grid = random_grid(10, 10)
>>> print_grid(grid)
0000000000
0100000110
0001111100
0101011110
0000111000
0010101010
0010111010
0011010110
0110001000
0000000000

Hint: Dont forget that random.choice([0, 1]) will return either a 0 or a 1.

As weve seen in lecture, copying a list variable does not actually copy the list. To see an example of this, try the following commands from the Shell:

>>> grid1 = create_grid(2, 2)
>>> grid2 = grid1 # copy grid1 into grid2
>>> print_grid(grid2)
00
00

>>> grid1[0][0] = 1
>>> print_grid(grid1)
10
00

>>> print_grid(grid2)
10
00

Note that changing grid1 also changes grid2! Thats because the assignment grid2 = grid1 did not copy the list represented by grid1; it copied the reference to the list. Thus, grid1 and grid2 both refer to the same list!

To avoid this problem, write a function copy(grid) that creates and returns a deep copy of grida new, separate 2-D list that has the same dimensions and cell values as grid. Note that you cannot just perform a full slice on grid (e.g., grid[:]), because you would still end up with copies of the references to the rows. Instead, you should do the following:

• Use create_grid to create a new 2-D list with the same dimensions as grid, and assign it to an appropriately named variable. (Dont call your new list grid, since that is the name of the parameter!) Remember that len(grid) will give you the number of rows in grid, and len(grid[0]) will give you the number of columns.
• Use nested loops to copy the individual values from the cells of grid into the cells of your newly created grid.
• Make sure to return the newly created grid and not the original one!

To test that your copy function is working properly, try the following examples:

>>> grid1 = diagonal_grid(3, 3)
>>> print_grid(grid1)
100
010
001

>>> grid2 = copy(grid1) # should get a deep copy of grid1
>>> print_grid(grid2)
100
010
001

>>> grid1[0][1] = 1
>>> print_grid(grid1) # should see an extra 1 at [0][1]
110
010
001

>>> print_grid(grid2) # should not see an extra 1
100
010
001

Problem 2: Matrix operations

This problem provides additional practice with using loops to process two-dimensional lists of numbers, and with writing a program that involves repeated user interactions.

You must complete this problem on your own, without the help of a partner.

Background

The program that you will write will allow the user to perform a variety of operations on a matrix of numbers. For the purposes of this assignment, you can just think of a matrix as a rectangular 2-D list of numbers. (Recall that a rectangular 2-D list is one in which all of the rows have the same number of values.)

Getting started

In ps10pr2.py, weve given you some starter code for the program. Download that file and open it in IDLE.

Youll notice that weve given you the beginnings of a function called main() that will serve as the main user-interaction loop. You will call this function to run the program.

main() includes a variable matrix that should be used for the 2-D list of numbers, and it assigns a default 3x4 matrix of numbers to that variable:

matrix = [[ 1, 2, 3, 4],
[ 5, 6, 7, 8],
[ 9, 10, 11, 12]]

You should not change this initial set of values, since we may use it for grading.

To try the program, run ps10pr3.py in IDLE, and make the following function call from the Shell:

>>> main()

You should see the following initial output:

[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]

(0) Enter a new matrix
(1) Negate the matrix
(2) Multiply a row by a constant
(3) Add one row to another
(4) Add a multiple of one row to another
(5) Transpose the matrix
(6) Quit

Enter your choice:

Notice that main() prints the current matrix before displaying the menu of options. This will allow the user to see the effect of each operation after it has been performed.

Weve also given you the code needed for options 0 and 1, and weve included a preliminary version of the function that prints the matrix.

Your tasks

Read over the starter code that weve given you. Make sure that you understand how the various functions work, and how they fit together.

Revise the print_matrix function so that it uses nested loops to print the matrix in 2-D form. The numbers in a given column should be aligned on the right-hand side, and each number should have two digits after the decimal. For example:

>>> print_matrix([[1, 2, 3], [4, 5, 6]])
1.00 2.00 3.00
4.00 5.00 6.00

To print an individual list element, you should use the following print statement, which includes the necessary formatting string:

print('%7.2f' % matrix[r][c], end=' ')

Note that the value of end is a single space, not an empty string.

Hint: This function is similar to the print_grid function that we gave you for Problem 1.

Add support for options 2-4 so that they perform the specified operations on the matrix.

Important notes:

• You must implement a separate helper function for each option, and these helper functions must have the names, inputs, and behaviors that we specify below. This will allow us (and you) to test the functions on their own, outside of the larger program.
• In addition, you must add code to the provided main() function to call the helper functions. The code that you add should take care of getting whatever values are needed from the user, and of passing those values into the function. The functions themselves should not use the input function.
• Because the code in main() already prints the matrix after every operation, your functions should not do any printing.
• These functions will not need to return anything. This is because you will be passing a reference to the matrix into each function, and thus any changes that are made to the matrix will still be there when the function returns. See the way that weve implemented option 1 (negating the matrix) for an example of this approach.

The functions for options 2-4

• For option 2, write a function mult_row(matrix, r, m) that multiplies row r of the specified matrix by the specified multiplier m. For example:

>>> matrix = [[1, 2, 3], [4, 5, 6]]
>>> mult_row(matrix, 0, 10)
>>> matrix
[[10, 20, 30], [4, 5, 6]]

>>> mult_row(matrix, 1, 0.5)
>>> matrix
[[10, 20, 30], [2.0, 2.5, 3.0]]

• Note that mult_row itself is not doing any printing. Rather, we are evaluting the variable matrix from the Shell to see the result of calling the function.
• You can also use your revised print_matrix to see the results, orafter you have added the code needed in main() to call mult_rowyou can (and should!) look at the results that are printed when you choose this option during a run of the program. However, make sure that you also test this function (and all of your other functions) from the Shell, as shown above. This will ensure that we can test the function on its own during grading.
• For option 3, write a function add_row_into(matrix, rs, rd) that takes the specified 2-D list matrix and adds each element of row rs (the source row) to the corresponding element of row rd (the destination row). For example:

>>> matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
>>> add_row_into(matrix, 0, 2) # add row 0 into row 2
>>> matrix
[[1, 2, 3], [4, 5, 6], [8, 10, 12]]

>>> add_row_into(matrix, 1, 0) # add row 1 into row 0
>>> matrix
[[5, 7, 9], [4, 5, 6], [8, 10, 12]]

• Note that the source row is not changed. Only the destination row is.
• For option 4, write a function add_mult_row_into(matrix, m, rs, rd) that takes the specified 2-D list matrix and adds each element of row rs (the source row), multiplied by m, to the corresponding element of row rd (the destination row). For example:

>>> matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
>>> add_mult_row_into(matrix, 3, 0, 2) # add 3 times row 0 into row 2
>>> matrix
[[1, 2, 3], [4, 5, 6], [10, 14, 18]]

• Here again, the source row is not changed. Only the destination row is. You might be tempted to try to call one or more of your other functions here, but that wont quite work! Have the function do all of the work itself.

Adding support to main()

If you havent already done so, add the code needed in main to call your functions for options 2-4.

• You will need to use the input function to get all of the necessary values from the user. If you need a reminder of how to do this, see the way that our starter code gets the users menu choice. Note that the multipliers needed for options 2 and 4 should be read in as floating-point values, so you will need to use the float() function instead of the int() function for them.
• You wont need to print the results, because the existing code in main() already prints the matrix at the start of each iteration of the user-interaction loop.
• See the sample run for examples of what these options should look like. In particular, make sure that you ask for the inputs for a particular option in the same order that we do in the sample run.

Finally, add support for option 5, which replaces the existing matrix with its transpose. The transpose of an n x m matrix is a new m x n matrix in which the rows of the original matrix become the columns of the new one, and vice versa.

Begin by writing a function transpose(matrix) that takes the specified 2-D list matrix and creates and returns a new 2-D list that is the transpose of matrix. The original 2-D list should not be changed.

For example:

>>> matrix = [[1, 2, 3], [4, 5, 6]]
>>> print_matrix(matrix)
1.00 2.00 3.00
4.00 5.00 6.00

>>> transp = transpose(matrix)
>>> transp
[[1, 4], [2, 5], [3, 6]]
>>> print_matrix(transp)
1.00 4.00
2.00 5.00
3.00 6.00

The function should begin by creating a new matrix with the necessary dimensions. You may want to use (and possibly adapt) one or more of the functions from Problem 1 for this purpose. If you do so, you should copy the necessary functions into ps10pr3.py.

Once the new matrix is created, iterate over its cells and set their values to the appropriate values from the original matrix.

Make sure that you return the new matrix! Because we arent changing the contents of the existing matrix, but rather are creating a new matrix, we need to return it so that it can be used by the caller of the function.

Once your transpose function is working, add code to main to use this function for option 5. The transpose should replace the original matrix in main, so that it can be used in subsequent operations. Replacing the existing matrix was also necessary in option 0, so you could look at how we handled that option.

See the sample run for an example of the desired behavior.

Anyone taking linear algebra?

If youre currently taking linear algebra or a similar course (like CS 132), you could use this program to help you on your homework! In particular, the program supports all of the operations needed to perform Gaussian elimination, which is a procedure that uses matrix operations to solve a system of linear equations. You might even want to extend the program to perform Gaussian elimination for you!

Problem 3: Images as lists

Problem Set 8 included two problems in which you manipulated PNG images using nested loops. In those problems, you used image objects and their associated methods (e.g., get_pixel) to access and change the underlying pixels of the image. If you were to look inside one of those image objects, you would see that the pixels are actually stored in a two-dimensional list, and that the methods of the image object give you indirect access to that 2-D list.

In this problem, you will bypass the use of image objects and work directly with 2-D lists of pixels. And since each pixel is a 1-D list of the form [R, B, G], you will actually be working with a 3-D list!

Getting started

Begin by downloading the following zip file: ps10image.zip

Unzip this archive, and you should find a folder named ps10image, and within it several files, including ps10pr4.py. Open that file in IDLE, and put your work for this problem in that file. You should not move any of the files out of the ps10image folder. Keeping everything together will ensure that your functions are able to make use of the image-processing module that weve provided.

Loading and saving pixels

At the top of ps10pr3.py, weve included an import statement for the hmcpng module, which was developed at Harvey Mudd College. This module gives you access to the following two functions that you will need for this problem:

• load_pixels(filename), which takes as input a string filename that specifies the name of a PNG image file, and that returns a 2-D list containing the pixels for that image
• save_pixels(pixels, filename), which takes a 2-D list pixels containing the pixels for an image and saves the corresponding PNG image to disk using the specified filename (a string).
• To see how these functions work, run ps10pr4.py in IDLE and enter the following command from the Shell:

To see how these functions work, run ps10pr4.py in IDLE and enter the following command from the Shell:

>>> pixels = load_pixels('spam.png')

>>> pixels[0][0] # the upper-left corner of the image, which is red
[255, 0, 0]

>>> for r in range(len(pixels)):
pixels[r][r] = [0, 0, 255] # make the pixels on the diagonal blue ([0, 0, 255])

>>> save_pixels(pixels, 'blue_diag_spam.png')
blue_diag_spam.png saved.

After executing these commands, your ps10image folder should now include a file named blue_diag_spam.png (although the .png extension may or may not be visible). Double-clicking on that file should show you the following image: See image.

Your tasks

In ps10pr4.py, weve given you a function create_pixel_row(width, pixel) that creates and returns a row of pixels with the specified width in which all of the pixels have the RGB values given by pixel. This is similar to the create_row function that we gave you for Problem 1, except that the row is filled with the specified pixel instead of with zeros.

Write a function create_uniform_image(height, width, pixel) that creates and returns a 2-D list of pixels with height rows and width columns in which all of the pixels have the RGB values given by pixel. Because all of the pixels will have the same color values, the resulting grid of pixels will produce an image with a uniform color i.e., a solid block of that color.

We strongly encourage you to make use of our create_pixel_row function to create each row of the 2-D list, just as you used our create_row function in Problem 1 to create your create_grid function. In general, that create_grid function is a good model for this one.

Try testing your function by re-running the file and entering the following from the Shell:

>>> pixels = create_uniform_image(100, 200, [255, 0, 0]) # all red
>>> save_pixels(pixels, 'red.png')
red.png saved.

Because [255,0,0] represents the color red, you should obtain the following solid red image: See image.

If you look closely at our create_pixel_row function, youll notice that we do not make a deep copy of the 1-D list represented by pixel. (To do so, we would have needed to compute a full slice of pixel, or to take some comparable step.)

Failing to perform a deep copy was a deliberate choice on our part, because it allows us to illustrate the impact of Pythons use of references in a dramatic way.

If you havent already entered the commands given above for testing your create_uniform_image function, go ahead and do so now. Once youre done, enter the following commands to create and save a new image that is based on the pixels used to create red.png:

>>> pixels[0][0][1] # the green component of the pixel at [0][0]
0
>>> pixels[0][0][1] = 255
>>> save_pixels(pixels, 'mystery.png')
mystery.png saved.

Before viewing this image, try to predict what it will look like...

Now go ahead and view it!

Pretty amazing, isnt it? There are 20000 cells in the 2-D list pixels, and this new image is the result of a single assignment to the green component of pixels[0][0]!

In comments at the top of ps10pr4.py, write a description of what mystery.png looks like, and explain briefly why its appearance makes sense, even though we only made a single assignment.

Write a function blank_image(height, width) that creates and returns a 2-D list of pixels with height rows and width columns in which all of the pixels are green (i.e., have RGB values [0,255,0]). This function will be very easy to write if you take advantage of your create_uniform_image function!

To test your function, re-run the file and enter the following from the Shell:

>>> pixels = blank_image(100, 50)
>>> save_pixels(pixels, 'blank.png')
blank.png saved.

Heres what blank.png should look like: See image.

Write a function flip_horiz(pixels) that takes the 2-D list pixels containing pixels for an image, and that creates and returns a new 2-D list of pixels for an image in which the original image is flipped horizontally. In other words, the left of the original image should now be on the right, and the right should now be on the left. For example, if you do the following:

>>> pixels = load_pixels('spam.png')
>>> flipped = flip_horiz(pixels)
>>> save_pixels(flipped, 'fliph_spam.png')
fliph_spam.png saved.

you should obtain the following image: See image.

This function will be similar to the flip_vert function that you wrote in Problem Set 7, but it will flip the image vertically instead of horizontally. In addition, there are several other key differences:

• It should take a 2-D list of pixels rather than a filename.
• It does not need to load or save the image, because you will be doing that separately using the load_pixels and save_pixels functions.
• It will manipulate the 2-D list of pixels, rather than an image object.
• It should return the new 2-D list of pixels that it creates.

Your function will need to create a new 2-D list of pixels with the same dimensions as pixels, and you can use your blank_image function for that purpose.

Write a function transpose(pixels) that takes the 2-D list pixels containing pixels for an image, and that creates and returns a new 2-D list that is the transpose of pixels.

You should start by copy-and-pasting your transpose function from Problem 3 into ps10pr4.py. The only real change that you need to make to your earlier function is to change the helper function that gets called to create the new 2-D list. Make this version of transpose call your blank_image function to create the new 2-D list. We also recommend changing the name of the variable matrix to pixels, but doing so is not essential.

Heres one way to test your new version of transpose:

>>> pixels = load_pixels('spam.png')
>>> transp = transpose(pixels)
>>> save_pixels(transp, 'transp_spam.png')
transp_spam.png saved.

This is the image you should obtain: See image.

Write two more functions, both of which should take a 2-D list pixels containing pixels for an image, and create and return a new 2-D list of pixels for an image that is a rotation of the original image:

• rotate_clockwise(pixels) should rotate the original image clockwise by 90 degrees. For example: See image.
• rotate_counterclockwise(pixels) should rotate the original image counterclockwise by 90 degrees. For example: See image.

Both of these functions can be implemented very simply by taking advantage of the other functions that you have already written! In each case, think about how a sequence of two or more transformations of the original image could be used to produce the desired transformation.