^{Il s'agit du deuxième d'une série de défis Island Golf. Défi précédent}

Deux ermites sont arrivés sur une île déserte. Depuis qu'ils sont venus chercher la solitude, ils souhaitent vivre le plus loin possible les uns des autres. Où devraient-ils construire leurs huttes pour maximiser la distance de marche entre eux?

Lecture connexe

Contribution

Votre entrée sera une grille rectangulaire composée de deux caractères, représentant la terre et l'eau. Dans les exemples ci-dessous, la terre est #et l'eau l'est ., mais vous pouvez remplacer les deux caractères distincts que vous souhaitez.

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

Il y aura toujours au moins deux tuiles de terrain. Les tuiles de terre seront toutes contiguës (c'est-à-dire qu'il n'y a qu'une seule île). Les tuiles d'eau seront également contiguës (c'est-à-dire qu'il n'y a pas de lacs). La bordure extérieure de la grille sera toutes des tuiles d'eau. Les tuiles de terre ne seront pas connectées en diagonale: c'est-à-dire que vous ne verrez jamais quelque chose comme

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

Production

Votre code doit sortir la même grille, avec deux emplacements de cabane marqués dessus. Dans les exemples ci-dessous, les emplacements des cabanes sont marqués d'un X, mais vous pouvez remplacer n'importe quel caractère tant qu'il est distinct de vos personnages terrestres et aquatiques.

Les emplacements des cabanes doivent être constitués de deux tuiles terrestres, choisies de manière à maximiser la distance de marche entre elles. Nous définissons la distance de marche comme la longueur du chemin le plus court, entièrement terrestre, entre les deux points. Les tuiles de terre sont considérées adjacentes horizontalement ou verticalement, mais pas en diagonale.

Une solution possible pour l'île ci-dessus:

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

La distance de marche entre ces deux points est de 11, ce qui est la plus grande distance entre deux points sur cette île. Il existe une autre solution à distance 11:

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

Détails

Votre solution peut être un programme complet ou une fonction . Toutes les méthodes d'entrée et de sortie par défaut sont acceptables.

Vos entrées et sorties peuvent être une chaîne multiligne, une liste de chaînes ou un tableau 2D / liste imbriquée de caractères / chaînes à un seul caractère. Votre sortie peut (facultativement) avoir une seule nouvelle ligne de fin. Comme mentionné ci-dessus, vous pouvez utiliser trois caractères distincts à la place de #.X(veuillez spécifier dans votre soumission les caractères que vous utilisez).

Cas de test

A. Îles avec des emplacements de cabane uniques:

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

....
.XX.
....

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

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

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

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

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

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

B. Exemple d'une île avec plusieurs solutions possibles:

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

Sorties possibles:

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

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

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

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

C. Grand cas de test comme un Gist

C'est le code-golf : le code le plus court dans chaque langue gagne.

Python 3, 249 246 octets

Rasé de 3 octets, merci DLosc.

L'entrée et la sortie sont des chaînes simples, avec '.', '@' Et 'X' représentant respectivement l'eau, les huttes et la terre.

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:]

Version antérieure:

L'entrée est une chaîne unique, avec '.' et «#» représentant respectivement l'eau et la terre. «X» représente les cases dans la sortie.

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:]

Explication:

Il s'agit essentiellement d'une première recherche étendue à partir de tous les points de départ possibles en même temps. Conservez un dictionnaire, d, de longueurs de chemin codées par le début et la fin du chemin, par exemple, d [(k, i)] est la distance de k à i. Ensuite, parcourez les clés du dictionnaire, d, et créez un nouveau dictionnaire, u, avec des chemins de 1 unité de plus en déplaçant l'unité de point final 1 vers le N, S, E, W, par exemple, u [(k, i + 1)] = d [(k, i)] + 1. Ne pas inclure les chemins qui sont déjà dans d. Si u n'est pas vide, ajoutez les nouveaux chemins plus longs à d et répétez. Lorsque u est vide, cela signifie qu'aucun chemin ne peut plus être créé. Maintenant d contient tous les chemins possibles et leurs longueurs. Il s'agit donc simplement d'obtenir la clé avec le chemin le plus long.

Version moins golfée, commentée:

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 octets

Lançons le bal ...

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

Essayez-le en ligne

Programme complet, lit depuis STDIN, écrit dans STDOUT. Il parcourt simplement chaque cellule et exécute un BFS pour calculer la cellule la plus éloignée, enregistrant les deux si elle est la plus éloignée enregistrée. Je n'y trouve vraiment rien et, frustrant, je ne trouve rien au golf.

Code formaté et commenté:

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