Im Schachspiel gibt es eine Figur, die Königin genannt wird und jede andere Figur angreifen kann, die sich in derselben Reihe, Spalte oder Diagonale befindet. Im Schach gibt es normalerweise zwei Seiten, schwarz und weiß, wobei jede Figur einer der Mannschaften gehört. Steine dürfen keine Steine des gleichen Teams angreifen.
Ihr Ziel ist es, die größten friedlichen, koexistierenden Armeen für ein quadratisches Brett zu finden. Das ist die größte Anzahl von schwarzen und weißen Königinnen, die auf das Brett passen, so dass sich keine zwei Königinnen angreifen können und die Anzahl der schwarzen Königinnen gleich der Anzahl der weißen Königinnen ist.
Sie erhalten als Eingabe die Seitenlänge eines quadratischen Brettes und sollten die Anzahl der Einheiten der größten friedlichen, koexistierenden Armeen ausgeben, die auf dieses Brett passen.
Dies ist Codegolf, daher gelten die Standardregeln für das Tag.
Diese Testfälle umfassen alle bekannten Antworten. Ihre Lösung sollte eine verallgemeinerte Antwort sein, die bei ausreichender Rechenleistung und Zeit die Lösung für jeden Eingabewert berechnen kann.
1: 0 2: 0 3: 1 4: 2 5: 4 6: 5 7: 7 8: 9 9: 12 10: 14 11: 17 12: 21 13: 24
Antworten:
C, 476 Bytes, DFS iterierende weiße Damen, O (2 n 2 )
518 Bytes, DFS mit Bereinigung, O (2 n )
577 Bytes, DFS iterierende weiße und schwarze Königinnen, O (?)
Grundsätzlich iteriert der Code über Möglichkeiten der weißen Dame und prüft, ob dann die schwarze Dame platziert werden konnte.
Geschwindigkeitsreferenztabelle (in Sekunden):
quelle
Clingo , 90 Bytes
Demo
quelle
Python 2 |
325284217 BytesProbieren Sie es online!
Bearbeiten: Tupel wurden durch ganze Zahlen in g und andere geringfügige Änderungen ersetzt.
Edit2: Bytes down to 217 dank musicman523 und CalculatorFeline !
Wie es funktioniert
Das Programm iteriert über alle möglichen Positionen von
nKöniginnen und filtert nicht friedliche Punkte heraus,gdie durch die Position der Königinnen verursacht wurden. Wenn die verbleibenden Punkte größer sind alsndann, können dienArmeen der Königinnen friedlich bleiben. Wenn für den nächsten Wert vonnkeine friedliche Situation gefunden wird, wird das Programm mit dem Beendigungscode beendet :n-1, was die Antwort ist. Kurz gesagt, es ist rohe GewaltDas Programm kann schneller gemacht werden, indem die letzten beiden Zeilen in geändert werden
quelle
from module import*alles aus einem Modul importieren und Bytes speichern.Haskell ,
169 156 153152 BytesDefiniert eine Funktion
g, kann weiter golffähig sein. Probieren Sie es online! Auf TIO, wenn sie mit kompilierte-O2erfolgt dies etwa 36 Sekunden , n = 4 und eine Zeitüberschreitung auf n = 5 . Die Zeitkomplexität sollte O sein (n 2 4 n 2 ) .Erläuterung
Wir iterieren über die möglichen Werte für die Anzahl der Königinnen ( q ). Für jedes q erzeugen wir alle Paare von Größen- q- Teilmengen von [1..n] 2 , eine Menge von schwarzen Damen ( b ) und eine von weißen Damen ( w ). Dann wird jedes Element von b mit jedem Element von w verglichen, um festzustellen, ob sie eine Reihe, eine Spalte, eine Diagonale oder eine Antidiagonale gemeinsam haben. Dies betrifft auch zwei Teile, die sich die gleiche Koordinate teilen. Der größte Wert von q , der eine friedliche Konfiguration zulässt, ist der Endwert.
Die ersten beiden Zeilen des Programms definieren die Funktion
!, die die Längen-kTeilfolgen einer Liste berechnetx. Die Implementierung erfolgt durch eine grundlegende Rekursion: Wählen Sie entweder das erste Element in der Menge oder nicht und kehren Sie zum Ende zurück und dekrementieren Sie es,kfalls erforderlich. Dann die leere Liste oder erreichte, überprüfen Sie dask==0.Die zweite Hilfsfunktion verwendet
&eine Zahlq(Anzahl der Damen auf jeder Seite) und eine Listel(die x-Koordinaten der Tafel, die auch als y-Koordinaten verwendet werden) und gibt einen Booleschen Wert zurück, der angibt, ob eine friedliche Konfiguration existiert. Wir erste Rechenp, die Liste der längs-qTeilfolgen der Werteliste[x,y,x-y,x+y], woxundy-umspannenl. Sie repräsentieren die Reihe, Spalte, Diagonale und Antidiagonale eines Quadrats(x,y)auf der Tafel.Als nächstes haben wir das Ergebnis von
q&l. Wir zeichnen zwei Untersequenzenbund bildenwausp, koppeln die 4-Listen auf alle möglichen Arten und prüfen, ob sie sich in allen 4 Koordinaten immer unterscheiden. Wenn eine Auswahl vonbundwzu einem wahrheitsgemäßen Ergebnis führt, kehren wir zurückTrue.Die letzte Zeile ist die Hauptfunktion. Vorausgesetzt
n, es findet einfach den größtmöglichen Wert,qfür denq&[1..n]wahr ist.quelle