Darkness 2010-11-10 12:00:00 UTC
 
Twilight 2010-11-11 12:00:00 UTC
 
Daylight 2010-11-12 12:00:00 UTC
 
Finish 2010-11-17 12:00:00 UTC

Sailing Home - Rules

Arrow_down  Download Sample Code

Sailing is the 22nd MATLAB Online Programming Contest.

 

The Problem

old_map.png

As the captain of a sailboat, you have been given the task of sailing to Faraway Island for some nutmeg and then sailing safely home. You reach for your trusted chart to plot the route. The chart, as shown below, shows your current location (point A), the location of Faraway Island (point B), and indications of how the wind is blowing. You have a motor on board, but you'd really like to take advantage of the wind wherever possible, even if that means a somewhat circuitous journey.

map1.png

The Details

Inside a rectangular region, you need to navigate from point A to point B and back again. To do this, you will manage your velocity. Initial velocity is zero, and at each time step you have a limited discretionary delta v (the motor) you can apply to either your horizontal or vertical velocity. In addition, each square in the matrix can have its own delta v (the wind) to add to the velocity. Travel is considered frictionless, so once you start moving, the only way to slow down is to encounter opposing winds or use your motor.

To keep everything as simple and matrix-based as possible, we'll describe all calculations in terms of rows and columns. A "row velocity" of -1 would thus shift the row of your boat up by one (decrease the row index by 1). Whenever your boat lands on a square where the wind is blowing, that wind value is added to your current velocity. In this example, the row and column winds can be represented by two matrices like so.

row winds    = [  .  . -1  .  .  . ]
               [  .  .  .  . -1  . ]
               [  .  .  .  . -1  . ]
               [  .  .  1  . -2  . ]
               [  .  1  .  .  .  . ]
               [  . -1  .  .  .  . ]
 
column winds = [  .  .  .  .  .  . ]
               [  .  .  .  .  .  . ]
               [  1  2  .  .  .  . ]
               [  .  .  . -2  .  . ]
               [  .  .  .  .  .  . ]
               [  .  .  .  .  .  . ]
 

The object of the contest is to navigate from point A to point B while minimizing

  1. the closest approach to point B
  2. the final distance to point A
  3. total motor usage

The motor gives you a limited ability to influence your velocity each turn. The limit is expressed as "maximum throttle". If your max throttle is 3, you can change your row or column velocity (or a combination of the two) by a total of 3. Velocity input is quantized into integer units and the four directions up, down, right, and left. So these would all be legal motor inputs for maxThrottle of 3:

change in row velocity   change in column velocity
         3                         0
         2                        -1
         1                         1
         0                        -3
         0                         0

If you request more power than you have available, you blow out the motor for that turn, resulting in zero input from the motor. Since the motor is ineffective for the turn, you won't be charged for motor command.

Turn Structure

Each turn breaks down like so:

  1. add local winds to velocity
  2. add motor input to velocity
  3. increment position based on velocity

Early Termination

If any move takes you off the chart, play is terminated and your score is calculated based on your last legal location and velocity. Even if play is terminated early, you will still be charged for all the motor authority you request.

Syntax

You will write the function solver.m which will be called by the test harness. It must have this signature:

[thrustRow, thrustCol] = solver(chart, aIndex, bIndex, maxThrottle)

The chart variable is a 3-D matrix, with the row winds given on the first page, chart(:,:,1), and the column winds given on the second page, chart(:,:,2).

The two arguments aIndex and bIndex are scalars that show where your boat will start and where it is expected to visit before returning home. Each one is an absolute index into the matrix. You can find the corresponding row and column values easily with the IND2SUB command like so.

[aRow, aCol] = ind2sub(size(chart(:,:,1)),aIndex)

maxThrottle is a scalar that limits the the motor input, which is the sum of the absolute value of the speed change in both the north-south and east-west directions.

