3.1 Using Data Types

In the first two chapters of this booksite our programs were confined to operations on numbers, booleans, and strings. Of course, the reason is that the Python data types that we've encountered so far — int, float, bool, and str — manipulate numbers, booleans, and strings, using familiar operations. In this chapter, we begin to consider other data types.

In this section, we focus on client programs that use existing data types, to give you some concrete reference points for understanding these new concepts and to illustrate their broad reach. We introduce constructors to create objects from a data type and methods to operate on their values. We consider programs that manipulate electrical charges, colors, images, files, and web pages — quite a leap from the built-in data types that we used in previous chapters.

Methods

A method is a function associated with a specified object (and, by extension, with the type of that object). That is, a method corresponds to a data-type operation.

We can call (or invoke) a method by using a variable name, followed by the dot operator (.), followed by the method name, followed by a list of arguments delimited by commas and enclosed in parentheses. As a simple example, Python's built-in int type has a method named bit_length(), so you can determine the number of bits in the binary representation of an int value as follows:

x = 3 ** 100
bits = x.bit_length()
stdio.writeln(bits)

This code writes 159 to standard output, telling you that 3¹⁰⁰ (a huge integer) has 159 bits when expressed in binary.

The syntax and behavior of method calls is nearly the same as the syntax and behavior of function calls. For example, a method can take any number of arguments, those arguments are passed by object reference, and the method returns a value to its caller. Similarly, like a function call, a method call is an expression. The main difference is syntactic: you invoke a method using a specified object and the dot operator. In object-oriented programming we usually prefer method-call syntax to function-call syntax because it emphasizes the role of the object.

The key difference between a function and a method is that a method is associated with a specified object. You can think of this specified object as an extra argument that gets passed to a function, in addition to the ordinary methods argument.

String Processing

Your experience with using str demonstrates that you do not need to know how a data type is implemented to be able to use it. You know that str values are sequences of characters and that you can perform the operation of concatenating two str values to produce a str result.

Python's str data type includes many other operations, as documented in the API shown below.

The operations in the str API can be divided into three categories:

Built-in operators +, +=, [], [:], in, not in, and the comparison operators, which are characterized by special symbols and syntax
A built-in function len() with standard function-call syntax
Methods upper(), startswith(), find(), and so forth, which are distinguished in the API with a variable name followed by the dot operator

From this point forward, any API that we might consider will have these kinds of operations. Next, we consider each of them in turn.

Built-in operators.

An operator (or function) that you can apply to more than one type of data is said to be polymorphic. You have already been using the + operator, familiar for numbers, for string concatenation. The API tells you that you can use the [] operator, familiar for arrays, to extract a single character from a string and the [:] operator to extract a substring from a string.

Built-in functions.

Python also builds in a number of polymorphic functions, such as the len() function. Polymorphic functions are like polymorphic operators, but without the special syntax.

Methods.

We include built-in operators and built-in functions for convenience (and to conform to Python norms), but most of our effort in creating data types goes into developing methods that operate on object values, such as upper(), startswith(), find(), and the other methods in the str API.

The table below gives several examples of simple string-processing applications that illustrate the utility of the various operations in Python's str data type.

The program potentialgene.py is a more substantial example of string processing. The program accepts a DNA sequence as a command-line argument, and determines whether it corresponds to a potential gene. The textbook provides details.

A User-Defined Data Type

