Darkness 2011-11-02 12:00:00 UTC
 
Twilight 2011-11-03 12:00:00 UTC
 
Daylight 2011-11-04 12:00:00 UTC
 
Finish 2011-11-09 12:00:00 UTC

Vines - Rules

Arrow_down  Download Sample Code

The Vines Contest

Japanese Rules / Chinese Rules

This contest is inspired by the popular 15-Puzzle.

The Problem

In the so-called 15-puzzle, you start with a 4-by-4 grid. There are fifteen movable tiles labeled 1 through 15. The square corresponding to tile 16 is empty. This empty square can be exploited to shift other tiles around until the desired pattern is established.

In our version of the game, the grid is bigger and the goal is more abstract.

The Details

Given a grid of numbers, you want to create the highest value path, which we'll call a "vine". A vine is a monotonically increasing series (successive equal values are permitted) of 4-connected squares. Put another way, it is a non self-crossing tour you can describe by advancing one square at a time in either the up, down, left, or right directions. The value of a vine is just the sum of all its numbers. An example should make this more clear. Here is a 4-by-4 puzzle grid. Right away you see two differences from the 15-puzzle: the numbers are not limited to 1 through 15 (although they are integers), and there's no empty square.

Remember that the vine's path must be monotonically increasing. Here's one potential vine for this grid: [5 8 14 15 20 50], for a total value of 112. Another possibility is [5 8 9 15 20 50], but then the value would only be 107.

Vine Length

You are welcome to make the vine as long as you like, but keep in mind that you are being rewarded for the value of the vine (the sum of its elements) and not the length of the vine.

To specify a vine, use the absolute index of each element in order. In this case, the first element of the vine is the [1,1] element, which has the absolute index of 1. To convert from [row,column] notation to absolute index notation, you can use MATLAB's sub2ind function like so

 ind = ind2sub(size(board),row,col)

The vine in the picture has this absolute index representation: [1 2 3 7 11 12]. Note that board(ind) returns the vector of values that make up the vine.

Sliding Tiles

Like the 15-puzzle, you can move tiles around. For this contest, you don't have to worry about whether or not the square you're moving to is empty. If you move one tile on top of another pre-existing tile, the stationary tile is removed.

Here's what happens if you shift the tiles 20 and 44 so as to make the vine [5 8 14 20 44 50]. In step 1 below we slide the 20 tile into the spot occupied by the 15 tile. The 15 tile is now completely removed from the board. This leaves behind a new empty spot which we then fill with the 44 tile in step 2.

This leaves us with the following board, and we can now form the vine [5 8 14 20 44 50].

Move Budget

We only made two moves to create this vine. It's clear that some other moves might also be helpful, such as sliding the 9 on top of the 8 to form the slightly better vine [5 9 14 20 44 50]. But there is a move budget, and in this case the budget is 2.

Other Considerations

  1. Empty squares are considered to contain zeros.
  2. The vine sequence, while monotonically increasing, can contain successive equal values. For example, [1 3 4 4 7] is a valid vine. So is [4 4 4 4].
  3. You are not required to move any squares.

Syntax

You will write the function solver.m which will be called by the test harness. It must have this signature:

[moves, vine] = solver(board, limit)

  • board is an n-by-m array of positive integers.
  • limit is the total budget of moves you can make.
  • moves is an n-by-2 array of move orders. Each row gives a move order. The first column contains the absolute index of the tile to be moved. The second column gives the index of the destination.
  • Return the empty set [] for moves if you don't want to move any tiles.
  • Illegal moves will be ignored.
  • vine is a vector of absolute indices into board that specifies the path of numbers.

Results

For each puzzle, the following score will be calculated. Note that, since the board is transformed by the moves, we can think of both the original board and the modified board.

result = sum(board(:)) - sum(modified_board(vine))

The result is to be minimized. Also, this constraint must not be violated:

size(moves,1) <= limit 

A Worked Example

For complete clarity, in actual practice the above problem would look like this.

>> board
 
     5     6    18     6
     8     9    44    12
    14    15    20    16
     7    11    50     3
 
>> limit
 
    2
 
>> [moves, vine] = solver(board, limit)
 
moves =
 
    11     7
    10    11
 
vine = 
 
     1     2     3     7    11    12
 
>> modified_board 
 
     5     6    18     6
     8     9     0     1
    14    20    44    16
     7    11    50     3
 
>> modified_board(vine)
 
     5     8    14    20    44    50
 
>> sum(board(:))
 
   244
 
>> sum(modified_board(vine))
 
   141
 
>> result = sum(board(:)) - sum(modified_board(vine))
 
   103
 

Scoring

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 checkcode. Try this, for example:

>> checkcode -cyc magic.m

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(filename,'-file');
length(t.nodesize)

Time and Size Limits

Your entry will time out and be disqualified if it takes more than 180 seconds (three minutes). To keep the queue moving smoothly, you are limited to submitting no more than five files every 15 minutes, for an average of three minutes per file. If we find you are creating multiple accounts in order to get around this limitation, we may disqualify all your entries.

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 in a ZIP-file available on the MATLAB Central File Exchange. If you download and uncompress this ZIP-file, you will have all the files you need to get started. You will be writing the file solver.m using the signature described in the Syntax section above. To test this function with the test suite in the ZIP-file, use runcontest.m.

>> runcontest

About the Contest

The contest is divided into three segments. Most of the week will run as usual, with free sharing of code, but the first two days of the contest will hide some of the information about each entry.

  • Darkness. During the first day of the contest, you can't see the code or scores for any of the entries.
  • Twilight. During the second day of the contest, you can see scores but no code.
  • Daylight. For the remainder of the contest you can see scores and code for all entries.

Starting and ending times are based on noon in Natick, Massachusetts, but the web pages will show all times in Coordinated Universal Time (UTC). For the exact timing of these three phases, refer to the box at the top right corner of the page.

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 in 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 not allowed. 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. Tuning the entry to the contest test suite via multiple entries is permitted, 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.