Island Golf # 1: Weltumsegelung

43

Dies ist die erste in einer Reihe von Island Golf Herausforderungen. Nächste Herausforderung

Wenn Sie eine Insel in ASCII-Kunst haben, geben Sie einen optimalen Pfad aus, um sie zu umrunden.

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 ein 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 dasselbe Raster mit einer kürzesten Umrundung ausgeben . In den folgenden Beispielen wird der Umrundungspfad mit gezeichnet o, Sie können jedoch jedes Zeichen ersetzen, sofern es sich von Ihren Land- und Wasserzeichen unterscheidet.

Eine Weltumsegelung ist eine einfache geschlossene Kurve, die vollständig auf Wasserplättchen gezeichnet ist und alle Landplättchen auf dem Gitter vollständig umgibt. Diagonale Verbindungen sind zulässig. Dies ist zum Beispiel eine Umrundung der obigen Insel (aber keine kürzeste):

.ooooo.....
o..##.oo...
o.#####.o..
o.#######o.
o#########o
ooo#######o
..o#####.#o
..oo####..o
....oooooo.

Die Länge einer Umrundung wird wie folgt berechnet: Addieren Sie für jedes Paar benachbarter Kacheln auf dem Pfad, wenn diese horizontal oder vertikal verbunden sind, 1; Wenn sie diagonal verbunden sind, fügen Sie √2 hinzu. Die Länge des obigen Pfades beträgt 22 + 7√2 (≈ 31.9).

Eine kürzeste Weltumsegelung ist eine Weltumsegelung mit möglichst kurzer Länge. Ihr Programm sollte einen Pfad ausgeben, der diese Bedingung erfüllt. Für die meisten Inseln gibt es mehrere mögliche Lösungen. Hier ist eine Lösung für die obige Insel mit einer Länge von 10 + 13√2 (≈ 28.4):

...oo......
..o##oo....
.o#####oo..
.o#######o.
o#########o
.o.#######o
..o#####.#o
...o####.o.
....ooooo..

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 oder eine Liste von Zeichenfolgen sein. Wenn Ihre Sprache einen Zeichentyp hat, der sich von Einzelzeichenfolgen unterscheidet, können Sie "Zeichenfolge" im vorherigen Satz durch "Zeichenliste" ersetzen. Wenn Ihre Sprache die Höhe und / oder Breite des Rasters eingeben muss, können Sie dies tun. Ihre Ausgabe kann (optional) eine einzelne nachgestellte Zeile enthalten. Wie oben erwähnt, können Sie drei verschiedene Zeichen anstelle von verwenden #.o(bitte geben Sie in Ihrer Übermittlung an, welche Zeichen Sie verwenden).

Testfälle

A. Inseln mit einzigartigen kürzesten Umrundungen:

...
.#.
...

.o.
o#o
.o.

......
.####.
......

.oooo.
o####o
.oooo.

......
......
..##..
...#..
......
......

......
..oo..
.o##o.
..o#o.
...o..
......

.......
.#####.
...#...
...#...
.#####.
.......

.ooooo.
o#####o
o..#..o
o..#..o
o#####o
.ooooo.

.......
...#...
...#...
.#####.
...#...
...#...
.......

...o...
..o#o..
.o.#.o.
o#####o
.o.#.o.
..o#o..
...o...

.......
.#####.
.##..#.
..#..#.
.......

.ooooo.
o#####o
o##..#o
.o#..#o
..oooo.

B. Beispiel einer Insel mit mehreren möglichen Lösungen:

........
....##..
...####.
..###...
.#####..
.#####..
..##....
........

Mögliche Ausgaben:

....oo..
...o##o.
..o####o
.o###.o.
o#####o.
o#####o.
.o##oo..
..oo....

....oo..
...o##o.
..o####o
.o###.o.
o#####o.
o#####o.
.o##.o..
..ooo...

....oo..
...o##o.
..o####o
.o###..o
o#####.o
o#####o.
.o##oo..
..oo....

....oo..
...o##o.
..o####o
.o###..o
o#####.o
o#####o.
.o##.o..
..ooo...