As a running example of a user-defined data type, we will consider a data type Charge for charged particles. In particular, we are interested in a two-dimensional model that uses Coulomb's law, which tells us that the electric potential at a point due to a given charged particle is represented by V = kq/r, where q is the charge value, r is the distance from the point to the charge, and k = 8.99 × 10⁹ N m²/C² is a constant known as the electrostatic constant, or Coulomb's constant. For consistency, we use SI (Systeme International d'Unites): in this formula, N designates newtons (force), m designates meters (distance), and C represent coulombs (electric charge). When there are multiple charged particles, the electric potential at any point is the sum of the potentials due to each charge.

Application programming interface.

We specify the behavior of the Charge data type by listing its operations in an API, deferring the discussion of the implementation until Section 3.2.

The first entry in the API, which has the same name as the data type, is known as a constructor. Each call to the Charge constructor creates exactly one new Charge object. The other two entries define the data-type operations. The first is a method potentialAt(), which computes and returns the potential due to the charge at the given point (x, y). The second is the built-in function str(), which returns a string representation of the charged particle.

File conventions.

The code that defines a user-defined data type resides in a .py file. By convention, we define each data type in a distinct .py file, with the same name as the data type (but not capitalized). Thus, the Charge data type is found in a file named charge.py. To compose a client program that uses the Charge data type, we put the following import statement at the top of the client .py file:

from charge import Charge

Note that the format of the import statement that we use with user-defined data types differs from the format we use with functions.

Creating objects.

To create an object from a user-defined data type, you call its constructor, which directs Python to create a new individual object. You call a constructor just as if it were a function, using the name of the data type, followed by the constructor's arguments enclosed in parentheses and separated by commas. For example, Charge(x0, y0, q0) creates a new Charge object with position (x0, y0) and charge value q0 and returns a reference to the new object.

Four variables referring to three Charge objects

You can create any number of objects of the same data type. Recall from Section 1.2 that each object has its own identity, type, and value. So, while any two objects reside at distinct places in computer memory, they may be of the same type and store the same value.

Calling a method.

As discussed at the beginning of this section, we typically use a variable name to identify the object to be associated with the method we intend to call. For our example, the method call c1.potentialAt(.20, .50) returns a float that represents the potential at the query point (0.20, 0.50) due to the Charge object referenced by c1. The distance between the query point and the charge location is 0.34, so this potential is 8.99 × 10⁹ × 21.3 / 0.34 = 5.63 × 10¹¹.

String representation.

In any data-type implementation, it is typically worthwhile to include an operation that converts an object's value to a string. Python has a built-in function str() for this purpose, which you have been using from the beginning to convert integers and floats to strings for output. Since our Charge API has a str() implementation, any client can call str() to get a string representation of a Charge object. For our example, the call str(c1) returns the string '21.3 at (0.51, 0.63)'.

These mechanisms are summarized in the client chargeclient.py, which creates two Charge objects and computes the total potential due to the two charges at a query point taken from the command line.

Next we consider several more examples of user-defined data types.

Color

Color is a sensation in the eye attributable to electromagnetic radiation. Since we often want to view and manipulate color images on our computers, color is a widely used abstraction in computer graphics.

To represent color values, we define a Color data type.

Color uses the RGB color model, in which a color is defined by three integers, each between 0 and 255, that represent the intensity of the red, green, and blue (respectively) components of the color. Other color values are obtained by mixing the red, green, and blue components. Color has a constructor that takes three integer arguments, so that you can compose the code

red  = Color(255,   0,   0) 
blue = Color(  0,   0, 255)

to create objects whose values represent pure red and pure blue, respectively. We have been using colors in stddraw since Section 1.5, but have been limited to a set of predefined colors, such as stddraw.BLACK, stddraw.RED, and stddraw.PINK. Now you have millions of colors available for your use.

The program alberssquares.py is a Color and stddraw client that allows you to experiment with colors. The program accepts two colors from the command line, and displays the colors in the format developed in the 1960s by the color theorist Josef Albers, who revolutionized the way that people think about color.

% python alberssquares.py 9 90 166 100 100 100

% python alberssquares.py 0 174 239 147 149 252

Luminance.

The quality of the images on modern displays such as LCD monitors, LED TVs, and cellphone screens depends on an understanding of a color property known as monochrome luminance, or effective brightness. A standard formula for luminance is derived from the eye's sensitivity to red, green, and blue. It is a linear combination of the three intensities: if a color's red, green, and blue values are r, g, and b, respectively, then its luminance is defined by this formula:

Y = 0.299r + 0.587g + 0.114b

Grayscale.

The RGB color model has the property that when all three color intensities are the same, the resulting color is on a grayscale that ranges from black (all 0s) to white (all 255s). To print a color photograph in a black-and-white newspaper (or a book), we need a function to convert from color to grayscale. A simple way to convert a color to grayscale is to replace the color with a new one whose red, green, and blue values equal its monochrome luminance.

Color compatibility.

The luminance value is also crucial in determining whether two colors are compatible, in the sense that printing text in one of the colors on a background in the other color will be readable. A widely used rule of thumb is that the difference between the luminance of the foreground and background colors should be at least 128. For example, black text on a white background has a luminance difference of 255, but black text on a (book) blue background has a luminance difference of only 74.

Program luminance.py is a module that we can use to convert a color to grayscale and to test whether two colors are compatible, for example, when we use colors in stddraw applications. The functions in luminance.py illustrate the utility of using data types to organize information. Using the Color data type and passing objects as arguments makes these implementations substantially simpler than the alternative of having to pass around the three intensity values. Returning multiple values from a function also would be awkward and more error prone without the Color data type.

Digital Image Processing

We have been using stddraw to plot geometric objects (points, lines, circles, squares) in a window on the computer screen. The basic abstraction for computer displays is the same one that is used for digital photographs and is very simple: A digital image is a rectangular grid of pixels (picture elements), where the color of each pixel is individually defined. Digital images are sometimes referred to as raster or bitmapped images.

Our Picture data type, defined in the module picture.py, implements the digital image abstraction. The set of values is nothing more than a two-dimensional array of Color values, and the operations are described by this API:

By convention, (0, 0) is the upper leftmost pixel, so the image is laid out as in the customary order for arrays (by contrast, the convention for stddraw is to have the point (0,0) at the lower-left corner, so that drawings are oriented as in the customary manner for Cartesian coordinates).

Using the Picture constructor you can create a Picture object by reading an image from a .png or .jpg file. Using the save() method, you can save the images that you create in either .png or .jpg format; subsequently can view the images that you create in the same way that you view photographs or other images. In addition, the stddraw module supports a picture() function that allows you to draw a given Picture object in the standard drawing window along with lines, rectangles, circles, and so forth.

Grayscale.

The program grayscale.py is a filter that takes a file name from the command line and produces a grayscale version of that image. It creates a new Picture object initialized with the color image, then sets the color of each pixel to a new Color having a grayscale value computed by applying the toGray() function in luminance.py to the color of the corresponding pixel in the source. Try running it on the files mandrill.jpg, mandrill.png, darwin.jpg, and darwin.png.

% python grayscale.py mandrill.jpg

% python grayscale.py darwin.jpg

Scaling.

One of the most common image-processing tasks is to make an image smaller or larger.

The program scale.py takes a filename and the width and height of the target image as command-line arguments, and rescales the image to the specified size. Try running it on mandrill.jpg, mandrill.png, darwin.jpg, and darwin.png.

% python scale.py mandrill.jpg 200 200

% python scale.py mandrill.jpg 200 100

% python scale.py mandrill.jpg 100 200

Fade effect.

The program fade.py is a Picture, Color, and stddraw client that uses a linear interpolation strategy to implement a fade effect. It computes n - 1 intermediate images, with each pixel in the tth image being a weighted average of the corresponding pixels in the source and target. The function blend() implements the interpolation: the source color is weighted by a factor of 1-t/n and the target color by a factor of t/n (when t is 0, we have the source color; when t is n, we have the target color). Note that fade.py assumes that the images have the same width and height; if you have images for which this is not the case, you can use scale.py to create a scaled version of one or both of them for fade.py. Try running it on various permutations of mandrill.jpg, mandrill.png, darwin.jpg, and darwin.png.

% python fade.py mandrill.png darwin.png 5

Potential value visualization.

Image processing is also helpful in scientific visualization. Program potential.py visualizes the potential values created by a set of charges. It relies on the data file charges.txt. The calculation at the heart of the approach is very simple: for each pixel, we compute corresponding (x, y) values in the unit square, then call potentialAt() for each charge to find the potential at that point due to all of the charges, summing the values returned.

% python potential.py < charges.txt

Input and Output Revisited

A bird's eye view of a Python program (revisited again)

In Section 1.5, you learned how to read and write numbers and text using our stdio module. When using stdio, we are dependent upon the operating system's piping and redirection mechanism for access to files, and any one program can work with just one input file and one output file.

In this section we define the data types InStream and OutStream for input streams and output streams, respectively. Rather than being restricted to just one input stream and one output stream, we can readily create multiple objects of each data type, connecting the streams to various sources and destinations. We also get the flexibility to set variables to reference such objects, pass them as arguments to or return values from functions or methods, and create arrays of them, manipulating them just as we manipulate objects of any data type.

Input stream data type.

Our data type InStream, defined in the module instream.py, is a more general version of the reading aspects of stdio that supports reading numbers and text from files and websites as well as the standard input stream. This is its API:

When you call the InStream constructor with a string argument, the constructor first tries to find a file on your local computer with that name. If it cannot do so, it assumes the argument is a website name and tries to connect to that website. (If no such website exists, it raises an IOError at run time.) In either case, the specified file or website becomes the source of the input for the InStream object thus created, and the read*() methods will read input from that stream.

Output stream data type.

Similarly, our data type OutStream, defined in the module outstream.py, is a more general version of the writing aspect of stdio that supports writing strings to a variety of output streams, including standard output and files. Again, the API specifies the same methods as its stdio counterpart.

You specify the file that you want to use for output by using the one-argument constructor with the file's name as argument. OutStream interprets this string as the name of a new file on your local computer, and sends its output there.

File concatenation and filtering.

The program cat.py is a sample client of InStream and OutStream that uses multiple input streams to concatenate several input files into a single output file. For example, this command concatenates files in1.txt and in2.txt to create the file out.txt:

python cat.py in1.txt in2.txt out.txt

Screen scraping.

The program stockquote.py is a client of the str and InStream data types. It queries a web page, extracts some information, and reports the results — a process known as screen scraping. Specifically, the program accepts as a command-line argument the symbol of a New York Stock Exchange stock and writes its current trading price to standard output. For example, if the command-line argument is goog (the NYSE symbol for Google), the program reads the Web page http://finance.yahoo.com/q?s=goog using the InStream constructor, identifies the stock price of Google using str methods, and writes the stock price to standard output. The program depends on the format of the Yahoo web page; if Yahoo changes their web page format, we would need to change our program. Nevertheless, this is likely more convenient than maintaining the data ourselves.

Extracting data.

The program split.py uses one InStream object and multiple OutStream objects to split a CSV (comma-separated value) file into separate files, one for each comma-delimited field. For example, the command

python split.py djia 3

splits the file djia.csv into files djia1.txt, djia2.txt, and djia3.txt.

Memory Management

In Python, we create objects by calling a constructor. Each time we create an object, Python reserves computer memory for that object. But when and how do we destroy objects so that the memory in which they reside can be freed for reuse? We will briefly address this question.

Orphaned objects.

The ability to bind a variable to a different object creates the possibility that a program may have created an object that it can no longer reference. For example, consider the three assignment statements in the figure at right. After the third assignment statement, not only do c1 and c2 refer to the same Charge object (the one at (.51, .63) with charge value 21.3), but there is also no longer a reference to the Charge object that was created and used to initialize c2. Such an object is said to be an orphan. Objects can also become orphans when variables go out of scope.

Memory management of objects.

Programs tend to create huge numbers of objects but have a need for only a small number of them at any given time. Accordingly, programming languages and systems need mechanisms to create objects (and allocate memory), and mechanisms to destroy objects (and free memory) when the objects become orphans. Most programming systems take care of allocating memory for variables when they come into existence and freeing that memory when they go out of scope. Memory management for objects is more complicated: Python knows to allocate memory for an object when it is created, but cannot know precisely when to free the memory associated with an object, because the dynamics of a program in execution determine when an object becomes an orphan and so should be destroyed. There is no way for the system to predict what a program will do, so it has to monitor what a program is doing and take action accordingly.

In many languages (such as C and C++), the programmer is responsible for both allocating and deallocating memory. Doing so is tedious and notoriously error-prone. One of Python's most significant features is its ability to automatically manage memory. The idea is to free the programmers from the responsibility of managing memory by keeping track of orphaned objects and returning the memory they use to a pool of free memory. Reclaiming memory in this way is known as garbage collection, and Python's type system enables it to perform this operation this efficiently and automatically.

Q & A

Q. What happens if I call a method that is not defined for a given object?

A. Python raises an AttributeError at run time.

Q. Why can we use stdio.writeln(x) instead of stdio.writeln(str(x)) to write an object x that is not a string?

A. For convenience, the stdio.writeln() function calls the built-in str() function automatically whenever a string object is needed.

Q. I noticed that potential.py calls stdarray.create1D() to create an array of Charge objects, but provides only one argument (the desired number of elements). Doesn't stdarray.create1D() require that I provide two arguments: the desired number of elements and the initial value of the elements?

A. If no initial value is specified, both stddarray.create1D() and stdarray.create2D() use the special value None, which refers to no object. Immediately after calling stdarray.create1D(), potential.py changes each array element so it refers to a new Charge object.

Q. Can I call a method with a literal or other expression?

A. Yes, from the client's point of view, you can use any expression to invoke a method. When Python executes the method call, it evaluates the expression and calls the method on the resulting object. For example, 'python'.upper() returns 'PYTHON' and (3 ** 100).bit_length() returns 159. However, you need to be careful with integer literals — for example, 1023.bit_length() raises a SyntaxError because Python interprets 1023. as a floating-point literal; instead, you can use (1023).bit_length().

Q. Can I chain together several string method calls in one expression?

A. Yes. For example, the expression s.strip().lower() works as expected. That is, it evaluates to a new string that is a copy of s with leading and trailing whitespace removed, and with all remaining characters converted to lowercase. It works because (1) each of the methods returns its result as a string and (2) the dot operator is left associative, so Python calls the methods from left to right.

Q. Why red, green, and blue instead of red, yellow, and blue?

A. In theory, any three colors that contain some amount of each primary color would work, but two different color models have evolved: RGB produces good colors on television screens, computer monitors, and digital cameras, and CMYK is typically used for the printed page (see the "color conversion exercise in Section 1.2). CMYK does include yellow (cyan, magenta, yellow, and black). Two different schemes are appropriate because printed inks absorb color; thus, where there are two different inks, there are more colors absorbed and fewer reflected. In contrast, video displays emit color; thus, where there are two different colored pixels, there are more colors emitted.

Q. Is there any problem with creating thousands of Color objects, as in grayscale.py? It seems wasteful.

A. All programming-language constructs come at some cost. In this case the cost is reasonable, since the time required to create the Color objects is tiny compared to the time required to actually draw the picture.

Q. Can a data type have two methods (or constructors) with the same name but with a different number of arguments?

A. No, just as with functions, you cannot have two methods (or constructors) with the same name. As with functions, methods (and constructors) can use optional arguments with default values. This is how the Picture data type creates the illusion of having two constructors.

Q. When using a linear filter, each pixel becomes a weighted average of its 8 neighbors. What do I do when the pixel has less than 8 neighbors because it is near the border?

A. You could assume the image is toroidal (periodic boundary conditions) and make the left boundary wrap around to the right boundary, and the top boundary wrap around to the bottom boundary.

Q. Where can I download some test files for image processing?

A. USC SIPI contains standard test images (including Mandrill).

Exercises

Compose a program that takes a float command-line argument w, creates four Charge objects (each with charge value 1.0) that are each distance w in each of the four cardinal directions from (.5, .5), and writes the potential at (0.25, 0.5).

Solution: See fourchargeclient.py.
Compose a program that takes from the command line three integers between 0 and 255 that represent red, green, and blue values of a color and then creates and shows a 256-by-256 Picture of that color.

Modify alberssquares.py to take nine command-line arguments that specify three colors and then draws the six squares showing all the Albers squares with the large square in each color and the small square in each different color.

Compose a program that takes the name of a grayscale picture file as a command-line argument and uses stddraw to plot a histogram of the frequency of occurrence of each of the 256 grayscale intensities.
Compose a program that takes the name of a picture file as a command-line argument and flips the image horizontally.
Compose a program that takes the name of an picture file as a command-line input, and creates three images — on with only the red components, one with only the green components, and one with only the blue components.
Compose a program that takes the name of an picture file as a command-line argument and writes the pixel coordinates of the lower left corner and the upper right corner of the smallest bounding box (rectangle parallel to the x- and y-axes) that contains all of the non-white pixels.
Compose a program that takes as command line arguments the name of a picture file and the pixel coordinates of a rectangle within the image; reads from standard input a list of Color values (represented as triples of integers); and serves as a filter, printing out those Color values for which all pixels in the rectangle are background/foreground compatible. (Such a filter can be used to pick a color for text to label an image.)
Compose a function isValidDNA() that takes a string as input and returns True if and only if it is comprised entirely of the characters A, C, T, and G.
Compose a function complementWC() that takes a DNA string as its argument and returns its Watson-Crick complement: replace A with T, C with G, and vice versa.
Compose a function palindromeWC() that takes a DNA string as its argument and returns True if the string is a Watson-Crick complemented palindrome, and False otherwise. A Watson-Crick complemented palindrome is a DNA string that is equal to the reverse of its Watson-Crick complement.
Compose a program to check whether an ISBN number is valid (see the "Checksum" exercise in Section 1.3), taking into account that an ISBN number can have hyphens inserted at arbitrary places.
What does the following code fragment write?
s = 'Hello World' s.upper() s[6:11] stdio.writeln(s)
Solution: 'Hello World'. String objects are immutable — a string method returns a new str object with the appropriate value, but does not change the value of the object that was used to invoke it. This code ignores the objects returned and just writes the original string. To update s, write s = s.upper() and s = s[6:11].
A string s is a circular shift of a string t if it matches when the characters are circularly shifted by any number of positions. For example, ACTGACG is a circular shift of TGACGAC, and vice versa. Detecting this condition is important in the study of genomic sequences. Compose a function that checks whether two given strings s and t are circular shifts of one another. Hint: The solution is a one-liner with the in operator and string concatenation.
Given a string site that represents a website URL, compose a code fragment to determine its domain type. For example, the domain type for the string http://introcs.cs.princeton.edu/python is edu.
Compose a function that takes a domain name as argument and returns the reverse domain (reverse the order of the strings between periods). For example, the reverse domain of introcs.cs.princeton.edu is edu.princeton.cs.introcs. This computation is useful for web log analysis (see the "Reverse domain" creative exercise in Section 4.2).

What does the following recursive function return?

def mystery(s):
    n = len(s)
    if n <= 1:
        return s
    a = s[0, n//2]
    b = s[n//2, n]
    return mystery(b) + mystery(a)

Compose a version of potentialgene.py that finds all potential genes contained in a long DNA string. Add a command-line argument to allow the user to specify a minimum length of a potential gene.
Compose a program that takes a start string and a stop string as command line arguments and writes all substrings of a given string that start with the first, end with the second, and otherwise contain neither. Note: Be especially careful of overlaps!
Compose a filter that reads text from an input stream and prints it to an output stream, removing any lines that consist only of whitespace.
Modify potential.py to take an integer n from the command line and generate n random Charge objects in the unit square, with potential values drawn randomly from a Gaussian distribution with mean 50 and standard deviation 10.
Modify stockquote.py to take multiple symbols on the command line.
The example file djia.csv used for split.py lists the date, high price, volume, and low price of the Dow Jones stock market average for every day since records have been kept. Download this file from the booksite and compose a program that plots the prices and volumes, at a rate taken from the command line.
Compose a program merge.py that takes a delimiter string followed by an arbitrary number of file names as command line arguments, concatenates the corresponding lines of each file, separated by the delimiter, and then writes the result to standard output, thus performing the opposite operation from split.py.
Find a website that publishes the current temperature in your area, and compose a screen-scraper program weather.py so that typing python weather.py followed by your zip code will give you a weather forecast.

Creative Exercises

Picture filtering. Compose a module rawpicture.py with read() and write() functions for use with standard input and standard output. The write() function takes a Picture as argument and writes the picture to standard output, using the following format: if the picture is w-by-h, write w, then h, then w*h triples of integers representing the pixel color values, in row major order. The read() function takes no arguments and returns a Picture, which it creates by reading a picture from standard input, in the format just described. Note: The picture filtering will use up much more disk space than the picture — the standard formats compress this information so that it will not take up so much space.
Kama Sutra cipher. Compose a filter that takes two strings as command-line arguments (the key strings), then reads standard input, substitutes for each letter as specified by the key strings, and writes the result to standard output. This operation is the basis for one of the earliest known cryptographic systems. The condition on the key strings is that they must be of equal length and that any letter in standard input must be in one of them. For example, if input is all capital letters and the keys are THEQUICKBROWN and FXJMPSVRLZYDG, then we make the table.
```
T H E Q U I C K B R O W N
F X J M P S V L A Z Y D G
```
which tells us that we should substitute F for T, T for F, H for X, X for H, and so forth when copying the input to the output. The message is encoded by replacing each letter with its pair. For example, the message MEET AT ELEVEN is encoded as QJJF BF JKJCJG. Someone receiving the message can use the same keys to get the message back.

Solution: See kamasutra.py.
Safe password verification. Compose a function that takes a string as argument and returns True if it meets the following conditions, False otherwise:
- At least eight characters long
- Contains at least one digit (0-9)
- Contains at least one uppercase letter
- Contains at least one lowercase letter
- Contains at least one character that is neither a letter nor a number
Such checks are commonly used for passwords on the web.
Color study. Compose a program that displays the color study shown below, which gives Albers squares corresponding to each of the 256 levels of blue (blue-to-white in row-major form) and gray (black-to-white in column-major form) that were used to print the textbook.

Solution: See colorstudy.py.
Entropy. The Shannon entropy measures the information content of an input string and plays a cornerstone role in information theory and data compression. Given a string of n characters, let f_c be the frequency of occurrence of character c. The quantity p_c = f_c / n is an estimate of the probability that c would be in the string if it were a random string, and the entropy is defined to be the sum of the quantity -p_c log₂ p_c, over all characters that appear in the string. The entropy is said to measure the information content of a string: if each character appears the same number times, the entropy is at its minimum value. Compose a program that computes and writes to standard output the entropy of the string from standard input. Run your program on a web page that you read regularly and on a recent paper that you wrote.
Minimize potential. Compose a function that takes an array of Charge objects with positive potential as its argument and finds a point such that the potential at that point is within 1% of the minimum potential anywhere in the unit square. Use a Charge object to return this information. Compose a test client that callsyour function to write the point coordinates and charge value for the data given in the text and for the random charges described in a previous exercise in this section.
Slide show. Compose a program that takes the names of several image files as command-line arguments and displays them in a slide show (one every two seconds), using a fade effect to black and a fade from black between pictures.
Tile. Compose a program that takes the name of an image file and two integers m and n as command-line arguments and creates an m-by-n tiling of the picture.
Rotation filter. Compose a program that takes two command line arguments (the name of an image file and a real number θ) and rotates the image θ degrees counterclockwise. To rotate, copy the color of each pixel (s_i, s_j) in the source image to a target pixel (t_i, t_j) whose coordinates are given by the following formulas:

t_i = (s_i - c_i)cos θ + (s_j - c_j)sin θ + c_i
t_j = (s_i - c_i)sin θ + (s_j - c_j)cos θ + c_j

where (c_i, c_j) is the center of the image. For example, these images show a 30 degree rotation:

Solution: See rotation.py.
Swirl filter. Creating a swirl effect is similar to rotation, except that the angle changes as a function of distance to the center. Use the same formulas as in the previous exercise, but compute θ as a function of (s_i, s_j), specifically π/256 times the distance to the center. For example:

Solution: See swirl.py.
Wave filter. Compose a filter like those in the previous two exercises that creates a wave effect, by copying the color of each pixel (s_i, s_j) in the source image to a target pixel (t_i, t_j), where t_i = s_i and t_j = s_j + 20 sin(2 π s_j/64). Add code to take the amplitude (20 in the accompanying figure) and the frequency (64 in the accompanying figure) as command-line arguments. Experiment with various values of these parameters.

Solution: See wave.py.
Glass filter. Compose a program that takes the name of an image file as a command-line argument and applies a glass filter: set each pixel p to the color of a random neighboring pixel (whose pixel coordinates are each within 5 pixels of p's coordinates). For example:

Solution: See glass.py.
Morph. The example images shown in this section for fade.py do not quite line up in the vertical direction (the mandrill's mouth is much lower than Darwin's). Modify fade.py to add a transformation in the vertical dimension that makes a smoother transition.
Clusters. Compose a program that take the name of a picture file from the command line and produces and displays to stddraw a picture with filled circles that cover compatible areas. First, scan the image to determine the background color (a dominant color that is found in more than half the pixels). Use depth first search, as described in Section 2.4, to find contiguous sets of pixels that are foreground-compatible with the background. A scientist might use this program to study natural scenarios such as birds in flight or particles in motion. Take a photo of balls on a billiards table and try to get your program to identify the balls and positions.
Digital zoom. Compose a program zoom.py that takes the name of an image file and three numbers s, x, and y as command-line arguments and displays a picture that zooms in on a portion of the input picture. The numbers are all between 0 and 1, with s to be interpreted as a scale factor and (x, y) as the relative coordinates of the point that is to be at the center of the output image. Use this program to zoom in on your dog or a friend in some digital image on your computer.

`% python alberssquares.py 9 90 166 100 100 100`
`% python alberssquares.py 0 174 239 147 149 252`

`% python grayscale.py mandrill.jpg`
`% python grayscale.py darwin.jpg`

`% python scale.py mandrill.jpg 200 200`
`% python scale.py mandrill.jpg 200 100`
`% python scale.py mandrill.jpg 100 200`