Darkness 2012-10-31 16:00:00 UTC
 
Twilight 2012-11-01 16:00:00 UTC
 
Daylight 2012-11-02 16:01:00 UTC
 
Finish 2012-11-07 16:00:00 UTC

Knots Contest - Rules

Arrow_down  Download Sample Code

Rules in Chinese

(Creative Commons. Some rights reserved. Thomas Good)

This contest is inspired by the game Planarity. But it was also inspired by the problem of the Gordian Knot. The problem is this: Given a deranged hairball of a knot, can you untie it?

In more software-friendly terms, the problem can be restated as this: Given a list of points and their connectivity as supplied by an adjacency matrix, move them around so that the lines do not cross.

The Problem

You start with a network of connected nodes. Sometimes the edges between nodes intersect, as in the diagram below. We refer to these intersections as "knots."

You don't like knots. Every knot gives you a substantial penalty, so you want to make the knots go away. But you can't simply cut the connections with scissors. All you can do is move the nodes. Your job is to keep moving the nodes until there are as few crossings as possible (it may be impossible to remove all the knots). The image below has the same network topology as the image above, but one of the nodes has been moved to eliminate line crossings.

Now everything looks nice and tidy. But there's a complication. Beyond the knot penalty, you also have to pay to move nodes. So the goal is to minimize the overall cost: crossing penalty plus moving penalty.

Syntax

Here is the syntax you will use.

xyOut = solver(a, xyIn, wts)

You are given a set of n nodes in the form of an n-by-2 matrix, xyIn. Each row corresponds to the (x,y) coordinates of a single node. The matrix a is the adjacency matrix defining the connectivity between the various points. The graph is undirected, so the adjacency matrix is guaranteed to be symmetric. wts is a vector that corresponds to how hard it is to move a given node. You must return the updated coordinates of all the points in xyOut. Each row in xyOut corresponds to the same row in xyIn. If you want to show that the nth point doesn't move, then xyOut(n,:) = xyIn(n,:).

The most important consideration is minimizing the number of crossings (knots). We will indicate number of knots with the variable nKnots. So to a first approximation,

Score = nKnots

As a tie-breaker among entries that all have the minimum number of knots, you should try to move the nodes as little as possible. We'll track that using a modification to the score. This modification depends on the weight vector wts, the distance vector dist (i.e. the distance moved by each individual node), and the maximum distance between any two points, max_dist.

sum(dist .* wts) / (max_dist*sum(wts))

Thus the overall scoring algorithm is...

Score = nKnots +  sum(dist .* wts) / (max_dist*sum(wts))

Other Considerations

  • Points must always be at integer locations.
  • It may be impossible to make all the knots go away.
  • No two nodes can occupy the same location.
  • Any line whose endpoint lies directly on another line counts as a knot.

A worked example

Let's work through the example shown above. As mentioned, there are five nodes and two intersections, or knots. The nodes are numbered like so:

Here are the parameters for this problem.

 xyIn = [ 1 5;
          1 2;
          3 1;
          5 2;
          5 5]
 a = [ 0 1 1 0 0;
       1 0 0 1 0;
       1 0 0 0 1;
       0 1 0 0 1;
       0 0 1 1 0]
 wts = [1 4 2 1 2]

Incidentally, you can visualize this problem with the gplot command like so.

>> gplot(a,xyIn,'o-')

Let's go ahead and find two values that show up repeatedly in the calculations below. The sum of all weights and the maximum distance between any two nodes.

 sum(wts) = 1 + 4 + 2 + 1 + 2 = 10
 max_dist = distance from node 1 to node 4 = sqrt( (5-1)^2 + (2-5)^2 ) = sqrt( 16 + 9 ) = 5

We're going to look at the score for each of three different scenarios to see which turns up the best score. But first, consider that not moving any nodes is an acceptable answer. Since there was no motion, the dist vector is [0 0 0 0 0]. But there are 2 knots, so the score is 2.

 dist = [0 0 0 0 0]
 wts  = [1 4 2 1 2]
 scoreA = knots + sum(dist .* wts)/(max_dist*sum(wts)) = 2 + 0/(5*10) = 2

Scenario A.

