Gerrymandering alegre

26

Fondo

Los Estados Unidos tienen un amor único por la gerrymandering, la manipulación deliberada de un distrito electoral para predecir ciertos resultados de votación. Recientemente se presentó un caso de gerrymandering ante la Corte Suprema. Gerrymandering, especialmente cuando está relacionado con la raza, se considera ilegal y da como resultado el requisito de volver a dibujar las líneas del distrito.

Dado un mapa rectangular de un municipio (matriz 2d), dibujará líneas de distrito para ayudar a su grupo a obtener la mayor representación. Es decir, usted gerrymander. Cada municipio tiene dos partidos, 0y 1. El mapa estará compuesto por cuadrados con uno 0o 1sobre ellos. Aquí hay un mapa de ejemplo:

Reto

Agrupará el mapa en distritos para que la 1parte obtenga al menos el número de distritos especificados por la Entrada.

Entrada

La entrada consistirá en un mapa, el número de distritos que se dibujarán y el número mínimo de distritos que el 1partido necesita ganar (el puntaje mínimo).

Salida

El resultado será un mapa de los distritos. Cada distrito estará compuesto únicamente por una letra mayúscula del alfabeto. Sí, esto significa que no habrá más de 26 distritos.

Si no hay salida posible donde la parte ingresada gana suficientes distritos, tampoco:

  1. Imprimir "Intentamos ..."
  2. Error fatal porque el partido resultó irreparablemente dañado por los resultados electorales
  3. O ambos

Reglas (también muy importantes)

  1. Todos los distritos deben ser contiguos.
  2. Los distritos pueden no tener otros distritos en ellos
  3. Cada distrito debe tener al menos cuatro nodos. La entrada será coherente con las reglas, lo que significa que habrá al menos number_of_districts * 4nodos en el mapa
  4. El puntaje de cada partido es el número de distritos en los que tiene mayoría
  5. Si un distrito tiene el mismo número de 0s y 1S, entonces ni los beneficios del partido de ella
  6. Reglas normales de no hacer trampa
  7. Este es el , por lo que gana el código más corto en bytes.

Casos de prueba

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     

Por supuesto, su programa debería funcionar para cualquier caso de prueba válido, no solo para estos.

Daniel
fuente
@Arnauld, sí, son solo ilustrativos. La salida real debería ser como en el primer caso de prueba con las letras del alfabeto. Cambié la etiqueta para reflejar esto.
Daniel
Una partición simple del primer caso de prueba sería algo como esto . ¿Es eso correcto?
Arnauld
@Arnauld, sí, eso es válido.
Daniel
Entonces, para el tercer ejemplo, si lo dividimos en filas horizontales, cada una de 1 distrito de altura, entonces los 1 ganarían 3 a 1, ¿sí?
Michael Dorgan
3
Esto me recuerda mucho de lo que había que hacer para los gráficos basados ​​en caracteres en las computadoras de mano Nintendo desde DMG hasta DS. Le dieron formas específicas para cortar gráficos y tuvo que minimizar la cantidad de formas utilizadas, ya que solo podía tener una cantidad definida de hardware de sprites (formas) en uso. Ese no fue un problema fácil.
Michael Dorgan

Respuestas:

6

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

Pruébalo en línea!

Una solución masiva > 900 > 800 (¡no!)> 900 bytes. El código funciona de la siguiente manera. Sea N el número de distritos electorales y M el número mínimo de distritos donde 1 desea tener una mayoría.

Primero, el código asigna aleatoriamente N distritos a diferentes grupos. Luego, los expande al azar, es decir, agrega un distrito a un grupo seleccionado al azar, asegurando que el distrito esté al lado de un distrito que ya pertenece a ese grupo. En el proceso de expansión, da prioridad a un distrito con una mayoría de 1, si el grupo de distrito aún no es una mayoría de 1; si el grupo ya es una cierta mayoría de 1, entonces da prioridad a un distrito 0. Continúa hasta que todos los distritos hayan sido asignados.

Cada grupo donde hay una mayoría para la 1 parte se almacena y sus distritos están cerrados. Si hay al menos M grupos con una mayoría de 1, entonces todo está bien y podemos imprimir el resultado , podemos verificar si hay al menos 4 distritos en cada grupo. Si se cumple el límite de 4 distritos, entonces podemos imprimir felizmente el resultado. De lo contrario, el código intenta reasignar los distritos que no están bloqueados a tantos grupos como estén disponibles, es decir, N - # grupos almacenados.

Los códigos lo intentan varias veces (9 veces). Si falla, restablece todo y comienza de nuevo. Lo hace por otras 9 veces antes de darse por vencido e imprimir "intentamos ...".

Si el código no tiene éxito al principio, intente nuevamente varias veces. Ajusté la cantidad de repeticiones para que pueda ejecutarse en TIO en menos de un minuto. Sin embargo, si hay una solución, este código puede (eventualmente) encontrarla. La parte de aleatoriedad del algoritmo da una probabilidad distinta de cero de que, si hay una solución, pueda encontrarla. El número limitado de ensayos es el único factor limitante para el éxito.

EDITAR: se agregó el control de que ningún grupo de distrito puede estar completamente rodeado por otro solo, a menos que el grupo de distrito tenga distritos en el borde del cuadrado dado. Creo que me lo perdí al principio.

NofP
fuente
¿Puedes eliminar alguna línea nueva?
NoOneIsHere
Yo si. También asigné nombres de funciones más largos a letras individuales, y reemplacé algunos ==0con <1cuando la variable era estrictamente entera y positiva.
NofP
1
Hay muchas cosas aquí que se pueden jugar trivialmente, pero este es un buen primer intento de respuesta, así que +1, ¡y estaré sugiriendo ediciones un par de horas una vez que no esté en mi teléfono!
Giuseppe
1
858 bytes - golfs "normales", limpiando el uso de aparatos ortopédicos con if...elselas declaraciones, el intercambio cde as.vector, cambiando "\n"con las nuevas líneas literales, y con el hecho de que >serán automáticamente números de coacción contra a los personajes en silencio y comparar sus puntos de código. Probablemente hay otros campos de golf que hice que no puedo recordar, pero este es un comienzo. Creo que hay algunas cosas más que podemos ajustar, pero no estoy 100% seguro de entender el código ...
Giuseppe
¡Buena esa! Me inspiré. Al compararlo con su código, también encontré un error en el mío que a veces conducía a grupos de distrito muy pequeños (menos de 4 distritos). Ahora está arreglado.
NofP