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:
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.
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.
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).
The main() method:
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; private StackMap<Point, Boolean> votes; public Knapsack(boolean party){ this(10, party); } public Knapsack(int quota, boolean party){ this.quota = quota; this.democrats = this.republicans = 0; this.party = party; votes = new StackMap<Point, Boolean>(); } public boolean add(int i, int j, boolean party){ if(votes.size() == quota) return false; votes.push(new Point(i,j), party); if(party) democrats++; else republicans++; return true; } public boolean pop(){ boolean party = votes.pop().getValue(); 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(){ if(quota != votes.size()) return false; if(party) return democrats > republicans; else return republicans > democrats; } public int count(){return votes.size();} 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(votes.size() > 0){ map2.put(votes.peek().getKey(), votes.peek().getValue()); tempMap.push(votes.peek().getKey(), votes.pop().getValue()); } while(tempMap.size() > 0){ votes.push(tempMap.peek().getKey(), tempMap.pop().getValue()); } 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(); } } } class MyThread extends Thread{ private Knapsack[] district; private Vote[][] votes; 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); votes = new Vote[state.length][state[0].length]; for(int i = 0; i < state.length; i++){ for(int j = 0; j < state[0].length; j++) votes[i][j] = new Vote(state[i][j].getParty()); } 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++; } if(votes[row][col].isInDistrict()) return; if(!votes[row][col].isInDistrict()){ district[knapsack].add(row, col, votes[row][col].getParty()); votes[row][col].setInDistrict(true); } if(row1 >= 0){ distribute(row1, col1, knapsack); distribute(row1, col, knapsack); distribute(row1, col+1, knapsack); } distribute(row, col+1, knapsack); distribute(row, col1, knapsack); if(row+1 < votes[0].length){ distribute(row+1, col1, 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 hcpslevetm */ import java.util.*; public class Main { public static void main(String[] args) throws Exception{ Vote[][] votes = new Vote[10][10]; 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++) votes[i][j] = new Vote(scan.next().equals("D")); } Gerrymander g = new Gerrymander(votes, 4, 25, true); } }
3 Comments On This Entry
Page 1 of 1
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
Page 1 of 1
My Blog Links
Recent Entries
Recent Comments
Search My Blog
0 user(s) viewing
0 Guests
0 member(s)
0 anonymous member(s)
0 member(s)
0 anonymous member(s)
