Dies ist die zweite in einer Reihe von Island Golf Herausforderungen. Vorherige Herausforderung
Zwei Einsiedler sind auf einer einsamen Insel angekommen. Da sie auf der Suche nach Einsamkeit kamen, möchten sie so weit wie möglich voneinander entfernt leben. Wo sollen sie ihre Hütten bauen, um die Entfernung zwischen ihnen zu maximieren?
Eingang
Ihre Eingabe ist ein rechteckiges Raster aus zwei Zeichen, die Land und Wasser darstellen. In den folgenden Beispielen ist Land #
und Wasser .
, Sie können jedoch zwei beliebige Zeichen ersetzen.
...........
...##......
..#####....
..#######..
.#########.
...#######.
...#####.#.
....####...
...........
Es wird immer mindestens zwei Landplättchen geben. Die Landplättchen werden alle zusammenhängend sein (dh es gibt nur eine Insel). Die Wasserplättchen werden auch zusammenhängend sein (dh es gibt keine Seen). Der äußere Rand des Gitters besteht aus Wasserplättchen. Landplättchen werden nicht diagonal verbunden, dh Sie werden niemals so etwas sehen
....
.#..
..#.
....
Ausgabe
Ihr Code muss Ausgang das gleiche Raster, mit zwei Hütte Standorten auf sie markiert. In den folgenden Beispielen sind die Hüttenpositionen mit einem X gekennzeichnet. Sie können jedoch jedes Zeichen ersetzen, sofern es sich von Ihren Land- und Wasserzeichen unterscheidet.
Die Hüttenpositionen müssen aus zwei Landplättchen bestehen, die so gewählt sind, dass der Abstand zwischen ihnen maximiert wird . Wir definieren die Gehstrecke als die Länge des kürzesten Weges zwischen den beiden Punkten, der sich vollständig an Land befindet. Landplättchen werden horizontal oder vertikal nebeneinander, aber nicht diagonal betrachtet.
Eine mögliche Lösung für die obige Insel:
...........
...X#......
..#####....
..#######..
.#########.
...#######.
...#####.X.
....####...
...........
Die Entfernung zwischen diesen beiden Punkten beträgt 11, was die größte Entfernung zwischen zwei Punkten auf dieser Insel darstellt. Es gibt noch eine andere Lösung mit Abstand 11:
...........
...##......
..X####....
..#######..
.#########.
...#######.
...#####.X.
....####...
...........
Einzelheiten
Ihre Lösung kann ein vollständiges Programm oder eine Funktion sein . Alle Standardeingabe- und -ausgabemethoden sind zulässig.
Ihre Eingabe und Ausgabe kann eine mehrzeilige Zeichenfolge, eine Liste von Zeichenfolgen oder ein 2D-Array / eine verschachtelte Liste von Zeichen / Einzelzeichenfolgen sein. Ihre Ausgabe kann (optional) eine einzelne nachgestellte Zeile enthalten. Wie oben erwähnt, können Sie drei verschiedene Zeichen anstelle von verwenden #.X
(bitte geben Sie in Ihrer Übermittlung an, welche Zeichen Sie verwenden).
Testfälle
A. Inseln mit einzigartigen Hüttenplätzen:
....
.##.
....
....
.XX.
....
......
......
..##..
...#..
......
......
......
......
..X#..
...X..
......
......
........
.#####..
.##..##.
.#..###.
.##..##.
........
........
.#####..
.##..##.
.#..###.
.#X..#X.
........
.........
.#####.#.
.#...#.#.
.#.###.#.
.#.....#.
.#######.
.........
.........
.#####.X.
.#...#.#.
.#.X##.#.
.#.....#.
.#######.
.........
B. Beispiel einer Insel mit mehreren möglichen Lösungen:
........
....##..
...####.
..###...
.#####..
.#####..
..##....
........
Mögliche Ausgaben:
........
....#X..
...####.
..###...
.#####..
.X####..
..##....
........
........
....#X..
...####.
..###...
.#####..
.#####..
..X#....
........
........
....##..
...###X.
..###...
.#####..
.X####..
..##....
........
........
....##..
...###X.
..###...
.#####..
.#####..
..X#....
........
Das ist Code-Golf : Der kürzeste Code in jeder Sprache gewinnt.
Antworten:
Python 3,
249246 Bytes3 Bytes gespart, danke DLosc.
Eingabe und Ausgabe sind einzelne Zeichenfolgen, wobei '.', '@' Und 'X' Wasser, Hütten bzw. Land darstellen.
Vorherige Version:
Die Eingabe ist eine einzelne Zeichenfolge mit '.' und '#' stehen für Wasser bzw. Land. 'X' steht für die Hütten in der Ausgabe.
Erläuterung:
Im Grunde genommen wird eine umfassende erste Suche von jedem möglichen Startpunkt zur gleichen Zeit durchgeführt. Behalten Sie ein Wörterbuch d der Pfadlängen bei, das durch den Anfang und das Ende des Pfades festgelegt ist, z. B. ist d [(k, i)] der Abstand von k zu i. Dann iterieren Sie über die Schlüssel im Wörterbuch d und erstellen ein neues Wörterbuch u mit Pfaden, die 1 Einheit länger sind, indem Sie den Endpunkt 1 Einheit auf N, S, E, W verschieben, z. B. u [(k, i + 1)] = d [(k, i)] + 1. Schließen Sie keine Pfade ein, die bereits in d enthalten sind. Wenn u nicht leer ist, fügen Sie die neuen längeren Pfade zu d hinzu und wiederholen Sie den Vorgang. Wenn u leer ist, können keine Pfade mehr erstellt werden. Jetzt enthält d alle möglichen Pfade und ihre Längen. Es geht also nur darum, den Schlüssel mit dem längsten Weg zu finden.
Weniger Golf, kommentierte Version:
quelle
C #, 387 Bytes
Lass uns die Kugel ins Rollen bringen...
Probieren Sie es online
Komplettes Programm, liest aus STDIN, schreibt nach STDOUT. Es geht einfach über jede Zelle und führt ein BFS aus, um die am weitesten entfernte Zelle zu berechnen, wobei beide aufgezeichnet werden, wenn es die am weitesten entfernte in der Aufzeichnung ist. Nichts wirklich, und frustrierend wenig finde ich zum Golfen.
Formatierter und kommentierter Code:
quelle