# Gerrymandering

#### Starts: 4 Dec, 12:00 pm UTC

##### (Ends 11 Dec, 12:00 pm UTC) ### 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```

### 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.

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