Midterm

Due: 5:00 p.m. EST, Tuesday 01 November 2005

Total Marks: 40.

Weight: 10% of course grade.

Submit your solutions by adding files to the directory midterm in your Subversion repository. If any of the questions are unclear, please email Greg Wilson directly at gvwilson@cs.utoronto.ca, rather than using the course mailing list.

Question 1 (10 marks)

You and your supervisor are studying the growth of thin films on flat surfaces. Surfaces are modelled using a Python class called Grid, which stores a two-dimensional (X by Y) array of cells. Each cell holds a non-negative integer whose value is greater than or equal to zero, and less than a positive integer value Lim that is specified when the grid is created.

Rather than writing a full description of Grid in English, your supervisor has written some tests for it (see gridtest.py in your midterm directory). For 10 marks, write a class that passes all of these tests. (Note that you may not modify gridtest.py.) Put your solution in a file called grid.py.

Question 2 (10 marks)

One way to study film growth is to use a simple random simulation. The simulator creates an X by Y grid with a Lim of 2, so that cell values are either 0 (empty) or 1 (filled), and sets the central cell's value to 1. It then fills in one cell at a time until it reaches the boundary of the grid.

In order to decide what cell to fill in next, the program finds all the empty cells that are adjacent to exactly one filled-in cell. It then chooses one of these candidates at random. For example, if the black squares in Figure 1 below are filled cells, then the red squares are candidates. If the candidate cell marked with an X in Figure 1 is selected and filled in, the new grid, and new candidates, are as shown in Figure 2.

Figure 1	Figure 2

For 5 marks, write a function called isCandidate that takes a Grid, an X coordinate, and a Y coordinate as arguments, and returns True if (X,Y) is a candidate cell, and False if it is not. If any of the arguments are invalid, your function must throw a ValueError exception. Put your function in candidate.py.

For another 5 marks, write as many unit tests as you think you need to in order to demonstrate that isCandidate is working properly. Use the unittest framework, and include these tests in candidate.py. Note that if someone else's program does this:

then your tests must not be executed---they should only run if someone types:

at the command line.

Question 3 (10 marks)

A Rudie number is a positive integer that has two properties:

1. No digit appears in it more than once.
2. It is divisible by all of its digits.

According to these rules, 4, 12, 15, and 61248 are Rudie numbers. 10 is not (division by zero is not allowed); neither are 11 (the digit 1 appears twice), 14 (not divisible by 4), or 27 (not divisible by either 2 or 7).

For 5 marks, write a function called isRudie that takes a single integer as an argument, and returns True if that integer is a Rudie, and False otherwise. Put your function in a file called rudie.py.

For an additional 5 marks, add more code to rudie.py so that when it is run from the command line like this:

$ python rudie.py 5

it finds the largest 5-digit Rudie number. (Obviously, if 3 is used instead of 5, your program should find the largest 3-digit Rudie number, and so on.) As with the previous question, this additional code must not be executed if some other program imports your function.

Question 4 (10 marks)

Rewrite copychange.py to make it easier to read and safer to use. Submit your answer by checking in your changes to copychange.py.