Winner the cyclist (typ2)

Darkness 2006-04-05 09:00:00 UTC
 
Twilight 2006-04-06 09:00:00 UTC
 
Daylight 2006-04-07 09:00:00 UTC
 
Finish 2006-04-12 09:00:00 UTC

Blockbuster - Rules

Arrow_down  Download Sample Code

Welcome to Blockbuster, the 13th MATLAB Online Programming Contest.

The Problem

In this contest, you are given a grid of numbers which you can imagine corresponds to a box filled with colored blocks. Your goal is to empty the box.

You remove a block by popping it. When a block pops, it vanishes and all blocks above it fall down one space as though pulled down by gravity. Furthermore, all similarly colored contiguous blocks also disappear. In fact, in order to pop a block, it must have at least one similar neighbor. Isolated blocks cannot be popped.

In order to maximize the effectiveness of your block removal, you can perform block swaps. Pick a pair of adjacent blocks (adjacent is defined vertical and horizontal only, no diagonal swaps) and exchange their positions. You may not swap a block with empty space.

Example

Here's an example of what a sequence of events might look like. Starting with the board on the left, we will first swap two blocks at the bottom and then remove four contiguous blocks.

As an exercise, what is the minimum number of pops required to clear this board?

How it works

Here are some of the specifics about the rules.
  • You have a limited number of moves.
  • Each move consists of either a swap or a pop.
  • You can only pop a contiguous set of two or more similar blocks.
  • Contiguous blocks and block swapping are both defined in the north-south-east-west sense. So diagonally situated blocks are not considered contiguous.
  • Your score is the sum of all remaining blocks. Thus you're better off removing high-value blocks, all other considerations being equal.
  • You may not perform a swap that involves a space (a zero)

The API

You define your move with a three element vector.
  [row column command]
A command code of zero means pop the block in the specified row and column. A command code of 1, 2, 3, or 4 indicates a swap with the block to the north, east, south, or west as shown below.

To command a swap of the leftmost column in the matrix below (thereby changing matrix a1 into matrix a2), use the vector move as shown.

 a1 = [  9 23  2 ]
      [ 12 12 15 ]
 
 move = [1 1 3]
  
 a2 = [ 12 23  2 ]
      [  9 12 15 ]
Note that the move vector [2 1 1] would have exactly the same result.

To command a removal of block (2,2) in the matrix below (thereby changing matrix a3 into matrix a4), use the vector move.

 a3 = [ 23 12 23 ]
      [  9 23 23 ]
 
 move = [2 2 0]
  
 a4 = [ 23  0  0 ]
      [  9 12  0 ]
In this case the move vectors [1 3 0] and [2 3 0] would have done the same thing, since they all touch the same contiguous block of 23s.

Popping empty space and swapping with empty space are considered no-ops by the contest code. Your code will not error out, but no action is performed. Similarly, attempting to pop an isolated block is an errorless no-op.

Scoring

The score is simply the sum of all remaining numbers in the matrix after you have taken all your moves. If the matrix a4 shown above is your ultimate board, then
 >> sum(a4(:)) 
   ans = 44
your final score would be 44.

The overall score for your entry is a combination of how well your algorithm does and how fast it runs on a multi-problem test suite. How well your algorithm does (the "result") depends on how low your final score is.

The average result for the entire test suite, along with the associated runtime of your entry, gets passed to our scoring algorithm before returning a final score, according to the equation

We don't publish the values k1, k2, and k3, but they aren't hard to figure out. Your entry will time out and be disqualified if it takes more than 180 seconds (three minutes).

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.

The main routine is solver.m.

 moves = solver(board, nMoves)
where board is the matrix representing the blocks in your initial game configuration, and nMoves is the number of moves you are allowed. The return matrix moves can be no longer than nMoves rows.

Keep in mind that this function must have the right signature: two input arguments, one output argument. Variable names are unimportant. To test this function with the test suite in the ZIP-file, run runcontest.m.

 >> runcontest

Size limitations

Some of you have asked about the limit to code size. 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.

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. (Wed. at 9 AM to Thurs. at noon) During the first day of the contest, you can't see the code or scores for any of the entries.
  • Twilight. (Thurs. at noon to Fri. at noon) During the second day of the contest, you can see scores but no code.
  • Daylight. (Fri. at noon to Wed. at 5 PM) For the remainder of the contest you can see scores and code for all entries.
All times are Eastern Daylight Time, US.

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.

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 MATLAB R2006a.

The following are prohibited:

  • MEX-files
  • Java commands or object creation
  • eval, feval, assignin, etc.
  • inline, function handles, anonymous functions, etc.
  • computer, ispc, which, exit, more, edit, inmem, 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, lasterr, etc.
  • persistent

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.