Question

Task 1
------

Soda-straw aquarium

Introduction

In the second soda-straw world simulation in lab the blobs lived in a barren world devoid of food, so all they could do was wander around until they starved to death. How depressing! This assignment adds food to the simulated world, which randomly grows and dies, and may be eaten by blobs. Blobs grow in size when they eat food, and if they get big enough they reproduce themselves by dividing in two. Of course they still shrink when they don't eat and so may may still starve to death if there is not enough food around them. Though by real-world standards this is still a very simple world, it is complex enough to demonstrate behavior that may be surprising.

To add interest to the simulation, we allow the probabilities of food growing and dying to be easily varied. Other parameters (in the general sense of the word) of this simulation, such as the size at which blobs divide and how fast they move, remain fixed. Still, changing the food evolution probabilities can dramatically effect the likelihood of blob survival and the patterns of their growth and death.

eScientists learn much about possibilities in the real world by similarly varying simulation parameters and studying the results. If a simulation's overall performance matches observed behavior in the real-world, this increases the likelihood that the simulation may accurately predict events under conditions that have not been observed yet but may happen in the future. Changes in water temperature are know, for example, to have a profound effect on the growth, and death, of food in the world's oceans. Computer simulations are extensively used to predict effects of global warming on ocean life years in the future.

Rules for extending the soda-straw world simulation

Simulations always make lots of simplifying assumptions. We assume food is of only one kind, and either exists, or not, in some fixed quantity in each world location. It can grow (appear) only in empty locations and never moves from its location. If a blob moves into a food location, the food is entirely consumed by the blob, and the blob then grows one unit in size. If a blob grows to its maximum size, it instantly divides into two blobs of half that size each. That's the basic idea, but we need a few rules to specify all the detail of the new simulation.

We extend the soda-straw world simulation from lab and its rules with the following additional food and blob evolution rules:

In each time interval, simulation begins by simulating food growth and death, followed by simulation of blob evolution.
Here "evolution" means "change with time", which includes motion, size changes, and the immediate consequences of these changes, such as blobs possibly dividing in half.
In each time interval, food may grows (appears out of nowhere) in any empty world location with some specified food growth probability.
In each time interval, any food (existing at the end of the last time interval) may die (in which case its location becomes empty) with some specified food death probability.
If a blob has food on one side and none on the other, it always eats (moves to and consumes) the food.
If a blob has food on both sides, it chooses between the food with equal probability.
If a blob moves to a location containing food, the food is consumed and the blob gets one unit bigger.
As before, if a blob does not move or moves to an empty space, it gets one unit smaller, and dies if its size becomes zero.
When a blob reaches size 10, it instantly (in the same time unit), splits into two blobs of size 5 each. One of these is in the location that contained the food just eaten, and the other is in the location the blob just moved from.
In evolution pictures we now print two world lines for each time step, one showing the results of food growth and death and the other the results of blob evolution. We represent food with the star * character. Here is such a picture for a simulation in which the food growth probability is 0.5, and the food death probability is 0.2. Thus if there is food in a given location at the beginning of time unit, there is a 20% chance of it dying at that time, which will be before the blob behavior in that time is simulated.

|*9.*.4*.*823*.4..*|
|*9**.4*.*823**4.**|
|55**..5.91..45..**|
|55*.**5.91.*45***.|
|4.6.*6.8...5..6**.|
|4.6*.6*8**.5*.6**.|
|.3.7..7.9*..6..7*.|
|*3.7..7*9**.6**7*.|
|4...6..855*..78.*.|
|4..*6.*855*..78.*.|
|.3.7..94..6.67..*.|
|.3*7*.94**6*67.**.|
|..4.88..57.7..6**.|
|*.4.88*.57*7..6.**|
|*3.7..94..8.6..5**|
|.3*7..94.*8.6.*5**|
|..4.68..39.5..6.**|
|**4*68..39*5**6***|
|*5.7..72.55.67.***|
|*5.7*.72.55.67.**.|
|6...86..14.45.6**.|
Carefully check that this picture is consistent with the rules above. How many times did blobs divide and die? Where did food grow, and die before being eaten? It appears from this example that food may have a better chance of survival if it is near a wall, which makes sense since blobs can then get to it from only one side.

We add the two food probabilities as arguments to the simulation function.

def simulate(world_string, food_growth_prob, food_death_prob, total_time):
"""
Print an evolution picture for the blob world, starting
with the indicated world and continuing for the given number
of time units. Use the indicated food growth and death probabilities.
"""
#.
#.
#.
#.
#.
#.
#.
#.
#.
#.
Each time around the simulation loop a food_step function is called to simulate the food growth phase of a time step, prints the world, and then calls blob_step and prints the world a second time.

