Darkness 2003-11-06 10:00:00 UTC
 
Twilight 2003-11-07 10:00:00 UTC
 
Daylight 2003-11-08 10:00:00 UTC
 
Finish 2003-11-13 10:00:00 UTC

MATLAB Golf: Pathfinder - Rules

Introduction

The objective in the game of golf is to reach the hole with the fewest strokes. In MATLAB golf, the objective is to go from one variable (the tee) to another (the hole) with the fewest keystrokes.

Example: How many positive elements in vector a?

One approach (score = 19):
b=length(find(a>0))
A better approach (score = 10):
b=sum(a>0)

The winner is the contestant who solves the problem with the fewest characters.

Scoring

An entry's score is determined by counting the total number of characters. The shortest entry that passes the test suite wins. If two entries use the same number of characters, the first one submitted is the winner. There are three important exceptions to the character-counting rule. You are not penalized for using spaces, newlines, or semicolons (this corresponds to ASCII 10, 13, 32, and 59). Because of this, we encourage you to make liberal use of them in order to keep your code as readable as possible.

Notice that the following pieces of code both do the same thing and have the same score. Please use the second approach.

 
b=ones(a);b(:)=4;if numel(b)>10 c=10;else c=0;end
 
b = ones(a);
b(:) = 4;
if numel(b) > 10
    c = 10;
else
    c = 0;
end

Ranking is "king of the hill" style. In order to move into first place, your entry must be shorter than the current leader. If it is, your entry takes over first place. The entry that was bumped out of first place moves into second place, the entry that was in second place moves into third, and so on.

Even if your entry is longer than the current leader, we encourage you to submit it if your approach is novel. The diversity adds to the fun, and it may provide inspiration to someone else who can then make further improvements. In addition, we reserve the right to give out extra prizes for originality when the contest has closed, so your quirky but slightly longer entry may bring you fame.

Warning! MATLAB Golf can lead to obfuscated code and may cause headaches and dizziness. Conscientious coders may want to avoid staring at contest code for prolonged periods of time. The authors of this contest make no claims about the merits of potentially dangerous coding tricks revealed herein.

The test suites represent the final word: if it passes the test suite, then it's a legal entry, even if a more comprehensive test suite might plausibly have failed the same entry.

Keep in mind that MATLAB Golf is a game.

Execution Time

There is no penalty for execution time, but an entry can't take more than a couple minutes to run through our test suite. This shouldn't be an issue for the complexity of the problems in this contest.

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 modify any entries in the queue. The contest server maintains a history for each modified entry. 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 comp.soft-sys.matlab thread that we've started from our newsreader (see the link for "Message board" on the right).

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 MATLAB version 6.5 (R13).

The following are prohibited:

    MEX-files
    Java commands or object creation
    eval, feval, 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, and flops

Challenge: Pathfinder

Suppose you have a network of connected points on a plane. It may not be fully connected, but it is possible to get from one point to any other point. If you found the shortest route from a starting point to every other point, which of these routes is the longest?

More formally, given the adjacency matrix a and the coordinates matrix b, find the path from the first point in b (given by the first row in b) to the most distant point from b as traveled through the minimal network distance.

Coordinates in b are provided in the form [x1 y1; x2 y2; ...]. Travel is permitted only between connected points as indicated by ones in the adjacency matrix a. Return your answer c in the form of a vector of indices that represent the waypoints from start to finish. c(1) will always be one.

So when

 a = [ 1     1     0
       1     1     1
       0     1     1 ]

and

 b = [ 0     0
       1     0
       1     1 ]

the most distant point from point 1 (x1,y1) is point 3 (x3,y3), a total distance of 2 away. Since point 1 is not directly connected to point 3, the trip must include point 2. Return

c  = [ 1 2 3 ]

If a had been the fully connected matrix ones(3), then the answer would have been

c = [ 1 3 ]

Since there would no longer be a need to detour through point 2.

A slightly more complex problem appears below.

a = [ 1     0     1     0     0     0
      0     1     1     1     0     0
      1     1     1     1     0     0
      0     1     1     1     1     1
      0     0     0     1     1     0
      0     0     0     1     0     1 ]
b = [ 0     0
      1     2
      1     1
      2     2
      3     0
      3     3 ]

Even if you take the shortest path from point 1 to point 5, it ends up being harder to reach than any other point in the network. What is the shortest path to point 5?

c = [ 1 3 4 5 ]

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.