^{Jest to drugi z serii wyzwań Island Golf. Poprzednie wyzwanie}

Dwóch pustelników przybyło na bezludną wyspę. Odkąd przybyli szukając samotności, chcą żyć jak najdalej od siebie. Gdzie powinni budować swoje chaty, aby zmaksymalizować odległość między nimi?

Powiązane czytanie

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ędą co najmniej dwie płytki lądu. 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 wyświetlać tę samą siatkę z zaznaczonymi dwoma lokalizacjami chaty . W poniższych przykładach lokalizacje chat są oznaczone X, ale możesz zastąpić dowolną postać, o ile różni się ona od twoich postaci lądowych i wodnych.

Lokalizacje chat muszą składać się z dwóch pól ziemi, wybranych tak, aby zmaksymalizować odległość między nimi. Definiujemy odległość marszu jako długość najkrótszej ścieżki, całkowicie na lądzie, między dwoma punktami. Płytki lądowe uważa się za sąsiadujące poziomo lub pionowo, ale nie po przekątnej.

Możliwe rozwiązanie dla powyższej wyspy:

...........
...X#......
..#####....
..#######..
.#########.
...#######.
...#####.X.
....####...
...........

Odległość między tymi dwoma punktami wynosi 11, co jest największą odległością między dowolnymi dwoma punktami na tej wyspie. Istnieje inne rozwiązanie odległości 11:

...........
...##......
..X####....
..#######..
.#########.
...#######.
...#####.X.
....####...
...........

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 wielowierszowym, listą ciągów lub tablicą 2D / zagnieżdżoną listą znaków / ciągami jednoznakowymi. 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 #.X(w zgłoszeniu określ, których znaków używasz).

Przypadki testowe

A. Wyspy z wyjątkowymi miejscami w chatach:

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

....
.XX.
....

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

......
......
..X#..
...X..
......
......

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

........
.#####..
.##..##.
.#..###.
.#X..#X.
........

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

.........
.#####.X.
.#...#.#.
.#.X##.#.
.#.....#.
.#######.
.........

B. Przykład wyspy z wieloma możliwymi rozwiązaniami:

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

Możliwe wyniki:

........
....#X..
...####.
..###...
.#####..
.X####..
..##....
........

........
....#X..
...####.
..###...
.#####..
.#####..
..X#....
........

........
....##..
...###X.
..###...
.#####..
.X####..
..##....
........

........
....##..
...###X.
..###...
.#####..
.#####..
..X#....
........

C. Duży przypadek testowy jako Gist

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

Python 3, 249 246 bajtów

Ogolono 3 bajty, dzięki DLosc.

Dane wejściowe i wyjściowe są pojedynczymi ciągami, gdzie „.”, „@” I „X” oznaczają odpowiednio wodę, chaty i ziemię.

A='@'
def f(s):
 w=s.find('\n')+1;d=u={(k,k):0for k,c in enumerate(s)if A<c}
 while u:d.update(u);u={(k,j):d[(k,i)]+1for k,i in d for j in{i+1,i+w,i-1,i-w}if A<s[j]and(k,j)not in d}
 k,j=sorted(max(d,key=d.get))
 return s[:k]+A+s[k+1:j]+A+s[j+1:]

Poprzednia wersja:

Dane wejściowe to pojedynczy ciąg znaków z „.” i „#” reprezentujące odpowiednio wodę i ziemię. „X” oznacza chaty na wyjściu.

def f(s):
 w=s.find('\n')+1;d=u={(k,k):0for k,c in enumerate(s)if'#'==c}
 while u:d.update(u);u={(k,j):d[(k,i)]+1 for k,i in d for j in{i+1,i+w,i-1,i-w}if'#'==s[j]and(k,j)not in d}
 k,j=sorted(max(d,key=d.get))
 return s[:k]+'X'+s[k+1:j]+'X'+s[j+1:]

Wyjaśnienie:

Zasadniczo wykonuje szerokie pierwsze wyszukiwanie z każdego możliwego punktu początkowego w tym samym czasie. Prowadź słownik d długości ścieżek wpisanych na początku i na końcu ścieżki, np. D [(k, i)] to odległość od k do i. Następnie iteruj po klawiszach w słowniku d i utwórz nowy słownik, u, ze ścieżkami dłuższymi o 1 jednostkę, przesuwając jednostkę punktu końcowego 1 do N, S, E, W, np. U [(k, i + 1)] = d [(k, i)] + 1. Nie dołączaj ścieżek, które są już w d. Jeśli u nie jest puste, dodaj nowe dłuższe ścieżki do d i powtórz. Kiedy u jest pusty, oznacza to, że nie można już utworzyć ścieżek. Teraz d zawiera wszystkie możliwe ścieżki i ich długości. Więc to tylko kwestia zdobycia klucza najdłuższą ścieżką.

