Lustiges Wandern

26

Hintergrund

Die Vereinigten Staaten lieben das Wandern - die absichtliche Manipulation eines Wahlbezirks, um bestimmte Abstimmungsergebnisse vorherzusagen. Erst kürzlich wurde vor dem Obersten Gerichtshof ein Gerichtsverfahren eingeleitet . Gerrymandering ist, insbesondere wenn es sich um eine Rasse handelt, illegal und führt dazu, dass die Bezirksgrenzen neu gezogen werden müssen.

Auf der Grundlage einer rechteckigen Karte einer Gemeinde (2D-Array) zeichnen Sie Bezirkslinien, damit Ihre Gruppe die bestmögliche Darstellung erhält. Das heißt, Sie werden gerrymander. Jede Gemeinde hat zwei Parteien 0und 1. Die Karte besteht aus Quadraten, auf denen sich entweder 0oder befindet 1. Hier ist eine Beispielkarte:

Herausforderung

Sie werden die Karte in Bezirke gruppieren, so dass die Gruppe 1mindestens die durch die Eingabe angegebene Anzahl von Bezirken erhält.

Eingang

Die Eingabe besteht aus einer Karte, der Anzahl der zu ziehenden Bezirke und der Mindestanzahl der Bezirke, die die 1Partei zum Gewinnen benötigt (Mindestpunktzahl).

Ausgabe

Die Ausgabe wird eine Karte der Bezirke sein. Jeder Distrikt besteht ausschließlich aus einem Großbuchstaben des Alphabets. Ja, dies bedeutet, dass es nicht mehr als 26 Bezirke geben wird.

Wenn keine Ausgabe möglich ist, bei der die eingegebene Partei genügend Distrikte gewinnt, gilt Folgendes:

  1. “Wir haben es versucht ...” drucken
  2. Tödlicher Fehler, weil die Partei durch das Wahlergebnis irreparabel verletzt wurde
  3. Oder beides

Regeln (auch sehr wichtig)

  1. Alle Stadtteile müssen zusammenhängend sein
  2. Distrikte dürfen keine anderen Distrikte enthalten
  3. Jeder Distrikt muss mindestens vier Knoten enthalten. Die Eingabe stimmt mit den Regeln überein, das heißt, es wird mindestens eine gebennumber_of_districts * 4 die Karte enthält Knoten
  4. Die Punktzahl jeder Partei ist die Anzahl der Bezirke, in denen sie die Mehrheit hat
  5. Wenn ein Distrikt die gleiche Anzahl von 0s und 1s hat, profitiert keine Partei davon
  6. Normale Regeln, nach denen nicht geschummelt wird
  7. Das ist , also gewinnt der kürzeste Code in Bytes.

Testfälle

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     

Natürlich sollte Ihr Programm für jeden gültigen Testfall funktionieren , nicht nur für diese.

Daniel
quelle
@ Arnauld, ja, sie sind nur zur Veranschaulichung. Die tatsächliche Ausgabe sollte wie im ersten Testfall mit den Buchstaben des Alphabets sein. Ich habe das Tag geändert, um dies widerzuspiegeln.
Daniel
Eine einfache Partition des ersten Testfalls wäre etwas, wie diese . Ist das korrekt?
Arnauld
@ Arnauld, ja, das ist gültig.
Daniel,
Wenn wir es also für das dritte Beispiel in horizontale Reihen aufteilen, von denen jede 1 Distrikt hoch ist, würde die 1 3 zu 1 gewinnen, ja?
Michael Dorgan
3
Das erinnert mich sehr an das, was für char-basierte Grafiken auf Nintendo-Handhelds von DMG bis DS getan werden musste. Sie erhielten bestimmte Formen zum Schneiden von Grafiken und mussten die Anzahl der verwendeten Formen minimieren, da nur eine hardwaredefinierte Anzahl von Sprites (Formen) verwendet werden konnte. Das war kein einfaches Problem.
Michael Dorgan

Antworten:

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

Probieren Sie es online!

Eine massive > 900 > 800 (nein!)> 900-Byte-Lösung. Der Code funktioniert wie folgt. Es sei N die Anzahl der Wahlkreise und M die Mindestanzahl der Kreise, in denen 1 eine Mehrheit haben möchte.

