Subscribe to Macosxnerd101's Blog

Democrats, Republicans, and Even Programmers Love to Gerrymander

We just studied Gerrymandering, or drawing electoral boundaries to give an advantage to some party, in AP Government. As part of this, we had to Gerrymander a grid of D's and R's to favor either the Dems or the GOP. We also had to play an online "game" to Gerrymander a state. Personally, I found this process very irritating and cumbersome. Exactly the type of thing a computer should be doing! Yes- I just brought programming and corrupt political practices together. So over the weekend, I cranked out some code to handle the grid problem. Enjoy!

The input:
```D D R R R R R D R D
D D R R R R R R D D
D D R R R R R D D D
D D R R R R R D R R
R D R R R D R D R R
R D D D D D D D D R
R R D D D D D R D R
R R R R D R D D R D
R D R D D R D R R D
R R D R D D R R R R

```

What I did with the input was read each letter into a Vote class, which basically did two things. It served to mark the party affiliation, as well as whether or not it was part of a district.
```package gerrymandering;

public class Vote {

private boolean party;
private boolean inDistrict;

public Vote(boolean party){
this.party = party;
this.inDistrict = false;
}

public boolean isInDistrict(){return inDistrict;}
public void setInDistrict(boolean inDistrict){this.inDistrict = inDistrict;}
public boolean getParty(){return party;}
}

```

This problem also reminded me of the Knapsack problem, so I created a Knapsack class to model a single district. The Knapsack class also deals with the quota, or desired number of voters per district, and whether or not the solution is optimal. I used my StackMap snippet here to associate a point in the Grid with a party in the Knapsack. It got a little messy in toString() b/c I had to use two StackMaps to ensure the integrity of the instance variable. The TreeMap was used to order the output.
```package gerrymandering;

import java.util.*;
import java.awt.Point;

//true- Democrat
//false- Republican
public class Knapsack {

private int quota;
private int democrats, republicans;
private boolean party;

public Knapsack(boolean party){
this(10, party);
}

public Knapsack(int quota, boolean party){
this.quota = quota;
this.democrats = this.republicans = 0;
this.party = party;
}

public boolean add(int i, int j, boolean party){
return false;

if(party)
democrats++;
else republicans++;
return true;
}

public boolean pop(){
if(party)
democrats--;
else republicans--;
return party;
}
public boolean belowQuota(){return (democrats + republicans) < quota;}
public boolean full(){return votes.size() == quota;}

public boolean loss(){return false;}

public boolean isOptimal(){
return false;
if(party)
return democrats > republicans;
else
return republicans > democrats;
}

public String toString(){
String temp = "Is full/is optimal/count/D/R: " + full() + "/" + isOptimal() + "/ " + votes.size() +
"/" + this.democrats + "/" + this.republicans + ": ";
StackMap<Point, Boolean> tempMap = new StackMap<Point, Boolean>();
TreeMap<Point, Boolean> map2 = new TreeMap<Point, Boolean>(new Comparator<Point>(){
public int compare(Point one, Point two){
if(one.x == two.x)
return one.y - two.y;
return one.x - two.x;
}
});

}

while(tempMap.size() > 0){
}

for(Point p:map2.keySet())
temp += p + ", " + map2.get(p) + ";   ";
return temp;
}

}

```

Finally, putting it all together is the Gerrymander class. Essentially, this class takes the Vote objects as a 2D array. From there, it treats it as a Tree and builds the n Knapsacks/districts according to the quotas, also enforcing that the votes will be connected to prevent a broken apart district. The solution is recursive, treating the Grid as a Tree, and recursing. I use Threads simply due to the size of the problem (the permutations), and treat each point as the root of its own Tree (and each Thread).
```package gerrymandering;

import java.util.*;
import java.io.*;
public class Gerrymander {

private Vote[][] state;

public Gerrymander(Vote[][] state, int numDistricts, int quota, boolean party) throws FileNotFoundException{
this.state = state;

for(int i = 0; i < state.length; i++){
for(int j = 0; j < state[i].length; j++){
new MyThread(i, j, 0, numDistricts, quota, party).start();
}
}
}

private Knapsack[] district;

private int row, col, initial;
private PrintWriter write;

MyThread(int row, int col, int initial, int numDistricts, int quota, boolean party) throws FileNotFoundException{
district = new Knapsack[numDistricts];

this.row = row;
this.col = col;
this.initial = initial;

for(int i = 0; i < numDistricts; i++)
district[i] = new Knapsack(quota, party);

for(int i = 0; i < state.length; i++){
for(int j = 0; j < state[0].length; j++)
}

write = new PrintWriter(row + "" + col + ".txt");
}

public void run(){
distribute(row, col, initial);
write.close();
}

private void distribute(int row, int col, int knapsack){

if(row >= votes.length || row < 0)
return;
else if(col >= votes[row].length || col < 0)
return;

String temp = "";
for(int i = 0; i < votes.length; i++){
for(int j = 0; j < votes[i].length; j++)
temp += (votes[i][j].isInDistrict() ? "T " : "F ");
temp += "\n";
}

for(Knapsack k:district)
temp += k.toString() + "\n";
temp += "\n\n";
write.println(temp);

if(district[knapsack].full()){
knapsack++;
}

return;

}

if(row-1 >= 0){
distribute(row-1, col-1, knapsack);
distribute(row-1, col, knapsack);
distribute(row-1, col+1, knapsack);
}

distribute(row, col+1, knapsack);
distribute(row, col-1, knapsack);

distribute(row+1, col-1, knapsack);
distribute(row+1, col, knapsack);
distribute(row+1, col+1, knapsack);
}

district[knapsack].pop();

} //end distribute
}
}

```

The main() method:
```/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/

package gerrymandering;

/**
*
* @author hcps-levetm
*/

import java.util.*;
public class Main {

public static void main(String[] args) throws Exception{
Scanner scan = new Scanner(new java.io.File("log.txt"));

for(int i = 0; i < votes.length; i++){
for(int j = 0; j < votes[i].length; j++)
}

Gerrymander g = new Gerrymander(votes, 4, 25, true);
}
}

```

Page 1 of 1

bhandari

08 February 2011 - 11:53 AM
Good one. I liked the title!!
0

macosxnerd101

08 February 2011 - 09:56 PM
0

ishkabible

15 February 2011 - 07:31 PM
i think your enabling them too much corrupt politics is one thing but corrupt political programing is another, shame on you
0
Page 1 of 1

S M T W T F S
1234567
891011121314
15161718192021
2223 24 25262728
2930