TweetFollow Us on Twitter

Sep 96 Challenge
Volume Number:12
Issue Number:9
Column Tag:Programmer’s Challenge

Programmer’s Challenge

By Bob Boonstra

Note: Source code files accompanying article are located on MacTech CD-ROM or source code disks.

Byte Code Interpreter

September is Assembly Language month at the Programmer’s Challenge, and this year we will be accepting solutions in PowerPC Assembly for the first time. This month’s Challenge, suggested by Xan Gregg, is to write an interpreter for a subset of the byte code language used by the Java Virtual Machine.

The prototype for the code you should write is:

void JavaMiniVM(
 void *constant_pool,/* pointer to cp_info array */
 void *fields,   /* pointer to field_info array */
 void *methods,  /* pointer to method_info array */
 void *classFile,/* pointer to class file */
 long methodToExecute,  /* index of method to start executing */
 void *heapSpace,/* preallocated storage for your use */
 void *returnStack /* stack where return values are stored */

Your Challenge is to write an efficient interpreter for a subset of the Java byte code instruction set. A Java instruction consists of a single-byte opcode specifying the operation to be performed, followed by zero or more operand bytes. So, for example, in the byte sequence 0x10 0xFF, the opcode 0x10 (bipush) indicates that the operand byte 0xFF is to be pushed onto the operand stack. The instruction 0x60 (iadd) indicates that two integers are to be popped off the operand stack, added, and the result pushed back onto the stack. The virtual machine operates by repeatedly fetching an opcode and performing the indicated action on the operands.

To participate in this Challenge, you don’t need to know anything about Java itself, but you do need to understand the Java Virtual Machine. A Java Virtual Machine executes a .class file, the format of which is too complicated to provide here; it is described in the Java Virtual Machine Specification (release 1.0 Beta) available at

The first three parameters passed to your JavaMiniVM routine are pointers to the constants, fields, and methods contained in the .class file that your interpreter is to execute. These parameters are taken directly from the classFile described in Section 2 of the VM specification. A pointer to the classFile is provided as the fourth parameter for those who feel they need direct access to the .class file. The parameter methodToExecute indicates which of the methods your VM is to start executing.

Stack space and execution frames should be established by your virtual machine in the memory provided in heapSpace. Adequate heap space will be allocated by the caller. Your code may include static data that might be needed for lookup tables, etc., to efficiently implement the virtual machine. The parameter returnStack is provided as the stack for the execution environment of the calling routine. It is to be used when executing the various return byte codes to provide the caller access to your results.

To simplify the Challenge, your code need not implement the long, float, and double data types supported by the Java Virtual Machine. You also do not need to process exceptions, breakpoints, monitored code regions, or the wide modifier for Load and Store instructions. Your interpreter should be robust enough to determine the operand size of these unimplemented instructions in order to skip any that are encountered. All methods invoked will be in the single .class file provided to your routine.

Sample test .class files will be provided via the Programmer’s Challenge mailing list, and are also available by writing me at If there are any questions about what needs to be implemented, please send me a note at the same email address.

Your code may be written in PowerPC Assembly, 68K Assembly, C, or C++. Testing will be performed on an 8500 using the latest CodeWarrior environment. Because this is a more difficult Challenge than usual, it has been sent to the mailing list earlier than normal to provide additional solution time. For those of you who haven’t had a chance to investigate Java in detail, it is a good opportunity to find out what all the excitement (hype?) is about. I hope you find this Challenge enjoyable and educational.

Two Months Ago Winner

Once again, congratulations go to Ernst Munter (Kanata, Ontario), this time for submitting the fastest entry to the Connect IV Challenge. Recall that the Challenge was to compete in a round-robin tournament against the other solutions in a generalized version of the well-known Connect 4 game. Pieces are inserted into the top of a column in the vertically oriented board, with the winner being the first player to arrange four or more pieces into a vertical, horizontal, or diagonal line.

Of the five entries I received, four worked completely or nearly correctly, although two of these occasionally forfeited a game by making an illegal move or incorrectly claiming victory. The two solutions winning the most tournament points required more execution time than the others, with the winning solution requiring the greatest amount of time for all but the largest board sizes. The winning solution uses a data structure dubbed a quad to denote each possible line of four pieces passing through a given point on the board, and keeps track of whether each quad represents a possible win for either player. Comments in the solution describe heuristics used to prune the recursive search for the best move.

Four test cases were used, consisting of different board sizes. Each solution competed twice against each other solution, playing once with the first move and once with the second move. The table below indicates how many points were earned by each entry for each of the board sizes:

Greg Cooper666826
Louis Deaett042410
Ernst Munter1210121246
Keith Pomakis644014

The table below summarizes the results for each entry, including tournament points, code size, data size, and execution time. Numbers in parentheses after a person’s name indicate that person’s cumulative point total for all previous Challenges, not including this one.

Ernst Munter (194)4662122944
Greg Cooper (7)2672721600
Keith Pomakis141113512
Louis Deaett10<14600

Top Twenty Contestants

Here are the top twenty contestants for the Programmer’s Challenge. The numbers below include points awarded over the twenty-four most recent contests, including points earned by this month’s entrants.

1.Munter, Ernst20311.Cutts, Kevin21
2.Gregg, Xan9212.Picao, Miguel Cruz21
3.Larsson, Gustav8713.Brown, Jorg20
4.[Name deleted]6714.Gundrum, Eric20
5.Lengyel, Eric4015.Karsh, Bill19
6.Lewis, Peter3016.Stenger, Allen19
7.Darrah, Dave2917.Cooper, Greg17
8.Beith, Gary2418.Mallett, Jeff17
9.Kasparian, Raffi2219.Nevard, John17
10.Vineyard, Jeremy2220.Nicolle, Ludovic14

There are three ways to earn points: (1) scoring in the top five of any Challenge; (2) 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 5th place 2 points

2nd place 10 points finding bug 2 points

3rd place 7 points suggesting Challenge 2 points

4th place 4 points

Here is Ernst’s winning solution:


Copyright © 1996 Ernst Munter

    “Connect IV”

    The challenge is to write code for a well-known game that will compete against 
    other entries, as well as against the clock.  The game board consists of an NxM 
    array into which two players alternate inserting pieces. Pieces are inserted into the 
    top of a column in the vertically oriented board, so that they drop into the lowest 
    unoccupied cell of that column. The objective is to be the first player to arrange 4 
    or more pieces into a vertical, horizontal, or diagonal line.

    My solution is based on an unsophisticated look-ahead scheme.  We search, depth 
    first, up to a maximum depth, to find the move which will give the highest board 
    score. Dummy moves are executed alternatingly by the 2 players, in a recursive 

    At each recursion level, the board score accumulated at the deeper levels is 
    subtracted from the value of the move contemplated at this level.

    In a full look-ahead to depth N, and with a board width of
    C columns, we would have C^N moves to examine.

    Two techniques are combined to reduce the number of moves to be examined:

    At each level, the search can stop if a certain threshold is exceeded or a winning 
    (losing) position is reached. Exceeding the threshold would mean that the calling 
    level could not gain a better score, given its best score to this point.

    In order to be able to stop searching (prune the tree), we would like to start with 
    moves which give the better scores, i.e. rather than go from left to right across
    the board, we start at the position of the last move and go alternatingly left and 
    right of that point. This tackles the active area of the board first where it is more 
    likely to find the best move.

Data Representation
    The scoring relies entirely on a simple representation of the state of the board.

    The board is visualized as covered with potential lines (horizontal, vertical, 
    diagonal) of 4 adjacent fields.  Each such line is called a “quad”.

    A given field is associated with at least 3 (corner fields)
    and at most 16 such quads (in the center of a large board).

    Each quad can have a state (empty, owned by player 1, owned by player 2, or 
    spoiled). The spoiled state implies this quad contains pieces from both players, and 
    can no longer be a winning quad.

    In addition, a non-empty quad has a value, depending on how many player pieces it 

    I have arbitrarily set these values as follows:

    empty 0
    1 piece                   1
    2 pieces   16
    3 pieces   256
    4 pieces   4096

    The value of a placing a piece in a given field, is calculated as the sum of the values 
    of all quads associated with this field.

    To simplify the book keeping, each field has an associated data structure which 
    points to all relevant quads.

    The Field structure also provides local stack space to hold the previous values of its 
    quads while a move is explored.

    A recognized weakness of this approach is that it treats all quads equally, and does 
    not recognize gravity, that is the need to fill columns from the bottom. This effect
    can shadow otherwise good candidates from ever winning. I had no time left to 
    include this consideration in the board scoring.

Running Time
    The depth of the tree dramatically affects the time to compute a move, as does the 
    width of the board.

    A few minor techniques are used to improve running time.

    After each move, all spoiled quads are removed from their field references.

    All full columns are excluded from the move list.

    Empty columns “far away” from the action are also excluded.

    The MAGIC_NR constant can be used to adjust the speed of the program. A higher 
    value increases the search depth and the running time. 
    I set MAGIC_NR to 17 for acceptable all-round performance on my computer.

    At least 7 columns are assumed.
    The calling program should check for wins;
    it is assumed that this function is not called
    if the opponent has already won.

    A move value of -1 is returned when errors are detected, e.g when there are no free 
    fields left.

    This program does not include a randomizer since it is assumed it will play only a 
    few times against computer opponents who, we hope will not be able to take 
    advantage of this.

    In a version to be played by humans, one would randomly choose between equally 
    good moves to make it more interesting.

Note on style
    This program is basically a C program in spirit, but using C++ structs for 
    convenience in accessing dynamic data.

    No inheritance, operator overloading or the like.

    All simple functions are listed inline, as part of the class. The implementations of 
    functions with loops are listed separately, following the struct declaration.

#include <stdlib.h>
#include "viervier.h"

#define maxRow 63
#define maxCol 64

#define maxQuad (((maxRow-3)*maxCol)+\
#define empty    0
#define self1
#define opponent 2
#define spoiled  3

#define OTHER_PLAYER (3-player)
#define WIN 4096
#define MAX_MOVES9

#define MAGIC_NR 17

struct Quad {
 short  status;  //who owns quad
 short  value;   //16 ^ (n-1);

 int  Update(int currentPlayer){
 if (status==empty) {
 return value;
 if (status==currentPlayer) {
 value <<= 4;    //higher value
 return value;
 if (status != spoiled) { //other player
 return value;   //plus for us
 return 0;//already spoiled
typedef struct Quad Quad;

struct Field {
 Quad* quadRef[16];//pointers to intersecting quads
 Quad savedState[16];//stack to save quads before move

 void AddQuad(Quad* qp);
 void SaveState();
 void RestoreState();
 int  MakeMove(int currentPlayer);
 void Rationalize();
 int  IsEmpty(){
 if (quadRef[0]->status) return 0;
 return 1;
typedef struct Field Field;

void Field::AddQuad(Quad* qp) {    //adds qp to list of quads
int k;
 for (k=0;k<16;k++) {
 if (0==quadRef[k]) {

void Field::SaveState() { //save all quads on stack
Quad* qp;
Quad**  qh=quadRef;
Quad* savePtr=savedState;
 for (k=0;k<16;k++) {
 if (0 == (qp=*qh++)) break;

void Field::RestoreState() {//restore quads from stack
Quad* qp;
Quad**  qh=quadRef;
Quad* savePtr=savedState;
 for (k=0;k<16;k++) {
 if (0 == (qp=*qh++)) break;

int Field::MakeMove(int currentPlayer) {
long  sum=0;
long  val;
Quad* qp;
Quad**  qh=quadRef;//move=update all quads
    //return value of move
 for (k=0;k<16;k++) {
 if (0 == (qp=*qh++)) break;
 if (val>=WIN) {
 return WIN;
 return sum;

void  Field::Rationalize() {
intnq=0;//remove all spoiled quads

//find number of non-0 quad refs
 for (k=0;k<16;k++) {
 if (quadRef[nq]) nq++;
 else break;

//scan quad refs for spoiled quads, and remove
 while(i<nq) {
 Quad* qp=quadRef[i];
 if (qp->status==spoiled) {
 if (i<nq) quadRef[i]=quadRef[nq];

struct PrivateData {
 int  nextMove;  //next real move to do
 int  numCols;   //number of columns
 int  numRows;   //number of rows
 int  numFree;   //number of fields free
 int  level;//recursion depth
 int  numMoves;  //number of moves in move list
 Field* endOfBoard;//sentinel pointer
 int  numHistory;//move counter
 int  history[maxCol*maxRow]; //move history
 int  moveList[maxCol];   //list of columns
 Field* nextField[maxCol];//next free field in column
 Field  board[maxCol*maxRow]; //array of all fields
 Quad quadSet[maxQuad];   //array of all quads

 void Initialize(long nCols,long nRows);
 void FirstMove() {nextMove = numCols >> 1;}
 void MakeMoveList(int move);
 int  BestMove(int level,int player,int threshold);
 void Rationalize(int move);
 int  CannedMove();
 void RecordMove(int move) {
 if (numHistory==0)
 else history[numHistory++]=move-history[0];
 void AdjustLevel() {
 level=MAGIC_NR - numMoves;
 if (numMoves<=7) level--;
 if (level>=numFree) level=numFree-1;
 int  UpdateBoard(int move,int player) {
 Field* fp=nextField[move];
 long score=fp->MakeMove(player);
 return score;
typedef struct PrivateData PrivateData;

field numbering example (6-by-7)

35             36 37  38         39 40  41               5           |
28             29 30  31         32 33  34               4           |
21             22 23  24         25 26  27               3           o
14             15 16  17         18 19  20               2           s
7        8           9           10  11         12 13  1    |
0        1           2           3           4           5           6           0           |
    -- columns --

void PrivateData::Initialize(long nCols,long nRows){
Field*  field;
Quad*   qp;

 numFree = nCols*nRows;


 for (col=0;col<nCols;col++)

 for (row=0;row<nRows;row++) {//set up quad references
 for (col=0;col<nCols;col++) {
 int direction,delta;
 for (direction=0;direction<4;direction++) {
 //right, up-right, up, up-left

 switch (direction) {
 //eliminate all that don’t fit
case 0: if (col>=nCols-3) continue;break;
case 1: if (col>=nCols-3) continue;
case 2: if (row>=nRows-3) continue;break;
case 3: if ((row>=nRows-3) || (col<3)) continue;

 for (delta=0;delta<4;delta++) {
 Field* fp;
 switch (direction) {
case 0: fp=field+row*nCols+(col+delta);break;
case 1: fp=field+(row+delta)*nCols+(col+delta);break;
case 2: fp=field+(row+delta)*nCols+col;break;
case 3: fp=field+(row+delta)*numCols+(col-delta);break;

void  PrivateData::Rationalize(int move) {

//remove spoiled quads from all free fields in the vicinity of a recent move

int i=move-3,j=move+4;
 if (i<0) i=0;
 if (j>numCols) j=numCols;
 for (;i<j;i++) {
 Field* fp=nextField[i];
 while (fp<endOfBoard) {

void PrivateData::MakeMoveList(int move) {

//build the move sequence, starting from the center
//out to the limits while skipping full columns.

 do {
 if (nextField[m]<endOfBoard) moveList[n++]=m;
 if (n>=MAX_MOVES) goto done;
 if (0>(m=m-k)) goto go_right;
 if (nextField[m]<endOfBoard) moveList[n++]=m;
 if (n>=MAX_MOVES) goto done;
 if (numCols<=(m=m+k)) goto go_left;
 } while(1);

 if (0>(m=m-k-1)) goto done;
 do {
 if (nextField[m]<endOfBoard) moveList[n++]=m;
 if (n>=MAX_MOVES) goto done;
 } while(m>=0);
 goto done;

 if (numCols<=(m=m+k+1)) goto done;
 do {
 if (nextField[m]<endOfBoard) moveList[n++]=m;
 if (n>=MAX_MOVES) goto done;
 } while(m<numCols);


int PrivateData::CannedMove() {
#define H0 (history[0])
 switch (numHistory) {
case 1: if (H0>=3) return H0;
 if (H0+3<numCols) return H0;
 return numCols/2;
case 2: switch (history[1]) {
 case 0:return H0;
 case 1:if (H0>=3) return H0-3; else return H0;
 case -1:if (numCols-H0>3) return H0+3; else return H0;
 case 2:case -2:return H0;
 case 3:if (H0>=1) return H0-1; else return H0-1;
 case -3:if (numCols-H0>1) return H0+1; else return H0+1;
 default:if (H0>=2) return H0-1; else return H0+3;
case 3: if (history[1]==0) {
 if (history[2]>=0) return H0-1;
 if (history[2]<0) {
 if (H0+1<numCols) return H0+1;
 return -1;

int PrivateData::BestMove(
 int level,int player,int threshold) {

//this routine is called recursively to return the value of the best move. The class //variable “nextMove” holds 
the column number for the “best” move.

 for (i=0;i<numMoves;i++) {
 int m=moveList[i];//work from list
 Field* fp=nextField[m];
 if (fp < endOfBoard) {   //else column is full
 moveValue = fp->MakeMove(player);

 if (moveValue>=WIN) {    //win here: return right away
 return WIN*2;

 if (level) {    //descend to next level

 if (score>=WIN) {
 moveValue=-score+1024;   //bias for depth
 goto skip;
 moveValue -= score; //and accumulate score

 if (moveValue>=threshold) {
 //no need to search further
 return moveValue;
 if (moveValue>bestV) {   //keep track of best so far

 return bestV;

long ConnectMove (
 long numCols,
 long numRows,
 void *privStorage,
 long prevMove,
 Boolean newGame,
 Boolean *victory) {

PrivateData* PD=(PrivateData*)privStorage;

 if (newGame) {  //initialize on first call
 if (prevMove==-1) {
 PD->FirstMove();//standard first move
 goto finish;


 if (PD->numFree<=0) return -1;    //the board is full

 if ((PD->nextMove=PD->CannedMove())<0) {



 return PD->nextMove;


Community Search:
MacTech Search:

Software Updates via MacUpdate

Ys Chronicles II (Games)
Ys Chronicles II 1.0.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0.0 (iTunes) Description: After a hard fight to recover the six sacred books in Ys Chronicles I, Adol is back for a sequel! | Read more »
FINAL FANTASY Ⅸ 1.0.4 Device: iOS Universal Category: Games Price: $16.99, Version: 1.0.4 (iTunes) Description: ==========●Special sale price for the FINAL FANTASY IX release! ●20% off from February 10 to February 21, 2016... | Read more »
Tennis Club Story (Games)
Tennis Club Story 1.03 Device: iOS Universal Category: Games Price: $4.99, Version: 1.03 (iTunes) Description: Aim for the ace position of tennis club prestige in this simulation! Your leadership decides if players make it to the big... | Read more »
Juggernaut Wars guide - How to use skill...
Juggernaut Warsis a brand new auto-RPG on iOS and Android that challenges you to build a team of heroes, send them out into various different missions to defeat waves of heroes, and level them up to increase their power. The actual combat itself... | Read more »
Check out the new Pirate Attack update i...
Love pirates and board games? Well, you'll love the new Pirate Attack themed update that just launched in Game of Dice. It adds a bunch of new content themed around pirates, like an all new event map based on a pirate ship which revamps the toll... | Read more »
Splash Cars guide - How to paint the tow...
Splash Cars is an arcade driving game that feels like a hybrid between Dawn of the Plow and Splatoon. In it, you'll need to drive a car around to repaint areas of a town that have lost all of their color. Check out these tips to help you perform... | Read more »
The best video player on mobile
We all know the stock video player on iOS is not particularly convenient, primarily because it asks us to hook a device up to iTunes to sync video in a world that has things like Netflix. [Read more] | Read more »
Four apps to help improve your Super Bow...
Super Bowl Sunday is upon us, and whether you’re a Panthers or a Broncos fan you’re no doubt gearing up for it. [Read more] | Read more »
LooperSonic (Music)
LooperSonic 1.0 Device: iOS Universal Category: Music Price: $4.99, Version: 1.0 (iTunes) Description: LooperSonic is a multi-track audio looper and recorder that will take your loops to the next level. Use it like a loop pedal to... | Read more »
Space Grunts guide - How to survive
Space Grunts is a fast-paced roguelike from popular iOS developer, Orange Pixel. While it taps into many of the typical roguelike sensibilities, you might still find yourself caught out by a few things. We delved further to find you some helpful... | Read more »

Price Scanner via

What iPad Pro Still Needs To Make It Truly Pr...
I love my iPad Air 2. So much that I’m grudgingly willing to put up with its compromises and limitations as a production tool in order to take advantage of its virtues. However, since a computer for... Read more
21-inch 3.1GHz 4K on sale for $1399, $100 off...
B&H Photo has the 21″ 3.1GHz 4K iMac on sale $1399 for a limited time. Shipping is free, and B&H charges NY sales tax only. Their price is $100 off MSRP: - 21″ 3.1GHz 4K iMac (MK452LL/A): $... Read more
Apple price trackers, updated continuously
Scan our Apple Price Trackers for the latest information on sales, bundles, and availability on systems from Apple’s authorized internet/catalog resellers. We update the trackers continuously: - 15″... Read more
Save up to $240 with Apple Certified Refurbis...
Apple is now offering Certified Refurbished 12″ Retina MacBooks for up to $240 off the cost of new models. Apple will include a standard one-year warranty with each MacBook, and shipping is free. The... Read more
Apple refurbished 13-inch Retina MacBook Pros...
Apple has Certified Refurbished 13″ Retina MacBook Pros available for up to $270 off the cost of new models. An Apple one-year warranty is included with each model, and shipping is free: - 13″ 2.7GHz... Read more
Apple refurbished Time Capsules available for...
Apple has certified refurbished Time Capsules available for $120 off MSRP. Apple’s one-year warranty is included with each Time Capsule, and shipping is free: - 2TB Time Capsule: $179, $120 off - 3TB... Read more
13-inch 2.5GHz MacBook Pro (refurbished) avai...
Apple has Certified Refurbished 13″ 2.5GHz MacBook Pros available for $829, or $270 off the cost of new models. Apple’s one-year warranty is standard, and shipping is free: - 13″ 2.5GHz MacBook Pros... Read more
Apple refurbished 15-inch Retina MacBook Pros...
Apple has Certified Refurbished 2015 15″ Retina MacBook Pros available for up to $380 off the cost of new models. An Apple one-year warranty is included with each model, and shipping is free: - 15″ 2... Read more
New Liquid Crystal Technology Prevents Automo...
Researchers at the University of Central Florida have developed three new liquid crystal mixtures which will allow automobile displays to operate at unprecedented high and low temperatures In... Read more
BookBook For iPad Pro Coming Soon
The iPad Pro is a device unlike any other, and with Apple Pencil, it’s the ideal portable sketchpad: all that’s missing is the modern easel and portfolio to go. TwelveSouth’s BookBook for iPad Pro... Read more

Jobs Board

Lead Engineer - *Apple* OSX & Hardware...
Lead Engineer - Apple OSX & Hardware **Job ID:** 3125919 **Full/Part\-Time:** Full\-time **Regular/Temporary:** Regular **Listed:** 2016\-02\-10 **Location:** Cary, Read more
*Apple* System Analyst - ATOS IT Services...
Apple System AnalystReference no.198783CountryUSARegionUS - CALIFORNIACityUS - CALIFORNIA - BURBANKPosition TypeProfessionalJob AreaIT SupportJob TypeFull Read more
*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Retail - Multiple Positions (US) - A...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Subject Matter Expert - Experis (Uni...
This position is for an Apple Subject Matter Expert to assist in developing the architecture, support and services for integration of Apple devices into the domain. Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.