Moving Furniture - Rules

This is the ninth MATLAB Online Programming Contest.

The Problem

Consider a room that contains some furniture. You are unhappy with the location of the furniture and you want to spice things up a little by shifting it around. Suppose, for example, your room has four pieces of furniture in this position.

You think you'd be much happier if only you could move the furniture into this configuration.

Your job for this contest is to move from the first to the second configuration using as little effort as possible. The effort required to move any given piece of furniture is defined as the product of that piece's weight and the distance it moves through. Heavy things naturally require more effort to move.

Here are some considerations that simplify the problem somewhat.

• Every piece of furniture is exactly the same size: one unit square.
• You can only move one piece of furniture at a time.
• Every move is exactly one unit in one of four directions: north, east, south, or west.
• No two pieces of furniture can occupy the same square at the same time.
• Furniture cannot be moved outside the walls of the room.

A list of furniture and starting locations is provided in a matrix for each problem. Movements are indicated by the following move code.

NOTE: Several people have pointed out a confusing discrepancy between the move code as originally stated here and the move code as implemented in the code distributed for the contest. We did, in fact, make a mistake with respect to the move code and the correct version is shown below.

1. east (columnIndex = columnIndex + 1)
2. south (rowIndex = rowIndex + 1)
3. west (columnIndex = columnIndex -1)
4. north (rowIndex = rowIndex - 1)

Scoring

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 (which we call the "result") is determined by the total work required to move all pieces of furniture from the initial to the final configuration. The work required for one piece of furniture is given by multiplying its weight by the total distance it moves through.

Example

If we step through this using the example that appears in the illustration at the top of this page, we get the following problem setup.

move = solver(aInit, aFinal, wt)

aInit  = [ 4 0 0 3 ;
           0 0 0 0 ;
           1 2 0 0 ]

aFinal = [ 0 0 0 4 ;
           0 2 3 0 ;
           0 1 0 0 ]

wt = [  5
       10
       20
        1 ];

One solution is

move = [ 3 3
         3 2
         4 1
         4 1
         4 1
         2 4
         1 1]

In other words, shift block 3 first west then south, then move block 4 east three times, then move block 2 north one, and finally move block 1 east one. The order can be slightly different and return the same end result, but for instance, you must move block 2 out of the way before block 1 can be moved to its final spot.

The result is easily calculated. Since each move is unit distance, we need only sum up the weights corresponding to the moves like so.

result = sum(wt(move(:,1))) = 20 + 20 + 1 + 1 + 1 + 10 + 5 = 58

We can imagine a longer instruction list that would give the same final location but would result in a higher score.

move = [ 3 3
         3 2
         4 1
         4 1
         4 1
         2 4
         1 1
         1 3
         1 1]

In this case, block 1 takes two superfluous moves at the end. The score would be

result = 20 + 20 + 1 + 1 + 1 + 10 + 5 + 5 + 5 = 68

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 k₁, k₂, and k₃, but they aren't hard to figure out. Your entry will time out and be disqualified if it takes more than 150 seconds (two and a half minutes).

Developing Your Entry

The files you need to get started on the contest are included in a ZIP-file available on the File Exchange. If you download and uncompress this ZIP-file, you will have the files described below.

The routine that does the algorithmic work is solver.m.

move = solver(aInit, aFinal, wt)

Keep in mind that this function must have the right signature: three 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

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 modify any entries in the queue. The contest server maintains a history for each modified entry. 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 comp.soft-sys.matlab 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 MATLAB version 7 (R14).

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

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