thrustRow and thrustCol are vectors that define your motor input in the north-south and east-west directions, respectively. These variables have one row for each turn. There is an absolute limit to the number of turns. After 1000 turns, play will be terminated, but you will still be charged for your entire requested input.

Results

For each chart, the following score will be calculated:

result = (finalRow - aRow)^2 + (finalCol - aCol)^2 + ...
  (closestRow - bRow)^2 + (closestCol - bCol)^2 + ...
    sum(abs(thrustRow)) + sum(abs(thrustCol))

This formula results in the lowest (lower is better) score when your ship reaches point A after successfully passing point B, all the while using the least amount of fuel (discretionary input from the motor). The variables closestRow and closestCol come from the point in your journey that is closest to Faraway Island at point B. You may have more than one point in your journey that are equidistant from point B; this doesn't matter.

Note that you will always be charged for all of your thrust inputs, including when your boat is stopped early because it goes off the chart.

This result will be used as part of the overall score as described in greater detail below.

An Example

Let's look at an extended example based on the map shown above. Assume that throttleMax is 8.

Let's say we want to sail south (down, or increasing row index) to catch the wind that will push us to the east (right, or increasing column index). Our first motor input might then be a change in row velocity of one. Later on, we'll need to stop our southward motion and then our eastward motion with more motor inputs. A tabular version of the whole sequence looks like this:

table.png

Ri = initial row, Ci = initial column, vRi = initial row velocity, vCi = initial column velocity, ΔvRw = change in row velocity due to wind, ΔvCw = change in column velocity due to wind, ΔvRm = change in row velocity due to motor, ΔvCm = change in column velocity due to motor, vRf = final row velocity, vCf = final column velocity, Rf = final row, Cf = final column.

In the table, the column labeled ΔvRm is the same as the variable thrustRow, and the column labeled ΔvCm is the same as the variable thrustCol.

The picture below shows the progress of the boat by the end of turn 3 (row 4, column 2).

map_turn3.png

By the end of turn 8, the boat has passed point B and returned home. Let's look at what the result would be in this situation.

result = (finalRow - aRow)^2 + (finalCol - aCol)^2 + ...
  (closestRow - bRow)^2 + (closestCol - bCol)^2 + ...
    sum(abs(thrustRow)) + sum(abs(thrustCol))

so

 result = (1 - 1)^2 + (1 - 1)^2 + ...
   (5 - 5)^2 + (5 - 5)^2  + ...
     (1 + 1 + 1 + 2) + (2) = 7

The result for this particular voyage is thus seven.

But there are plenty of other solutions. If you just want to reach your destination as quickly as possible, there's nothing stopping you from completing the trip in three turns.

table2.png

The distance errors are still zero, but you had to use a lot of fuel.

 result = (1 - 1)^2 + (1 - 1)^2 + ...
   (5 - 5)^2 + (5 - 5)^2  + ...
     (4 + 4 + 4) + (4 + 4 + 4) = 24

Not moving at all is also an option. If you returned a empty matrices for thrustRow and thrustCol (perfectly legal), what would the score be?

 result = (1 - 1)^2 + (1 - 1)^2 + ...
   (0 - 5)^2 + (0 - 5)^2  + ...
     (0) + (0) = 50

Scoring

The overall score for your entry is a combination of several factors. The first two in this list are the most important. The other two have a milder effect.
  1. Your average result across all the problems
  2. How fast your code runs
  3. The cyclomatic complexity of your code (more information below)
  4. The node count of your code (more information below)
Since each of these is to be minimized, the lowest overall score at the end of the contest wins.

Cyclomatic Complexity

Cyclomatic complexity, also known as McCabe complexity, is a measure of the number of independent paths through a program's source code. Typically, as this number gets higher, it becomes more difficult to understand what's happening in a program. This makes it harder to test, modify, and refactor.

