text: 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.
  __init__
  __repr__
  __str__
  __cmp__
  __hash__
  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.
  Currency
  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.
  __iadd__
  currency
  __isub__
  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.
  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.
  UnableToMakeChange
  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.
  StatSeq
  __add__
  __radd__
  __mul__
  list
  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
  .
  map
  filter
  reduce
  zip
  Sample
  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 ):.
  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 ):.
  object
  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.
  mean
  append
  insert
  pop
  remove
  __setitem__
  __delitem__
  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.
  bisect
  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.
  __getitem__
  key
  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:
  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.
  move
  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.
  We need the following collection of special-purpose
  iterators.
  The kingIter method has to enumerate
  the eight positions that surround the king.
  kingIter
  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.
  queenIter
  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.
  bishopIter
  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.
  knightIter
  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.
  rookIter
  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.
  pawnIter
  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, ….
  r
  f
  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.