fundo

Os Estados Unidos têm um amor único pela gerrymandering - a manipulação deliberada de um distrito eleitoral para prever certos resultados das votações. Recentemente, houve um caso de gerrymandering apresentado ao Supremo Tribunal. A gerrymandering, especialmente quando relacionada à raça, é considerada ilegal e resulta na necessidade de redesenhar as linhas do distrito.

Dado um mapa retangular de um município (matriz 2d), você desenhará linhas de distrito para ajudar seu partido a obter o máximo de representação. Ou seja, você gerrymander. Todo município tem duas partes, 0e 1. O mapa será composto de quadrados com 0ou 1sobre eles. Aqui está um exemplo de mapa:

Desafio

Você agrupará o mapa em distritos para que a 1parte obtenha pelo menos o número de distritos especificado pela Entrada.

Entrada

A entrada consistirá em um mapa, o número de distritos a serem sorteados e o número mínimo de distritos que a 1parte precisa vencer (a pontuação mínima).

Saída

A saída será um mapa dos distritos. Cada distrito será composto exclusivamente por uma letra maiúscula do alfabeto. Sim, isso significa que não haverá mais de 26 distritos.

Se não houver saída possível em que a parte inserida ganha distritos suficientes, ou:

1. Imprimir "Tentamos ..."
2. Erro fatal porque o partido foi irreparavelmente ferido pelos resultados das eleições
3. Ou ambos

Regras (também muito importantes)

1. Todos os distritos devem ser contíguos
2. Os distritos podem não ter outros distritos neles
3. Cada distrito deve ter pelo menos quatro nós. A entrada será consistente com as regras, o que significa que haverá pelo menos number_of_districts * 4nós no mapa
4. A pontuação de cada parte é o número de distritos com maioria em
5. Se um distrito tem o mesmo número de 0s e 1s, então nem benefícios partido dele
6. Regras normais de não trapaça
7. Isso é código-golfe , então o código mais curto em bytes vence.

Casos de teste

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     

Obviamente, seu programa deve funcionar para qualquer caso de teste válido, não apenas para esses.

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="
"))}}}

Experimente online!

Uma solução > 900 > 800 maciça (não!)> 900 bytes. O código funciona da seguinte maneira. Seja N o número de distritos eleitorais e M o número mínimo de distritos em que 1 deseja obter a maioria.

Primeiro, o código atribui aleatoriamente N distritos a diferentes grupos. Em seguida, as expande aleatoriamente, ou seja, adiciona um distrito a um grupo selecionado aleatoriamente, garantindo que o distrito esteja próximo a um distrito que já pertence a esse grupo. No processo de expansão, ele dá precedência a um distrito com 1 maioria, se o grupo de distritos ainda não tiver 1 maioria completa; se o grupo já tiver uma certa maioria de 1, dará prioridade a um distrito 0. Ele continua até que todos os distritos tenham sido designados.

Todo grupo em que há maioria para a parte 1 é armazenado e seus distritos são bloqueados. Se houver pelo menos grupos M com maioria igual a 1, tudo está bem e podemos imprimir o resultado e verificar se há pelo menos 4 distritos em cada grupo. Se o ponto de corte de 4 distritos for atendido, poderemos imprimir o resultado com satisfação. Caso contrário, o código tentará reatribuir os distritos que não estão bloqueados para tantos grupos quanto disponíveis, ou seja, N - # grupos armazenados.

Os códigos tentam algumas vezes (9 vezes). Se falhar, redefine tudo e inicia novamente. Faz isso por outras 9 vezes antes de desistir e imprimir "tentamos ...".

Se o código não der certo no início, tente novamente algumas vezes. Ajustei o número de repetições para que ele possa executar no TIO em menos de um minuto. No entanto, se houver uma solução, esse código poderá (eventualmente) encontrá-lo. A parte aleatória do algoritmo fornece uma probabilidade diferente de zero de que, se houver uma solução, ela pode ser encontrada. O número limitado de tentativas é o único fator limitante ao sucesso.

EDIT: adicionou o controle de que nenhum grupo distrital pode ser totalmente cercado por apenas outro, a menos que o grupo distrital tenha distritos nos limites do quadrado especificado. Eu acho que perdi no começo.