Gerrymandering - Rules

Gerrymandering is the process of carving up an electoral district into strange shapes in order to derive a political advantage. The name comes from a cross between the name Gerry (from the early Massachusetts governor Elbridge Gerry) and the elongated shape of a salamander.

The Problem

For the eighth MATLAB programming contest, you are given the task of preparing for an upcoming election in the state of Rectanglia. As the director of redistricting, your job is to divide the state into N districts of equal population. Therefore, given a matrix A in which each element corresponds to the population in a given square mile, return a matrix B that indicates which voting district each square mile belongs in.

For example, suppose, given the following census data for Rectanglia in matrix A, you are told to divide the state into N = 3 districts of equal population.

So 3 people live in square (1,1) and 28 people live in square (3,2). A total of 120 people live in the entire state (it's a small state). Our goal, therefore, is to make three separate districts, each of which is connected, each with a population of 120/3, or 40 people. Voting districts must be contiguous, or connected in the four-neighbor sense (no diagonal connections). Thus, district 1 could not consist solely of square (1,1) and square (2,2).

Here's one way to divide the state.

It's easy to see that this solution, while not unique, can't be improved. We have successfully made sure that each district has exactly 40 people. We would label our districts using the matrix B as shown below.

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 considering the deviation of your solution from the perfect population in each district. If a district's population is given by pop_n, and the total population is pop_total, and the number of districts to be assigned is N, then the result is computed by

This result corresponds to the number of people that must be redistributed in order to even out the district population. A result of zero is the best you can do, since no one needs to move (pop_n is equal to pop_total/N for all districts). The example shown above yields a perfect result of zero.

Suppose instead you partitioned matrix A like so.

so the B matrix looks like this.

In this case, pop₁ is 3 + 0 + 0 + 0 + 2 + 12 + 10 + 2, or 29. pop₂ is 12 + 11 + 28, or 51, and pop₃ is still 40. The result is calculated as follows.

result = 1/(2*120) * ( abs(40 - 29) + abs(40 - 51) + abs(40 - 40) )

or

result = (11 + 11)/240 = 11/120

That is, if we could magically move 11 people from district 2 to district 1, the result would be perfect. And 11, expressed as a ratio of the total population, is 11/120, or 0.0917.

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.

Developing Your Entry

The files you need to get started on the contest are included in a ZIP-file available at the MATLAB Central 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.

function b = solver(a,n)
b = n*ones(size(a));
b(1:n) = 1:n;

Keep in mind that this function must have the right signature: two input arguments, one output argument. Variable names are unimportant.

 function b = solver(a,n)

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 6.5.1 (R13sp1).

The following are prohibited:

MEX-files
Java commands or object creation
eval, feval, 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

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