Riang gembira

26

Latar Belakang

Amerika Serikat memiliki kecintaan khusus pada persekongkolan - manipulasi yang disengaja dari suatu daerah pemilihan untuk memprediksi hasil pemilihan tertentu. Baru-baru ini ada kasus persekongkolan yang dibawa ke Mahkamah Agung. Gerrymandering, terutama yang terkait dengan ras, dianggap ilegal dan menghasilkan persyaratan untuk menggambar ulang garis kabupaten.

Diberikan peta persegi panjang kotamadya (array 2d), Anda akan menggambar garis distrik untuk membantu pesta Anda mendapatkan representasi terbanyak. Yaitu, Anda akan berpasangan. Setiap kota memiliki dua pihak, 0dan 1. Peta akan terdiri dari kotak dengan salah satu 0atau 1di atasnya. Ini contoh peta:

Tantangan

Anda akan mengelompokkan peta ke dalam distrik sehingga 1partai akan mendapatkan setidaknya jumlah distrik yang ditentukan oleh Input.

Memasukkan

Input akan terdiri dari peta, jumlah distrik yang akan diundi, dan jumlah minimum distrik yang 1harus dimenangkan oleh partai (skor minimum).

Keluaran

Outputnya akan menjadi peta kabupaten. Setiap distrik akan secara unik terdiri dari huruf besar alfabet. Ya, ini berarti tidak akan ada lebih dari 26 kabupaten.

Jika tidak ada output yang memungkinkan di mana pihak yang diinput memenangkan cukup distrik, baik:

  1. Cetak “Kami mencoba ...”
  2. Kesalahan fatal karena partai itu tidak dapat diperbaiki karena hasil pemilu
  3. Atau keduanya

Aturan (juga sangat penting)

  1. Semua distrik harus bersebelahan
  2. Kabupaten mungkin tidak memiliki kabupaten lain di dalamnya
  3. Setiap kabupaten harus memiliki setidaknya empat node di dalamnya. Masukan akan konsisten dengan aturan, artinya setidaknya akan ada number_of_districts * 4simpul di peta
  4. Skor dari masing-masing pihak adalah jumlah kabupaten yang memiliki mayoritas
  5. Jika suatu kabupaten memiliki jumlah 0s dan 1s yang sama, maka tidak ada pihak yang mendapat manfaat darinya
  6. Aturan larangan normal
  7. Ini adalah , jadi kode terpendek dalam byte menang.

Uji kasus

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     

Tentu saja, program Anda harus bekerja untuk setiap kasus uji yang valid, bukan hanya yang ini.

Daniel
sumber
@Arnauld, ya mereka hanya ilustratif. Output nyata harus seperti dalam kasus uji pertama dengan huruf-huruf alfabet. Saya mengubah tag untuk mencerminkan ini.
Daniel
Partisi sederhana dari test case pertama akan menjadi seperti ini . Apakah itu benar?
Arnauld
@Arnauld, ya, itu sah.
Daniel
Jadi untuk contoh ke-3, jika kita membaginya menjadi baris horizontal, masing-masing 1 distrik tinggi, maka 1s akan menang 3 banding 1 ya?
Michael Dorgan
3
Ini mengingatkan saya pada banyak hal yang harus dilakukan untuk grafis berbasis char pada perangkat genggam Nintendo mulai dari DMG hingga DS. Anda diberi bentuk khusus untuk memotong grafik dan harus meminimalkan jumlah bentuk yang digunakan karena Anda hanya bisa memiliki jumlah sprite (bentuk) perangkat keras yang digunakan. Itu bukan masalah yang mudah.
Michael Dorgan

Jawaban:

6

R , 938 896 858 952 byte

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

Cobalah online!

Solusi > 900 > 800 (nggak!)> 900 byte. Kode berfungsi sebagai berikut. Biarkan N menjadi jumlah daerah pemilihan dan M jumlah minimum kabupaten di mana 1 ingin memiliki mayoritas.

Pertama, kode ini secara acak menetapkan N distrik ke berbagai kelompok. Selanjutnya, itu memperluas mereka secara acak, yaitu menambahkan kabupaten ke kelompok yang dipilih secara acak, memastikan bahwa kabupaten tersebut di sebelah kabupaten yang sudah menjadi milik kelompok itu. Dalam proses perluasan, ia lebih diutamakan dari sebuah distrik dengan mayoritas 1, jika kelompok distrik belum menjadi mayoritas penuh 1; jika grup sudah menjadi mayoritas 1, maka diutamakan untuk 0 distrik. Ini berlanjut sampai semua distrik ditugaskan.

Setiap grup di mana ada mayoritas untuk 1 pihak disimpan, dan distriknya dikunci. Jika setidaknya ada kelompok M dengan mayoritas 1, maka semuanya baik dan kita dapat mencetak hasilnya kita dapat memeriksa apakah ada setidaknya 4 kabupaten di masing-masing kelompok. Jika cutoff 4 distrik terpenuhi, maka kita dapat dengan senang hati mencetak hasilnya. Jika tidak, kode akan mencoba menetapkan kembali distrik yang tidak dikunci ke grup sebanyak yang tersedia, yaitu N - # grup yang tersimpan.

Kode mencoba beberapa kali (9 kali). Jika gagal, ini akan mengatur ulang segalanya dan mulai lagi. Ia melakukannya selama 9 kali sebelum menyerah dan mencetak "kami mencoba ...".

Jika kode tidak berhasil pada awalnya, coba lagi beberapa kali. Saya menyetel jumlah pengulangan sehingga bisa berjalan di TIO kurang dari satu menit. Namun jika ada solusi, kode ini dapat (akhirnya) menemukannya. Bagian keacakan dari algoritma memberikan probabilitas bukan nol bahwa, jika ada solusi, ia dapat menemukannya. Terbatasnya jumlah percobaan adalah satu-satunya faktor pembatas untuk sukses.

EDIT: menambahkan kontrol bahwa tidak ada kelompok kabupaten dapat sepenuhnya dikelilingi oleh yang lain, kecuali kelompok kabupaten memiliki kabupaten di tepi alun-alun yang diberikan. Saya pikir saya melewatkannya pada awalnya.

NofP
sumber
Bisakah Anda menghapus baris baru?
NoOneIsHere
Aku melakukannya. Saya juga menetapkan nama fungsi yang lebih panjang untuk huruf tunggal, dan menggantikan beberapa ==0dengan <1ketika variabel itu benar-benar bilangan bulat dan positif.
NofP
1
Ada banyak hal di sini yang bisa golf trivially tapi ini adalah upaya pertama yang bagus untuk jawaban, jadi +1, dan saya akan menyarankan pengeditan saya beberapa jam setelah saya tidak di ponsel saya!
Giuseppe
1
858 byte - "biasa" golfs, membersihkan penggunaan kawat gigi dengan if...elsepernyataan, swapping cuntuk as.vector, mengubah "\n"dengan baris baru literal, dan menggunakan fakta bahwa >akan secara otomatis nomor memaksa untuk karakter diam-diam dan membandingkan codepoints mereka. Mungkin ada beberapa golf lain yang saya lakukan yang tidak dapat saya ingat tapi ini awal. Saya pikir ada beberapa hal lagi yang dapat kita atur tetapi saya tidak 100% yakin saya memahami kode ...
Giuseppe
Yang bagus! Saya mengambil inspirasi. Dengan membandingkan dengan kode Anda, saya juga menemukan bug di tambang yang terkadang mengarah ke grup distrik yang sangat kecil (kurang dari 4 distrik). Sekarang sudah diperbaiki.
NofP