Задний план

Соединенные Штаты обладают уникальной любовью к зачаточному воспитанию - преднамеренному манипулированию избирательным округом для предсказания определенных результатов голосования. Совсем недавно в Верховном суде было возбуждено дело о подстрекательстве . Gerrymandering, особенно когда это связано с расой, считается незаконным и приводит к требованию перерисовать линии района.

Имея прямоугольную карту муниципалитета (массив 2d), вы нарисуете линии округа, чтобы помочь вашей группе получить наибольшее представление. То есть ты будешь геррмандером. У каждого муниципалитета есть две стороны, 0и 1. Карта будет состоять из квадратов с 0или 1на них. Вот пример карты:

Вызов

Вы сгруппируете карту по районам, чтобы 1партия получала как минимум количество районов, указанное в поле «Входные данные».

вход

Входные данные будут состоять из карты, количества районов, которые нужно нарисовать, и минимального количества районов, в которых 1партия должна выиграть (минимальный счет).

Выход

На выходе будет карта районов. Каждый район будет состоять из заглавной буквы алфавита. Да, это значит, что не будет более 26 районов.

Если нет никакого возможного выхода, где введенная сторона выигрывает достаточно районов, либо:

1. Распечатать «Мы пытались ...»
2. Фатальная ошибка, потому что партия была непоправимо ранена результатами выборов
3. Или оба

Правила (тоже очень важно)

1. Все районы должны быть смежными
2. Районы могут не иметь других районов в них
3. В каждом районе должно быть как минимум четыре узла. Входные данные будут соответствовать правилам, что означает, что number_of_districts * 4на карте будут хотя бы узлы
4. Оценка каждой партии - это количество округов, в которых она имеет большинство
5. Если в округе одинаковое количество 0s и 1s, то ни одна из сторон не получает от него выгоды
6. Нормальные правила обмана
7. Это код-гольф , поэтому выигрывает самый короткий код в байтах.

Контрольные примеры

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     

Конечно, ваша программа должна работать для любого действительного теста, а не только для этих.

R , 938 896 858 952 байт

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

Попробуйте онлайн!

Массивное решение > 900 > 800 (нет!)> 900 байт. Код работает следующим образом. Пусть N - количество избирательных округов, а M - минимальное количество округов, где 1 желает иметь большинство.

Во-первых, код случайным образом назначает N районов различным группам. Затем он случайным образом расширяет их, то есть добавляет район в случайно выбранную группу, гарантируя, что район находится рядом с районом, уже принадлежащим этой группе. В процессе расширения приоритет отдается району с 1 большинством, если группа округов еще не является полным 1 большинством; если группа уже имеет определенное 1 большинство, то она дает приоритет 0 району. Это продолжается, пока все районы не будут назначены.

Каждая группа, в которой существует большинство для 1 партии, сохраняется, а ее районы блокируются. Если есть хотя бы M групп с большинством в 1, то все хорошо, и мы можем напечатать результат, мы можем проверить, есть ли по крайней мере 4 района в каждой группе. Если отсечение 4 районов выполнено, то мы можем с радостью напечатать результат. В противном случае код пытается переназначить районы, которые не привязаны к как можно большему количеству групп, т.е. N - # сохраненных групп.

Коды пытается несколько раз (9 раз). Если это не удается, он сбрасывает все и запускается снова. Это происходит еще 9 раз, прежде чем сдаться и напечатать «мы пытались ...».

Если код сначала не выполняется, попробуйте еще раз несколько раз. Я настроил количество повторений так, чтобы он мог работать в TIO менее чем за минуту. Однако, если есть решение, этот код может (в конце концов) его найти. Часть алгоритма случайности дает ненулевую вероятность того, что, если есть решение, оно может его найти. Ограниченное количество испытаний является единственным ограничивающим фактором успеха.

РЕДАКТИРОВАТЬ: добавлен контроль, что ни одна группа районов не может быть полностью окружена только другой, если только группа районов не имеет районов на краю данной площади. Я думаю, что я пропустил это сначала.