tło

Stany Zjednoczone mają wyjątkową miłość do gerrymanderingu - celowej manipulacji okręgiem wyborczym w celu przewidzenia pewnych wyników głosowania. Niedawno przed Sądem Najwyższym została wniesiona sprawa przestępcza . Gerrymandering, szczególnie gdy jest związany z rasą, jest uznawany za nielegalny i powoduje konieczność przerysowania linii dystryktu.

Biorąc pod uwagę prostokątną mapę gminy (tablica 2d), narysujesz linie okręgów, aby pomóc twojej drużynie uzyskać jak najlepszą reprezentację. To znaczy, będziesz gerrymander. Każda gmina ma dwie strony 0i 1. Mapa będzie się składać z kwadratów z jednym 0lub 1na nich. Oto przykładowa mapa:

Wyzwanie

Zgrupujesz mapę w dzielnice, aby drużyna 1otrzymała co najmniej liczbę okręgów określoną przez Wejście.

Wkład

Dane wejściowe będą składały się z mapy, liczby dzielnic do narysowania i minimalnej liczby dzielnic, które 1partia musi wygrać (minimalny wynik).

Wydajność

Wynikiem będzie mapa dzielnic. Każda dzielnica będzie jednoznacznie składać się z dużej litery alfabetu. Tak, oznacza to, że nie będzie więcej niż 26 dzielnic.

Jeśli nie ma możliwości wyjścia, w przypadku gdy strona, którą wprowadzono, wygrywa wystarczającą liczbę okręgów, albo

1. Drukuj „Próbowaliśmy ...”
2. Błąd krytyczny, ponieważ partia została nieodwracalnie poszkodowana przez wyniki wyborów
3. Lub obydwa

Zasady (również bardzo ważne)

1. Wszystkie dzielnice muszą być ciągłe
2. Dzielnice mogą nie mieć w sobie innych dzielnic
3. Każda dzielnica musi mieć co najmniej cztery węzły. Dane wejściowe będą zgodne z regułami, co oznacza, że ​​będą przynajmniej number_of_districts * 4węzły na mapie
4. Wynik każdej ze stron to liczba okręgów, w których ma większość
5. Jeśli dzielnica ma taką samą liczbę 0s i 1s, wówczas ani korzyści z podmiotami od niego
6. Normalne zasady oszukiwania
7. To jest golf golfowy , więc wygrywa najkrótszy kod w bajtach.

Przypadki testowe

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     

Oczywiście twój program powinien działać dla każdego ważnego przypadku testowego, nie tylko tych.

R , 938 896 858 952 bajtów

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

Wypróbuj online!

Ogromne > 900 > 800 (nie!)> 900 bajtów. Kod działa w następujący sposób. Niech N będzie liczbą okręgów wyborczych, a M minimalną liczbą okręgów, w których 1 chce mieć większość.

Po pierwsze, kod losowo przypisuje N dzielnic do różnych grup. Następnie losowo je rozszerza, tzn. Dodaje dzielnicę do losowo wybranej grupy, zapewniając, że dzielnica znajduje się obok dzielnicy już należącej do tej grupy. W procesie ekspansji daje pierwszeństwo dystrykcie z 1 większością, jeśli grupa dystryktów nie ma jeszcze pełnej 1; jeśli grupa ma już pewną 1 większość, wówczas daje pierwszeństwo dzielnicy 0. Trwa do momentu przypisania wszystkich dzielnic.

Każda grupa, w której jest większość dla 1 drużyny, jest przechowywana, a jej dzielnice są zamknięte. Jeśli jest co najmniej M grup z przewagą 1, to wszystko jest dobrze i możemy wydrukować wynik , możemy sprawdzić, czy w każdej grupie są co najmniej 4 dzielnice. Jeśli granica 4 dzielnic zostanie spełniona, możemy z przyjemnością wydrukować wynik. W przeciwnym razie kod próbuje ponownie przypisać dzielnice, które nie są zablokowane do tylu grup, ile jest dostępnych, tj. N - # przechowywanych grup.

Kody próbują kilka razy (9 razy). Jeśli zawiedzie, resetuje wszystko i zaczyna od nowa. Robi to jeszcze 9 razy, zanim zrezygnował i wydrukował „próbowaliśmy ...”.

Jeśli kod początkowo się nie powiedzie, spróbuj ponownie kilka razy. Dostosowałem liczbę powtórzeń, aby można było uruchomić w TIO w ciągu minuty. Jeśli jednak istnieje rozwiązanie, ten kod może (ostatecznie) je znaleźć. Część losowości algorytmu daje niezerowe prawdopodobieństwo, że jeśli istnieje rozwiązanie, może je znaleźć. Ograniczona liczba prób jest jedynym czynnikiem ograniczającym sukces.

EDYCJA: dodano kontrolę, że żadna grupa okręgów nie może być w pełni otoczona przez inną, chyba że grupa okręgów ma dzielnice na skraju danego kwadratu. Myślę, że na początku mi tego brakowało.