Wersja mniej golfowa, komentowana:

def f(s):
  w=s.find('\n')+1                    # width of a row, or a move N or S

  d = {}                              # dictionary of all the paths.
                                      # The key is a tuple (k,j) and the
                                      # value is the distance from k to j.
  for k,c in enumerate(s):            # Initialize. Distance from k to k is 0
    if'#'==c:                         # Only do land.
      d[(k,k)] = 0

  u = d                               # dictionary of new paths. initialize it to d
                                      # so loop is entered. first d.update is
                                      # basically a NOP

  while u:                            # while there are new paths
    d.update(u)                       # add the new paths to the dict of old paths
    u={}                              #
    for k,i in d:                     # iterate over the known paths. k is the start, i is the end
      for j in{i+1,i+w,i-1,i-w}:      # iterate over squares 1 move to the E,S,W,N from i
        if'#'==s[j]and(k,j)not in d:  # if it's still land, and the path (k,j) isn't already in d,
          u[(k,j)] = d[(k,i)]+1       # then add the new path to u

  k,j=sorted(max(d,key=d.get))        # find the longest path

  return s[:k]+'X'+s[k+1:j]+'X'+s[j+1:]  # X marks the endpoints.

C #, 387 bajtów

Zacznijmy...

using C=System.Console;class P{static void Main(){string D="",L;int W=0,H=0,z,n,q,h,b=0,c,a,i=0,j=0;for(;(L=C.ReadLine())!=null;H+=W=L.Length)D+=L+="\n";for(z=H;z-->0;){int[]S=new int[H],Q=new int[H*8];for(Q[h=q=0]=z;q<=h;)if((c=S[n=Q[q++]]-1)<0&D[S[n]=n]==35)for(a=4;a-->0;b=c<b?c+(i=z)*(j=n)*0:b)S[Q[++h]=new[]{1,-1,W,-W}[a]+n]=S[Q[h]]<1?c:1;}for(;++z<H;)C.Write(z==i|z==j?'X':D[z]);}}

Wypróbuj online

Kompletny program, odczytuje ze STDIN, pisze do STDOUT. Po prostu przechodzi przez każdą komórkę i uruchamia BFS, aby obliczyć najdalszą komórkę, rejestrując oba, jeśli jest ona najdalej zapisana. Naprawdę nic, a frustrująco mało mogę znaleźć w golfa.

Sformatowany i skomentowany kod:

using C=System.Console;

class P
{
    // \n 10
    // \r 13
    // . 46
    // # 35
    // x 88

    static void Main()
    {
        string D="", // map
            L; // line of input

        int W=0, // width
            H=0, // length
            z, // outer position
            n, // next position to expand
            q, // queue position pointer
            h, // queue head pointer
            b=0, // best
            c, // distance to this cell (negative)
            a, // counter
            i=0, // hermit 1 pos
            j=0; // hermit 2 pos

        for(;(L=C.ReadLine())!=null; // read a line, while we can
                H+=W=L.Length) // record the width, and add to length
            D+=L+="\n"; // add a newline, and add the line to the map

        for(z=H;z-->0;) // for each cell
        {
            int[]S=new int[H], // 'seen' >0 -> seen, else it is the distance we have found to it
                Q=new int[H*8]; // due queue (fewer than H*4 expantions, two ints each)

            // standard BFS
            for(Q[h=q=0] // reset currect 
                =z; // expand z first
                q<=h;)
                if((c=S[n=Q[q++]]-1)<0& // record 'seen', and check we havn't been seen
                    D[S[n]=n]==35) // mark as seen, and check we are a hash #
                    // 'move'
                    for(a=4;a-->0; // for each of the 4 neighbours
                            b=c<b? // if we have beaten the best
                            c+(i=z)*(j=n)*0: // set new best, record hermit positions
                            b)
                        S[Q[++h]=new[]{1,-1,W,-W}[a]+n]= // queue it for expantion
                        S[Q[h]]<1? // not seen? (this is BFS, don't need to check c is less thatn S[l+n]
                        c: // distance
                        1; // mark as seen (means it won't actually be expanded)
        }

        // z = -1
        for(;++z<H;) // for each cell
            C.Write(z==i|z==j?'X':D[z]); // print either the original char, or X if it is a hermit's home
    }
}