Jun 95 Challenge
- Jan 95 Challenge
- Feb 95 Challenge
- Mar 95 Challenge
- Apr 95 Challenge
- May 95 Challenge
- Jul 95 Challenge
- Aug 95 Challenge
- Sep 95 Challenge
- Oct 95 Challenge
- Nov 95 Challenge
- Dec 95 Challenge
Volume Number: 11
Issue Number: 6
Column Tag: Programmer’s Challenge
Programmer’s Challenge 
By Bob Boonstra and Mike Scanlin
Note: Source code files accompanying article are located on MacTech CD-ROM orsource code disks.
Goodbye From Mike
This month is a special month. I have decided to turn the Programmer Challenge over to
Bob Boonstra. Readers of this column will recognize Bob’s name from his many
excellent winning solutions to the Challenges I’ve posed. In fact, Bob is the proud
owner of six 1st-place showings. I can think of no-one I’d rather turn this column
over to than Bob. I will judge the last two puzzles I have posed and Bob will judge the
puzzles he poses (the first of which, Check Checkmate, is in this issue).
It’s been almost three years since I first started this column. While it has been
incredibly rewarding to see so much optimal code and meet so many like-minded
efficiency nuts, my life has changed during those three years and I no longer have the
time that this column deserves. Even though I won't be writing it any more I'm sure
this column will remain my favorite part of MacTech (I may even submit an entry
once in a while...).
Thanks to everyone who took the time to write to me over the years with
suggestions for Challenges. I have given Bob the compiled list of ideas. I’m sure he’d
love to hear from you if you have any other ideas or comments on what you want to see
in this column. I leave you in Bob’s capable hands...
Optimally yours,
Mike Scanlin
scanlin@genmagic.com
Check Checkmate
This month’s Challenge deals with the game of chess. You will be given a chess
position and asked to produce the list of moves and captures that it is legal for one of
the sides to make in accordance with the rules of chess. The objective is to produce the
legal move list in minimum time.
Here are the prototypes for the routines you should write:
typedef enum {rowA=0,rowB,rowC,rowD,rowE,rowF,rowG,rowH} Row;
typedef enum {col1=0,col2,col3,col4,col5,col6,col7,col8} Col;
typedef enum {whiteSide=0,blackSide} Side;
typedef enum {king=0,queen,rook,bishop,knight,pawn} ChessPiece ;
typedef struct Square {
Row row;
Col col;
} Square;
typedef struct PiecePosition {
Square sq;
Side side;
ChessPiece piece;
} PiecePosition;
typedef struct ChessMove {
Square fromSq;
Square toSq;
Boolean moveIsCapture;
Boolean opponentPlacedInCheck;
} ChessMove;
short /*numberOfMoves*/ LegalChessMoves(
PiecePosition piecePositionArray[],
short numberOfPieces,
Side sideToMove,
ChessMove legalMoveArray[],
void *privateDataPtr
);
void InitChess(void *privateDataPtr);
This Challenge will consist of one call to InitChess, followed by multiple calls to
LegalChessMoves. The InitChess routine will not be timed, and may initialize up to 32K
bytes of storage preallocated by my testbench and pointed to by privateDataPtr. Your
program should not use any static storage besides that pointed to by privateDataPtr.
Each call to LegalChessMoves will provide a piecePositionArray containing
numberOfPieces chess pieces. Each piece is described in a PiecePosition struct
containing the ChessPiece, Side, and position. The position is provided as a Square
struct containing a Row and a Col, where rowA represents the starting row for the
White major pieces, and rowH the starting row for Black. The columns are numbered
from left to right as viewed from the White side, so that (rowH, col4) is the starting
square of the Black queen in a new game. The piecePositionArray will describe a legal
set of chess piece positions, anything from the initial positions in a new game to an
end-game position. No position will be provided that could not be reached during a
chess game. Remember that due to past pawn promotions, a side may have (for
example) more than one queen. You should generate the moves for the side provided in
sideToMove. The privateDataPtr parameter will be the same pointer provided to
InitChess.
LegalChessMoves should store in legalMoveArray the complete list of legal
ChessMoves for the sideToMove. The legalMoveArray will be allocated by my testbench
and will be large enough to hold all of the legal moves for the given chess position. You
should describe each legal move/capture by placing the row/col location of the moving
piece in fromSq and the rol/col of the destination in toSq. In addition, for each move,
the Boolean moveIsCapture should be set to true if the move captures an opponent's
piece (and set to false otherwise). Similarly, the Boolean opponentPlacedInCheck
should be set to true if the move places the opponent in check (and set to false
otherwise). The return value of the function should be the number of moves stored in
legalMoveArray. In generating the list of legal moves, you should assume that castling
moves or en passant pawn captures cannot occur. Remember that it is not legal to make
a chess move which places or leaves the moving side's king in check. If the sideToMove
has been checkmated and cannot move, LegalChessMoves should return zero.
This month brings one change to the rules of the contest. From now on, with
apologies (and sympathies) to any MacPlus users still out there, the 68020 code
generation option will be turned ON. This Challenge will be scored using the THINK C
compiler and 68K instruction set, but future Challenges will include occasional use of
the CodeWarrior compiler and/or the PowerPC instruction set. This month, you should
also include the following pragmas in your code:
#pragma options (mc68020, !mc68881, require_protos)
#pragma options (pack_enums, align_arrays)
Have fun, and e-mail me if there are any questions.
Two Months Ago Winner
I guess most people spent the beginning of April working on their taxes instead of
the Stock Market Database Challenge because I only received 3 entries. Of those, only
two worked correctly. Despite the lack of competition, I’m happy to say that the
winning solution is quite good. Congratulations to Xan Gregg (Durham, NC) for his
efficient solution. And thanks to Ernst Munter for taking the time to enter. Ernst was at