Island Golf #2: The Eccentric Hermits

Question

^{This is the second in a series of Island Golf challenges. Previous challenge}

Two hermits have arrived on a desert island. Since they came seeking solitude, they wish to live as far away from each other as possible. Where should they build their huts to maximize the walking distance between them?

Related reading

Input

Your input will be a rectangular grid consisting of two characters, representing land and water. In the examples below, land is # and water is ., but you may substitute any two distinct characters you wish.

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

There will always be at least two land tiles. The land tiles will all be contiguous (i.e. there's only one island). The water tiles will also be contiguous (i.e. there are no lakes). The outer border of the grid will all be water tiles. Land tiles will not be connected diagonally: i.e., you will never see something like

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

Output

Your code must output the same grid, with two hut locations marked on it. In the examples below, the hut locations are marked with X, but you may substitute any character as long as it is distinct from your land and water characters.

The hut locations must be two land tiles, chosen so as to maximize the walking distance between them. We define walking distance as the length of the shortest path, entirely on land, between the two points. Land tiles are considered adjacent horizontally or vertically, but not diagonally.

A possible solution for the above island:

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

The walking distance between these two points is 11, which is the greatest distance between any two points on this island. There is another distance-11 solution:

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

Details

Your solution may be a full program or a function. Any of the default input and output methods are acceptable.

Your input and output may be a multiline string, a list of strings, or a 2D array/nested list of characters/single-character strings. Your output may (optionally) have a single trailing newline. As mentioned above, you may use any three distinct characters in place of #.X (please specify in your submission which characters you're using).

Test cases

A. Islands with unique hut placements:

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

....
.XX.
....

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

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

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

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

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

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

B. Example of an island with multiple possible solutions:

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

Possible outputs:

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

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

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

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

C. Large test case as a Gist

---

This is code-golf: the shortest code in each language wins.

Answer 1

Python 3, 249 246 bytes

Shaved off 3 bytes, thanks DLosc.

Input and output are single strings, with '.', '@', and 'X' representing water, huts, and land, respectively.

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

Prior version:

Input is a single string, with '.' and '#' representing water and land, respectively. 'X' represents the huts in the output.

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

Explanation:

It's basically doing a breadth first search from every possible starting point at the same time. Keep a dictionary, d, of path lengths keyed by the start and end of the path, e.g., d[(k,i)] is the distance from k to i. Then iterate over the keys in the dictionary, d, and create a new dictionary, u, with paths that are 1 unit longer by moving the end point 1 unit to the N,S,E,W, e.g., u[(k, i+1)] = d[(k,i)] + 1. Don't include paths that are already in d. If u is not empty, then add the new longer paths to d and repeat. When u is empty, that means no more paths could be made. Now d contains all the possible paths and their lengths. So its just a matter of getting the key with the longest path.

Less golfed, commented version:

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.

Answer 2

C#, 387 bytes

Let's get the ball rolling...

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

Try it Online

Complete program, reads from STDIN, writes to STDOUT. It simply goes over each cell, and runs a BFS to compute the farthest cell, recording both if it is the farthest on record. Nothing to it really, and frustratingly little I can find to golf.

Formatted and commented code:

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