C. Großer Testfall als Kern


Das ist : Der kürzeste Code in jeder Sprache gewinnt.

DLosc
quelle
1
Die kürzeste Umrundung für den 3. Testfall ist das Laibmuster in Conways Game of Life!
Genosse SparklePony

Antworten:

18

Mathematica (Version 9), 165 Bytes

Die nette, kurze ConvexHullMeshFunktion, die Greg Martin verwendete, wurde erst in Mathematica Version 10 eingeführt, und ich dachte, ich würde einen Versuch ohne sie mit meiner alten Mathematica Version 9 unternehmen. Ich habe es jedoch geschafft, sie etwas kürzer zu machen! Es ist eine Funktion , die nimmt und gibt eine Liste von Zeichenketten (mit ., #und owie die Symbole).

""<>#&/@("o"MorphologicalTransform[MorphologicalComponents[#,Method->"ConvexHull"],Max[#(1-#[[2,2]])CrossMatrix@1]&]+"#"#/.{0->"."})&[Characters@#/.{"."->0,"#"->1}]&

Erläuterung:

  • Zuerst Characters@# /. {"."->0, "#"->1}schaltet die Eingabe in eine Matrix von 0s und 1s.
  • "o"MorphologicalTransform[MorphologicalComponents[#,Method->"ConvexHull"],Max[#(1-#[[2,2]])CrossMatrix@1]&]+"#"#Dann nutzt Mathematica die leistungsstarken Bildverarbeitungsfunktionen (die jedoch extrem byteaufwändig sind…), um zuerst den konvexen Rumpf der Insel auszufüllen (die Form, die Sie erhalten würden, wenn Sie ein Stück Schnur darum spannen würden) und dann dessen Grenze zu erreichen. Wir multiplizieren diese Matrix dann mit der Zeichenfolge "o", um eine Matrix aus 0s und "o"s zu erhalten (dank Mathematics beeindruckender Anpassungsfähigkeit in Bezug auf Typen), und addieren diese zu "#"der Matrix der Insel.
  • Schließlich ""<>#& /@ (... /. {0->"."})macht diese Matrix "o"s, "#"S und 0S in eine Matrix von "o"n, "#"s und "."s und verbindet jede Zeile in einen String.

Wenn wir dies an Beispiel B testen , erhalten wir die Ausgabe

{"....oo..",
 "...o##o.",
 "..o####o",
 ".o###..o",
 "o#####o.",
 "o#####o.",
 ".o##oo..",
 "..oo...."}

[Bearbeiten, danke an Greg Martin:] Wenn wir anstelle von Listen mit Strings Arrays von Zeichen verwenden dürfen, können wir dies auf 144 Bytes reduzieren:

"o"MorphologicalTransform[MorphologicalComponents[#,Method->"ConvexHull"],Max[#(1-#[[2,2]])CrossMatrix@1]&]+"#"#/.{0->"."}&[#/.{"."->0,"#"->1}]&
Kein Baum
quelle
1
Schön gemacht! Ich wusste nie über MorphologicalComponents[#, Method->"ConvexHull"] :) Sie können noch mehr Bytes sparen, indem Sie davon ausgehen, dass die Eingabe bereits in Zeichen aufgeteilt ist, und indem Sie auch ein 2D-Array von Zeichen zurückgeben.
Greg Martin
@ GregMartin, ich wusste nicht über diese Verwendung von MorphologicalComponentsentweder bis heute!
Kein Baum
Mathematica-Neuling hier: Wie soll ich diese Funktion aufrufen? Ich habe versucht, f[{"...",".#.","..."}]einige Fehler zu bekommen.
DLosc
@DLosc, Die Funktion ist das Ganze, nicht nur f. (Genau genommen ist es das Zeug nach dem Semikolon.) Um die Funktion aufzurufen, geben Sie das Ganze in ein Mathematica-Fenster ein, gefolgt von [Ihrer Eingabe, und ]so sollte es aussehen f@m_:=m(1-m[[2,2]]) . . . #/.{"."->0,"#"->1}]&[{"...", ".#.", "..."}](für Leerzeichen abgekürzt).
Kein Baum
@ DLosc Nun, das liegt daran, dass der Code kaputt ist. Ich denke, ich habe es jetzt behoben! (Ich habe keine Ahnung, was dort passiert ist; sorry ...)
Kein Baum
11

(Aber stimme der Lösung von Notatree zu , es ist besser!)

Mathematica, 168 Bytes

(x_~n~y_:=Min[Norm[x-#]&/@y];i=#;p=i~Position~#&;t=p["#"|"."]~Select~#&;(i~Part~##="o")&@@@t[#~n~t[ConvexHullMesh[Join[s=p@"#",#+{.1,.1}&/@s]]~RegionMember~#&]==1&];i)&

Reine Funktion, die ein 2D-Array von Zeichen als Eingabe verwendet und ein 2D-Array von Zeichen zurückgibt. Eine leichter lesbare Version:

1  (x_~n~y_ := Min[Norm[x - #] & /@ y];
2  i = #; p = i~Position~# &; 
3  t = p["#" | "."]~Select~# &;
4  (i~Part~## = "o") & @@@ 
5    t[#~n~
6      t[ConvexHullMesh[
7        Join[s = p@"#", # + {.1, .1} & /@ s]]
8      ~RegionMember~# &] == 1 &];
9  i) &

Linie 1 definiert eine Funktion n, die den (kleinsten) Abstand zwischen einem Punkt xin der Ebene und einer Menge yanderer Punkte erzeugt. Zeile 2 initialisiert die Variable ifür die Eingabe, um eine auftretende Mehrdeutigkeit später aufzulösen und sie zu ändern, um die endgültige Ausgabe zu erhalten. Zeile 2 definiert auch eine Funktion p, die die Koordinaten aller Vorkommen ihrer Eingabe in zurückgibt i.

In Zeile 3 wird p["#" | "."]jede einzelne Koordinate aus der Eingabekarte dargestellt (da alle ihre Zeichen entweder "#"oder sind "."). Dies tist auch eine Funktion, die nur die Koordinaten auswählt, die einer noch nicht festgelegten Eigenschaft entsprechen. In Zeile 4 i~Part~## = "o"wird eine Reihe von Einträgen für idas Zeichen geändert "o". Diese Zeichen werden aus dem Satz möglicher Koordinaten gemäß den Angaben in den Zeilen 5-8 ausgewählt. Und Zeile 9 gibt die Antwort nur zurück, wenn sie berechnet wurde.

Okay, Infrastruktur fertig, jetzt zur eigentlichen Berechnung. ConvexHullMeshist in Mathematica integriert, um die konvexe Hülle einer Menge von Punkten zu berechnen (das kleinste konvexe Polygon, das diese Punkte enthält). Moralisch gesehen sollte dies die Buchten und Fjorde der Insel "ausfüllen" s = p@"#", um sie von unserer Weltumsegelung auszuschließen. Es gibt ein kleines Problem, ConvexHullMeshwenn sich diese Punktmenge in einer Zeile befindet (danke, Testfall Nr. 2), das wir lösen, indem wir sin Zeile 7 eine leicht versetzte Version von an sich selbst anhängen . Diese Ausgabe ist ein Polygon, also Zeilen 7 -9 (t[...~RegionMember~# &]) erzeugt eine Liste der Punkte mit ganzzahligen Koordinaten in diesem Polygon. Schließlich berechnen die Linie 5 und das Ende der Linie 9 alle Punkte, die genau 1 (also nicht 0) von dieser Menge ganzzahliger Punkte entfernt sind. Diese Menge wird zum Umrundungspfad.

Unten finden Sie die Ausgabe für den großen Testfall unter dem Link des OP. Beachten Sie oben links, dass die ungewöhnliche Wahl zwischen West und Südwest darauf hindeutet, dass eine unsichtbare Neigungslinie -2/3 zwischen zwei Halbinseln abgeschattet wird (wobei das Liniensegment Teil der Grenze der konvexen Hülle ist).

........................
.............o..........
...........oo#ooooooo...
..........o#.#.##...#o..
........oo.#.#.###.##o..
.......o..########.##o..
.....oo...############o.
...oo#....############o.
..o#.###.##############o
.o##.##################o
.o####################o.
.o.##################.o.
.o##################..o.
.o..################..o.
o###################..o.
o#####################o.
o.##################.o..
o####################o..
o#...##############.o...
o##...#############o....
o#.....###....#oooo.....
.oooooo#ooooooo.........
.......o................
Greg Martin
quelle
Stellt Mathematica Zeichenfolgen normalerweise als 1D-Arrays von Zeichen dar? Wenn nicht, müssen Sie stattdessen ein 1D-Array von Strings nehmen / zurückgeben. (Ich freue mich auch auf die Erklärung! Ich glaube nicht, dass ich dies ausführen kann, ohne Mathematica zu haben, oder?)
DLosc
Mathematica hat einen String-Datentyp, aber es scheint, dass ein Array von Zeichen auch für die Zwecke dieser Site gültig ist (dh ich habe dies erfahren, als ich mit PPCG angefangen habe, aber ich vergesse die Rechtmäßigkeiten des Warum). Ja, leider ist Mathematica nicht kostenlos und daher für viele Menschen nicht zugänglich :(
Greg Martin
1
@ GregMartin Ich probiere Mathematica-Lösungen immer unter sandbox.open.wolframcloud.com
ovs
Derzeitiger Konsens besagt, dass Listen von Einzelzeichenfolgen nicht anstelle einer Zeichenfolge verwendet werden können. Soweit ich das beurteilen kann, sind die "Zeichen" in Mathematica wie in Python nur einzelne Zeichenfolgen. In einer Sprache wie Java, die einen eigenen charTyp hat, ist die Situation anders . In diesem Fall charkönnte ein Array anstelle einer Zeichenfolge verwendet werden.
DLosc
1
So lese ich es: Die wichtigste hochgeladene Antwort wurde im Jahr 2014 veröffentlicht. Die von mir verknüpfte Antwort wurde im Jahr 2016 veröffentlicht, um die Mehrdeutigkeit in der vorherigen Antwort zu klären. Ich habe die negative Bewertung der neueren Antwort gelesen, als die Leute sagten: "Nein, wir wollen nicht, dass die ältere Antwort bedeutet, dass Listen mit einzelnen Zeichenfolgen in Ordnung sind." Unabhängig vom Meta lasse ich Listen mit einzelnen Zeichenfolgen in dieser Frage nicht zu (und habe den Wortlaut präzisiert, um dies widerzuspiegeln).
DLosc
10

Python 3, 779 Bytes (Einrücken mit Tabulatoren)

Das ist das ganze Programm. Es liest die Eingabe von stdin und druckt sie nach stdout. Stdin muss mit EOF enden. Beispiellauf mit der großen Eingabe: https://ideone.com/XIfYY0

import itertools,sys
L=list
C=itertools.count
d=L(map(L,filter(None,sys.stdin.read().split('\n'))))
X=len(d[0])
Y=len(d)
R=range
def P(r):return all(d[y][x]=='.'for x,y in r)
def S(f):
    for n in C(0):
        if P(f(n)):l=n
        else:break
    for n in C(l+1):
        if P(f(n)):return l,n
def f(V,a,*b):return L(eval('lambda '+a+':('+i+')',V)for i in b)
V=locals()
def D(n):
    y=min(n,Y-1);x=n-y
    while y>=0and x<X:yield(x,y);x+=1;y-=1
def E(n):
    x=max(0,n-Y);y=x+Y-n
    while y<Y and x<X:yield(x,y);x+=1;y+=1
F=f(V,'p','(p,y)for y in R(0,Y)','(x,p)for x in R(0,X)')+[D,E]
r=f(V,'x,y','x','y','x+y','x-y+Y')
B=L(map(S,F))
for x in R(0,X):
    for y in R(0,Y):
        z=L(zip(r,B))
        if all(g(x,y)in R(a,b+1)for g,(a,b)in z)and any(g(x,y)in e for g,e in z):d[y][x]='o'
print('\n'.join(''.join(x)for x in d))

Die Idee ist einfach: Sie berechnet kleinste achteckige Grenzen und zeichnet Zellen, die sich innerhalb aller berechneten Grenzen befinden und mindestens eine der Kanten schneiden.

Lera
quelle
1
Sie müssen nicht wirklich sys.stdinals Eingabe verwenden. input(), immer mehrzeilig würde die Arbeit erledigen und weniger Bytes kosten
Dead Possum
2
R(0,x)R(x)
Kann
+1 für die Nichtverwendung eines eingebauten.
Robert Fraser
1
Nett! Noch ein paar Golftipps: Speichern Sie jeweils 5 Bytes, indem Sie Lambdas verwenden, um Pund zu definieren f. L(generator expression)=> [generator expression]; F, rUnd Berscheint nur einmal pro Person und damit inlined werden können verwendet werden.
DLosc
8

JavaScript (ES6), 369 343 Byte

f=s=>(a=s.split`
`.map(s=>[...s]),m=Array(8),a.map((b,i)=>b.map((c,j)=>c>'#'||[i-j,i,j+i,j,j-i,-i,-i-j,-j].map((d,k)=>d>m[k]||(m[k]=d-1)))),[o,p,q,r,t,u,v,w]=m,g=(i,j,k,l,...p)=>i-k|j-l?a[i][j]=g(i+(k>i)-(k<i),j+(l>j)-(l<j),k,l,...p):1/p[0]?g(k,l,...p):'o',g(p,p-o,p,q-p,q-r,r,r-t,r,-u,t-u,-u,u-v,w-v,-w,o-w,-w,p,p-o),a.map(b=>b.join``).join`
`)

Erläuterung: Die Zeichenfolge ist in ein Zeichenarray aufgeteilt (mir ist nicht klar, ob die Eingabe eines Zeichenarrays zulässig ist). Das Array wird dann durchlaufen und die Positionen aller Landfelder werden lokalisiert. Die Begrenzungslinien durch die Gleichungen x - y = o, x = p, x + y = q, y = r, y - x = t, -x = u, -x - y = v, -y = wsind so festgelegt , dass die maximal möglichen Parameter in dem alle über die Linie des Land liegt gewählt wird. Dies hat den Effekt, dass die Insel in einem Achteck eingeschlossen wird. Die Koordinaten der Ecken des Achtecks ​​werden leicht aus den Parametern berechnet und die Zellen an seinem Rand werden ausgefüllt. Das Array wird dann wieder zu einer Zeichenfolge verbunden. Der Grund, warum ein Achteck ausreicht, ist folgender:

   /o#     /o#     /o#
 |/o #   |/o #   |/ o#
 *o###   * o #   *  o#
/|o #   /|o #   /| o#
 |o#     |o#     |o#

Betrachten Sie eine Ecke des Achtecks. Irgendwann entlang der beiden Kanten wird der Pfad durch das Land begrenzt, da wir das Achteck so konstruiert haben, dass es das Land so genau wie möglich berührt. Wenn sich an der Ecke selbst kein Land befindet, kann der Pfad die rechts gezeigten alternativen Routen nehmen, aber das ist immer noch die gleiche Anzahl von orthogonalen und diagonalen Schritten, sodass der Abstand unverändert bleibt.

Neil
quelle
Was macht ´ ... p´?
Robert Fraser
@RobertFraser Der technische Name ist Array Destructuring. In diesem Fall handelt es sich jedoch nur um einen rest of argumentsParameter.
Neil
@Neil Eigentlich ist der technische Name Rest Parameter . Dieselbe Syntax wird für den Spread-Operator verwendet . (Sie verwenden beides wie ...pan verschiedenen Orten.) Die Destrukturierung ist etwas anderes (obwohl der Spread-Operator bei der Destrukturierung verwendet werden kann).
Brian McCutchon
@BrianMcCutchon Du hast recht, ich meinte den Spread-Operator, aber die Destrukturierung funktioniert trotzdem in Argumentlisten.
Neil
6

Python 3.5, 224, 263, 234 218 Bytes

Weitere 16 Bytes wurden entfernt, indem die verschachtelte Funktion entfernt und ein Einzeiler daraus gemacht wurde.

def h(s,k=0,i=0):w=s.find('\n')+1;x=s.find('X')-w;k=k or x;d=[1,w+1,w,w-1,-1,-w-1,-w,-w+1]*2;u=s[:k]+'o'+s[k+1:];return['X'>s[k]and i<8and(h(u,k+d[i+2],i+2)or h(u,k+d[i+1],i+1)or h(u,k+d[i],i))or'',s][s[k]>'X'and k==x]

Ab 29 Bytes gespielt:

def f(s):
 w=s.find('\n')+1;x=s.find('X')-w;d=[1,w+1,w,w-1,-1,-w-1,-w,-w+1]*2
 def h(s,k,i):u=s[:k]+'o'+s[k+1:];return['X'>s[k]and i<8and(h(u,k+d[i+2],i+2)or h(u,k+d[i+1],i+1)or h(u,k+d[i],i))or'',s][s[k]>'X'and k==x]
 return h(s,x,0)

Die Eingabe ist eine einzelne Zeichenfolge mit '~' für Ozean, 'X' für Land und 'o' für die Grenze. (Mit 'X' wird ein Byte für '>' anstelle von '==' gespeichert.)

Weniger Golf Version mit Kommentaren:

def f(s):
    w=s.find('\n')+1                         # width of one row
    x=s.find('X')-w                          # starting point
    d=[1,w+1,w,w-1,-1,-w-1,-w,-w+1]*2        # delta to add to current index to move in 
                                             # the 8 directions: E, SE, S, SW, W, NW, 
                                             # N, NE. Make it long to avoid
                                             # lots of modulo operations in 
                                             #    the recursive calls

    def h(s,k,i):                            # s is the island string, k the current
                                             # position, i the direction index
        if s[k]>'X'and k==x:                 # if back at the begining,
            return s                         #   return the map

        elif 'X'>s[k] and i<8:               # if there is water here, and haven't
                                             #  looped around,
            u=s[:k]+'o'+s[k+1:]              #  make a new map with an 'o' in the 
                                             #  current spot

            r = h(u,k+d[i+2],i+2)            # try a 90 degree right turn
            if r: return r

            r = h(u,k+d[i+1],i+1)            # try a 45 degree turn
            if r: return r

            r= h(u,k+d[i],i)                 # try straight ahead
            if r: return r

        return ''                            # this path failed

    return h(s,x,0)
RootTwo
quelle
@ DLosc behoben. (
Soll
Nett! (Ja, Sie sollten die alte Antwort entfernen - wenn jemand sie sehen möchte, kann er sich den Revisionsverlauf des
Posts ansehen
5

C # 7 - 414 369 327 Bytes

Edit : auf 1D-Looping, Computing iund jOn-the-Fly umgestellt

Bearbeiten : Die Eingabemethode wurde geändert, die Nachschlagetabelle reduziert und zu genau definierten Anfangsgrenzen gewechselt ... und der sinnlose Raum in der letzten äußeren for-Schleife entfernt

using C=System.Console;class P{static void Main(){var D=C.In.ReadToEnd().Replace("\r","");int W=D.IndexOf('\n')+1,H=D.Length,z=H,k,q,c;int P()=>z%W*(k%3-1)+z/W*(k/3-1)+H;var B=new int[9];for(;z-->0;)for(k=9;k-->0&D[z]%7<1;)if(B[k]<=P())B[k]=P()+1;for(;++z<H;C.Write(q>9?'o':D[z]))for(q=k=9;k-->0;)q*=(c=P()-B[k])>0?0:c<0?1:2;}}

Probieren Sie es online

Das Gesamtprogramm, nimmt die Eingabe zu Standard in, druckt er auf die Standardausgabe, Anwendungen #, .und o. Für jede Zelle wird ein 'Profil' berechnet (dies ist die Entfernung in 8 Richtungen (dies scheint aus praktischen Gründen eine Neunte zu sein, dies ist jedoch immer der Fall 0), und es wird jeweils ein Maximum von jeder dieser Zellen aufgezeichnet. Anschließend wird die gesamte Karte geschrieben Ersetzt jede Zelle, die sich an einer Grenze befindet und nicht außerhalb einer Zelle, durch ein 'o'. Der unten stehende kommentierte Code erklärt, wie alles funktioniert.

Gemäß meiner Antwort auf Save the Geese from Extinction ergibt dies das kleinste Achteck (gültige Umrundung mit der größten Fläche), das die Insel begrenzt.

Hinweis : Ich verwende zum ersten Mal in meinem Leben etwas aus dem aktuellen Jahrzehnt, und für das Kompilieren dieses Codes ist C # 7 erforderlich. Wenn Sie nicht über C # 7 verfügen, muss eine Zeile ersetzt werden, die im Code deutlich gekennzeichnet ist.

Beispielverwendung und Ausgabe:

type t7.txt | IslandGolf1.exe

.........ooooooooooo....
........o....#......o...
.......o...#.#.##...#o..
......o....#.#.###.##.o.
.....o....########.##..o
....o.....############.o
...o.#....############.o
..o#.###.##############o
.o##.##################o
o.####################.o
o..##################..o
o.##################...o
o...################...o
o###################...o
o#####################.o
o.##################..o.
o####################o..
o#...##############.o...
o##...#############o....
o#.....###....#...o.....
.o.....#.........o......
..ooooooooooooooo.......

Formatierter und kommentierter Code:

using C=System.Console;

class P
{
    static void Main()
    {
        // \n 10
        // # 35
        // . 46
        // o 111


        var D=C.In.ReadToEnd().Replace("\r",""); // map

        int W=D.IndexOf('\n')+1, // width
            H=D.Length, // length
            z=H, // position in map (decomposed into i and j by and for P)
            k, // bound index
            q, // bound distance, and later cell condition (0 -> outside, 8 -> inside, >8 -> on boudary)
            c; // (free), comparison store

        // 'indexes' into a profile for the point z at index k
        // effectively {i=z%W,j=z/W,-i,-j,i+j,j-i,-i-j,i-j,0}[k] (inside order is a bit different) (0 const is always treated as 'inside bounds')
        // each non-zero-const entry describes the distance in one of the 8 directions: we want to maximise these to find the 'outer bounds'
        // the non-zero-const bounds describe 8 lines, together an octogen
        int P()=>z%W*(k%3-1)+z/W*(k/3-1)+H; // new C#7 local method syntax (if you don't have C#7, you can test this code with the line below instead)
        //k=0;System.Func<int>P=()=>z%W*(k%3-1)+z/W*(k/3-1)+H; // old lambda syntax (must pre-assign k to make static checker happy)

        var B=new int[9]; // our current bounds, each is initially null (must only call P() when on a #)
        // B[k] starts off a 0, P() has a +H term, and W+(H/W)<H for W >= 3, so B[k] is assigned the first time we compare it (H-i-j always > 0)

        for(;z-->0;) // for each cell
            for(k=9;k-->0& // for each bound
                D[z]%7<1;) // if this cell is #
                if(B[k]<=P())B[k]=P()+1; // update bound if necessary (add one so that we define the bound _outside_ the hashes)
        // z=-1
        for(;++z<H; // for each cell
                C.Write(q>9?'o':D[z])) // print the cell (if q > 9, then we are on the bounds, otherwise, spit out whatever we were before)
            // check we are not 'outside' any of the bounds, and that we are 'on' atleast one of them
            for(q=k=9;k-->0;) // for each bound
                q*=(c=P()-B[k])>0?0: // outside bound (q=0)    (??0 is cheaper than (int) or .Value)
                    c<0?1: // inside (preserve q)
                    2; // on bound (if q != 0, then q becomes > 9)
    }
}
VisualMelon
quelle
größtes Achteck? oder kleinste?
Sarge Borsch
@SargeBorsch danke, korrigiert den Text.
VisualMelon