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.

Rational Numbers

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 and the Cash Drawer

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.

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.

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.

Sequences with Statistical Methods

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.

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.

Define a subclass of list with a few
additional methods. This will be defined as class StatSeq(
list ):.

Define a new class (a subclass of
object) that contains an internal list, and
provides all of the sequence special methods. Some (like append)
will be delegated to the internal list object. Others (like mean)
will be performed by the StatSeq class itself. This will be
defined as class StatSeq( object ):.

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.

Chessboard Locations

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.

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.

white pawn from e2 to e4; K2 to K5

black pawn from e7 to e5; K2 to K5

white knight from g1 to f3; KKt1 to KB3

black pawn from d7 to d6; Q2 to Q3

white pawn from d2 to d4; Q2 to Q4

black bishop from c8 to g4; QB1 to KKt5

white pawn at d4 takes pawn at e5; Q4 to K5

black bishop at g4 takes knight at f3; KKt5 to KB6

white Q at d1 takes bishop at f3; Q1 to KB3

black pawn at d6 takes e5; Q3 to K4

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.

Relative Positions on a Chess Board

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

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.

The kingIter method has to enumerate
the eight positions that surround the king.

The queenIter method has to enumerate
all the positions in the same rank, the same file, and on the
diagonals. Each of these must be examined from the queen's
position moving toward the edge of the board. This search from the
queen outward allows us to locate blocking pieces that would
prevent the queen from making a particular move.

The bishopIter method has to enumerate
all the positions on the diagonals. Each of these must be examined
from the bishop's position moving toward the edge of the
board.

The knightIter method has to enumerate
the eight positions that surround the knight, reflecting the
knight's peculiar move of 2 spaces on one axis and 1 space on the
other axis. There are four combinations of two ranks and one file
and four more combinations of two files and one rank from the
ending position. As with the king, no piece can block a knight's
move, so order doesn't matter.

The rookIter method has to enumerate
all the positions in the same rank and the same file. Each of
these must be examined from the rook's position moving toward the
edge of the board.

The pawnIter method has to enumerate a
fairly complex set of positions. Most pawn moves are limited to
going forward one rank in the same file. Since we need to know
which direction is forward, we need to know the color of the pawn.
For white pawns, forward means the ranks increase from 2 to 8. For
black pawns, then, forward means the ranks decrease from 7 down to
1. Pawn captures involve going forward one rank in an adjacent
file. Further complicating the analysis is the ability for a
pawn's first move to be two ranks instead of one.

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.

Published under the terms of the Open Publication License