Darkness 2009-11-04 12:00:00 UTC
 
Twilight 2009-11-05 12:00:00 UTC
 
Daylight 2009-11-06 12:00:00 UTC
 
Finish 2009-11-11 12:00:00 UTC

Color Bridge - Rules

Arrow_down  Download Sample Code

Color Bridge is the 20th MATLAB Online Programming Contest.

This contest is based on the color flooding problem as popularized in the online game Flood-It, although as usual our version is somewhat different. In this version, you don't need to paint the whole space a single color. Instead, your job is to make a single-color "bridge" between two points in the matrix.

Specifically, you need to create a four-connected single-color region that reaches from the upper left (1,1) element of a given m-by-n matrix to the target element located somewhere else in the matrix. By "four-connected" we mean that only blocks that are adjacent horizontally or vertically (north, south, east, and west) are considered connected.

Example

Imagine starting with the matrix A shown below. Let's assume that the target is in the lower right corner.

Every time you change the color of the top left element A(1,1), it grows the region of connected color (the "bridge"). The sequence below shows a series of color changes that eventually grows the bridge to include the bottom right element A(4,4). The colors shifted through this sequence:

  1. Initial position
  2. 5 (blue)
  3. 4 (green)
  4. 3 (yellow)
  5. 6 (purple)
At this point the four-connected purple bridge stretches from start to finish and the puzzle is solved. Conveniently, each color is represented by an integer, and the solution vector is just the list of color changes: [5 4 3 6].

Scoring

Your code will be called with two input arguments and one output argument like so: 
 colors = solver(A, targetIndex)
The second argument, targetIndex, is an absolute index into the matrix. You can find the target row and column easily with the IND2SUB command like so. 
 [targetRow, targetColumn] = ind2sub(size(A),targetIndex)
The cost of the solution, which you want to minimize, is the sum of all the elements in the final matrix plus the sum of all the elements in the solution vector. In code, 
 score = sum(Afinal(:)) + sum(colors)
Suppose, as shown above, you start with this matrix. 
 A = [ 1     5     4     2
       2     1     4     3
       3     5     3     6
       5     5     5     6 ]
and the target element is (4,4). Your goal is to "paint" a bridge from A(1,1) to A(4,4) as cheaply as possible, which is to say, the lowest possible score as defined above. In the introductory example, we used the solution vector [5 4 3 6]. This is the Afinal matrix.

The final cost is given by 

 cost = sum(Afinal(:)) + sum(colors) = 76 + 18 = 94
But we can easily imagine a different solution sequence. Here is the bridge resulting from the sequence [5 1 5 6]. 

 cost = sum(Afinal(:)) + sum(colors) = 75 + 17 = 92
Since a lower cost is better, we've improved our overall score by 2.

Other Considerations

For scoring purposes, Afinal is frozen at the first moment at which the necessary color bridge has been completed. You can provide a color solution vector that is longer than necessary, but it will not change the appearance of Afinal.

Puzzles may include walls. A wall is a square with the value zero. Since you can only choose positive integers for your paint colors, walls constrain the space in which you operate.

If your solver does not return a solution, it will not fail, but you will be penalized. In the cost equation, Afinal's non walls will be entirely populated with the highest value element. In code, this would be 
 penaltyValue = max(Aoriginal(:));
 Afinal = Aoriginal;
 Afinal(Aoriginal ~= 0) = penaltyValue;
Thus returning the empty set is a legitimate answer. In the example given above, 
 Afinal = [ 6     6     6     6
            6     6     6     6
            6     6     6     6
            6     6     6     6 ]
and so 
 cost = sum(Afinal(:)) + sum(colors) = 96 + 0 = 96

If the color list returned by solver is longer than the number of elements in the matrix, it will be truncated like so. 

 if numel(colors) > numel(A)
   colors = colors(1:numel(A)); 
 end


Color values may be sequential, as in the examples above, but they may not be. Keep in mind that very high or very low numbers relative to the target value may influence your overall strategy. A problem might look like this (black squares correspond to zeros, or "wall" regions).

Overall Score

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

We have also included a getComplexity.m function with the contest distribution to make it easier to find the complexity for your entry.

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('your code');
length(t.nodesize)

Time and Size Limits

Your entry will time out and be disqualified if it takes more than 180 seconds (three minutes).

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 the files described below.

Syntax

The main routine is solver.m. The syntax is described above. Keep in mind that these functions must have the right signature. Variable names are unimportant. To test this function with the test suite in the ZIP-file, run runcontest.m. 
 >> runcontest

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 no longer allowed. We've all learned some interesting MATLAB tricks in the past by contestants figuring out how to pass information from one entry to the next, or finding clever ways to execute disallowed functions, but it's too hard for the few of us running the contest to keep ahead of the group intelligence. In short, 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. In the small scale, this has been an element of many past contests, but in the Blockbuster Contest, Alan Chalker turned this into a science. Tuning the entry to the contest test suite via tweak bombing or other techniques is still allowed, 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.