May 97 Challenge
Volume Number: 13
Issue Number: 5
Column Tag: Programmer's Challenge
Programmer's Challenge
By Bob Boonstra, Westford, MA
Equation Evaluator
Those of you with PowerPCs have probably experimented with the Graphing Calculator
application installed by default into the Apple Menu Items folder. As one of the first
native applications for the PowerPC, the ability of the Graphing Calculator to display,
and even animate 2-dimensional and 3-dimensional equations demonstrating the
computing power of the PowerPC chip using native code. Underlying the display
capability is code to parse an equation and rapidly compute the equation value for a
range of input values. In this month's Challenge, you will produce code to perform
these parsing and computation functions.
The prototype for the code you should write is:
typedef unsigned long ulong;
float first; /* first equation input value */
float delta; /* first+delta is second input value */
ulong howMany; /* number of input values */
typedef struct IntValues {
long first;/* first equation input value */
long delta;/* first+delta is second input value */
ulong howMany; /* number of input values */
float equationResult; /* result of equation given x,y,n */
float x; /* input value of x producing equationResult */
float y; /* input value of x producing equationResult */
long n;/* input value of x producing equationResult */
void Evaluate(
char *equation, /* null-terminated equation to evaluate */
const Values *xP, /* equation input values for x */
const Values *yP, /* equation input values for y */
const IntValues *nP,/* equation input values for n */
Results w[]/* preallocated storage for equation values */
);
The input equation you are to evaluate will be provided as a null-terminated string in
the 2-dimensional curve form (y=x+2x^2) or the 3-dimensional surface form (z=r
cos(t) r sin(t)). You are to evaluate the equation for each of the values of x and n (in
the case of a 2-dimensional equation) or x, y, and n (in the 3-dimensional case)
provided and return the results in the preallocated array w. Each input is described as
an initial value, a delta between each value and the next value, and the number
howMany of values this input parameter is to assume. For example, if x is to take on
the range of values [1.0, 1.1, 1.2, — 2.0], then the x input could be described as:
xP->first = 1.0; xP->delta = .1; xP->howMany = 11
In the event that the equation does not contain one of the input parameters, that
parameter should be ignored. There is no guarantee, for example, that nP->howMany
will be zero when the input equation is not a function of n. Similarly, for a
2-dimensional equation, yP should be ignored.
The input equation might be written as a function of r and q, which should be calculated
from x and y just as the Graphing Calculator does. Because the Graphing Calculator
displays equations in ways that cannot be directly represented in a character string,
the following symbols will be used in the equation to represent the operator or value
indicated:
\ square root
/ division
^ exponentiation
p pi (p)
t theta (q)
. multiplication (also represented by juxtaposition)
Standard algebraic operator precedence should be used: exponentiation and square
roots, then multiplication and division, then addition and subtraction, with
left-to-right evaluation order for operators of equal precedence, and with parentheses
used to override normal precedence. Arguments to trigonometric functions will always
be surrounded by parentheses. Where the Graphing Calculator would use superscripts
to indicate an extended exponent, parentheses will be used to make the meaning clear
(e.g., e^(x+y)).
Store the equation result for the i-th combination of input values in
w[i]->equationResult, and store the corresponding input values in w[i]->x, w[i]->y,
and w[i]->n. The results may be stored in any order, but each input combination
should appear exactly once. Results should be calculated with a minimum relative
accuracy of .00001.
Even though the Graphing Calculator handles inequalities, multiple equations,
differentiation, simplification, and expansion, your code does not need to deal with
these cases. With these exceptions, your code should handle any equation that the
Graphing Calculator can handle.
You may allocate any amount of dynamic storage up to 20MB, provided you deallocate
the storage before returning. This will be a native PowerPC Challenge, using the
CodeWarrior environment. Solutions may be coded in C, C++, or Pascal. Limited use of
assembly language is also permitted, for anyone who might need it to access any
dynamically generated code as part of their solution. The solution computing the
correct results in the least amount of time will be the winner.
Three Months Ago Winner
Congratulations to Jeff Mallett (Boulder Creek, CA) for producing the winning entry
among ten submitted for the Othello Challenge. The objective was to win a round-robin
Othello tournament, generalized to allow a board size between 8 and 64 (even numbers
only), by as large a margin as possible, using as little computation time as possible.
Tournament points were based on the margin of victory (the number of the winner's
pieces showing at the end of the game minus the number of the opponent's pieces
showing), and on the amount of computation time used, as follows:
[margin of victory - seconds of execution time / 30] / number of squares
The test cases included board sizes of 8x8 and 18x18, with each player competing
against each other player twice, once playing first, with the black pieces, and once
playing second, with the white pieces. I had planned to run some larger cases, but the
first two still had not completed after running all night, so I had to stop at 18x18.
The solutions submitted varied considerably in complexity. The simplest (and fastest)
solutions assigned values to each board position and made the move which maximized
total value. Some solutions took that approach one step further and evaluated an
opponent's potential responses and used a min/max approach to select the best move.
Other solutions took credit for the number of pieces flipped on a move, with possible
consideration for vulnerability to reversal on the next move. The winning solution
used the most complicated approach, with lines of play being examined by a
progressively deepening search.
The table below describes how each player fared against each other player. Each row
shows the number of victories that player had against the player represented by the
corresponding column. The final column shows the total number of victories won out of
the 36 games played by each entry. As you can see, the second place entry by Randy
Boring won nearly as many games as Jeff's winning entry, and actually beat the
winning entry in one of the four games they played.
Player Name 1 2 3 4 5 6 7 8 9 10 Wins
1 David Whitney - 1 4 2 4 2 2 0 0
4 19
2 Dan Farmer 3 - 4 2 4 4 4 1 0 4
26
3 David McGavran 0 0 - 2 4 1 1 0 1
1 10
4 Eric Hangstefer 2 2 2 - 4 0 1 0 0
3 14
5 Ken Slezak 0 0 0 0 - 0 0 0 0 0
0
6 Gregory Cooper 2 0 3 4 4 - 2 0 1
4 20
7 Mason Thomas 2 0 3 3 4 2 - 0 0
3 17
8 Randy Boring 4 3 4 4 4 4 4 - 1
4 32
9 Jeff Mallett 4 4 3 4 4 3 4 3 - 4
33
10 Ludovic Nicolle 0 0 3 1 4 0 1 0 0
- 9
The top two entries used significantly more computation time than the others. Jeff's
winning entry used an average of more than one second per move (as you can see by
examining the parameter settings in his code), but the larger margin of victory more
than offset the execution time penalty.
The table below provides the code and data sizes for each of the solutions submitted,
along with the total number of victories won in all of the test cases, and the cumulative
score earned in those victories. Numbers in parenthesis after a person's name indicate
that person's cumulative point total for all previous Challenges, not including this one.
Jeff Mallett (44) 6988 277 33 25.49
Randy Boring (27) 6908 64 32 20.37
Gregory Cooper (27) 4764 284 20 15.00
Dan Farmer 9240 96 26 14.27
David Whitney 7216 864 19 9.79
Eric Hangstefer 4124 80 14 9.72
Mason Thomas (4) 6976 57 17 9.01
David McGavran 3272 48 10 8.09
Ludovic Nicolle (21) 6436 120 9 6.33
Ken Slezak (20) 9256 77 0 0.00
Sample Game
Here is one of the games played by the top two entries. Randy Boring's entry played
Black, and Jeff Mallett's played White. The moves are given as the row and column
selected by the programs, interspersed with an occasional view of the resulting board
position.
Move Black (Boring) White (Mallett) row col rowcol
1 2 3 42
2 5 2 24
3 2 5 35
4 4 5 36
5 2 2 32
6 2 6 53
- - - - - - - -
- - - - - - - -
- - B B B B B -
- - W W W B W -
- - W W B B - -
- - B W - - - -
- - - - - - - -
- - - - - - - -
7 3 1
...missing an opportunity to place a piece on the edge at (2,7), inviting (1,7) as a
response by white, in hope of moving to (0,7)
5 4
8 4 1 1 5
9 3 7
- - - - - - - -
- - - - - W - -
- - B B B W B -
- B B B B B B B
- B B B B W - -
- - B W W - - -
- - - - - - - -
- - - - - - - -
Black occupies the first edge square.
2 7
10 1 7 1 3
11 1 2 4 6
12 0 3 5 5
13 6 2 0 2
- - W B - - - -
- - B W - W - B
- - B B W W B B
- B B W B B W B
- B B W B W W -
- - B B W W - -
- - B - - - - -
- - - - - - - -
Black's next move, to (0,1), prevents White from obtaining a foothold on one of the
edges.
14 0 1 2 1
15 3 0 2 0
16 1 0 5 0