In this case we're shifting node 3 straight up a distance of two. It would be legal, but pointless, to move node 3 up a distance of one, since a node resting on a line between two other nodes counts as two knots.

   
 dist = [0 0 2 0 0]
 wts  = [1 4 2 1 2]
 scoreA = knots + sum(dist .* wts)/(max_dist*sum(wts)) = 0 + 4/(5*10) = 0.08

Scenario B.

Suppose instead we move node 3 to the left 3 steps. This removes one of the knots, leaving one in place.

   
 dist = [0 0 3 0 0]
 wts  = [1 4 2 1 2]
 scoreB = knots + sum(dist .* wts)/(max_dist*sum(wts)) = 1 + 6/(5*10) = 1.12

Clearly a bad idea.

Scenario C.

Finally consider moving node 4 down two steps and to the left two steps as shown.

   
 dist = [0 0 0 sqrt(8) 0]
 wts  = [1 4 2 1 2]
 scoreC = knots + sum(dist .* wts)/(max_dist*sum(wts)) = 0 + sqrt(8)/(5*10) = 0.0566

This is the best result we've seen so far. Can you do better?

Entry Setup

To become a player in the contest, follow this setup:

  • Locate the contest-related zip file by visiting File Exchange. (See Resources.)
  • Download and uncompress this zip file.
  • Write the file solver.m using the signature described above Syntax.
  • Use runcontest.m to test this function with the test suite in the zip file.
  •    >> runcontest
    

Scoring

The overall score for your entry is a combination of several factors. Items 1 and 2 below are the most important factors. Items 3 and 4 have a milder effect.

  1. Your average result across all problems
  2. How fast your code runs
  3. Cyclomatic complexity of your code (below)
  4. Node count of your code (below)

Because the goal is to minimize each of these factors, 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 increases, understanding what's happening in a program becomes more difficult. This difficulty makes it harder to test, modify, and refactor.

Because a file can contain multiple functions, the complexity for any given file is defined as the maximum complexity of any functions contained within the file. A good practice is to keep the complexity for each function below 10. For the contest, your overall score increases according to complexity in excess of 10. No complexity penalty applies to 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 checkcode, for example:

>> checkcode -cyc magic.m

Node Count

Node count is a rough measure of the length of your code. Note that you are not penalized for comments and variable name length.

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

Time and Size Limitations

To keep the queue moving smoothly, we limit your code in the following ways:

  • Number of entries
    You may submit no more than 5 files every 15 minutes for an average of 3 minutes per file. If you create multiple accounts to work around this limit, we may disqualify all of your entries for the duration of the contest.

  • Run time
    If your entry requires more than 180 seconds (3 minutes) to run, it will time out and be disqualified.

  • Size
    If your submission exceeds 65535 characters, it will fail.

Entry Changes and Collaboration

After you submit an entry, you cannot change it. However, any player can view, edit, and resubmit an existing entry as a new entry. This rule means that you can view and copy any entry in the queue.

If you change an existing entry and improve its score, then you are considered the author of that entry when we determine contest winners. We encourage you to examine and optimize existing entries.

We also encourage you to discuss your solutions and strategies with others by posting to the contest thread on MATLAB Newsgroup. (See Resources.)

Helpful Hints

Allowable functions are those contained in the basic MATLAB package available in $MATLAB/toolbox/matlab, where $MATLAB is the MATLAB root directory. Functions from other toolboxes are not available. All entries are tested against the latest version of MATLAB. (See Resources.)

The following items are prohibited:

  • MEX-files
  • Java commands or object creation
  • eval, feval, inline, and function handles
  • Shell escapes such as !, dos, unix, and system
  • Handle Graphics commands
  • ActiveX commands
  • File I/O commands
  • Debugging commands
  • Printing commands
  • Simulink commands
  • Benchmark commands such as tic, toc, flops, clock, and pause
  • error, clear, and persistent functions

About Hacking

In consideration of all players, we ask that you do not abuse the system and follow these rules:

  • Entries compromising contest machinery are disallowed.
  • Extraction of puzzles in the test suite by manipulating the score, runtime, or error conditions is also disallowed.
  • While tuning the entry to the contest test suite using multiple entries is permitted, overwhelming the queue is discouraged.

Resources

Check out these helpful resources:

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 - During the first day of the contest, you cannot see code or scores for any entry.
  • Twilight - During the second day of the contest, you see scores but cannot see code.
  • Daylight - For the remainder of the contest, you see both scores and code for all entries.
  • Finish - Contest end time.