^{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 Code-Golf : Der kürzeste Code in jeder Sprache gewinnt.

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}]&

(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................

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.

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.

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)

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)
    }
}