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.
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.
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 popn
, and the total population is poptotal
, 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 (popn
is equal to poptotal
/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, pop1
is 3 + 0 + 0 + 0 + 2 + 12 + 10 + 2, or 29. pop2
is 12 + 11 + 28, or 51, and pop3
is still 40. The result is calculated as follows.
result = 1/(2*120) * ( abs(40 - 29) + abs(40 - 51) + abs(40 - 40) )
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 k1
, and k3
, 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
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.
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:
Java commands or object creation
eval, feval, etc.
Shell escape such as !, dos, unix
Handle Graphics commands
File I/O commands
Benchmark commands such as tic, toc, flops, clock, pause
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.