Stellen Sie sich folgendes Szenario vor: Sie spielen Schlachtschiffe mit einem Freund, entscheiden sich aber zu betrügen. Anstatt ein Schiff zu bewegen, nachdem es an der Stelle geschossen hat, an der sich Ihr Schiff befand, beschließen Sie, überhaupt keine Schiffe zu platzieren. Sie sagen ihm, dass alle seine Schüsse Fehlschüsse sind, bis es unmöglich ist, Schiffe so zu platzieren.
Sie müssen eine Funktion oder ein vollständiges Programm schreiben, das irgendwie drei Argumente akzeptiert: die Feldgröße, eine Liste der Schiffsgrößen und eine Liste der Schüsse.
Schlachtfeld
Einer der angegebenen Parameter ist die Kartengröße. Das Schlachtfeld ist ein Quadrat aus Zellen, und der angegebene Parameter ist einfach eine Seite des Quadrats.
Das folgende Beispiel ist eine Tafel der Größe 5.
Koordinaten auf dem Feld werden als 2-Komponenten-Zeichenfolge angegeben: ein Buchstabe, gefolgt von einer Zahl. Sie können sich darauf verlassen, dass die Buchstaben in einem bestimmten Fall sind.
Buchstabe gibt die Spalte an, Zahl die Zeile der Zelle (1-indiziert). Im obigen Bild ist die hervorgehobene Zelle beispielsweise mit gekennzeichnet "D2"
.
Da es nur 26 Buchstaben gibt, kann das Feld nicht größer als 26x26 sein.
Schiffe
Die Schiffe sind gerade Linien von 1 oder mehr Blöcken. Die Anzahl der Schiffe wird in einer Liste angegeben, wobei das erste Element die Anzahl der 1-Zellen-Schiffe, das zweite die Anzahl der 2-Zellen-Schiffe usw. ist.
Beispielsweise [4,1,2,0,1]
würde die Liste die folgende Schiffsgruppe erstellen:
Schiffe, die sich auf dem Schlachtfeld befinden, können sich nicht kreuzen oder sogar berühren. Nicht einmal mit Ecken. Sie können jedoch die Ränder des Feldes berühren.
Unten sehen Sie ein Beispiel für eine gültige Schiffsplatzierung:
Sie können davon ausgehen, dass für eine bestimmte Schiffsgruppe immer eine Platzierung auf einem leeren Brett einer bestimmten Größe vorhanden ist.
Ausgabe
Wenn solche Platzierungen von Schiffen existieren, müssen Sie eine von ihnen ausgeben.
Das Programm muss eine durch Zeilenumbrüche getrennte Matrix von ASCII-Zeichen eines von drei Typen ausgeben - eine, um eine leere Zelle, eine - ein Schiffsstück und eine - eine Zelle, die als "vermisst" markiert ist. Es dürfen keine anderen Zeichen ausgegeben werden.
Zum Beispiel,
ZZ@Z
\@@Z
@\\Z
\Z\\
(In diesem Beispiel habe ich definiert @
, dass es sich um eine leere Zelle, \
eine "verpasste" Zelle und Z
ein Schiffsstück handelt.)
Wenn keine solche Platzierung vorhanden ist, sollte das Programm / die Funktion zurückkehren, ohne etwas auszugeben.
Eingang
Wenn Sie sich für ein vollwertiges Programm entscheiden, müssen Sie angeben, wie die Listen eingegeben werden. Einige können über Argumente, andere über stdin erfolgen.
Dies ist Code-Golf , die niedrigste Anzahl an Charakteren gewinnt.
Ein Beispiel für eine nicht für den Golfsport optimierte Lösung finden Sie hier.
Kompilieren Sie mit -std=c99
. Das erste Argument ist die Größe des Bretts. Die anderen Argumente sind Schiffsgrößen. Eine durch Zeilenumbrüche getrennte Liste von Aufnahmen ist auf stdin angegeben. Beispiel:
./a 4 1 1 1 <<< $'A2\nA4\nB3\nC3\nC4\D4'
quelle
26x26
? Ich habe eine Lösung entworfen, die auf regulären Ausdrücken und Rekursionen basiert und die extrem langsam wird = für Felder über unbrauchbar6x6
. Entweder mache ich etwas sehr Dummes, oder fehlende Antworten führen dazu, dass andere ebenfalls keinen Erfolg haben.10x10
mit einem4,3,2,1
SchiffssatzAntworten:
GolfScript, 236 Zeichen
Die Eingabe erfolgt über STDIN. Die erste Zeile enthält die Größe und Anzahl der Schiffe, wobei jede Zeile die Koordinaten eines einzelnen Schusses enthält.
Beispiel:
Ich dachte, dass auch diese Herausforderung mindestens eine GolfScript-Antwort haben sollte. Am Ende wurde es aufgrund des verwendeten Algorithmus, der die Leistung gegenüber der Kürze begünstigt, sehr ungolfskriptisch.
Kommentierter Code:
quelle
SWI-Prolog,
536441 1 Bytes1 UNIX-Zeilenende, letzte neue Zeile nicht gezählt
Die Version mit allen Optimierungen entfernt ( 441 Bytes):
Da der Code geändert wird, um die Anzahl der Bytes zu minimieren, akzeptiert er keine Liste von Aufnahmen mit Duplikaten mehr.
Die Version mit Basisoptimierung, voll ausgereift ( 536 → 506 Bytes)
Ich führe einige grundlegende Überprüfungen durch ( zähle die Anzahl der erforderlichen Schiffsblöcke ), um die Code-Exits für eindeutig unmögliche Fälle zu beschleunigen. Der Code ist außerdem immun gegen Duplikate in der Liste der bisher aufgenommenen Bilder.
Unten ist die (etwas) lesbare Version mit detaillierten Kommentaren:
Abfrageformat:
Beispielabfrage (unter Verwendung des Beispiels in der Frage):
quelle
Matlab - 536 Zeichen
Aktualisiert: Deutlich kleinere Ausgabeformatierung, einige Loop-Leerzeichen entfernt.
Aktualisiert: Golfversion hinzugefügt
Aktualisiert: Kommentierte Version hinzugefügt, Golfversion um ~ 100 Zeichen reduziert
Hier ist die Golfversion.
Hier sind einige Beispiele.
Die große Zeile mit 'kron' (in der Nähe des unteren Randes des Codes ohne Golf) ist mein Lieblingsteil davon. Es schreibt eine '1' an alle Orte auf der Karte, die einer bestimmten Position benachbart sind. Kannst du sehen, wie es funktioniert? Es verwendet das Kronecker-Tensorprodukt, die Matrixmultiplikation und indiziert die Karte als lineares Array ...
quelle
Python, 464 Zeichen
Eingabe (stdin):
Ausgabe:
Funktioniert mit ganzen Zahlen, die Bitmaps verschiedener Funktionen enthalten:
quelle
[::-1]
, die es das längste Schiff zuerst versuchen lässt. Es fährt auch zurück, sobald es ein Schiff findet, das es nicht platzieren kann.Python, 562 Zeichen, -8 mit hässlicher Ausgabe, +4? für Bash-Aufruf
Hinweis: Die Einzugsebenen sind Leerzeichen, Tabulator, Tabulator + Leerzeichen, Tabulator + Tabulator und Tabulator + Tabulator + Leerzeichen. Dies erspart einigen Zeichen die Verwendung von Leerzeichen.
Verwendung und Beispiel :
Übernimmt Eingaben von Befehlszeilenargumenten. Gibt eine Leerstelle als Leerzeichen, eine Aufnahme als
.
und eine@
als Teil eines Schiffs aus:Wenn unlösbar, druckt nichts:
Dies
2>X
dient zum Unterdrücken einer Fehlermeldung, da das Programm durch Auslösen einer Ausnahme beendet wird. Fühlen Sie sich frei, eine Strafe von +4 hinzuzufügen, wenn dies als fair erachtet wird. Andernfalls müsste ich ein tuntry: ... except:0
, um es zu unterdrücken, was sowieso mehr Zeichen erfordern würde.Ich kann auch die Ausgabe als Zahlen (drucken
0
,1
und2
) 8 Zeichen abzurasieren, aber ich Wert Ästhetik.Erklärung :
Ich stelle die Tafel als eine Liste von Listen mit ganzen Zahlen dar, deren Größe 2 größer ist als die Eingabe, um zu vermeiden, dass Grenzen überprüft werden müssen.
0
repräsentiert einen leeren Raum,1
einen Schuss und2
ein Schiff. Ich gehe die Schussliste durchQ
und markiere alle Schüsse. Ich wandle die Liste der Schiffe in eine explizite ListeX
der Schiffe um, zB[4, 0, 2, 0, 1]
wird[5, 3, 3, 1, 1, 1, 1]
. Dann ist es ein einfacher Backtracking-Algorithmus: Versuchen Sie in absteigender Reihenfolge, ein Schiff zu platzieren, und versuchen Sie dann, den Rest der Schiffe zu platzieren. Wenn es nicht funktioniert, probieren Sie den nächsten Steckplatz. Sobald es erfolgreich ist, ist die SchiffslisteX
null und der ZugriffX[0]
löst eine Ausnahme aus, die das Programm beendet. Der Rest ist nur starkes Golfen (ursprünglich 1615 Zeichen).quelle
Perl,
455 447 437 436 422418Eingerückt:
Ich gehe davon aus, dass es weiter golfen werden kann (z. B. mit vorformatierten
eval<>
Eingaben, wie ich es sehe (?)) Und auch einigen anderen Dingen (50$
Siegel? Nein, sie bleiben).Wie ich bereits sagte, kann die Geschwindigkeit ein Problem sein (von augenblicklich (siehe Beispiel unten) bis sehr, sehr lang), abhängig davon, wo sich die Lösung im Rekursionsbaum befindet, aber es sollte die Frage der Veralterung der verwendeten Hardware sein. Ich werde später eine optimierte Version machen, mit verschwundener Rekursion und 2-3 anderen offensichtlichen Tricks.
Es läuft so, 3 Zeilen werden durch STDIN geführt:
~
ist der Ozean (künstlerische Lösung, nicht wahr),o
undx
sind Schiffe und Schüsse. Die ersten 5 Zeilen erhalten die Eingabe und bereiten unser 'Schlachtfeld' vor.$N
ist die Größe,@S
ist eine entrollte Reihe von Schiffen (z. B.1 1 1 1 2 3 3 5
wie oben) , und es wird zur nächsten Iteration verzweigt. Und so weiter.$f
ist eine Zeichenfolge, die das Schlachtfeld darstellt (Zeilen mit verketteten Zeilenumbrüchen). Als nächstes folgt eine rekursive Subroutine, die den aktuellen Status des Schlachtfelds und eine Liste der verbleibenden Schiffe erwartet. Es prüft von links nach rechts, von oben nach unten und versucht, jedes Schiff in jeder Position horizontal und vertikal zu platzieren (siehe? Reif für die Optimierung, aber das wird später sein). Horizontale Schiffe sind offensichtlich durch reguläre Ausdrücke zu ersetzen, vertikale etwas komplizierter - durch bitweise Manipulation von Zeichenfolgen, die in der Spalte ersetzt werden müssen. Bei Erfolg (H, V oder beide) werden neue unzugängliche Positionen mit gekennzeichnet!
Bearbeiten: OK, hier ist eine 594- Byte-Version (wenn nicht eingerückt), die tatsächlich versucht, nützlich (dh schnell) zu sein - nach besten Kräften optimiert, aber immer noch dieselben Techniken implementiert - Rekursion (wenn auch 'manuell') und Regexps. Es unterhält einen "Stapel" -
@A
Reihe von Zuständen, die es wert sind, untersucht zu werden. Ein 'Zustand' besteht aus 4 Variablen: aktueller Schlachtfeld-String, Index, von dem aus versucht werden soll, Schiffe zu platzieren, Verweis auf die Anzahl der verbleibenden Schiffe und Index des nächsten Schiffs, das versucht werden soll. Anfänglich gibt es einen einzigen 'Zustand' - Beginn einer leeren Kette, alle Schiffe. Bei Übereinstimmung (H oder V, siehe oben) wird der aktuelle Status zur späteren Untersuchung verschoben, der aktualisierte Status (wenn ein Schiff platziert und unzugängliche Positionen markiert sind) wird verschoben und der Block wird neu gestartet. Wenn das Ende der Schlachtfeldzeichenfolge ohne Erfolg erreicht wird, wird der nächste verfügbare Status von@A
(falls vorhanden) untersucht.Andere Optimierungen sind: Nicht am Anfang der Zeichenfolge neu starten, versuchen, große Schiffe zuerst zu platzieren, nicht Schiff der gleichen Größe überprüfen, wenn das vorherige an derselben Position fehlgeschlagen ist, + möglicherweise etwas anderes (wie keine
$&
Variable usw.)..
OTOH, es dauert immer noch für den unmöglichen Fall
6 5 4 3 2 1
im obigen Beispiel. Vielleicht sollte die praktische Version sofort beendet werden, wenn die gesamte Schiffstonnage die Kapazität des Schlachtfelds überschreitet.quelle
C # -Lösung
quelle
size=1 ships={1} moves={"A1"}
.Java, 1178
Ja, viel zu lang.
Ungolfed:
Sample-Input
Sample-Ausgabe
Mit
O
Fehlschuss#
Schiffsteil_
schieß hier weiter ;-)Sieh auf ideone.com
Eingabe-Handling erwartet die Leerzeichen um Zahlen /
;
und funktioniert ansonsten nicht.Ich platziere zuerst große Schiffe, da sie weniger Plätze haben. Wenn Sie zu small-first wechseln möchten, können Sie dies
pop()
nachremove(0)
undpush(s)
nach ersetzenadd(0,s)
selbst nur eine der beiden Ersatz noch in einem gültigen Programm führen sollte.Wenn Sie zulassen, dass sich Schiffe berühren,
g(int,int)
kann die Funktion erheblich vereinfacht oder entfernt werden.quelle