Jolly gerrymandering

Question

Background

The United States has a unique love of gerrymandering––the deliberate manipulation of an electoral district to predict certain voting results. Just recently there was a gerrymandering case brought before the Supreme Court. Gerrymandering, especially when related to race, is ruled illegal and results in the requirement to redraw the district lines.

Given a rectangular map of a municipality (2d array), you will draw district lines to help your party get the most representation. That is, you will gerrymander. Every municipality has two parties, 0 and 1. The map will be comprised of squares with either 0 or 1 on them. Here is an example map:

Challenge

You will group the map into districts so that the 1 party will get at least the number of districts specified by the Input.

Input

The input will consist of a map, the number of districts to draw, and the minimum number of districts the 1 party needs to win (the minimum score).

Output

The output will be a map of the districts. Each district will be uniquely comprised of a capitalized letter of the alphabet. Yes, this means that there will not be more than 26 districts.

If there is no possible output where the inputted party wins enough districts, either:

1. Print “We tried...”
2. Fatally error because the party was irreparably injured by the election results
3. Or both

Rules (also very important)

1. All districts must be contiguous
2. Districts may not have other districts in them
3. Each district must have at least four nodes in it. The input will be consistent with the rules, meaning that there will be at least number_of_districts * 4 nodes in the map
4. The score of each party is the number of districts it has a majority in
5. If a district has the same number of 0s and 1s, then neither party benefits from it
6. Normal no-cheating rules
7. This is code-golf, so shortest code in bytes wins.

Test cases

1. Input       1. Output       2. Input       2. Output     3. Input      3. Output
districts: 5   Image and map   districts: 3   Image below   districts: 3  fatal error
min wins: 3                    min wins: 3                  min wins: 3
map:                           map:                         map:
00000110000    AAAAAAAAAAA     101101                       101101
10000010000    AAAAAAAAAAA     100000                       100000
10010000011    AAAAAAAAAAA     011011                       011011
11001110000    BBBBBBBAAAA     111111                       100111
00111111000    BBBBBBBAAAA     
01111111000    CCCCCDDDAAA     
01111111001    CCCCCDDDAAA     
01000111100    EEEEEDDDDDD     
00000001000    EEEEEDDDDDD     

Of course, your program should work for any valid test case, not just these ones.

Answer 1

R, 938 896 858 952 bytes

function(N,M,m){U="We tried...
"
L=length
A=matrix
W=which
K=sum
S=sample
G=unique
H=function(s,p=s-1){Y=S(c(s-j,s+j,p*(p%%j>0),(s+1)*(s%%j>0)))
Y[Y>0&Y<=k]}
C=function(v,z=W(r==v))K(z%%j<2,z-j<0,(z+j)>k)
m=A(strsplit(m,"")[[1]],1)
i=W(m<0)[1]-1
m=((t(A(m,i+1))[,1:i]>0)-.5)*2
if((K(m)<M&(N-M)<1)|K(m>0)<(3*M))cat(U) else{j=max(1,nrow(m))
k=i*j;w=g=T
while(w<9&g){Z=R=N;Q=M;b=0
r=A(0,j,i)
while(b<9&g){s=W(r<1)
s=s[S(L(s))][1:min(L(s),R)]
r[s]=1:L(s);a=0
while(K(r<1)>0&a<(k^2)){a=a+1
s=S(W(r>0&r<=R),1);p=r[s]
Y=H(s)
Y=Y[r[Y]<1]
if(L(Y)){Y=Y[order(m[Y])]
if(K(m[r==p]>1))r[Y[1]]=p else r[Y[L(Y)]]=p}}
if(a<(k^2)){for(v in 1:R){if(K(m[r==v])>0){r[r==v]=max(k,max(r))+1
Q=Q-1;Z=Z-1}}
if(Q<1){g=F
for(v in 1:R)r[r==v]=max(k,max(r))+1
for(v in G(c(r)))g=g|(K(r==v)<4)|(L(G(r[H(W(r==v))]))+C(v))<3}}
b=b+1;r[r<=R]=0;R=Z}
w=w+1}
if(g)cat(U) else{u=G(c(r))
for(v in 1:L(u))r[r==u[v]]=v
cat(paste(apply(A(LETTERS[r],j,i),1,paste,collapse=""),collapse="
"))}}}

Try it online!

A massive >900 >800 (nope!) >900 bytes solution. The code works as follows. Let N be the number of electoral districts and M the minimum number of district where 1 wishes to have a majority.

First, the code randomly assigns N districts to different groups. Next, it randomly expands them, i.e. adds a district to a randomly selected group, ensuring that the district is next to a district already belonging to that group. In the expansion process, it gives precedence to a district with a 1 majority, if the district group is not yet a full 1 majority; if the group is already a certain 1 majority, then it gives precedence to a 0 district. It continues until all districts have been assigned.

Every group where there is a majority for the 1 party is stored, and its districts are locked. If there are at least M groups with a majority of 1, then everything is good and we can print the result we can check whether there are at least 4 districts in each group. If the cutoff of 4 districts is met, then we can happily print the result. Otherwise, the code tries to reassign the districts that are not locked to as many groups as available, i.e. N - #stored-groups.

The codes tries a few times (9 times). If it fails, it resets everything and starts again. It does so for other 9 times before giving up and printing "we tried...".

If the code does not succeed at first, try again a few times. I tuned the number of repetitions such that it can run in TIO under a minute. However if there is a solution, this code can (eventually) find it. The randomness part of the algorithm gives a non-zero probability that, if there is a solution, it can find it. The limited number of trials is the only limiting factor to success.

EDIT: added the control that no district group can be fully surrounded by just another one, unless the district group has districts on the edge of the given square. I think I missed it at first.