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 0
und 1
. Die Karte besteht aus Quadraten, auf denen sich entweder 0
oder befindet 1
. Hier ist eine Beispielkarte:
Herausforderung
Sie werden die Karte in Bezirke gruppieren, so dass die Gruppe 1
mindestens 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 1
Partei 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:
- “Wir haben es versucht ...” drucken
- Tödlicher Fehler, weil die Partei durch das Wahlergebnis irreparabel verletzt wurde
- Oder beides
Regeln (auch sehr wichtig)
- Alle Stadtteile müssen zusammenhängend sein
- Distrikte dürfen keine anderen Distrikte enthalten
- Jeder Distrikt muss mindestens vier Knoten enthalten. Die Eingabe stimmt mit den Regeln überein, das heißt, es wird mindestens eine geben
number_of_districts * 4
die Karte enthält Knoten - Die Punktzahl jeder Partei ist die Anzahl der Bezirke, in denen sie die Mehrheit hat
- Wenn ein Distrikt die gleiche Anzahl von
0
s und1
s hat, profitiert keine Partei davon - Normale Regeln, nach denen nicht geschummelt wird
- Das ist Code-Golf , 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.
quelle
Antworten:
R ,
938896858952 BytesProbieren 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 ausdruckenund 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.
quelle
==0
bei<1
denen die Variable streng ganzzahlig und positiv war.if...else
Aussagen, Swappingc
füras.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 ...