Sep 98 Prog Challenge
Volume Number: 14
Issue Number: 9
Column Tag: Programmer's Challenge
Sep 98 Programmer's Challenge
by Bob Boonstra, Westford, MA
Big Baby
Fifty years ago this past June, the Manchester Mark I prototype computer, also known
as "Baby", became operational. Baby was the first computer to store a program
electronically, and was also the first computer to store instructions and data in the
same memory. Because vacuum tube technology was too immature to store memory
reliably, Baby was designed to test memory based on a cathode ray tube. Not much
memory, mind you. Baby boasted a full 1K bits of memory, organized as 32 words (or
lines) of 32 bits each.
In celebration of the birth of the first stored program computer on June 21, 1948,
the Department of Computer Science at the University of Manchester recently
reconstructed Baby and ran a programming contest to write the most imaginative
program for Baby. Inspired by that contest, your Challenge is to write an assembler
and an emulator for an extended ("Big") version of Baby. The prototype for the code
you should write is:
#if defined(__cplusplus)
pragma extern "C" {
#endif
#define kMaxInstructions 32
typedef UInt32 CRT_memory[kMaxInstructions];
pascal void AssembleBabyProgram(
char *program,
CRT_memory memory,
UInt32 address_bits
);
pascal void ExecuteBabyProgram(
CRT_memory memory,
UInt32 address_bits
);
#if defined(__cplusplus)
}
#endif
Baby has a single general-purpose register, called the Accumulator. The program
counter is called the Control Instruction, or CI. The CI is incremented just before the
next instruction is fetched, which means that a jump instruction, for example, is
coded with a value one less than the actual target address. Baby also has a red light that
indicates the program has halted. One interesting thing about Baby is that it lacks an
addition instruction - addition is done by subtraction.
Baby's instruction repertoire is listed below. The function bits (or opcode) associated
with each instruction is listed in parentheses after the mnemonic.
STO (110)
Store the contents of the Accumulator in the store line.
SUB (001 or 101)
Subtract the contents of the store line from the Accumulator. There is no ADD
instruction; addition is done indirectly by combining the SUB and the
LDN instruction.
LDN (010)
Copy the contents of the store line, negated, to the accumulator.
JMP (000)
Copy the contents of the store line to the CI (so the store line holds the number
of the line one before we want to jump to). In modern terms, this an
indirect jump, which uses up an extra store line compared to a direct jump.
JRP (100)
Add the contents of the store line to the CI. This looks forward to larger
machines, where it would be important to be able to load the same code
in different places, and hence would need relative jumps.
CMP (011)
Skip the next instruction if the contents of the Accumulator are
negative, i.e. a conditional branch.
STOP (111)
Stop the machine and turn the red light on
NUM (N/A)
An assembler mnemonic to initialize a store line to a data value.
For example, the following program computes the greatest common divisor of the
number in locations 30 and 31:
22
0000 NUM 0
0001 LDN 30
0002 STO 29
0003 LDN 31
0004 STO 31
0005 LDN 31
0006 STO 30
0007 LDN 29
0008 SUB 30
0009 CMP
0010 JRP 27
0011 SUB 31
0012 STO 31
0013 SUB 28
0014 CMP
0015 JMP 00
0016 STP
0027 NUM -3
0028 NUM 2
0029 NUM 0
0030 NUM 3141593
0031 NUM 5214
Baby's instructions are assembled into a 32 bit word by placing the function code
associated with the mnemonic into bits 13-15 (numbered with bit 0 as the most
significant bit). In the original Baby, the store line associated with the instruction is
placed in bits 0-4. Bits 5-12 and 16-31 are not used as part of the instruction,
although they can be used as data. The program listed above assembles to the following:
22
0000:00000000000000000000000000000000
0001:01111000000000100000000000000000
0002:10111000000001100000000000000000
0003:11111000000000100000000000000000
0004:11111000000001100000000000000000
0005:11111000000000100000000000000000
0006:01111000000001100000000000000000
0007:10111000000000100000000000000000
0008:01111000000000010000000000000000
0009:00000000000000110000000000000000
0010:11011000000001000000000000000000
0011:11111000000000010000000000000000
0012:11111000000001100000000000000000
0013:00111000000000010000000000000000
0014:00000000000000110000000000000000
0015:00000000000000000000000000000000
0016:00000000000001110000000000000000
0027:10111111111111111111111111111111
0028:01000000000000000000000000000000
0029:00000000000000000000000000000000
0030:10011011111101111111010000000000
0031:01111010001010000000000000000000
Our contest will make one change to the original Baby: in our extended, Big Baby,
machine, the store line is extended from 5 bits (0-4) to address_bits bits (0 -
address_bits-1). This allows more than 32 words of memory and therefore larger
programs.
Your AssembleBabyProgram routine should accept the mnemonic input listed above,
pointed to by the program parameter, and assemble them into 32-bit Baby
instructions in memory. Your ExecuteBabyProgram routine will be called to execute
the program one or more times. Both of your routines will be provided an address_bits
parameter that describes the size of memory. You will be asked to assemble more than
one program, your assembled programs may be executed more than one time each, and
you may be asked to execute a program that has been hand-assembled.
More information about the University of Manchester Baby programming contest can
be found at http://www.cs.man.ac.uk/prog98/. Programming reference documentation
for Baby can be found at http://www.cs.man.ac.uk/prog98/ssemref.html and at
ftp://ftp.cs.man.ac.uk/pub/CCS-Archive/misc/progref1.doc.
The winner will be the solution that assembles and executes a set of test programs in
the minimum amount of time.
This will be a native PowerPC Challenge, using the latest CodeWarrior environment.
Solutions may be coded in C, C++, Pascal or, as is our tradition in the month of
September, in assembly language. Thanks to Eric Shapiro for suggesting this
Challenge.
Three Months Ago Winner
Congratulations to Tom Saxton for writing the most successful simulated gambler at
the blackjack table of our June Programmer's Challenge Casino. Tom beat out four
other entries and was one of only two entries to actually come out ahead at the
blackjack table.
Tom precomputed the expected winnings for each situation and created tables with the
action that led to the best result. He uses the Hi-Lo card counting method to determine
whether the remaining cards contain a disproportionate number of high-valued cards,
and then uses that estimate to adjust his wager. Tom's solution is also not too greedy; it
contains heuristics to quit when it has won a reasonable amount or played long enough,
ensuring that it has wagered enough credits to avoid the "freeloader" penalty imposed
by the problem.
A few words about our other gamblers are in order. The second-place solution, by
Kevin Hewitt, also used precomputed tables, but his were based only on the initial pair
of cards dealt. Kevin also spent more time at the table, quitting only when winnings or
losses exceeded a threshold. JG Heithcock's solution spent the least amount of time at
the table. He quit soon after the minimum total bet criterion was met. Ken Slezak kept
playing until he lost 75% of his bankroll (or quadrupled his money) and Randy Boring
played until he ran out of money or, as it turned out, until the house threw him out of
the casino. Both of those players left with not much more than the shirts on their
backs.
Here are the statistics for the entries to the Blackjack Challenge. Each player played a
series of five games where the house varied the number of decks of cards used. Players
were given the same number of credits at the start of each game, totaling 21000
credits for all of the games. The table below lists the total number of credits wagered
by the player, the number of credits left when the player decided to quit, the number
of hands played, total execution time, and the overall player score. Also listed are the
code and data sizes for the entries, along with the programming language used. As
usual, the number in parentheses after the entrant's name is the total number of
Challenge points earned in all Challenges to date prior to this one.
Name Credits Wagered Credits Left Hands Played Exec. Time Score Code Size Data Size Lang Tom Saxton (19) 47451 25199 327 7169 25194 1496 1924
Kevin Hewitt 438700 23800 1833 37923 23766 996 2156
JG Heithcock (20) 22616 20484 769 17950 20470 1304 232
Ken Slezak (20) 91760 9140 1701 36911 9106 1240 172
Randy Boring (81) 437230 8670 15425 460099 8213 4920
353 C
Top Contestants
Here are the Top Contestants for the Programmer's Challenge, including everyone who
has accumulated more than 20 points during the past two years. The numbers below
include points awarded over the 24 most recent contests, including points earned by
this month's entrants.
1. Munter, Ernst 190
2. Boring, Randy 76
3. Cooper, Greg 54
4. Mallett, Jeff 50
5. Rieken, Willeke 47
6. Nicolle, Ludovic 34
7. Lewis, Peter 31
8. Maurer, Sebastian 30
9. Saxton, Tom 29