The Problem

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

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

How it works

• 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

  [row column command]

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 ]

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 ]

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

 >> sum(a4(:)) 
   ans = 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 main routine is solver.m.

 moves = solver(board, nMoves)

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

About the Contest

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

Collaboration and Editing 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 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