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

World of Tanks Generals guide - Tips and...
World of Tanks Generals is a brand new card game by the developer behind the World of Tanks shooter franchise. It plays like a cross between chess and your typical card game. You have to keep in consideration where you place your tanks on the board... | Read more »
TruckSimulation 16 guide: How to succeed...
Remember those strangely enjoyable truck missions in Grand Theft Auto V whereit was a disturbing amount of fun to deliver cargo? TruckSimulation 16 is reminiscent of that, and has you play the role of a truck driver who has to deliver various... | Read more »
The best GIF making apps
Animated GIFs have exploded in popularity recently which is likely thanks to a combination of Tumblr, our shorter attention spans, and the simple fact they’re a lot of fun. [Read more] | Read more »
The best remote desktop apps for iOS
We've been sifting through the App Store to find the best ways to do computer tasks on a tablet. That gave us a thought - what if we could just do computer tasks from our tablets? Here's a list of the best remote desktop apps to help you use your... | Read more »
Warhammer 40,000: Freeblade guide - How...
Warhammer 40,000: Freebladejust launched in the App Store and it lets you live your childhood dream of blowing up and slashing a bunch of enemies as a massive, hulking Space Marine. It's not easy being a Space Marine though - and particularly if... | Read more »
Gopogo guide - How to bounce like the be...
Nitrome just launched a new game and, as to be expected, it's a lot of addictive fun. It's called Gopogo, and it challenges you to hoparound a bunch of platforms, avoiding enemies and picking up shiny stuff. It's not easy though - just like the... | Read more »
Sago Mini Superhero (Education)
Sago Mini Superhero 1.0 Device: iOS Universal Category: Education Price: $2.99, Version: 1.0 (iTunes) Description: KAPOW! Jack the rabbit bursts into the sky as the Sago Mini Superhero! Fly with Jack as he lifts impossible weights,... | Read more »
Star Wars: Galaxy of Heroes guide - How...
Star Wars: Galaxy of Heroes is all about collecting heroes, powering them up, and using them together to defeat your foes. It's pretty straightforward stuff for the most part, but increasing your characters' stats can be a bit confusing because it... | Read more »
The best cooking apps (just in time for...
It’s that time of year again, where you’ll be gathering around the dinner table with your family and a huge feast in front of you. [Read more] | Read more »
Square Rave guide - How to grab those te...
Square Rave is an awesome little music-oriented puzzle game that smacks of games like Lumines, but with its own unique sense of gameplay. To help wrap your head around the game, keep the following tips and tricks in mind. [Read more] | Read more »

Price Scanner via

Sunday roundup of Holiday weekend Mac sales:...
Take up to $500 off MSRP on the price of a new Mac at B&H Photo today as part of their Black Friday/Holiday weekend sale. Shipping is free, and B&H charges NY tax only. These prices are... Read more
Holiday weekend: Apple Watch on sale for $50-...
B&H Photo has the Apple Watch on sale today for $50-$100 off MSRP. Shipping is free, and B&H charges NY sales tax only: - Apple Watch Sport: $50 off - Apple Watch: $50-$100 off Read more
Holiday weekend: iPad Air 2s on sale for up t...
B&H Photo has iPad Air 2s on sale for up to $80 off MSRP including free shipping plus NY sales tax only: - 16GB iPad Air 2 WiFi: $459 $40 off - 64GB iPad Air 2 WiFi: $569 $30 off - 128GB iPad Air... Read more
Holiday weekend Mac sales roundup: B&H Ph...
B&H Photo continues to have all new Macs on sale for up to $500 off MSRP as part of their Black Friday/Holiday weekend sale. Shipping is free, and B&H charges NY tax only: - 15″ 2.2GHz Retina... Read more
iMobie Releases its Ace iOS Cleaner PhoneClea...
iMobie Inc. has announced the new update of PhoneClean 4, its iOS cleaner designed to reclaim wasted space on iPhone/iPad for use and keep the device fast. Alongside, iMobie hosts a 3-day giveaway of... Read more
U.S. Cellular Offering iPad Pro
U.S. Cellular today announced that it is offering the new iPad Pro with Wi-Fi + Cellular, featuring a 12.9-inch Retina display with 5.6 million pixels — the most ever in an iOS device. U.S. Cellular... Read more
Newegg Canada Unveils Black Friday Deals for...
Newegg Canada is offering more than 1,000 deep discounts to Canadian customers this Black Friday, available now through Cyber Monday, with new deals posted throughout the week. “Black Friday is... Read more
Black Friday: Macs on sale for up to $500 off...
BLACK FRIDAY B&H Photo has all new Macs on sale for up to $500 off MSRP as part of their early Black Friday sale including free shipping plus NY sales tax only: - 15″ 2.2GHz Retina MacBook Pro: $... Read more
Black Friday: Up to $125 off iPad Air 2s at B...
BLACK FRIDAY Walmart has the 16GB iPad Air 2 WiFi on sale for $100 off MSRP on their online store. Choose free shipping or free local store pickup (if available): - 16GB iPad Air 2 WiFi: $399, save $... Read more
Black Friday: iPad mini 4s on sale for $100 o...
BLACK FRIDAY Best Buy has iPad mini 4s on sale for $100 off MSRP on their online store for Black Friday. Choose free shipping or free local store pickup (if available): - 16GB iPad mini 4 WiFi: $299.... Read more

Jobs Board

Technical Program Manager, Strategic Merchant...
# Technical Program Manager, Strategic Merchants - Apple Pay Job Number: 44001177 Santa Clara Valley, Califo ia, United States Posted: Oct. 30, 2015 Weekly Hours: 40.00 Read more
Frameworks Engineer, *Apple* Watch - Apple...
# Frameworks Engineer, Apple Watch Job Number: 41403122 Santa Clara Valley, Califo ia, United States Posted: Jul. 1, 2015 Weekly Hours: 40.00 **Job Summary** Join the Read more
Software Engineer - *Apple* Pay - Apple (Un...
# Software Engineer - Apple Pay Job Number: 44003246 Santa Clara Valley, Califo ia, United States Posted: Nov. 16, 2015 Weekly Hours: 40.00 **Job Summary** Apple Pay Read more
Merchant Operations Manager: *Apple* Pay -...
# Merchant Operations Manager: Apple Pay Job Number: 43593822 Santa Clara Valley, Califo ia, United States Posted: Nov. 10, 2015 Weekly Hours: 40.00 **Job Summary** The Read more
Product Design Engineer - *Apple* Watch - A...
# Product Design Engineer - Apple Watch Job Number: 41727161 Santa Clara Valley, Califo ia, United States Posted: Jul. 22, 2015 Weekly Hours: 40.00 **Job Summary** Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.