Software Carpentry Day 3: Data Structures and Image Processing Exercises

Data Structures (Morning)

A nanotechnology company called Molecules 'R' Us has hired you to write a simple inventory management program for them. Your program is supposed to read in a file describing how many atoms of various kinds are required to make different molecules, and another file describing how many atoms the company actually has in its teeny tiny warehouse, and then print out a list of the molecules the company could make. The first file (describing molecules) is formatted like this:

# Comments start with '#' and go to the end of the line.
# Blank lines (like the one below) are allowed.

helium : He 1               # molecule name, colon, atom type, number of atoms
ammonia : N 1 H 3           # molecules may contain many types of atoms
salt : Na 1 Cl 1            # atom names may be one or two characters long
lithium hydride : Li 1 H 1  # molecule names may be several words long

The file that specifies how many atoms the company has on hand is formatted like this:

# Once again, comments and blank lines are allowed.

He 3                        # atom name, number available
H 2
N 5
Li 1

For these two input files, the output would be:

helium
lithium hydride

Note that molecules' names appear in alphabetical order, and that the system doesn't have to say how many molecules of any type could be made.

To solve this problem, break it up into four pieces:

read_formulas(filename) reads a file of the first kind, returning a dictionary whose keys are the names of molecules, and whose values are also dictionaries showing how many atoms of each kind are required by that molecule. Using the first input file above as an example, read_formulas would return:
```
{
    'helium' : {'He' : 1},
    'ammonia' : {'N' : 1, 'H' : 3},
    'salt' : {'Na' : 1, 'Cl' : 1},
    'lithium hydride' : {'Li' : 1, 'H' : 1}
}
```
read_inventory(filename) reads a file of the second kind, returning a dictionary whose keys are atomic symbols and whose values are the number of atoms of that kind available. Using the second input file above as an example, read_inventory would return:
```
{
    'He' : 3,
    'H' : 2,
    'N' : 5,
    'Li' : 1
}
```
makeable(formulas, inventory) takes a dictionary of formulas as its first argument, and an inventory dictionary as its second, and returns a set of makeable molecules. In this example, its output would be:
```
{'helium', 'lithium hydride'}
```
show_result(molecules) takes a set of molecule names as input, and prints their names in alphabetical order.

Note: you're working with a partner on this exercise, so you could either split up the work and coordinate through a version control repository, or pair program as before. In either case, spend a few minutes thinking of very simple test cases before you start to write your functions. What are the simplest examples of each kind of file? The next-to-simplest? What output should your program produce for them?

Image Processing (Afternoon)

Write a function called greyscale that takes a picture as a parameter and makes it greyscale. To make a pixel grey, get the average intensity of the RGB components and set each component to that average.

You just saw bits of Greg teleport like a bad special effect from Star Trek. Here is the code:

import media

def chromakey(person, background):
    '''Replace blue pixels in the person picture with the corresponding
    pixels in the background picture. The pictures must have the same
    dimensions.'''

    for pixel in person:

        # If the blue dominates the pixel, replace its colour with the colour of
        # the corresponding pixel from the background picture.
        if media.get_blue(pixel) > media.get_green(pixel) and \
                media.get_blue(pixel) > media.get_red(pixel):
            x = media.get_x(pixel)
            y = media.get_y(pixel)
            background_px = media.get_pixel(background, x, y)
            media.set_color(pixel, media.get_color(background_px))

if __name__ == '__main__':
    pic1 = media.load_picture(media.choose_file())
    media.show(pic1)
    pic2 = media.load_picture(media.choose_file())
    media.show(pic2)
    chromakey(pic1, pic2)
    media.show(pic1)

Work with your partner to fix the code so that he can travel in peace instead of in pieces.

The following picture has lots of stars in it:

Write a function turn_stars_blue(pic, intensity) that makes all pixels in Picture pic that are brighter than the intensity the color media.blue.

Now a really tough one: write a function flood_fill(pic, x, y, intensity, c) that sets all pixels in Picture pic brighter than int intensity and connected to x, y to Color c. You can assume that c's brightness is less than intensity. Hint: you can call flood_fill from within the body of flood_fill.

Write a function count_stars(pic, intensity) that counts stars in Picture pic that are brighter than int intensity and returns that count. Hint: stars usually take up more than one pixel but you only want to count each star once. Use flood_fill when you find a bright pixel so that you can colour the entire star a dark colour such as media.darkblue.

One of the Reasons Programming Is Hard

Where would you shelve books by the following authors?

Leonardo da Vinci
Catherine de Medici
Juan Ponce de Leon
Jean de La Fontaine
Gabriel Garcia Marquez
Wernher von Braun
Elizabeth Alexandra May Windsor
Thomas a Beckett
Mao Tse-tung

The correct answers are:

Leonardo da Vinci under 'L' ("da Vinci" just means "from Vinci")
Catherine de Medici under 'M': family name
Juan Ponce de Leon under 'P': full family name is "Ponce de Leon"
Elizabeth Alexandra May Windsor under 'E': monarchs sort by the name under which they took the throne
Thomas a Beckett under 'T': special rules for saints, too
Gabriel Garcia Marquez under 'G': double-barrelled Spanish surname
Jean de La Fontaine also under 'L': family name is "La Fontaine"
Wernher von Braun: depends whether he was in Germany or the US when he wrote the book (no, I'm not kidding)
Mao Tse-tung under 'M': Chinese family names come first

My thanks to Margaret Menzin for this example.