def food_step(world, food_growth_prob, food_death_prob):
"""
Simulate one time unit of possible food growth and death for the given
world. The world list contains the food probabilities.
"""
#.
#.
#.
#.
#.
#.
#.
#.
#.
Much of the function blob_step is similar to the previous version.

def blob_step(world):
"""
Simulate blob changes of one time step in the given world, in accord
with the blob motion rules, the blob evolution rules, and the food growth
rules.
"""
index = 1
while True:
char = world[index]
if char == WALL:
break
elif char.isdigit(): # it's a blob
#.
#.
#.
#.
#.
#.
#.
#.
else: # nothing to eat
world[index] = str(int(world[index]) - 1) # shrink
if world[index] == '0': # shrinks to 0 and dies
world[index] = EMPTY
elif world[index - 1] == EMPTY: # can move left
if world[index + 1] == EMPTY and chance(0.5):
# move right half of the time when both possible
move_blob(world, index, index + 1)
index = index + 1 # blob has moved to right
else: # move left
move_blob(world, index, index - 1)
elif world[index + 1] == EMPTY: # move right
move_blob(world, index, index + 1)
index = index + 1
# else can't move left or right
index = index + 1
The style is improved by using a separate function to handle the complexity of eating food and possible blob division.

def eat(world, blob_index, food_index):
"""
Simulate a blob eating food according to the blob evolution rules.
"""
#.
#.
#.
#.
#.
#.
As always, look for ways to simplify the problem and approach it in stages. For example, you might implement and test the new blob behavior with food added to the world initially, and add food growth and death later. If you cannot get every feature working, document what is missing and you will loose less credit.

Determining if you have a correct solution to a problem this complex is not easy. To gain a more practical understanding of each rule, it helps to make up some very simple worlds with only a few locations and determine what the next step in evolution must be, or could be with certain probabilities.

You need to check a lot of evolution picture lines carefully and verify that all changes from one line to the next are consistent with the rules. It will help to test the simulator with some initial worlds that are constructed to test as many of the rules as possible in the first time step or two.

But that is not enough. You also need to read each rule very carefully and check that your code's behavior will be consistent with the rule.

Finally, run a number of tests, with different initial worlds and probabilities. What general hypothesis might be draw from patterns you observe in the evolution pictures? (One example is the speculation above about food being more likely to survive near walls.) Include a doc string at the beginning of your program that includes two or three such speculations (in English sentences), along with evolution pictures or picture fragments that provide support for your speculations. This doc string should not be more than 100 lines long (most of which are evolution pictures).

-----------------------------------------------------------------------

Task 2
------

Mortgage Data


Introduction

The United States Department of Housing and Urban Development (HUD) publishes data for all mortgages backed by the "government-sponsored enterprises" Fannie Mae and Freddie Mac, which you may have heard in relation to the current financial crisis. (Though these enterprises have contributed somewhat to the overall mortgage crisis, contrary to some claims they have not played a major role in the overall situation.)

The 2006 data is available for download from http://www.huduser.org/DATASETS/gse/gse2006.html in a zip archive that contains several files. We will just be using the primary data file, MF2006C.LOA, and the description of its contents. This data file has about 13,000 lines and a million characters. The format of the data is once again a table in which each row is a line of characters and the columns are separated by whitespace.

The data description uses standard terms from the database world, where table rows are called records and columns are called fields. Visit the description link above and see that field 12 (one-based counting, third from last) contains a digit that is a code for the "unpaid balance" when the mortgage was "acquired". Roughly speaking this is size of the loan. Note especially that the code "9" means the data is missing. For example, in the first line of data:

11 06 41940 XXX XXXXXX 53.35 113759 XXXXXX.XXXX 97100 5 1 2
the code is 5, so the size was over 4 million dollars.

Fields 9 and 11 indicate median income in the area in census years 2000 and 2006, respectively. (The "median" of a set of data values is the "middle" value: about half are greater and half are less. It may be close to the mean (average), but if the data is "skewed" it is not.) These fields have integer values and the value "999999" indicates missing data. The growth of median income in the area (the difference between the field 11 value and the field 9 value) is an indication how much the "prosperity" of the area was changing in the few years before the mortgage. For example, this growth was 97100 - 80198, or $16,902, in the area of the mortgage associated with the first line of data above.

All kinds of questions can be asked about this much data, and the answers to the right questions may be very in policy making. Often it is necessary to look at the data in many ways to discover what is really significant. One question that could be asked is

