Diese Herausforderung ist von dieser App inspiriert . Die Testfälle werden von dieser App ausgeliehen.
Dies ist eine Herausforderung mit dem schnellsten Code , bei der es darum geht, die größten Testfälle in kürzester Zeit zu lösen. Es werden einige kleinere Testfälle bereitgestellt, damit die Benutzer ihre Algorithmen möglicherweise schneller testen können.
Sie erhalten ein quadratisches Eingabegitter mit den Abmessungen n x n, wobei 9 <= n <= 12 ist . Dieses Raster wird in n Bereiche unterteilt, in denen die Zellen der einzelnen Bereiche eindeutige Bezeichner aufweisen (ich verwende im Text hier Kleinbuchstaben von al , aber Sie können wählen, was Sie möchten, z. B. Ganzzahlen von 1 bis 12 ). .
Die Eingabe kann folgendermaßen aussehen (optionales Eingabeformat):
aabbbbbcc
adddbbbcc
adeeecccc
adddefgcc
hhhdifggg
hdddifffg
hhhiifffg
hihiifffg
iiiiiiggg
Oder einfacher zu visualisieren:
Herausforderung:
Sie müssen 2 * n Bäume in diesem Park nach folgenden Regeln platzieren:
- Es müssen genau 2 Bäume pro Spalte und 2 Bäume pro Zeile vorhanden sein
- Alle Gebiete müssen genau 2 Bäume haben.
- Kein Baum darf neben einem anderen Baum stehen, weder vertikal noch horizontal noch diagonal
Die Lösung für das obige Layout lautet:
Hinweis: Für jedes Rätsel gibt es nur eine Lösung
Zusätzliche Regeln:
- Die Eingabe- und Ausgabeformate sind optional
- Die Ausgabe kann beispielsweise eine Liste von Indizes sein, ein Raster mit 1/0, das angibt, ob sich an dieser Position ein Baum befindet, oder eine modifizierte Version der Eingabe, in der die Bäume angezeigt werden
- Die Ausführungszeit muss deterministisch sein
- Das Programm muss innerhalb von 1 Minute auf dem Computer von @ isaacg beendet sein
- Technische Daten: 4 CPUs, i5-4300U CPU bei 1,9 GHz, 7,5 G RAM.
- Falls Ihr Programm den zweitgrößten Testfall nicht in jeweils einer Minute lösen kann, ist die Zeit für den zweitgrößten ( n = 11 ) Ihre Punktzahl. Sie verlieren gegen eine Lösung, die den größten Fall löst.
Testfälle:
Ich könnte diese Liste bearbeiten, wenn die Einsendungen an diese Testfälle angepasst zu sein scheinen.
12-mal-12 :
--- Input ---
aaaaabccccdd
aaaaabccccdd
aaaaabbbbddd
eeeafffgbghh
eeaafffgbghh
eefffffggghh
eeefijffghhh
iieiijjjjkhh
iiiiijjjjkhk
lljjjjjjjkkk
llllllkkkkkk
llllllkkkkkk
--- Solution ---
aaaaabcccCdD
aaaaaBcCccdd
aAaaabbbbdDd
eeeaffFgBghh
eeAaFffgbghh
eefffffGgGhh
EeefijffghhH
iiEiIjjjjkhh
IiiiijjjjkHk
lljJjJjjjkkk
lLllllkkKkkk
lllLllKkkkkk
11-mal-11 :
--- Input ---
aaaaaaabbcc
adddabbbbcc
edddbbbbbbc
eddddbbbbbb
effffggghhh
effffgghhii
eefffjjhhii
eeeejjjhhii
eeejjjjkiii
jjjjjjkkiii
jjjjjkkkiii
--- Solution ---
aaAaaaabbCc
adddAbBbbcc
eDddbbbbbbC
eddDdBbbbbb
effffggGhHh
eFfffGghhii
eefFfjjhHii
EeeejjjhhiI
eeEjjjjKiii
JjjjJjkkiii
jjjjjkKkIii
10-mal-10
--- Input ---
aaaaabccdd
aeaabbbccd
aeaabfbgcd
eeeaafggcd
eeeaafghcd
eeeiifghcd
ieiiigghcd
iiijighhcd
jjjjighhcd
jjjggghhdd
--- Solution ---
aaAaabccdD
aeaaBbBccd
aEaabfbgcD
eeeaaFgGcd
eEeAafghcd
eeeiiFghCd
IeiIigghcd
iiijigHhCd
JjJjighhcd
jjjgGghHdd
9-mal-9
--- Input ---
aabbbbbcc
adddbbbcc
adeeecccc
adddefgcc
hhhdifggg
hdddifffg
hhhiifffg
hihiifffg
iiiiiiggg
--- Solution ---
aAbBbbbcc
adddbbBcC
adEeEcccc
AdddefgCc
hhhDiFggg
hDddifffG
hhhiIfFfg
HiHiifffg
iiiiiIgGg
--- Input ---
aaabbbccc
aaaabbccc
aaaddbcce
ffddddcce
ffffddeee
fgffdheee
fggfhhhee
iggggheee
iiigggggg
--- Solution ---
aaAbBbccc
AaaabbcCc
aaaDdBcce
fFddddcCe
fffFdDeee
fGffdheeE
fggfHhHee
IggggheeE
iiIgggGgg
quelle
There shall be exactly 2 trees per column, and 2 trees per row
.Antworten:
JavaScript (ES6), 271 Byte
Nimmt die Eingabe als Array von Arrays von Zeichen. Gibt ein Array von Bitmasken (Ganzzahlen) zurück, die die Position der Bäume in jeder Zeile beschreiben, wobei das niedrigstwertige Bit die Position ganz links ist.
Formatiert und kommentiert
Testfälle
Dieses Snippet enthält eine zusätzliche Funktion, um die Ergebnisse in einem besser lesbaren Format anzuzeigen. Es ist zu langsam, um den letzten Testfall zu lösen.
Erwartete Laufzeit: ~ 5 Sekunden.
Code-Snippet anzeigen
quelle
C, offizielle Zeit: 5 ms für 12 x 12
Kompiliert mit GCC 7 unter Verwendung der Flags
-O3
und-fopenmp
. Sollte bei jeder Version von GCC mit installiertem OpenMP ähnliche Ergebnisse erzielen.Eingabe- und Ausgabeformat sind wie in der Frage angegeben.
Auf meinem Computer dauert dies
0,009s0,008s0,005s für das 12x12-Beispiel und0,022s0,020s0,019s, um alle Beispiele auszuführen. Auf dem Benchmark-Rechner meldet isaacg 5 ms für das 12x12-Beispiel, wobei die ursprüngliche (nicht mit Thread versehene) Version des Codes verwendet wird.Verwendung:
Nur ein einfacher Brute-Force-Löser, der jeweils an einer Reihe arbeitet. Es läuft mit einer guten Geschwindigkeit, indem unmögliche Situationen frühzeitig erkannt werden (z. B. keine Regionszellen mehr, aber weniger als 2 Bäume in der Region).
Die erste Aktualisierung verbessert die Cachetreffer, indem die zugehörigen Daten eng im Speicher abgelegt werden, und macht die Berechnungen der möglichen verbleibenden Bäume im Segment etwas intelligenter (berücksichtigt jetzt die Tatsache, dass Bäume nicht benachbart sein können). Es extrahiert auch die äußerste Schleife, so dass im heißesten Teil des Algorithmus weniger Sonderfälle erforderlich sind.
Bei der zweiten Aktualisierung wird die äußerste Schleife parallel über die verfügbaren Prozessoren (mit OpenMP) ausgeführt, wodurch eine lineare Geschwindigkeitssteigerung erzielt wird. Dies ist nur für n> = 11 aktiviert, da der Aufwand für das Laichen von Threads die Vorteile für kleinere Gitter überwiegt.
quelle
Java (OpenJDK 8) , offizielles Timing: 1.2s auf 12x12
bearbeiten: nicht mehr Code Golf
Probieren Sie es online!
TIO Link ist für den 12x12 Testfall. TIO meldet 2,429s für die Laufzeit.
Nimmt ein Array von Ganzzahlen als Eingabe und ändert das Array so, dass es Einsen für Bäume und Nullen für Nicht-Bäume enthält.
Dies gilt für alle Testfälle. Der größte Testfall läuft auf meinem Rechner in weniger als einer Sekunde, obwohl ich einen ziemlich leistungsstarken Rechner habe
Testcode für das 12x12, kann für andere modifizieren
Produziert dies auf meiner Maschine:
quelle
Clingo , 7 ms für 12 × 12, 116 Bytes
(Zeilenumbrüche sind optional und werden nicht gezählt.)
Laufen Sie mit,
clingo plant.lp - -c n=<n>
wo<n>
die Rastergröße ist. Das Eingabeformat ist eine Liste vonc(X,Y,Z).
Anweisungen für jede Zelle (X
,Y
) gefärbtZ
, mit 1 ≤X
,Y
,Z
≤n
durch Leerzeichen getrennt optional. Die Ausgabe enthältt(X,Y)
für jeden Baum um (X
,Y
).Die Zeit ist ziemlich bedeutungslos, da es sich im Grunde genommen nur um die Startzeit handelt. Betrachten Sie dies also als eine Abstimmung für größere Testfälle.
Demo
Um die Bearbeitung des Eingabe- / Ausgabeformats zu vereinfachen, finden Sie hier Python-Programme, die von und in das in der Challenge angegebene Format konvertiert werden können.
Eingang
Ausgabe
quelle