Month
Month
Program: Laser1w.cpp
Author: Bruce Arnold
In this month's main presentation we will discuss a contest presented in this months Dr. Dobb's Journal. (Dr. Ecco's Omniheurist corner). A VC++ program will be shown which attempts to solve the problem. The code presented will discuss the following:
Dennis E. Shasha
Dr. Dobb's Journal, 8/99 Emma Skylight explained, "NASA is preparing missions for a hundred years from now." The appropriately named scientist described yourself as an optical propulsion physicist. She came to Ecco's apartment with an arm full of detailed construction and laser designs.
"Among the propulsion mechanisms we have designed for space colonies are laser shuttles", she continued. "A laser shuttle propels a vehicle at high speed for short distances (a the few tens of kilometers). In a large Martian plain, this will permit vehicles to be ejected from one space station and 'caught' by breaking lasers on the other side. By the very nature of this transport mechanism, the route that is taken must be linear. Further, for safety sake, we don't want routes to intersect. Collisions would almost surely be fatal."
"Let me see if I understand", Liane said. "Between two stations, there can only be one route. Between three stations there can be the three routes of a triangle. Among the four stations in a square there can be the four links of the square plus one diagonal. The other diagonal is disallowed because it would cross the first."
"Right", said skylight. "At the same time we want there to be as many connections as possible among the stations so that no station will be isolated. Let me tell you about the stations. Each one will have a ground area of 200 by 200 meters and a height of 100 meters. The laser shuttles will fly to and from the roof. The stations will be placed at points in a large grid. The grid points are separated by 10 kilometers in the x and y coordinates."
"We have 20 points. They're not laid down very symmetrically I admit, but they follow the contours of the most temperate Martian Valley, as in figure 1. What we seek from you is a way to lay out the routes so that there are as many as possible and no station has fewer than three routes connecting it to the other stations. Further, no journey should require more than four shuttle trips."
Reader: would you like to give it a try? Ecco and Liane were able to lay out 44 flight paths (edges in the graph) while meeting constraints, including the absence of crossing edges. If you have as good or better solution, please send me a Web page address for viewing a GIF or JPEG of your solution -- I'm not good attachments. Doing better means maintaining positions of the stations and meeting the other conditions of the problem while either: increasing the number of routes without increasing the maximum length of trip; or decreasing the maximum length of the trip without decreasing the number of routes.
void Laser_main( void )
{
int i, j, k, BestCount=0;
for(i=0; i<ARRAYSIZE; ++i) // LIST STATIONS
{
// printf("Station %2d at ", i); station[i].Show(); puts("");
}
for(i=0; i<Rcount; ++i) delete p_route[i]; // clear out any used memory
for(Rcount=i=0; i<ARRAYSIZE; ++i) // FIND ALL POSSIBLE ROUTES
{
for(j=i+1; j<ARRAYSIZE; ++j)
{
p_route[Rcount] = new CRoute(Rcount, &station[i], &station[j]);
if (++Rcount==MAXROUTES)
{ printf("\n+++ MAXROUTES (%d) EXCEEDED +++\n",MAXROUTES); return; }
}
}
// printf("All Possible routes = %d\n",Rcount);
srand( (unsigned)time( NULL ) );
CShuffel *px; // create deck
px = new CShuffel (Rcount);
for(j=i=0; i<Rcount; ++i) p_route[i]->valid = 0; // invalidate all routes
// ---------------------------------------------------------------------------------
// pick a random route.
// check for intersection with other routes picked.
// if no intersections, mark as valid.
for(k=0; k<Rcount; ++k) // FIND ALL VALID ROUTES
{
i = px->next();
for (j=0; j<Rcount; ++j)
{
if (p_route[j]->valid && intersect(p_route[i],p_route[j])) break;
}
if (j==Rcount)
{
p_route[i]->valid = 1; // printf("%d ",i);
}
}
delete px;
// ---------------------------------------------------------------------------------
// puts("VALID ITEMS:");
for(j=i=0; i<Rcount; ++i)
{
if (p_route[i]->valid)
{
++j;
// printf("(%d,%d %d,%d) \t",
// p_route[i]->start->x, p_route[i]->start->y,
// p_route[i]->end->x, p_route[i]->end->y);
}
}
if (j > BestCount) BestCount = j;
// printf("\nSelected routes = %d (%d)\n",j,BestCount);
}
// ------------------------- end of main program -------------------------