Since a file can contain multiple functions, the complexity for any given file is defined as the MAXIMUM complexity of any functions contained in it. A good practice is to keep the complexity for each function below 10, so for this contest your overall score will increase according to the complexity in excess of 10. So there is no complexity penalty for submissions in which all functions have a complexity of 10 or less.

You can measure the cyclomatic (or McCabe) complexity of any function in MATLAB using the "cyc" switch for mlint. Try this, for example:

>> mlint -cyc magic.m

Node Count

This is a rough measure of how long your code is, but it will not penalize you for comments and variable name length.

t = mtree(filename,'-file');
length(t.nodesize)

Time and Size Limits

Your entry will time out and be disqualified if it takes more than 180 seconds (three minutes). To keep the queue moving smoothly, you are limited to submitting no more than five files every 15 minutes, for an average of three minutes per file. If we find you are creating multiple accounts in order to get around this limitation, we may disqualify all your entries.

The code is limited in size by the database architecture. The column in our MySQL database that stores the M-code is of type text, which is limited of 65535 characters. Submissions longer than this limit will fail.

Developing Your Entry

The files you need to get started on the contest are included in a ZIP-file available on the MATLAB Central File Exchange. If you download and uncompress this ZIP-file, you will have all the files you need to get started. You will be writing the file solver.m using the signature described in the Syntax section above. To test this function with the test suite in the ZIP-file, use runcontest.m.

>> runcontest

About the Contest

The contest is divided into three segments. Most of the week will run as usual, with free sharing of code, but the first two days of the contest will hide some of the information about each entry.

Starting and ending times are based on noon in Natick, Massachusetts, but we the web pages will show all times in Coordinated Universal Time (UTC).

  • Darkness (Wed. 17:00 UTC to Thurs. 17:00 UTC). During the first day of the contest, you can't see the code or scores for any of the entries.
  • Twilight (Thurs. 17:00 UTC to Fri. 17:00 UTC). During the second day of the contest, you can see scores but no code.
  • Daylight (Fri. 17:00 UTC to Wed. 17:00 UTC). For the remainder of the contest (with the exception of Late-Stage Twilight) you can see scores and code for all entries.

Collaboration and Editing Existing Entries

Once an entry has been submitted, it cannot be changed. However, any entry can be viewed, edited, and resubmitted as a new entry. You are free to view and copy any entry in the queue. If your modification of an existing entry improves its score, then you are the "author" for the purpose of determining the winners of this contest. We encourage you to examine and optimize existing entries.

We also encourage you to discuss your solutions and strategies with others. You can do this by posting to the thread that we've started from our newsreader.

Fine Print

The allowable functions are those contained in the basic MATLAB package available in $MATLAB/toolbox/matlab, where $MATLAB is the root MATLAB directory. Functions from other toolboxes will not be available. Entries will be tested against the latest version of MATLAB.

The following are prohibited:
  • MEX-files
  • Java commands or object creation
  • eval, feval, inline, function handles, etc.
  • Shell escape such as !, dos, unix
  • Handle Graphics commands
  • ActiveX commands
  • File I/O commands
  • Debugging commands
  • Printing commands
  • Simulink commands
  • Benchmark commands such as tic, toc, flops, clock, pause
  • error, clear, persistent

Hacking

Entries that compromise the contest machinery are not allowed. Out of consideration for everyone participating in the contest, we ask that you not abuse the system.

Extraction of puzzles in the test suite by manipulating the score, runtime, or error conditions is also forbidden. Tuning the entry to the contest test suite via multiple entries is permitted, but we ask that you not overwhelm the queue.

FAQ

Check our FAQ for answers to frequently asked questions about the contest.

About named visibility periods

Contests are divided into segments where some or all of the scores and code may be hidden for some users. Here are the segments for this contest:

  • Darkness - You can't see the code or scores for any of the entries.
  • Twilight - You can see scores but no code.
  • Daylight - You can see scores and code for all entries.
  • Finish - Contest end time.