Follow Techotopia on Twitter

On-line Guides
All Guides
eBook Store
iOS / Android
Linux for Beginners
Office Productivity
Linux Installation
Linux Security
Linux Utilities
Linux Virtualization
Linux Kernel
System/Network Admin
Programming
Scripting Languages
Development Tools
Web Development
GUI Toolkits/Desktop
Databases
Mail Systems
openSolaris
Eclipse Documentation
Techotopia.com
Virtuatopia.com

How To Guides
Virtualization
General System Admin
Linux Security
Linux Filesystems
Web Servers
Graphics & Desktop
PC Hardware
Windows
Problem Solutions

  




 

 

Special Method Name Exercises

Geometric Points

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.

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.

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.

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.

  • 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.

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.

  1. white pawn from e2 to e4; K2 to K5

    black pawn from e7 to e5; K2 to K5

  2. white knight from g1 to f3; KKt1 to KB3

    black pawn from d7 to d6; Q2 to Q3

  3. white pawn from d2 to d4; Q2 to Q4

    black bishop from c8 to g4; QB1 to KKt5

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

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

  5. 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

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.

  • 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 Design by Interspire