Gerrymandering

Starts: 4 Dec, 12:00 pm UTC

(Ends 11 Dec, 12:00 pm UTC)

You are the elections coordinator for Rectanglia, a region divided by a bitter political dispute regarding the usage of the Oxford Comma. Polling numbers tell us that Faction A voters (Comma Forever) have the distribution a over the countryside and Faction B voters (Oxit) have the distribution b.

Your job is to divide Rectanglia into n voting districts in which the total voting population is as close to equal as possible. So if there are 1000 citizens and 4 districts, each district should contain as close to 250 as possible. And since there have been complaints that the current voting districts favor one side or the other, you should minimize the disparity between factions. In general, it's impossible to meet both of these constraints, so you'll have to do the best you can.

An Example

Rectanglia is a rectangular region of size nRows by nCols. As an example, consider this 3-by-4 rectangle. Here is a map of all the voters for Faction A.

#

If we sum them up by matrix element, we get this.

#

So a is 

a = [ ...
      18    3     8     21
      9     16    0     18
      0     3     24    10];

Similarly, can map Faction B voters like so.

#

Thus b is 

  b = [ ...
      16     4     7    13
      26    12    11    16 
      4     14     7     0];

In this case, both a and b contain a total of 130 voters, for a grand total of 260 voters (a and b will not always be equal). Suppose you are told to divide this region into two districts, and you decide on this one. 

r = [ ...
      1     2     2     2
      1     1     2     2
      1     1     2     2 ];

#

The 1s define one district, and the 2s define the other.

The Syntax

You must write a function that has this signature. 

    function r = solver(a,b,n)
            % Define r here...
            r = 0;
    end

Test suite

To help with developing your solution, you can download a test suite here.

Scoring

Let's calculate the score for this example. For the answer to be legal, it must contain exactly n districts defined by the integers 1 through n. All elements for any given district must be contiguous in the 4-connected sense. That is, two squares in the same region must be adjacent on north, south, east, or west. A diagonal connection is not sufficient.

Here is the population of District 1. 

  district1Pop = sum(a(r==1) + b(r==1))

district1Pop = 118


And District 2. 

  district2Pop = sum(a(r==2) + b(r==2))

district2Pop = 142


Ideally each district should have an equal number of people: (total population)/n, or 130. Since it doesn't, we apply the penalty of the absolute value of the difference between each district's population and its ideal size. 

  n=2;
  totalPop = sum([a(:); b(:)])

totalPop = 260

idealDistrictPop = totalPop/n

idealDistrictPop = 130

penalty1 = abs(district1Pop - idealDistrictPop) + abs(district2Pop - idealDistrictPop)

penalty1 = 24


And overall we should minimize the disparity between a and b voters.

To do this we minimize the worst district's disparity. 


  district1Disparity = abs(sum(a(r==1)) - sum(b(r==1)))

district1Disparity = 26 

  district2Disparity = abs(sum(a(r==2)) - sum(b(r==2)))

district2Disparity = 26 

  penalty2 = max([district1Disparity district2Disparity])

penalty2 = 26 

  totalPenalty = penalty1 * penalty2

totalPenalty = 624


A Better Solution

Now suppose we add one grid element from the 2 side to the 1 side as shown here.

#

r = [ ...
      1     2     2     2
      1     1     1     2
      1     1     2     2 ];

p1 = [ ...
       abs(sum([a(r==1); b(r==1)]) - idealDistrictPop)
       abs(sum([a(r==2); b(r==2)]) - idealDistrictPop)]

p1 = 1

1 

  penalty1 = sum(p1)

penalty1 = 2

The total population error is now much lower. In fact, it's nearly ideal. 

p = [ ...
      abs(sum(a(r==1)) - sum(b(r==1)))
      abs(sum(a(r==2)) - sum(b(r==2))) ]

p2 = 37

37 

  penalty2 = max(p2)

penalty2 = 37


The a vs. b disparity is higher, but this is more than compensated for by the first factor. The overall penalty has decreased. 

  totalPenalty = penalty1 * penalty2

totalPenalty = 74

Scoring

The overall score for your entry is a combination of two things:

  • Your average score across all the game boards (result)
  • How fast your code runs (runtime)

These three factors are passed to our scoring algorithm to produce a final score, according to the equation:

score = k1*result *(1 + k2*ek3 * runtime)

Both of these are to be minimized and the lowest overall score at the end of the contest wins. We don't publish the values k1-k3, but they aren't hard to figure out.

About the Contest

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.

Starting and ending times are based on noon in St Andrews, UK, but the web pages will show all times in Coordinated Universal Time (UTC).

Prizes

We'll be offering cash prizes in the form of Amazon vouchers to the best players:

  • £60 Amazon voucher for the grand prize winner
  • £30 Amazon voucher daily at 12 p.m. for the one player who managed to take the lead from someone else most times.

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

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

Hacking

Your entry will time out and be disqualified if it takes more than 50 seconds. You can submit as many entries as you like, but entries that compromise the contest machinery are not allowed. Out of consideration for everyone participating in the contest, we ask that you not abuse the system.

Extraction of puzzles in the test suite by manipulating the score, runtime, or error conditions is also forbidden. Tuning the entry to the contest test suite via multiple entries is permitted, but we ask that you not overwhelm the queue.

We'll be monitoring the queue - if we find signs of malicious behaviour we'll be issuing warnings, which could lead to temporary or permanent bans.