Mar 99 Challenge
Volume Number: 15
Issue Number: 3
Column Tag: Programmer's Challenge
Mar 99 Programmer's Challenge
by Bob Boonstra, Westford, MA
Terrain Traversal
You're on foot with cargo to deliver, and a mountain range between you and your
destination. You have no map, nothing except a set of elevation readings provided by a
meticulous surveyor that you met at a pub in the last town. And oh, how you hate to
climb. Fortunately, this month's Challenge comes to the rescue once again with an
efficient and labor saving solution to your problem.
The prototype for the code you should write to solve this Challenge is:
#if defined(__cplusplus)
typedef long PointNum, TriangleNum;
double x; /* x coordinate */
double y; /* y coordinate */
PointNum thePointNum; /* point number */
Point2D thePoint; /* x and y coordinates */
double ht; /* point height (z coordinate) */
typedef struct Triangle {
TriangleNum theTriangleNum; /* triangle number */
PointNum thePoints[3]; /* numbers of points comprising
triangle */
TriangleNum theTriangleNum; /* segment is part of triangle with
this number */
Point2D startingPoint; /* x,y coordinates of segment start */
Point2D endingPoint; /* x,y coordinates of segment end */
long /*numTriangles*/ InitTerrainMap(
const Point3D thePoints[], /* input points */
long numPoints, /* number of input points */
Triangle theTriangles[] /* output triangles constructed from
thePoints */
);
long /*numSegments*/ FindAPath(
const Point3D thePoints[], /* input points (input to
InitTerrainMap) */
long numPoints, /* number of input points */
const Triangle theTriangles[], /* input triangles (from
InitTerrainMap) */
long numTriangles, /* number of input triangles */
const Point2D pathStart, /* input starting point x,y */
const Point2D pathEnd, /* input ending point x,y */
Segment theSegments[] /* output segments from pathStart to
pathEnd */
);
void TermTerrainMap(void);
#if defined(__cplusplus)
}
#endif
Your InitTerrainMap routine is provided a set of points (thePoints), numbered
between 1 and numPoints, that define the terrain to be traversed. It is required to
divide the terrain into a set of non-overlapping triangles (theTriangles) that will be
provided to FindAPath and return the number of triangles created. InitTerrainMap can
divide the terrain into any set of triangles, provided that each of thePoints is a
member of at least one triangle, and that none of thePoints is strictly inside of any
triangle, measured in the x-y plane. Thus, given points (0,1), (1,-1),(-1,1), and
(0,0), the triangle formed by (0,1),(1,-1), and (0,0) would be legal, but the
triangle formed by (0,1), (1,-1), and (-1,-1) would not be allowed, because (0,0)
is strictly inside the latter.
After InitTerrainMap is called, FindAPath will be called an average of 5 times to
generate a sequence of theSegments that traverse a route from pathStart to pathEnd.
FindAPath is provided the same set of thePoints given to InitTerrainMap, as well as
theTriangles produced by InitTerrainMap. Each segment created by FindAPath crosses
from a point along one edge of a triangle to another point along an edge of the same
triangle. The startingPoint and endingPoint of each segment must be inside or on the
boundary of the same triangle (theTriangleNum). The startingPoint of segment 0 must
be pathStart, the endingPoint of segment j must be identical to the startingPoint of
segment j+1, and the endingPoint of the last segment must be pathEnd. The starting and
ending points pathStart and pathEnd will be in the set of thePoints given to
InitTerrainMap, and therefore will be vertices in at least one of theTriangles.
After traversal of some number of paths across the terrain, TermTerrainMap will be
called, where you should dispose of any dynamically allocated storage.
Unfortunately, the surveyor who provided us with thePoints in our terrain map was
not considerate enough to put them on a regular x-y grid. However, he was limited in
the amount of storage he had with him on his mapping expedition, so we know that
there will be no more than 32K points in any given terrain map.
The winner will be the solution that minimizes the amount of work required to reach
the destination, where work is a combination of distance traveled and elevation change.
Specifically, the total work is the sum of the work expended on each segment, which is
calculated as the distance traveled in the x-y plane, plus ten times the absolute value
of the elevation change from the starting and ending points of the segment. In addition,
there will be a penalty of 10% for each second of execution time required to compute a
solution. There is no storage constraint for this Challenge, except that your solution
must run on a 128MB machine.
This will be a native PowerPC Challenge, using the latest CodeWarrior environment.
Solutions may be coded in C, C++, or Pascal.
Three Months Ago Winner
The December Word Neighbors Challenge was intended to be a little easier than some
recent Challenges, but apparently that was not the case. The Challenge was to find all
occurrences of a set of words that occurred within a specified distance of one another
in a body of text. The problem had enough subtle complications that none of the four
solutions submitted by the deadline completed all of my test cases correctly. The
solution by Randy Boring, however, performed correctly with a two-line code change.
It also was the most efficient submission and exhibits some interesting techniques, so I
chose to publish that solution. The code change, while small, was algorithmically
significant, so no prizes or points are going to be awarded for this Challenge. Ludovic
Nicolle and Gregory Sadetsky did submit a correct solution, but it was submitted after
the deadline. Since they described the code as the "ugliest I have ever written in my
entire life", I decided against publishing that solution.
The problem complication that tripped up two of the solutions had to do with treatment
of overlapping matches. The problem requirement was to find all occurrences of the
search words in the text where the distance between search words is less than a
specified amount. No word in the text was allowed to be part of more than one match,
and the solutions were required to return the location of the first matching word. The
fact that search words need not be immediately adjacent allows the match sequences to
overlap. As an example, if the problem is to find a case insensitive and order
independent match of the words "a", "b", "c", "d", "e", and "f" within a distance of 4 or
fewer intervening words in the following text:
c.2.D.4.b.B.7.B.a.B.D.d.C.14.B.e.f.F.F.A.b.F.a.c.E.d
the correct solution is to return the matches starting at character 0 and character 4,
as indicated below:
text: c.2.D.4.b.B.7.B.a.B.D.d.C.14.B.e.f.F.F.A.b.F.a.c.E.d
match1: c----b----a---d----e-f
match2: --D-----B-----C-----F--A-----E
Because of the correctness issues, I did not run the full set of evaluation test cases that
I had originally planned. In putting together a collection of digitized text to use for
testing, I found my way to the Project Gutenberg site at
<http://sailor.gutenberg.org/gutenberg/>, home to a large and growing collection of
digitized literature. It has been quite a while since I read "Twenty Thousand Leagues
Under The Sea", and it was something of a surprise to rediscover, courtesy of this
Challenge, the fact that Captain Nemo doesn't appear until the second half of the book.
Randy's solution is sparsely commented, but there are some interesting features to
notice. Noticing that the problem statement called for numerous searches for each set
of text, Randy parses the text in his InitText routine, creating a UniqueSummary table
of each unique word in the text, and a WordInstance table entry for each word
occurrence in the text. To save space, Randy kept pointers back to the text only in the
UniqueSummary table, not in the WordInstance table, which cost him the Challenge
win. The problem has been corrected in the published solution by adding a word
pointer to the WordInstance table, increasing storage requirements, in order to
provide the required output. To make word comparisons efficient, Randy hashes each
word in the Hash function, and uses that hash to compare words in the FindUniqueWord
function.
In searching for a match, Randy divides the code into four cases, based on whether the
search is case sensitive or not, and on whether the order of the search words is to be
preserved or not. The solution then performs a recursive search of the word instance
table to determine if a match exists within the specified distance.
The table below lists, for each of the solutions submitted, the total execution time, the
types of errors that turned up in the evaluation, the code and data size, and the
programming language. As usual, the number in parentheses after the entrant's name
is the total number of Challenge points earned in all Challenges prior to this one.
Name Time (msec) Memory Alloc. Errors Code Size Data Size Lang
Randy Boring (83) 262 Original* B 7088 34132
Ed Agoff 334 Original A 3212 4236 C++
Ernst Munter (430) 2022 New A 11432 1624
Ludovic Nicolle (48) /
Gregory Sadetsky (2) 120964 New Late 9676 434 C
P.B. - New CRASH 5176 539 C++
A - problems with overlapping matches
B - incorrect return values before correction; correction required revised memory
allocation
Top Contestants
Listed here are the Top Contestants for the Programmer's Challenge, including
everyone who has accumulated 20 or more 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 204
2. Saxton, Tom 79
3. Boring, Randy 56
4. Mallett, Jeff 50
5. Rieken, Willeke 47
6. Maurer, Sebastian 40
7. Heithcock, JG 37
8. Cooper, Greg 34
9. Murphy, ACC 34
10. Lewis, Peter 31
11. Nicolle, Ludovic 27
12. Brown, Pat 20
13. Day, Mark 20
14. Higgins, Charles 20
15. Hostetter, Mat 20
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
2nd place ›10 points
3rd place ›7 points
4th place ›4 points