HERAUSFORDERUNG
Ordnen Sie eine Reihe gruppierter Buchstaben so an, dass sie den gesamten Bereich abdecken.
Vorstandsvertretung (auch bekannt als SHIP DECK)
- Das Board ist ein 6x6-Raster.
- Es wird immer insgesamt 36 Quadrate geben.
- Spalten sind mit AF gekennzeichnet.
- Zeilen sind mit 1-6 markiert.
Beispiel:
A B C D E F
+---+---+---+---+---+---+
1 : : : : : : :
+---+---+---+---+---+---+
2 : : : : : : :
+---+---+---+---+---+---+
3 : : : : : : :
+---+---+---+---+---+---+
4 : : : : : : :
+---+---+---+---+---+---+
5 : : : : : : :
+---+---+---+---+---+---+
6 : : : : : : :
+---+---+---+---+---+---+
INPUT (auch bekannt als die CRATES)
- Eine mehrzeilige Zeichenfolge, die den Satz gruppierter Buchstaben enthält.
- Kisten werden aus den Gruppen identischer Buchstaben hergestellt.
- Die Kisten sind IMMUTIERBAR, dh sie können nicht gedreht oder gedreht werden.
- Der Startpunkt für jede Kiste befindet sich oben links (sollte beim Bewegen einer Kiste auf das Deck berücksichtigt werden).
- Vom oberen linken Punkt einer Kiste können die folgenden identischen Quadrate nur rechts oder unten sein.
- Jeder Buchstabe kann verwendet werden, um eine Kiste darzustellen. Die Kisten beginnen immer mit Buchstaben
[a]
und bewegen sich im Alphabet nach oben. - Kisten sind mit ihrem Buchstaben gekennzeichnet (dh Kiste A, Kiste B usw.)
- Die Anzahl der Kisten kann variieren (trotz der angegebenen Beispiele sind es nicht immer 10).
- Es gibt 24 Zeichen, die jeden Kistenblock pro Zeile trennen. (Anfang von [a] bis Anfang von [b] getrennt durch 24 Zeichen usw.)
Beispiel:
[a][a][a] [b] [c][c]
[a] [b][b][b] [c]
[a] [b][b]
[d] [e] [f][f][f][f][f]
[d][d] [e]
[d][d] [e]
[e]
[e][e]
[g] [h] [i]
[g] [i]
[i]
AUSGABE
Es ist erforderlich, dass Sie eine Reihe von Befehlen ausdrucken, mit denen die Kisten so positioniert werden, dass sie vollständig abgedeckt sind (keine leeren Stellen).
Das Befehlsformat ist wie folgt:
HAUL <crate> TO <column> <row>
dh HAUL E ZU A 1
Zur Verdeutlichung wird es immer eine Lösung für die gegebenen Eingaben geben.
TESTFÄLLE <- Klicken Sie hier, um weitere Informationen zu erhalten .
Eingang
[a][a][a] [b] [c][c][c]
[a][a] [b]
[a] [b][b]
[b][b]
[d] [e] [f]
[d] [f]
[d] [f]
[d]
[d]
[g][g] [h] [i]
[i][i]
[i]
[i][i]
[j][j][j]
Ausgabe
HAUL I TO A 1
HAUL B TO A 3
HAUL A TO B 1
HAUL J TO D 6
HAUL D TO F 1
HAUL F TO E 1
HAUL C TO C 5
HAUL G TO D 4
HAUL E TO D 3
HAUL H TO C 6
Ergebnis:
A B C D E F
+---+---+---+---+---+---+
1 : i : a : a : a : f : d :
+---+---+---+---+---+---+
2 : i : i : a : a : f : d :
+---+---+---+---+---+---+
3 : b : i : a : e : f : d :
+---+---+---+---+---+---+
4 : b : i : i : g : g : d :
+---+---+---+---+---+---+
5 : b : b : c : c : c : d :
+---+---+---+---+---+---+
6 : b : b : h : j : j : j :
+---+---+---+---+---+---+
SCORING
Dies ist Code-Golf, also gewinnt die kürzeste Antwort in Zeichen.
code-golf
sequence
decision-problem
parsing
board-game
Jonathan Picazo
quelle
quelle
Antworten:
Python 3.6,
435437385331 BytesRufen Sie
F()
mit der Kistenschnur.Hat es geschafft, viel mehr Golf zu spielen:
re
Bibliothek zu verwenden.Der Code wurde neu strukturiert, um redundante Schleifen zu entfernen.
Der vorherige Code hat eine Liste aller Positionen einer Kiste erstellt
F()
und dann über die Liste in iteriertR()
. Neuer Code erstellt eine Position einer KisteF()
undR()
probiert alle möglichen Positionen aus.R()
Sammeln Sie im vorherigen Code eine mögliche Lösung ina
undF()
iterieren Sie dann über die zurückgegebene Lösung.R()
Gibt im neuen Code die HAUL-Befehle direkt ausErläuterung
Die Grundidee besteht darin, das Schiffsdeck und die Kisten als Bitmaps darzustellen. Durch die Verwendung von Bitmaps wird das Verschieben einer Kiste zu einer Verschiebung ihrer Bitmap, und das Überprüfen auf Überlappung zwischen Kisten wird zu einem bitweisen UND und Testen auf Null.
Ungolfed Code:
F()
analysiert die Kistendefinitionszeichenfolge und erstellt die Bitmaps. Ein Regex durchsucht (Zeile 9) jede Zeile der Kistendefinitionszeichenfolge nach Kisten (ein Buchstabe gefolgt von einem ']'). Wenn eine Übereinstimmung gefunden wird, wird die entsprechende (Zeile, Spalte) zu einem Wörterbuch hinzugefügt, das durch den Buchstaben (Zeilen 11-13) gekennzeichnet ist. Für die im Problem angegebene Beispiel-Kistendefinitionszeichenfolge:Die Koordinaten jeder Kiste werden normalisiert (Zeile 17), so dass jede Kiste bei (0,0) beginnt und jeder Block eine Einheit breit ist (anstelle von 3 a la '[a]').
Basierend auf den normalisierten Koordinaten wird dann für jede Kiste eine Bitmap erstellt (Zeile 18).
Das Deck wird als 7 x 7-Raster behandelt. Spalte 'G' und Zeile 7 werden verwendet, um zu erkennen, wann sich eine Form von der Platte erstreckt. Eine Bitmap hat eine 1, wenn die Kisten das entsprechende Feld auf dem Deck einnehmen würden. Die Bits 48 bis Bit bis 42 entsprechen den Quadraten A1 bis A7, die Bits 41 bis 35 entsprechen den Quadraten B1 bis B7 und so weiter.
R(used, bitmaps)
Verwenden Sie dann die Bitmaps, um rekursiv nach Kistenplatzierungen zu suchen, bei denen nicht versucht wird, zwei Kisten auf demselben Quadrat zu platzieren.used
ist eine Bitmaske, die angibt, welche Quadrate nicht verwendet werden können, weil sie bereits von einer Kiste besetzt sind oder weil sie nicht auf dem Brett sind (dh Spalte G und Zeile 7).bitmaps
ist eine Liste von Kisten, die noch platziert werden müssen.Der Grundfall für die Rekursion ist, wenn keine Kisten mehr zu platzieren sind, dh
bitmaps
leer sind (Zeile 23). In diesem Fall wird True zurückgegeben, um anzuzeigen, dass eine Lösung gefunden wurde.Andernfalls werden ein Kistenname und seine Bitmap aus der Liste der Bitmaps entfernt (Zeile 26). Während die Kistenbitmap nicht leer ist (Zeile 28), prüfen Sie, ob die aktuelle Kistenplatzierung, die durch die Kistenbitmap dargestellt wird, mit zuvor platzierten Kisten in Konflikt steht. In Zeile 29
not used & crate_bitmap
ist False, wennused
undcrate_bitmap
beide eine 1 an derselben Bitposition haben, was auf einen Konflikt hinweist. Wenn es keinen Konflikt gibt,R()
wird rekursiv aufgerufen (Zeile 30), um zu versuchen, die verbleibenden Kisten zu platzieren.Wenn der rekursive Aufruf an
R()
True zurückgibt, bedeutet dies, dass eine Lösung gefunden wurde und dass die aktuelle Platzierung der Kisten Teil dieser Lösung ist. Der entsprechende Befehl zum Verschieben der Kisten wird gedruckt und True wird über die rekursiven Aufrufe (Zeilen 31-32) weitergegeben.Beim
F()
Erstellen in repräsentiert jede Kistenbitmap die Deckquadrate, die von den Kisten belegt würden, wenn sie an Position A1 platziert würden. Das Verschieben einer Bitmap um ein Bit nach rechts entspricht dem Verschieben der Kisten in Position A2. Eine 7-Bit-Rechtsverschiebung entspricht dem Verschieben der Kisten nach B1 usw. Die folgenden Bitmaps repräsentieren beispielsweise Kisten 'a' an verschiedenen Positionen:Wenn eine mögliche Platzierung von Kisten nicht funktioniert, weil sie mit einer zuvor platzierten Kiste in Konflikt steht (Zeile 30) oder weil die verbleibenden Kisten nicht gültig platziert sind (Zeile 31). Die Kisten werden an eine andere Position bewegt, indem die Bitmaske um ein Bit nach rechts verschoben wird (Zeile 35).
Shift
Verfolgt, um wie viele Stellen die Bitmap verschoben wurde, was der aktuellen Position der Kisten entspricht.Wenn die Bitmap leer ist (Null), bedeutet dies, dass alle möglichen Platzierungen versucht wurden. False wird zurückgegeben (Zeile 37), um einen Fehler anzuzeigen, sodass ein Aufruf zu einem
R()
früheren Zeitpunkt in der Rekursion eine andere Platzierung für seine Kisten versucht.Um sicherzustellen, dass sich die Kisten nicht von der Seite des Decks erstrecken, werden
used
für den ersten Aufruf vonR()
(Zeile 20) Bits entsprechend Spalte G und Zeile 7 gesetzt .4432676798719
ist das leere Deck entsprechend0b0000001000000100000010000001000000100000011111111
quelle
Python 2 , 864 Bytes
Probieren Sie es online aus!
Erläuterung
Viele Bytes werden verwendet, um die zweidimensionalen Kisten zu analysieren, die über eine einzelne Zeichenfolge eingegeben werden. Kisten werden als verschachtelte Liste von Booleschen Werten dargestellt.
Nachdem die Kisten analysiert wurden, berücksichtigt die Funktion alle möglichen Positionen aller Kisten. Dazu ruft es sich iterativ auf. Wenn eine unmögliche Position gefunden wird (wenn die Kiste außerhalb des Decks oder auf einer anderen Kiste platziert wird), wird der aktuelle Rekursionsbaumzweig getötet, um die Leistung zu verbessern.
Wenn festgestellt wird, dass eine bestimmte Kombination von Platzierungen zu einem vollständig abgedeckten Deck geführt hat, wird der aufgezeichnete Verlauf der Kistenplatzierung gedruckt und global beendet, indem eine hoffnungslose Teilung versucht wird. Die gedruckten Transportanweisungen sind sogar alphabetisch sortiert.
Python 2 , 812 Bytes
Probieren Sie es online aus!
Erläuterung
Die Kistenzeichenfolge wird analysiert und in ein aufgelistetes Nest von Booleschen Werten umgewandelt, die jede Kiste darstellen.
Eine iterative Funktion generiert alle möglichen Längenlisten, die der Anzahl der angegebenen Kisten mit den ganzen Zahlen entsprechen
0 <= x < 36
(alle möglichen Schiffsdeckpositionen). Jede Liste wird als Anweisung zum Positionieren aller Kisten interpretiert und getestet. Wenn die getestete Anweisungsliste zu einem Deck ohne Leerzeichen führt, muss die Anweisungsliste gültig sein und wird gedruckt.Da es äußerst ineffizient ist, habe ich es nicht mit dem bereitgestellten Testfall getestet, allerdings mit Szenarien mit weniger Kisten (siehe TIO-Link). Da der Algorithmus jede mögliche Anordnung durchsucht , versucht er, sie zu betrachten
36**10 = 3.656e15
. Doch in der Theorie sollte es immer noch funktionieren.quelle
H
/M
aus der Funktionsdeklaration verschieben, da die Funktionen in der Deklaration nicht wiederverwendbar sind. Guter alter Python.[i]
mit tauschen[b]
, funktioniert dies . Der Algorithmus könnte verbessert werden, indem zuerst die Kisten so sortiert werden, dass sperrigere vor kleinen getestet werden.JavaScript, 366
Hinweis: Diese Funktion kann eine kompaktere Eingabe analysieren, da der Abstand um 24 Zeichen nicht berücksichtigt wird und Löcher in Kisten zulässig sind.
Ich denke, es könnte ein bisschen mehr Golf gespielt werden, aber jetzt ist es kurz und nicht zu langsam, also mag ich es so wie es ist
Weniger Golf gespielt
Testfälle viele von ihnen
quelle