Apr 95 Challenge
- Jan 95 Challenge
- Feb 95 Challenge
- Mar 95 Challenge
- May 95 Challenge
- Jun 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: 4
Column Tag: Programmer’s Challenge
Programmer’s Challenge 
By Mike Scanlin, Mountain View, CA
Note: Source code files accompanying article are located on MacTech CD-ROM orsource code disks.
Stock Market Database
This month’s Challenge is to write a piece of code that records stock market trades and
then allows you to query it to find out price and volume information for a particular
stock at a particular time. This code could be the core of a much larger stock analysis
program (and it would likely be the bottleneck).
The typedefs you will use are:
typedef unsigned char uchar;
typedef unsigned long ulong;
typedef struct TimeStamp {
uchar yearsFrom1900;
uchar month;
uchar day;
uchar hour;
uchar minute;
uchar second;
} TimeStamp;
typedef char Str7[8];
typedef struct Trade {
Str7 symbol;
TimeStamp time;
Fixed price;
ulong numShares;
} Trade;
The four routines you’ll write are:
void *
InitTradeDatabase(maxRAM)
ulong maxRAM;
void
NewTrade(privateDataPtr, trade)
void *privateDataPtr;
Trade trade;
PriceIs(privateDataPtr, symbol, time);
void *privateDataPtr;
Str7 symbol;
TimeStamp time;
ulong
VolumeIs(privateDataPtr, symbol, time);
void *privateDataPtr;
Str7 symbol;
TimeStamp time;
InitTradeDatabase is called once before any other functions. It is untimed (i.e. it
doesn’t matter if it’s slow to execute) and should return a pointer to your database’s
private data (which is passed to the other 3 routines as privateDataPtr). MaxRAM is
the largest amount of RAM that your code can use (in bytes); it will be between 512K
and 4MBs. You can also use up to 50MBs of disk space.
Once InitTradeDatabase has been called, the other 3 routines will be called
pseudo-randomly many times. The only restriction is that each time NewTrade is
called, the trade’s time will be later than all previous trades. You can think of
NewTrade being called once for each trade that occurs, as it occurs (like the data
flowing across a ticker tape, which happens in chronological order).
The chronological sequence of NewTrade calls will be interspersed with calls to
PriceIs and VolumeIs. PriceIs returns the price of a given stock at or before the given
time. If you are asked for the price of a stock at a time before you have any trade data
for that stock then return a price of zero.
VolumeIs returns the daily volume of a given stock as of a given time on that day.
For example, if the time is 2/28/95 at 11am then VolumeIs should return the sum of
all trades’ numShares that occurred on the 28th of February, 1995, before 11am
(and excluding trades that occurred at exactly 11am).
Taken together these routines will allow someone to produce price/volume
graphs for a stock of their choice (once they’ve fed it lots of trade data).
Here are some examples. A time of 13:32:15 (15 seconds past 1:32pm) on Mar
2nd, 1995, is:
yearsFrom1900 = 95;
month = 3;
day = 2;
hour = 13;
minute = 32;
second = 15;
A price of 14 and 11/16ths would be:
price = 0x000EB000; /* 14.6875 */
Remember, a Fixed is 16 bits of integer (0x000E) and 16 bits of fraction (0xB000).
You can think of it as a 32 bit integer that you could divide by 216 to get the floating
point equivalent. The value 1 is 0x00010000. The value 0.5 is 0x00008000. Stock
prices are normally quoted in 1/2s, 1/4s, 1/8s, 1/16ths, 1/32nds and 1/64ths, and
those are the only possible fractions your code will receive.
Symbols are uppercase, 7 character PStrings. The symbol for Apple Computer is
AAPL. It would be:
Str7 symbol;
symbol[0] = 4; /* length */
symbol[1]=‘A’; symbol[2]=‘A’; symbol[3]=‘P’; symbol[4]=‘L’;
NumShares is always greater than zero and will only very rarely be larger than
100,000 (the max, for our purposes, is 10,000,000).
Note that, on a typical day, the stock exchanges of the world have hundreds of
thousands of transactions. It is all but certain that your routine will run out of RAM.
You will need to be prepared to swap some trade data to disk. And then you need an
efficient way to retrieve that data if you are asked for price or volume information
once you’ve swapped it to disk. Part of this Challenge is to come up with a clever way
to store RAM indexes of disk-based trade data. And you’ll probably want to cache at
least some (if not all) of the trade data in RAM when you can. You will not be given
more than 10MB of trade data (since you can use 50MB of disk space, you should be
fine).
Write to me if you have any questions. Happy trading.
Two Months Ago Winner
Congratulations to Gustav Larsson (Mountain View, CA) for winning the Symbolize
Challenge. Last month, Gustav was complimented for his small code that was only
slightly slower than the winner. This month he has the largest code, but it’s almost 3x
faster than the nearest competitor.
Here are the times and code sizes for each entry. Numbers in parens after a
person’s name indicate that person’s cumulative point total for all previous
Programmer Challenges, not including this one (see Top 20 chart below for info on the
new cumulative point total plan):
Name time code
Gustav Larsson (10) 74 2942
Paul Hoffman 197 2100
Scott Manjourides 205 1972
Mason Thomas 235 1742
David Salmon 239 946
Dave Darrah (26) 249 1392
David Wiser 355 1492
Gustav’s solution is extremely nice code. It’s well thought out (good algorithms),
well implemented (he knows his compiler) and well commented. If all of the authors
of my favorite applications took as much care at crafting their code, then I’m sure I’d
get at least an extra half hour of work done each day. I highly recommend that you
study his code and comments.
Top 20 Contestants of All Time
This month marks the 32nd installment of the Programmer’s Challenge in MacTech.
Prompted by Bob Boonstra’s retirement in February, I decided I needed to have some
way to recognize past entrants who had done well. Thus was born the Top 20 Of All
Time Chart.
Here’s how it works. There are three ways to earn points: (1) by scoring in the
top 5 of any particular challenge, (2) by being the first person to find a bug in a
published winning solution or, (3) being the first person to suggest a challenge that I
use. The points you can win are:
1st place 20 points
2nd place 10 points
3rd place 7 points
4th place 4 points
5th place 2 points
finding bug 5 points
suggesting challenge 2 points
Each month I will present the cumulative point totals for the top 20 contestants.
It took me a while to compile the point totals for this month’s chart. I may have made a
mistake. If you think you deserve more points than I’ve given you, please write to me
and explain why (i.e. give me a list the months you finished in the top 5 as well as the
months you found a bug or suggested a challenge I used and I’ll check it out). If your
name is not in the current Top 20 but you want to know how many points you have,
then e-mail me and I’ll tell you. Note that the numbers below include points awarded
for this months’ top 5 entrants.
So, here it is. Congrats, everyone, on the hard work it took to get here! (Note:
ties are listed alphabetically by last name -- there are 23 people listed this month
because 7 people had 20 points each.)
Top 20 Contestants of All Time
1. Boonstra, Bob 176
2. Karsh, Bill 71
3. Stenger, Allen 65
4. Cutts, Kevin 56