A 2-dimensional point is a coordinate pair, an x and y value. If we limit the range to the range 0 to 2**16, we can do a few extra operations quickly.

Develop the basic routines for __init__, __repr__, __str__. The __cmp__ function should compute the point's distance from the origin, . when comparing two points, or a point and a real number. The __hash__ function can simply combine x and y via x<<16+y.

Develop a test routine that creates a sequence of points and then sorts the points. Also, be sure to develop a test that uses points as keys in a dictionary.

Finish the Rational number class by adding all of the required special methods. The the section called “Rational Numbers” exercise in Chapter 21, Classes describes the basic structure of a class to handle rational math, where every number is represented as a fraction.

Currency comes in denominations. For instance, US currency comes in $100, $50, $20, $10, $5, $1, $.50, $.25, $.10, $.05, and $.01 denominations. Parker Brothers Monopoly™ game has currency in 500, 100, 50, 20, 10, 5 and 1. Prior to 1971, English currency had £50, £20, £10, £5, £1, shillings (1/12 of a pound) and pence (1/20 of a shilling). An amount of money can be represented as an appropriate tuple of integers, each of which represents the specific numbers of each denomination. For instance, one representation for $12.98 in US currency is (0, 0, 0, 1, 0, 2, 0, 3, 2, 0, 3).

Each subclass of Currency has a specific mix of denominations. We might define subclasses for US currency, Monopoly currency or old English currency. These classes would differ in the list of currencies.

An object of class currency would be created with a specific mix of denominatioons. The superclass should include operations to add and subtract Currency objects. An __iadd__( currency ) method, for example would add the denominations in currency to this object's various denominations. An __isub__( currency ) method, for example would subtract the denominations in currency to this object's various denominations; in the event of attempting to subtract more than is available, the object would raise an exception.

Be sure to define the various conversions to float, int and long so that the total value of the collection of bills and coins can be reported easily.

An interesting problem is to translate a decimal amount into appropriate currency. Note that numbers like 0.10 don't have a precise floating-point representation; floating point numbers are based on powers of 2, and 0.10 can only be approximated by a finite-precision binary fraction. For US currency, it's best to work in pennies, representing $1.00 as 100.

Develop a method which will translate a given integer into an appropriate mixture of currency denominations. In this case, we can iterate through the denominations from largest to smallest, determining the largest number of that denomination ≤ the target amount. This version doesn't depend on the current value of the Currency object.

A more advanced version is to create a Currency object with a given value; this would represent the money in a cash drawer, for example. A method of this object would make an amount of money from only the available currency, or raise an exception if it could not be done. In this case, we iterate through the denominations from largest to smallest, determining the largest number ≤ the target amount, consistent with available money in the cash drawer. If we don't have enough of a given denomination, it means that we will be using more of the smaller denominations.

One basic test case is to create a currency object with a large amount of money available for making change.

In the following example, we create a cash drawer with $804.55. We accept a payment of $10 as 1 $5, 4 $1, 3 $.25, 2 $.10 and 1 $.05. Then we accept a payment of $20, for a bill of $15.24, meaning we need to pay out $4.76 in change.

drawer = USCurrency( (5,2,6,5,5,5,5,5,5,5,5) ) 
drawer += USCurrency((0,0,0,0,1,4,0,3,2,1,0))
drawer += USCurrency((0,0,1,0,0,0,0,0,0,0,0))
drawer.payMoney( 4.76 )

Interestingly, if you have $186.91 (one of each bill and coin) you can find it almost impossible to make change. Confronted with impossible situations, this class should raise an UnableToMakeChange exception.

Each subclass of Currency has a specific mix of denominations. We might define subclasses for US currency, Monopoly currency or old English currency. These classes would differ in the list of currencies.

An object of class currency would be created with a specific mix of denominatioons. The superclass should include operations to add and subtract Currency objects. An __iadd__( currency ) method, for example would add the denominations in currency to this object's various denominations. An __isub__( currency ) method, for example would subtract the denominations in currency to this object's various denominations; in the event of attempting to subtract more than is available, the object would raise an exception.

Be sure to define the various conversions to float, int and long so that the total value of the collection of bills and coins can be reported easily.

An interesting problem is to translate a decimal amount into appropriate currency. Note that numbers like 0.10 don't have a precise floating-point representation; floating point numbers are based on powers of 2, and 0.10 can only be approximated by a finite-precision binary fraction. For US currency, it's best to work in pennies, representing $1.00 as 100.

