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.
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:
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 = 94But 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 = 92Since a lower cost is better, we've improved our overall score by 2.
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
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.
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)
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.
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.
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:
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.
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: