^{To pierwszy z serii wyzwań Island Golf. Następne wyzwanie}

Biorąc pod uwagę wyspę w sztuce ASCII, wygeneruj optymalną ścieżkę do jej opłynięcia.

Wejście

Twój wkład będzie w prostokątną siatkę składającą się z dwóch znaków reprezentujących ląd i wodę. W poniższych przykładach ziemia jest #i woda jest ., ale możesz zastąpić dowolne dwa różne znaki, które chcesz.

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

Zawsze będzie co najmniej jeden żeton ziemi. Wszystkie kafelki ziemi będą sąsiadować (tzn. Jest tylko jedna wyspa). Płytki wodne również będą przylegające (tj. Nie będzie żadnych jezior). Zewnętrzna krawędź siatki będzie stanowić płytki wodne. Kafelki lądowe nie zostaną połączone po przekątnej: tzn. Nigdy nie zobaczysz czegoś takiego

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

Wynik

Twój kod musi generować tę samą siatkę, z narysowanym najkrótszym okrążeniem . W poniższych przykładach narysowano ścieżkę dookoła o, ale możesz zastąpić dowolną postać, o ile różni się ona od twoich postaci lądowych i wodnych.

Opłynięcie jest prosta krzywa zamknięta, sporządzony wyłącznie na płytki wodnych, które całkowicie otacza wszystkie płytki wylądować na siatce. Połączenia ukośne są dozwolone. Na przykład jest to opłynięcie powyższej wyspy (ale nie najkrótszej):

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

Długość okrążenia oblicza się w następujący sposób: Dla każdej pary sąsiadujących ze sobą płytek na ścieżce, jeśli są one połączone poziomo lub pionowo, dodaj 1; jeśli są połączone po przekątnej, dodaj √2. Długość powyższej ścieżki wynosi 22 + 7√2 (≈ 31,9).

Najkrótsza opłynięcie jest opłynięcie z najkrótszym długości. Twój program powinien wypisać dowolną ścieżkę, która spełnia ten warunek. W przypadku większości wysp istnieje wiele możliwych rozwiązań. Oto jedno rozwiązanie dla powyższej wyspy o długości 10 + 13√2 (≈ 28,4):

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

Detale

Twoje rozwiązanie może być pełnym programem lub funkcją . Każda z domyślnych metod wejścia i wyjścia jest akceptowalna.

Dane wejściowe i wyjściowe mogą być ciągiem wieloliniowym lub listą ciągów. Jeśli twój język ma inny typ znaków niż ciągi jednoznakowe, możesz zastąpić „listę znaków” wyrazem „ciąg” w poprzednim zdaniu. Jeśli twój język musi wprowadzić wysokość i / lub szerokość siatki, możesz to zrobić. Twój wynik może (opcjonalnie) mieć jeden końcowy znak nowej linii. Jak wspomniano powyżej, możesz użyć dowolnych trzech różnych znaków zamiast #.o(w zgłoszeniu określ, których znaków używasz).

Przypadki testowe

A. Wyspy z unikalnymi najkrótszymi opłynięciami:

...
.#.
...

.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. Przykład wyspy z wieloma możliwymi rozwiązaniami:

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

Możliwe wyniki:

....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. Duży przypadek testowy jako Gist

To jest golf-golf : wygrywa najkrótszy kod w każdym języku.

Mathematica (wersja 9), 165 bajtów

Ładna, krótka ConvexHullMeshfunkcja, której używał Greg Martin, została wprowadzona tylko w wersji Mathematica 10, więc pomyślałem, że spróbuję bez niej, używając mojej starożytnej wersji Mathematica 9. Udało mi się jednak nieco ją skrócić! Jest to funkcja, która przyjmuje i zwraca listę łańcuchów (z ., #i ojako symbole).

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

Wyjaśnienie:

• Najpierw Characters@# /. {"."->0, "#"->1}zamienia dane wejściowe na macierz 0s i 1s.
• "o"MorphologicalTransform[MorphologicalComponents[#,Method->"ConvexHull"],Max[#(1-#[[2,2]])CrossMatrix@1]&]+"#"#następnie wykorzystuje potężne (ale wyjątkowo duże bajt…) możliwości przetwarzania obrazu Mathematiki, aby najpierw wypełnić wypukły kadłub wyspy (taki kształt uzyskałbyś, gdybyś rozciągnął wokół niego kawałek sznurka), a następnie wyznaczył granicę. Następnie mnożymy tę macierz przez ciąg, "o"aby uzyskać macierz 0s i "o"s (dzięki imponującej zdolności Mathematica do dostosowywania typów), i dodajemy to do "#"macierzy wyspy.
• Na koniec ""<>#& /@ (... /. {0->"."})zamienia tę macierz "o"s, "#"si 0na macierz "o"s, "#"si "."i łączy każdy wiersz w ciąg.

Kiedy testujemy to na przykładzie B , otrzymujemy wynik

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

[Edytuj, dzięki Gregowi Martinowi:] Jeśli wolno nam używać tablic znaków zamiast list ciągów, możemy przyciąć to do 144 bajtów:

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

(Ale przejdź do rozwiązania Notatree , lepiej!)

Mathematica, 168 bajtów

(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)&

Czysta funkcja przyjmująca tablicę znaków 2D jako dane wejściowe i zwracająca tablicę znaków 2D. Wersja łatwiejsza do odczytania:

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

Linia 1 definiuje funkcję, nktóra wytwarza (najmniejszą) odległość między punktem xna płaszczyźnie a zestawem yinnych punktów. Wiersz 2 inicjuje zmienną ina wejściu, zarówno w celu późniejszego rozwiązania niejednoznaczności curry, jak i możliwości modyfikacji jej w celu uzyskania ostatecznego wyniku; wiersz 2 definiuje również funkcję, pktóra zwraca współrzędne wszystkich wystąpień jej wejścia i.

W linii 3 p["#" | "."]reprezentuje każdą współrzędną z mapy wejściowej (ponieważ wszystkie jej znaki są albo "#"albo "."), więc tjest funkcją, która wybiera tylko te współrzędne, które spełniają jeszcze nieokreśloną właściwość. W wierszu 4 i~Part~## = "o"zmienią kilka wpisów ipostaci "o"; znaki te zostaną wybrane z zestawu możliwych współrzędnych zgodnie z materiałami w liniach 5-8. A linia 9 po prostu zwraca odpowiedź po jej obliczeniu.

Dobra, infrastruktura zakończona, teraz do faktycznego obliczenia. ConvexHullMeshjest wbudowanym programem Mathematica do obliczania wypukłego kadłuba zestawu punktów (najmniejszego wypukłego wielokąta zawierającego te punkty). Moralnie rzecz biorąc, powinno to „wypełnić” zatoczki i fiordy wyspy (która jest s = p@"#"), aby wykluczyć je z naszej cykli nawigacji. Jest mały problem z ConvexHullMeshtym, kiedy ten zestaw punktów jest w linii (dziękuję, przypadek testowy nr 2), który rozwiązujemy, dodając nieco przesuniętą wersję sdo siebie w linii 7. To wyjście jest wielokątem, więc linie 7 -9 (t[...~RegionMember~# &]) tworzy listę punktów o współrzędnych całkowitych w tym wielokącie. Wreszcie, linia 5 i koniec linii 9 obliczają wszystkie punkty, które znajdują się w odległości dokładnie 1 (stąd nie 0) od tego zestawu punktów całkowitych; ten zestaw staje się ścieżką okrężną.

Poniżej znajduje się wynik dla dużego przypadku testowego na łączu PO. Zwróć uwagę na lewy górny róg, niezwykłe wybory, kiedy wybrać się na zachód, a na południowy zachód, wskazując na fakt, że zasłania niewidzialną linię nachylenia -2/3 między dwoma półwyspami (wspomniany odcinek linii jest częścią granicy wypukłego kadłuba).

........................
.............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 bajtów (wcięcie za pomocą tabulatorów)

To jest cały program. Odczytuje dane wejściowe ze standardowego wejścia i drukuje je na standardowe wyjście. Stdin musi kończyć się EOF. Przykład uruchom z dużym wejściem: 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))

Pomysł jest prosty: oblicza najmniejsze ośmiokątne granice i rysuje komórki, które znajdują się we wszystkich obliczonych granicach i przecinają co najmniej jedną krawędź.

JavaScript (ES6), 369 343 bajtów

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

Objaśnienie: Łańcuch jest podzielony na tablicę znaków (nie jestem pewien, czy dane wejściowe z tablicy znaków są dopuszczalne). Tablica jest następnie iterowana i lokalizowane są pozycje wszystkich kwadratów ziemi. Linie ograniczające podane przez równania x - y = o, x = p, x + y = q, y = r, y - x = t, -x = u, -x - y = v, -y = wsą określone tak, że maksymalny możliwy parametr jest wybrany, gdzie wszystkie kłamstwa ziemi poza linię. To powoduje zamknięcie wyspy w ośmiokącie. Współrzędne narożników ośmiokąta są łatwo obliczane na podstawie parametrów, a komórki na jego krawędzi są wypełniane. Tablica jest następnie ponownie łączona w ciąg. Powód, dla którego wystarczy ośmiokąt, jest następujący:

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

Rozważ narożnik ośmiokąta. W pewnym momencie wzdłuż dwóch krawędzi ścieżka będzie ograniczona przez ląd, ponieważ zbudowaliśmy ośmiokąt tak, aby dotykał ziemi tak blisko, jak to możliwe. Jeśli w samym rogu nie ma ziemi, ścieżka może obrać alternatywne trasy, jak pokazano po prawej stronie, ale nadal jest to ta sama liczba kroków ortogonalnych i ukośnych, więc odległość pozostaje niezmieniona.

Python 3.5, 224, 263, 234 218 bajtów

Grał w golfa o kolejne 16 bajtów, pozbywając się funkcji zagnieżdżonej i czyniąc ją jednowierszową.

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]

Gra w golfa poza 29 bajtami:

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)

Dane wejściowe to pojedynczy ciąg znaków używający „~” dla oceanu, „X” dla lądu i „o” dla granicy. (Użycie „X” zapisuje bajt dla „>” zamiast „==”)

Wersja mniej golfowa z komentarzami:

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 bajtów

Edycja : przełączono na pętlę 1D, przetwarzanie ii jw locie

Edycja : zmieniono metodę wprowadzania, zwiniętą tabelę wyszukiwania i przełączono na dobrze zdefiniowane początkowe granice ... i usunięto niepotrzebne miejsce w ostatniej zewnętrznej pętli for

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

Wypróbuj online

Kompletny program, bierze wkład standard w drukuje go na standardowe wyjście, zastosowań #, .oraz o. Dla każdej komórki oblicza „profil” (czyli odległość w 8 kierunkach (dla wygody wydaje się, że jest to dziewiąta, ale zawsze tak jest 0), i zapisuje maksimum każdego z nich. Następnie zapisuje całą mapę ponownie i zastępuje każdą komórkę, która jest zarówno na granicy, jak i poza nią, znakiem „o”. Skomentowany kod poniżej wyjaśnia, jak to wszystko działa.

Zgodnie z moją odpowiedzią „Uratuj gęsi przed wyginięciem” daje to najmniejszy ośmiokąt (ważne okrążenie z największym obszarem), który ogranicza wyspę.

Uwaga : raz w życiu używam czegoś z obecnej dekady, a ten kod wymaga kompilacji w C # 7. Jeśli nie masz C # 7, jest jeden wiersz, który będzie musiał zostać zastąpiony, co jest wyraźnie zaznaczone w kodzie.

Przykładowe użycie i dane wyjściowe:

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

Sformatowany i skomentowany kod:

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