Starts: 4 Dec, 12:00 pm UTC
(Ends 11 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.
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.
You must write a function that has this signature.
function r = solver(a,b,n) % Define r here... r = 0; end
To help with developing your solution, you can download a test suite here.
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
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
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
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).
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.
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:
- 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
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.