Wiring - Rules

The Wiring Contest is the 17th MATLAB Online Programming Contest.

The Problem

This contest is inspired by the problem of wiring printed circuit boards. It was suggested to us by a contest participant, Edward Meyer. This is our first contest theme based on community input, and we hope it will be the first of many. We've already sent Edward a MATLAB baseball cap to thank him for the idea. Send us your ideas for future contests to contest@mathworks.com.

Here is the challenge. Given a board with numbered pins, your job is to connect each pin to all other pins with the same number. Thus in the diagram above, the pins labeled 11 should be connected to each other. Similarly, the pins labeled 8 and 3 should be connected to their respective partners. Every time you connect a group of pins, your score improves (is reduced by) the total value of the pins connected.

To connect these pins, imagine that you have a box filled with unit-length connector wires. You can use as many as you like, but each one also has an associated cost.

Step One

In the diagram below, we have connected the 8 pins successfully.

Five connectors were required to link these pins. At the same time, we reduced the total score by 8 + 8 or 16 points. The net value of this connection is 5 - (8 + 8), or -11. Since a lower score is better, that's moving us in the right direction.

Step Two

We still need to connect the 3 pins.

The total cost for this connection is 10. Notice that it's okay for the connecting wires to pass across one of the pins. The net value of this wire is 10 - (3 + 3 + 3), or 1. The fact that the result is positive indicates this isn't a wise move.

Step Three

Now we want to wire the 11 pins together. But there's a problem: there's no way to do this without crossing a wire that's already in place. What would happen if we just connected the pins directly like so?

This is a legal move, but it has a bad result on the score. By shorting the 3 circuit and the 11 circuit together, we lose the credit you gained by connecting them. So we would be paying for the connectors, but they wouldn't be doing us any good. A better idea is to use a "bridge". The bridge is indicated below by the red arrow.

Bridges are expensive: they cost 25 points each. In this diagram we've saved 22 points by connecting the two 11 pins, but we had to buy three connectors and a bridge, for a total cost of 28. The net score for this move is 6, making it a really bad move.

It's not hard to see that there's a much better way to connect up this particular board. This bad solution just served as an introductory example.

Scoring

Every time you connect pins together, you get to remove those points from your score. Your final score is the sum of all unconnected pins on the board plus the cost of all your connectors. Connects cost one point. Bridges cost 25. You want to minimize your score.

Details

• Connectors have length one, but you may use as many as you like.
• It may be impossible or unwise to connect all of the posts to their partners. What matters is the score, not how many pins you connect.
• If you cross-wire two different types of pins ("short out" the circuit) you will receive no credit for any of the pins thus connected.
• All pins have positive value.

Inputs and Outputs

Your code will be called with one input argument and one output argument like so:

W = solver(B)

The board B is a matrix. You return the wiring list, which is an n-by-4 matrix with as many rows as you have connectors. Each row has the following form

 [ r1 c1 r2 c2 ]

Each line segment is one unit in length. There is no directionality to the lines, so it doesn't matter which end comes first.

The example shown above would have the following B (for board) matrix. Note that dots are being used instead of zeros for greater clarity.

B = [  .  .  .  .  .  . ]
    [  .  .  8  .  3  . ]
    [  .  . 11  .  .  . ]
    [  .  3  .  .  .  8 ]
    [  .  .  .  3  .  . ]
    [  .  . 11  .  .  . ]

The segments for the connector between the 8 pins could be written like so.

w = [ 2 3 2 4 ]
    [ 2 4 3 4 ]
    [ 3 4 3 5 ]
    [ 3 5 4 5 ]
    [ 4 5 4 6 ]

Note that a great many legal and equivalent permutations of this instruction list exist. The order of the segments, for example, is unimportant.

To indicate a bridge, you need to lay down all the segments as above. Then in addition you enter a line like so at the point where the bridge is needed.

 [ r1 c1 r1 c1 ]

Bridges only support perpendicular crossovers. The segment between the two 11 pins could be written like this.

w = [ 3 3 4 3 ]
    [ 4 3 5 3 ]
    [ 5 3 6 3 ]
    [ 5 3 5 3 ]

Special Cases

If you connect two dissimilar pins, you receive no credit for those pins. In the diagram below, the two 4s are removed from the score, but the 3s and the 8 are not. Although the 3s are connected, they are also tied to the number 8 pin, thereby shorting out the circuit. The score for this board is 3 + 3 + 8 for the short-circuited pins and 1 + 1 + 1 for the connectors, for a total of 17.

    [  .  .  .  . ]
    [  3 --- 3  4 ] 
    [  |  .  .  | ] 
    [  8  .  .  4 ]

In the next diagram, there are five 3s. To receive full credit, they must all be connected. But in fact, there are two separate "islands". How is this scored? The answer is that we give you credit for the largest island only. The score for this board is 3 + 3 for the pins in the small island and 1 + 1 + 1 for the connectors, for a total of 9. The obvious lesson is that it's a waste of time and material to connect isolated islands of pins.

    [  .  .  .  .  . ]
    [  3 --- 3  .  3 ] 
    [  |  .  .  .  | ] 
    [  3  .  .  .  3 ]
    [  .  .  .  .  . ]

If you short-circuit any of the pins of a given number, you get no credit for any of those pins. So the board below would give no bonus.

    [  .  .  .  .  . ]
    [  3 --- 3  .  3 ] 
    [  |  .  .  .  | ] 
    [  3  .  5 --- 3 ]
    [  .  .  .  .  . ]

Scoring

The overall score for your entry is a combination of three things:

• Your average score across all the problems
• How fast your code runs
• The cyclomatic complexity of your code (more information below)
• The node count of your code (more information below)

Since all of these are to be minimized, the lowest overall score at the end of the contest wins.

Late-Stage Test Suite Swap

At noon on Monday, we will do a score-neutral swap of the test suite. This means we will halt the queue briefly and switch in a new test suite. For the purposes of score continuity, we will then add an offset factor to the score of the leader so that the score for that entry is the same using the old and new test suites. That offset factor will remain constant for the rest of the contest.

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. You can calculate this length using the MATLAB function MTREE, which parses the file. Note that if you are using a older version of MATLAB, you may not have access to MTREE, as it is relatively new Note also that it is still experimental and sparsely documented. Future versions may change.

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

The node count penalty is designed to have a secondary impact on the score. Its multiplying constant will be low. It has been added to the scoring function only to motivate the removal of stale code.

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 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 newsgroup 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.


Download Sample Code