Erstens weist der Code N Bezirke zufällig verschiedenen Gruppen zu. Anschließend werden sie zufällig erweitert, dh es wird ein Bezirk zu einer zufällig ausgewählten Gruppe hinzugefügt, um sicherzustellen, dass der Bezirk neben einem Bezirk liegt, der bereits zu dieser Gruppe gehört. Bei der Erweiterung hat ein Distrikt mit einer Mehrheit von 1 Vorrang, wenn die Distriktgruppe noch keine volle Mehrheit von 1 hat. Wenn die Gruppe bereits eine bestimmte 1-Mehrheit hat, hat ein 0-Distrikt Vorrang. Dies wird fortgesetzt, bis alle Bezirke zugewiesen wurden.

Jede Gruppe, in der es eine Mehrheit für die eine Partei gibt, wird gespeichert und ihre Bezirke werden gesperrt. Wenn es mindestens M Gruppen mit einer Mehrheit von 1 gibt, ist alles in Ordnung und wir können das Ergebnis ausdrucken und prüfen, ob es mindestens 4 Bezirke in jeder Gruppe gibt. Wenn der Grenzwert von 4 Distrikten erreicht ist, können wir das Ergebnis gerne ausdrucken. Andernfalls versucht der Code, die Distrikte, die nicht für so viele Gruppen wie verfügbar gesperrt sind, neu zuzuweisen, dh N - # gespeicherte Gruppen.

Der Code versucht es ein paar Mal (9 Mal). Wenn es fehlschlägt, wird alles zurückgesetzt und neu gestartet. Dies geschieht neunmal, bevor "Wir haben es versucht ..." aufgegeben und gedruckt wird.

Wenn der Code zunächst nicht erfolgreich ist, versuchen Sie es einige Male erneut. Ich habe die Anzahl der Wiederholungen so eingestellt, dass sie in weniger als einer Minute in TIO ausgeführt werden können. Wenn es jedoch eine Lösung gibt, kann dieser Code sie (irgendwann) finden. Der Zufallsteil des Algorithmus gibt eine Wahrscheinlichkeit ungleich Null an, mit der eine Lösung gefunden werden kann. Die begrenzte Anzahl von Versuchen ist der einzige begrenzende Faktor für den Erfolg.

BEARBEITEN: Es wurde die Kontrolle hinzugefügt, dass keine Bezirksgruppe vollständig von einer anderen umgeben werden kann, es sei denn, die Bezirksgruppe verfügt über Bezirke am Rand des angegebenen Quadrats. Ich glaube, ich habe es zuerst verpasst.

NofP
quelle
Kannst du irgendwelche Zeilenumbrüche entfernen?
NoOneIsHere
Ich tat. Ich habe auch einzelnen Buchstaben längere Funktionsnamen zugewiesen und einige durch solche ersetzt, ==0bei <1denen die Variable streng ganzzahlig und positiv war.
NofP
1
Es gibt hier eine Menge Dinge, die trivial gespielt werden können, aber dies ist ein guter erster Versuch, eine Antwort zu geben, also +1, und ich werde einige Stunden lang Änderungen vorschlagen, wenn ich nicht auf meinem Handy bin!
Giuseppe
1
858 Bytes - „normaler“ Golf spielt, ist die Verwendung von Klammern mit Reinigung if...elseAussagen, Swapping cfür as.vector, Wechsel "\n"mit wörtlichen Zeilenumbrüchen und mit der Tatsache , dass >leise automatisch coerce Zahlen Zeichen werden und ihre Codepoints vergleichen. Es gibt wahrscheinlich einige andere Golfplätze, an die ich mich nicht erinnern kann, aber dies ist ein Anfang. Ich glaube, wir können noch ein paar Dinge optimieren, aber ich bin mir nicht 100% sicher, ob ich den Code verstehe ...
Giuseppe
Schön! Ich habe mich inspirieren lassen. Beim Vergleich mit Ihrem Code habe ich auch einen Fehler in meinem gefunden, der manchmal zu sehr kleinen Bezirksgruppen führte (weniger als 4 Bezirke). Es ist jetzt behoben.
NofP