Develop a method which will translate a given integer into an appropriate mixture of currency denominations. In this case, we can iterate through the denominations from largest to smallest, determining the largest number of that denomination ≤ the target amount. This version doesn't depend on the current value of the Currency object.

A more advanced version is to create a Currency object with a given value; this would represent the money in a cash drawer, for example. A method of this object would make an amount of money from only the available currency, or raise an exception if it could not be done. In this case, we iterate through the denominations from largest to smallest, determining the largest number ≤ the target amount, consistent with available money in the cash drawer. If we don't have enough of a given denomination, it means that we will be using more of the smaller denominations.

One basic test case is to create a currency object with a large amount of money available for making change.

In the following example, we create a cash drawer with $804.55. We accept a payment of $10 as 1 $5, 4 $1, 3 $.25, 2 $.10 and 1 $.05. Then we accept a payment of $20, for a bill of $15.24, meaning we need to pay out $4.76 in change.

drawer = USCurrency( (5,2,6,5,5,5,5,5,5,5,5) ) 
drawer += USCurrency((0,0,0,0,1,4,0,3,2,1,0))
drawer += USCurrency((0,0,1,0,0,0,0,0,0,0,0))
drawer.payMoney( 4.76 )

Interestingly, if you have $186.91 (one of each bill and coin) you can find it almost impossible to make change. Confronted with impossible situations, this class should raise an UnableToMakeChange exception.

Create a sequence class, StatSeq that can hold a sequence of data values. This class should define all of the usual sequence operators, including __add__, __radd__, __iadd__, but not __mul__. The __init__ function should accept a sequence to initialize the collection. The various __add__ functions should append the values from a StatSeq can instance as well as from ordinary sequences like list and tuple.

Most importantly, this class shold define the usual statistical functions like mean and standard deviation, described in the exercises after Chapter 13, Tuples , the section called “Sequence Processing Functions: map, filter, reduce and zip” and the section called “Sample Class with Statistical Methods” in Chapter 21, Classes .

Since this class can be used everywhere a sequence is used, interface should match that of built-in sequences, but extra features are now readily available. For a test, something like the following should be used:

import random

samples = StatSeq( [ random.randrange(6) for i in range(100) ] )
print samples.mean()

s2= StatSeq()
for i in range(100):
    ss.append( random.randrange(6) )
    # Also allow s2 += [ random.randrange(6) ]
print s2.mean()

There are two approaches to this, both of which have pros and cons.

Note that the value of mean does not have to be computed when it is requested. It is possible to simply track the changing sum of the sequence and length of the sequence during changes to the values of the sequence. The sum and length are both set to zero by __init__. The sum and length are incremented by every __add__, append, insert, pop, remove, __setitem__ and __delitem__. This way the calculation of mean is simply a division operation.

Keeping track of sums and counts can also optimize mode and standard deviation. A similar optimization for median is particularly interesting, as it requires that the sample data is retained by this class in sorted order. This means that each insert must preserve the sorted data set so that the median value can be retrieved without first sorting the entire sequence of data. You can use the bisect module to do this.

There are a number of algorithms for maintaining the data set in sorted order. You can refer to Knuth's The Art of Computer Programming[Knuth73], and Cormen, Leiserson, Rivest Introduction to Algorithms[Cormen90] which cover this topic completely.

A chessboard can be thought of as a mapping from location names to pieces. There are two common indexing schemes from chessboards: algebraic and descriptive. In algebraic notation the locations have a rank-file address of a number and a letter. In descriptive notation the file is given by the starting piece's file, rank and player's color.

See Chapter 42, Chess Game Notation for an extension to this exercise.

The algebraic description of the chess board has files from a-h going from white's left to right. It has ranks from 1-8 going from white's side (1) to black's side (8). Board's are almost always shown with position a1 in the lower left-hand corner and h8 in the upper right, white starts at the bottom of the picture and black starts at the top.