What effect the change in prosperity of the area has on the values of the mortgages in the area?
Let's develop a program to help answer this question. (Whether this is really a valuable question to ask about this data we leave to economists. Our interest is in learning to do the kind of programming that data analysis of this kind requires, regardless of the field of study.)

It's a rather vague question that could be looked at in several ways. The effects we are looking for may be different for different sizes of mortgages, so we decide to print a histogram of the mortgage size codes. That way we can see in one picture the relative effects over a range of mortgage sizes. And we would like to look at such histograms for several mortgages from areas with several different ranges of change in prosperity.

These ideas lead us to design a function mortgage_size_histogram that takes parameters low and hi providing lower and upper bounds on the size of the income change in the area. For example,

mortgage_size_histogram(5000, 10000)
will print a histogram of mortgage size codes by scanning all the data but using only lines in which the difference between the 2006 and 2000 income values was greater than 5000 and less than 10000.

We would like to use the histogram function from lab 11, but the size of the data presents a problem (almost 20,000 records, though many will not fall in a given income change range). For ranges of interest, such as $5,000 to $10,000 in the example above, there are well over 1000 montages in the over $4 million range. We don't want a histogram with over 1000 stars on a line!

This prompts a small change in the histogram function, giving it an extra parameter named values_per_star. The number of stars printed on a line will be the count in the corresponding accumulator divided by this number. We assume this number is an integer and do not worry about the lost remainder when we do this division. We only need to change a line or two in the body of the function.

def histogram(int_list, values_per_star):
"""
Print a histogram of the integers in int_list, with at most max_stars
on a line.
>>> histogram([2, 5, 4, 5, 4, 3, 2, 4, 4, 3, 6, 2], 1)
2 ***
3 **
4 ****
5 **
6 *
>>> histogram([2, 5, 4, 5, 4, 3, 2, 4, 4, 3, 6, 2], 2)
2 *
3 *
4 **
5 *
6
>>>
"""
min_data = min(int_list)
max_data = max(int_list)
accumulators = [0] * (max_data - min_data + 1)
index = 0
while index < len(int_list):
data = int_list[index]
accumulators[data - min_data] = accumulators[data - min_data] + 1
index = index + 1
data_column_width = len(str(max_data))
index = 0
while index < len(accumulators):
line_value = str(min_data + index).rjust(data_column_width)
#.
#.
#.
Now we are ready to create a skeleton for the main function.

def mortgage_size_histogram(low, hi):
"""
Print a histogram of mortgage size codes (field 12), for mortgages
from areas in which the median income change from 2000 to 2006 is
between the parameter values low and hi. Each histogram star
represents 50 mortgages. The data is in the file MF2006C.LOA.
"""
fob = open('MF2006C.LOA')
SIZE_CODE_INDEX = 11 # zero-based index for field 12
INCOME_2000_INDEX = 8
INCOME_2006_INDEX = 10
#.
#.
#.
#.
#.
#.
#.
#.
#.
#.
#.
#.
#.
#.
#.
#.
#.
#.
Some sample output follows:

>>> mortgage_size_histogram(5000, 10000)
1 **********
2 **************
3 ******************
4 ********************
5 *********************************
>>> mortgage_size_histogram(10000, 15000)
1 *******************************
2 ***********************
3 ************************
4 ***********************
5 *************************************
>>> mortgage_size_histogram(15000, 20000)
1 ******
2 ***
3 **
4 **
5 *****
Hints on program structure

Since we want to read the data a line at a time, this calls for a sentinel (end-of-file) loop that accumulates a list of numbers. The area income difference from 2000 to 2006 needs to be computed for each record (line) of data, and the mortgage size value added to the accumulation list only if it the difference is between low and hi. (With such large numbers it does not really matter if we use < or <= when testing the ranges.) Actually, before using any of the field values we need to check if the data in any of the three fields we are using is missing, and if so skip that record.

When this loop is done, we pass the code number list to the histogram function, indicating one star for each 50 values.----------------------------------------------------------------------

Task 3
------

Simple Ciphers

Several encryption-specific terms are introduced in this assignment to help state the assignment problems and express their "real world" context. You need to follow their meaning in this assignment, but will not be held responsible for them later.
We've learned enough now to implement some crude forms of hiding data, including data encryption. Text with hides data is called cipher text and the text that is hidden is called plain text.

One simple approach to hidding information is to bury it in garbage! When the plain text (information being hidden) appears at regular intervals amidst the garbage, this is called a "skip cipher". A simple way to generate a skip cipher is to insert a random character before every character of the text to be hidden. For example, for the plain text "cat", we might cipher text might be "fcdaut".

