August 2001 Programmer's Challenge

I love sailing. That is, most of the time I love it, in between the moments when I’m terrified in an exhilarating sort of way. I don’t own a boat, which has allowed me to avoid both of the two favorite days of a boat owner’s life — the day he buys the boat, and the day he sells the boat. Most years I’m a two-week-a-year sailor, renting small to medium size boats on inland lakes during summer vacations.

But this year we did something different. We decided to charter a sailboat and spend a week in the U.S. and British Virgin Islands. Thanks to Captain Jerry and Chef Christine Miller on a 51’ Beneteau, the Rusty Nail II, we had a wonderful week sailing, snorkeling, (drinking — I’d forgotten how many truly excellent drinks can be made with rum) and dining our way around St John, Tortola, Norman Island, Virgin Gorda, Marina Cay, and several other islands.

So why am I telling you this? Not to arouse envy, certainly not. No, I’m telling you this because the August Challenge is based on sailing. Your task this month is to write code that will efficiently sail a simulated boat through a specified sequence of marks.

The prototype for the code you should write is:

typedef struct Position {
  long x;  /* positive x is East */
  long y;  /* positive y is North */
} Position;

typedef double Direction;  /* clockwise from north, in radians */

typedef struct Velocity {
  Direction direction;
  double speed;
    /* x velocity is speed*sin(direction) */
    /* y velocity is speed*cos(direction) */
} Velocity;

void InitCarribeanCruise(
  short numberOfMarks,
  Position mark[],
    /* must pass through mark[i] for each i in turn */
  double tolerance,
    /* must pass within this distance of each mark */
  double integrationInterval
    /* amount of time between calls to Cruise, in seconds */
);

Boolean /* done */ Cruise(  
  Position boatLocation,  /* boat position at the start of this time segment */
  Velocity boatVelocity,  /* boat velocity at the start of this time segment */
  Velocity windVelocity,  /* true wind velocity at this location and time */
  double currentTime,      /* time since cruise start, in seconds */
  Direction *targetBoatDirection,
    /* commanded boat direction */
  Direction *sailTrim
    /* commanded sail trim, 0..PI/4, measured as angle off the stern, in the direction away from the source of the wind. */
    /* Actual sail position is a function of trim and wind direction. */
);

void TermCarribeanCruise(void);

The Challenge works like this. First, your InitCarribeanCruise routine is called, providing you with a description of the course to be followed. You will need to pass through the specified marks in sequence, approaching each within a specified distance tolerance. Then your Cruise routine is called repeatedly, at time intervals of integrationInterval, until you complete the course. Finally, your TermCarribeanCruise routine is called, where you should return any dynamically allocated memory.

With each Cruise call, you are given the current boatLocation and boatVelocity, along with the current WindVelocity for your location at the currentTime. You have two controls for the boat, the helm and the sailTrim. For simplicity, we’re going to treat your boat as if it has only one sail — no need to separately trim the main and the jib. Our simplified sail trim model lets you control the maximum amount the sail can be let out, from 0° off the stern (tight trim) to 90° off the stern. The sail always moves away from the stern in the direction away from the source of the wind, clockwise off the stern when the wind is from starboard (right of the boat), and counterclockwise when the wind is from port (left of the boat).

High fidelity sailing models use complicated velocity prediction programs to determine boat speed as a function of wind and sails, but we’ll use something simpler. When sailing into the wind (you cannot sail directly into the wind, but you can sail up to 45° off the wind direction in our model), the greatest sailing force is provided with the sails tight, 0° off the stern. As you fall off the wind, greater thrust is provided by easing the sails out. When the wind is directly astern (behind you), letting the sail out a full 90° provides the greatest thrust.

As counterintuitive as it might seem, you actually sail faster when going upwind. This is because the motion of the boat actually increases the apparent speed of the wind. You can take my word for it, or you can do a little vector arithmetic to convince yourself. Similarly, going downwind, the force of the wind on the boat actually approaches zero as the boat speed gets closer to the true wind speed, reducing the apparent wind speed. Of course, the resistance of the water prevents the boat from actually reducing the apparent wind speed to zero.

Enough about sailing, back to what you need to do. For each call to Cruise, you need to return the direction you want the boat to move (targetBoatDirection), and how you want to trim the sail (sailTrim). There are limits on how quickly the boat can turn, so you might not actually attain the targetBoatDirection in one integration interval. As for the sailTrim, if you ease the sail too much, it will luff and provide less (or perhaps no) force. If you keep it too tight, you’ll also get less force from the wind and will go more slowly. The specifics of the velocity model will be included in the test code provided with the problem — see www.mactech.com/progchallenge for details.

Your objective is to sail through the marks as quickly as possible. The winner will be the entry that completes the course in the minimum simulated time, after adding a penalty of one simulated second for each millisecond of execution time. The Challenge prize will be divided between the overall winner and the best scoring entry from a contestant that has not won the Challenge recently.

This will be a native PowerPC Challenge, using the CodeWarrior Pro 6 environment. Solutions may be coded in C or C++. You may provide a solution in Java instead, provided you also provide a test driver equivalent to the C code provided on the web for this problem.

Test code for this Challenge will be available soon.

You can get a head start on the Challenge by reading the Programmer's Challenge mailing list. It will be posted to the list on or before the 12th of the preceding month. To join, send an email to listserv@listmail.xplain.com with the subject "subscribe challenge-A". You can also join the discussion list by sending a message with the subject "subscribe challenge-D".