In addition to the simplified algebraic notation, there is also a descriptive notation, which reflects each player's unique point of view. The descriptive board has a queen's side (white's left, files a-d) and a king's side (white's right, files e-h). Each rank is numbered starting from the player. White has ranks 1-8 going from white to black. Black, at the same time as ranks 1-8 going back toward white. Each of the 64 spaces on the board has two names, one from white's point of view and one from black's.

Translation from descriptive to algebraic is straight-forward. Given the player's color and a descriptive location, it can be translated to an algebraic location. The files translate through a relatively simple lookup to transform QR to a, QKt to b, QB to c, Q to d, K to e, KB to f, KKt to g, KR to h. The ranks translate through a simple calculation: white's ranks are already in algebraic notation; for black's rank of r , 9- r is the algebraic location.

Create a class to represent a chess board. You'll need to support the special function names to make this a kind of mapping. The __getitem__ function will locate the contents of a space on the board. The __setitem__ function will place a piece at a space on the board. If the key to either function is algebraic (2 characters, lower case file from a-h and digit rank from 1-8), locate the position on the board. If the key is not algebraic, it should be translated to algebraic.

The codes for pieces include the piece name and color. Piece names are traditionally "p" or nothing for pawns, "R" for rook, "N" for knight, "B" for bishop, "Q" for queen and "K" for king. Pawns would be simply the color code "w" or "b". Other pieces would have two-character names: "Rb" for a black rook, "Qw" for the white queen.

The __init__ function should set the board in the standard starting position:

piece	algebraic	descriptive	piece code
white rooks	a1 and h1	wQR1, wKR1	Rw
white knights	b1 and g1	wQKt1, wKKt1	Nw
white bishop	c1 and f1	wQB1, wKB1	Bw
white queen	d1	wQ1	Qw
white king	e1	wK1	Kw
white pawns	a2-h2	wQR2-wKR2	w
black rooks	a8 and h8	bQR1, bKR1	Rb
black knights	b8 and g8	bQKt1, bKKt1	Nb
black bishops	c8 and f8	bQB1, bKB1	Bb
black queen	d8	bQ1	Qb
black king	e8	bK1	Kb
black pawns	a7-a7	bQR2-bKR2	b

Here's a sample five-turn game. It includes a full description of each move, and includes the abbreviated chess game notation.

The main program should be able to place and remove pieces with something like the following:

chess= Board()
# move pawn from white King 2 to King 5
chess['wK5']= chess['wK2']; chess['wK2']= ''
# move pawn from black King 2 to King 5
chess['bK5']= chess['bK2']; chess['bK2']= ''

# algebraic notation to print the board
for rank in [ '8', '7', '6', '5', '4', '3', '2', '1']:
    for file in [ 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']:
        print "%5s" % board[file+rank],
    print

The algebraic output can be changed to the following, which some people find simpler.

for rank in ('8','7','6','5','4','3','2','1'):
    print "".join( 
    [ "%5s" % board[file+rank] 
        for file in ('a','b','c','d','e','f','g','h') ] )

You should also write a move function to simplify creating the test game. A move typically consists of the piece name, the from position, the to position, plus optional notes regarding check and pawn promotions.

When decoding a log of a chess game in Short Algebraic Notation (SAN), it is often necessary to search for a piece that made a given move. We'll look at this problem in detail in Chapter 42, Chess Game Notation . There are actually a number of search algorithms, each constrained by the rules for moving a particular piece. For example, the knight makes a short “L”-shaped move and there are only 8 positions on the board from which a knight can start to end up at a given spot. The queen, on the other hand, moves horizontally, vertically or diagonally any distance, and there are as many as 24 starting positions for the queen to end up at a given spot.

This search is simplified by having iterators that know a few rules of chess and an give us a sequence of appropriate rank and file values. We'd like to be able to say something like the following.

piece, move, toPos = ( "Q", "x", "f3" )
for fromPos in aBoard.queenIter( toPos ):
    if aBoard[fromPos] == 'Q':
        print "Queen from", fromPos, \
        "takes", aBoard[toPos], "at", toPos

We'll review a few chess definitions for this problem. You can also see the section called “Chessboard Locations” in the section called “Container Special Methods” for some additional background.

The algebraic description of the chess board has files from a-h going from white's left to right. It has ranks from 1-8 going from white's side (1) to black's side (8). Board's are almost always shown with position a1 in the lower left-hand corner and h8 in the upper right, white starts at the bottom of the picture and black starts at the top.

We need the following collection of special-purpose iterators.

We note that the queen's iterator is really a combination of the bishop and the rook. We'll look at the rook's iterator, because it is can be adapted to be a bishop iterator, and then those two combined to create the queen iterator.

Given a starting position with a rank of r and a file of f, we'll need to examine all ranks starting from r and moving toward the edge of the board. These are r−1, r+1, r−2, r+2, r−3, r+3, …. Similarly, we need to examine all of the files starting from f and moving toward the edge of the board. These are f−1, f+1, f−2, f+2, f−3, f+3, ….

Before doing an comparison, we need to filter the file and rank combinations to assure that they are legal positions. Additionally, we need to stop looking when we've encountered a piece of our own color or an opposing piece that isn't the one we're searching for. These intervnening pieces "block" the intentended move.