Apr 96 Challenge
- Jan 96 Challenge
- Feb 96 Challenge
- Mar 96 Challenge
- May 96 Challenge
- Jun 96 Challenge
- Jul 96 Challenge
- Aug 96 Challenge
- Sep 96 Challenge
- Oct 96 Challenge
- Nov 96 Challenge
- Dec 96 Challenge
Volume Number: 12
Issue Number: 4
Column Tag: Programmer’s Challenge
Programmer’s Challenge 
By Bob Boonstra, Westford, Massachusetts
Note: Source code files accompanying article are located on MacTech CD-ROM orsource code disks.
Mutant Life
Time for a little nostalgia this month. Most of you probably remember John Conway’s
exploration of cellular automata known as the game of Life. The game is played on a
grid of square cells. A cell has one of two states - it can be occupied (“alive”) or
empty (“dead”). Time proceeds in discrete increments, or generations, and the state
of a cell at time N+1 is determined by its state and that of its eight neighbors at time N.
In the simplest variations of the game, a “birth” occurs in an empty cell if exactly
three of its neighbors were alive in the previous generation. A “death” occurs in an
occupied cell surrounded by four or more living cells, or by fewer than two living
cells.
This month, the challenge is to write code that will compute the state of a
Life-like world some number of generations into the future. The prototype for the
code you should write is:
pascal long PropagateLife(
BitMap cells, /* the boundaries and population of your automata */
long numGenerations, /* number of generations to propagate */
short birthRules, /* defines when cells become alive */
short deathRules /* defines when cells die */
);
Your automata live in a world defined by the rectangle cells.bounds (with top
and left coordinates guaranteed to be 0). Their world is actually a torus instead of a
rectangle: the cells.bounds.right-1 column of cells is adjacent to column 0, and the
cells.bounds.bottom-1 row of cells is adjacent to row 0. The rules for birth and
death are generalized from those in the first paragraph and defined by birthRules and
generation if the bit (birthRules & (1< is set. An occupied cell with Y occupied
neighbors dies in the next generation if the bit (deathRules & (1< is set. Any
other cell retains its previous state (occupied or empty) from one generation to the
next. As an example, the version of the game described in the first paragraph would
have birthRules=0x0008 and deathRules=0x01F3.
The initial population of automata is pointed to by cells.baseAddr, one bit per
cell, when PropagateLife is called. An occupied cell has the value 1, and an empty
cell has the value 0. The cells BitMap is defined in the usual way, with row R found
starting at *(cells.baseAddr + R*cells.rowBytes). You are to use birthRules
and deathRules to propagate this population ahead for numGenerations generations,
stopping only in the event that the population of generation N is identical to that of the
immediately preceeding generation. Your code must return the number of generations
processed (which will be numGenerations unless a static population was reached).
When you return, the memory pointed to by cells.baseAddr must contain the
propagated population.
You may allocate a reasonable amount of auxiliary storage if that is helpful,
provided (as always) that you deallocate any memory before returning, as I will be
calling your code many times.
This month, we continue the language experiment that permits your solution to
the Challenge to be coded in C, C++, or Pascal, using your choice among the MPW,
Metrowerks, or Symantec compilers for these languages. The environment you choose
must support linking your solution with test code written in C. Along with your
solution, you should provide a project file or make file that will generate a stand-alone
application that calls your solution from C test code.
This will be a native PowerPC Challenge. Now, start propagating
Two Months Ago Winner
Congratulations to Ernst Munter (Kanata, Ontario) for submitting the fastest entry
to the Intersecting Rectangles Challenge. Of the eighteen contestants who submitted
entries, sixteen provided correct solutions. Recall that the Challenge was to provide
code that would return a set of output rectangles containing all points inside in an odd
number (or an even number, depending on an input parameter) of input rectangles.
A number of solutions scanned the list of input rectangles and created a list of
rectangles formed by the intersections, keeping track of whether the resulting
subrectangles were inside an odd or an even number of input rectangles. Other
solutions used a bitmap approach, calculating the exclusive OR of the input rectangles
(for the odd parity case). The bitmap technique tended to suffer when the rectangles
spanned a large x/y space.
The winning solution combines these techniques in an interesting way. Ernst first
scans the input rectangles to collect and sort the unique x and y vertex coordinates. He
then forms a reduced-scale bitmap using these virtual pixels (dubbed “vixels”),
applying the XOR technique to compute the odd or even parity intersections of the input
rectangles. Finally, Ernst scans the “vixelMap” to form output rectangles of the
appropriate parity. An innovative technique that was not only fast but also
space-efficient compared with many of the other entries.
The table below summarizes the results for entries that worked correctly. It
shows the total time required for 60 test cases of up to 250 input rectangles per test
case, the number of output rectangles produced, and the total code/data size of each
entry. (The limit of 250 input rectangles resulted from the large memory
requirements of some of the solutions.) Numbers in parentheses after a person’s name
indicate that person’s cumulative point total for all previous Challenges, not including
this one.
Name time # of rects size
Ernst Munter (112) 312 105460 2264
ACC Murphy 398 446556 1210
John Nevard (10) 551 98804 3092
Miguel Cruz Picão (7) 1032 261562 1328
Xan Gregg (88) 1716 103673 1232
Cathy Saxton 1854 457508 1148
David Cary 4361 436993 2205
Elden Wood 5824 1785710 1012
Bob Clark 6016 1789749 1572
Randy Boring 6033 446556 2589
Alex Kipnis 10158 1785710 1218
Tom Saxton (10) 15206 98041 1264
Richard Cann 23103 282124 3581
Erik Sea 54838 435049 1125
Rishi Khan 180205 2795136 1288
Michael White 938191 239924 1796
Top 20 Contestants of All Time
Here are the Top Contestants for the Programmer’s Challenges to date, including
everyone who has accumulated more than 20 points. The numbers below include points
awarded for this month’s entrants.
Rank Name Points Rank Name Points
1. [Name deleted] 176 11. Mallett, Jeff 44
2. Munter, Ernst 132 12. Kasparian, Raffi 42
3. Gregg, Xan 92 13. Vineyard, Jeremy 42
4. Larsson, Gustav 87 14. Lengyel, Eric 40
5. Karsh, Bill 80 15. Darrah, Dave 31
6. Stenger, Allen 65 16. Brown, Jorg 30
7. Riha, Stepan 51 17. Landry, Larry 29
8. Cutts, Kevin 50 18. Elwertowski, Tom 24
9. Goebel, James 49 19. Lee, Johnny 22
10. Nepsund, Ronald 47 20. Noll, Robert 22
There are three ways to earn points: (1) scoring in the top 5 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 [TOKEN:12832]points
2nd place 10 points finding bug 2 points
3rd place 7 points suggesting Challenge 2 points
4th place 4 points
Xan Gregg earns two points this month for being the first to point out an error
in the winning Find Again and Again solution by Gustav Larsson published in the
February issue. The error occurs because the routines BMH_Search() and
char *. As a result, processing is not correct in some cases when the textToSearch
contains characters >= 0x80. There was confusion on this point in a number of the
entries, and I did not penalize any of the solutions for making this error.
Here is Ernst’s winning Intersecting Rectangles solution:
IntersectRects.c
Copyright 1996, Ernst Munter, Kanata, ON, Canada
/*
The Problem
-----------
Given a bunch of overlapping rectangles, compute a set
of rectangles which covers the area of either an odd or
an even number of overlaps. The output rects should only
use edges from the repertoire of edges contained in the
input set of rects.
General Strategy
----------------
We create a virtual raster with a (variable) resolution,
where each x or y coordinate value corresponds to an
edge of at least one input rectangle. Depending on the
number of input rects, and their coincidence of edges,
this raster may be very small, or fairly large, but never
larger than the screen it represents.
We then paint rectangles into the raster, each raster
point being represented by 1 bit, regardless how many
pixels are within the corresponding edges on the real
screen. I call these bits “virtual pixels” or “vixels”.
After all vixels are painted, the bit map is scanned
to identify rectangular areas of set bits.
The vertical extent of each output rect is at least equal
to the distance between the two neighboring input edges.
We then follow the slice down over as many slices as
possible to maximize the height of the rectangle.
Memory Use
----------
The maximum amount of memory allocated dynamically is
determined by the number of input rects. The actual
amount will be less if some input rects share edge
coordinate values.
Approximate size of the index heap:
(16 * numRectsIn) bytes
plus a few overhead bytes
Approximate combined size of the two vixel maps:
(numRectsIn * numRectsIn) bytes
plus a few overhead bytes,
minus gain from elimination of duplicate values
A double size vixel map is always allocated although
only the even parity case needs both.
For example, total dynamic memory for 100 rectangles will
be about 16K. 1000 rectangles might need 1MB, but on
any reasonable size screen, 1000 rectangles will share
a very large number of edges, and will have considerably
less memory allocated.
Other assumptions (these are not checked)
-----------------------------------------
There is at least one input rect.
All input rects are legal and not empty, that is:
top
*/
#include
#include
#include
#define MAXLONG 0x7fffffff
void RectangleIntersections(
const Rect inputRects[],
const long numRectsIn,
Rect outputRects[],
long *numRectsOut,
const Boolean oddParity);
// Local function prototypes:
void PaintOdd(long* vm,long H,long L,long R,long mapWidth);
void PaintEven(long* vm,long H,long L,long R,long mapWidth);
void PackMap(long* vm,long mapSize);
void Insert(long* h,long size,long x);
long* Sort(long* h,long size);
long GetIndex(long size,long* index,long z);
//Some shorthand macros:
#define IRT (inputRects[i].top)
#define IRL (inputRects[i].left)
#define IRB (inputRects[i].bottom)
#define IRR (inputRects[i].right)
#define ORT (ORptr->top)
#define ORL (ORptr->left)
#define ORB (ORptr->bottom)
#define ORR (ORptr->right)
/* Masks needed to process the edges of vixel blocks
which are not necessarily aligned with bitmap words.
*/
long leftMask[32] =
{0xFFFFFFFF, 0x7FFFFFFF, 0x3FFFFFFF, 0x1FFFFFFF,
0x0FFFFFFF, 0x07FFFFFF, 0x03FFFFFF, 0x01FFFFFF,
0x00FFFFFF, 0x007FFFFF, 0x003FFFFF, 0x001FFFFF,
0x000FFFFF, 0x0007FFFF, 0x0003FFFF, 0x0001FFFF,
0x0000FFFF, 0x00007FFF, 0x00003FFF, 0x00001FFF,
0x00000FFF, 0x000007FF, 0x000003FF, 0x000001FF,
0x000000FF, 0x0000007F, 0x0000003F, 0x0000001F,
0x0000000F, 0x00000007, 0x00000003, 0x00000001};
long rightMask[32] =
{0x80000000, 0xC0000000, 0xE0000000, 0xF0000000,
0xF8000000, 0xFC000000, 0xFE000000, 0xFF000000,
0xFF800000, 0xFFC00000, 0xFFE00000, 0xFFF00000,
0xFFF80000, 0xFFFC0000, 0xFFFE0000, 0xFFFF0000,
0xFFFF8000, 0xFFFFC000, 0xFFFFE000, 0xFFFFF000,
0xFFFFF800, 0xFFFFFC00, 0xFFFFFE00, 0xFFFFFF00,
0xFFFFFF80, 0xFFFFFFC0, 0xFFFFFFE0, 0xFFFFFFF0,
0xFFFFFFF8, 0xFFFFFFFC, 0xFFFFFFFE, 0xFFFFFFFF};
RectangleIntersections
void RectangleIntersections(
const Rect inputRects[],
const long numRectsIn,
Rect outputRects[],
long *numRectsOut,
const Boolean oddParity) {
long* xHeap;
long* yHeap;
long* vixelMap;
long* xIndex;
long* yIndex;
long xIndexMax;
long yIndexMax;
long xHeapSize;
long yHeapSize;
long i;
long mapWidth;
long mapSize;
Rect* ORptr = outputRects;
// First, we collect all X and Y coordinate values of
// all input rectangles in a heap (priority queue), which
// is then sorted into an index without duplicates for each