We just need a function that takes two strings and merges them into one string. In the example above, one string is "fdu" and the other is "cat", and the merged result is "fcdaut". Notice that in the resulting string each character in the first string is followed by the corresponding character in the second string. Here by "corresponding" we mean "having the same index". We will see that this notion of "correspondence" is important a number of computer programs.

def merge(s1, s2):
"""
Return a string that consists of the characters in strings s1 and s2 such
that every character from s1 is followed by the corresponding character in
s2. Assume s1 and s2 have the same length.
>>> merge('abc', 'def')
'adbecf'
>>>
"""
#.
#.
#.
#.
#.
#.
Merging operations such as this, on various kinds of data, are also common in computer programs.

Using the merge and random letter functions it is now easy to program a function a function that generates a simple skip cipher.

def skip_cipher(s):
"""
Return the result of encrypting string s by inserting
a randomly chosen letter before every letter of s.
>>> skip_cipher('cat')
'fcdaut'
>>>
"""
#.
#.
It is very tedious to extract text that is hidden in this way, so we would also like to have a function that extracts every other character in a string.

def every_other(s):
"""
Return a string consisting of every other character in string s,
starting from the second character.
>>> every_other("fcdaut")
'cat'
>>> every_other('The Knights said Ni!')
'h ngt adN!'
>>>
"""
# Hint: use an indexed accumulating loop
#.
#.
#.
#.
#.
#.
"Encryption" refers to techniques for systematically transforming data to form cipher text. The simplest approach, called a "substitution cipher", is to replace every character in the alphabet in the plain text with some other character in a systematic way. The best known kind of substitution ciphers is a "rotation", or "rot", cipher in which each character is replace by the one that is a fixed distance from it in the alphabet. For example, in a rot-1 cipher "a" is replace by "b", "b" by "c", and so on. The notion of "rotation" comes in because at the end of the alphabet it rotates back to the beginning. Thus in rot-1, plain text "z" becomes cipher text "a". The most widely used rotation cipher is rot-13, because it rotates exactly half-way around the alphabet. (There are 26 letters and 13 is 26/2.) Thus rot-13 has the nice property that the encryption function, which converts plain text to cipher text, is the same as the decryption function, which converts cipher text back to plain text.

Rotation ciphers (along with other substitution ciphers that use a fixed character transformation) were in serious use a few hundred years ago, until it was discovered that they are easy to "crack". The rot-13 cipher is still used in some very low-security computer applications.
To simplify implementation of a rotation-cipher encryption function, we will only do rotation on lower-case characters. How can our program recognize a lower-case character? One way would be an expression such as

c in 'abcdefghijklmnopqrstuvwxyz'
Using features of Python that we have not learned yet there are several other, more elegant, ways to do this. But it is also a good exercise to try defining a function to do the job using just what we have learned of Python so far.

def is_lower(char):
"""
Return a boolean value indicating if char is a lower-case letter.
>>> is_lower('g')
True
>>> is_lower('G')
False
>>> is_lower('*')
False
>>>
"""
if ord('a') <= ord(char):
#.
#.
#.
The rot-13 function itself is mostly an indexed accumulating loop with a structure similar to several you have already done. The new part of course is rotating a lower-case character. To do this, it is first necessary to compute the zero-based position of the character in the alphabet (so "a" is in position 0 and "z" in position 25). Since the lower case characters are all in sequence in the ASCII character set, the position in the alphabet of a character, c, can be obtained by subtracting the ordinal value of the character "a" from the ordinal value of c.

Once you have the zero-based alphabet position of a character, add 13 to this position in a way that "rotates" around to 0 when it goes beyond 25. Recall that the Python's modulus operator accomplishes such numeric "rotations" nicely. Finally, the rotated position number has to be converted back into an ASCII ordinal position and then back into a character.

Taken as a whole this process seems rather complicated, but if you carefully follow this breakdown into separate small operations, and you focus on one at a time, it is not that bad. Much of the challenge of programming is putting together a number of small peaces, each of which is not very complicated, to form a whole that does a lot automatically. The computations in the last two paragraphs can be expressed reasonably in about three lines of code with a managable amount being done on each line.

Here is the skeleton for the complete function:

def lower_rot13(s):
"""
Return the result of encoding the string s by applying the 'rot-13'
cipher to the lowercase characters in s and leaving the the others
unchanged.

>>> lower_rot13('abc')
'nop'
>>> lower_rot13('nop')
'abc'
>>> lower_rot13('This is an encoded message.')
'Tuvf vf na rapbqrq zrffntr.'
>>>
"""
#.
#.
#.
#.
#.
#.
#.
#.
#.
#.
#.
#.
#.