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;
    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(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);


            if(row+1 < votes[0].length){
                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{
        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);
    }
}