This week’s Riddler was finding a geometric split to segment a population:
The Problem:
Below is a rough approximation of Colorado’s voter preferences, based on county-level results from the 2012 presidential election, in a 14-by-10 grid. Colorado has seven districts, so each would have 20 voters in this model. What is the most districts that the Red Party could win if you get to draw the districts with the same rules as above? What about the Blue Party? (Assume ties within a district are considered wins for the party of your choice.)
The Process:
To solve myself and @CheddaBob10 created a random search process. Given a seed of districts the correct size it would:
- Pick a random square
- Pick a random square surrounding it. Swap them
- Check to see if the districts are contiguous
- Check to see how many of your districts have a majority. if more than your current maximum, print the districtization
- Repeat
The Results:
An example of all the districts moving:
The reality is that it took over 100,000 iterations to find the optimal districts. They are:
For blue to win 5 of the 7 (its upper bound):
For red to win 7 of 7: