Finding Poly Nemo!

Question

Oh no! Nemo, our small clown fish is lost in this ASCII ocean and his dad Marlin is trying to find him.

Your task is to get Marlin to Nemo safely. But beware, we have a feeding frenzy Bruce on the loose, so better avoid him at all costs!

Details

You are given a rectangular ASCII ocean grid containing only lowercase alphabets a-z. This ocean will have nemo, marlin and bruce inside it in the form of a continuous polyomino, always starting from the top most cell in the first column of polyomino. So for example, out of all possible tetrominos, the valid ones are listed in the below snippet

nemo

n
e
m
o

no
em

ne
om

nem
  o

  o
nem

n
e
mo

 o
 m
ne

ne
 m
 o

n
emo

ne
 mo

n
em
 o

 mo
ne

But forms like these are invalid and won't be present in the input:

omen

ne
mo

nem
o

o
m
en

nem
 o

n
eo
m

Finally, your task is to find a path from the marlin polyomino tile to the nemo polyomino tile making sure that any cell in your path is not adjacent to the bruce polyomino tile. Your output should replace all alphabets which are not part of the marlin tile, nemo tile and the path connecting them both with a character from the printable ASCII range (including space) other than the lowercase a-z.

Example

If the input ocean is as following:

oxknvvolacycxg
xmliuzsxpdzkpw
warukpyhcldlgu
tucpzymenmoyhk
qnvtbsalyfrlyn
cicjrucejhiaeb
bzqfnfwqtrzqbp
ywvjanjdtzcoyh
xsjeyemojwtyhi
mcefvugvqabqtt
oihfadeihvzakk
pjuicqduvnwscv

(with the 3 polyominos being:

...n..........
.mli..........
.ar...........
..............
....b.........
....ruce......
..............
.....n........
.....emo......
..............
..............
..............

)

Then a valid solution may look like:

...n..........
.mli..........
.ar...........
.u............
.n............
.i............
.z............
.wvjan........
.....emo......
..............
..............
..............

Below snippet contains a few more examples:

oxknvvolacycxg
xmliuzsxpdzkpw
warukpyhcldlgu
tucpzymenmoyhk
qnvthsalyfrlyn
cibrucejhiaebu
bzqfnfwqtrzqbp
ywvjanjdtzcoyh
xsjeyemojwtyhi
mcefvugvqabqtt
oihfadeihvzakk
pjuicqduvnwscv

...n..........
.mli..........
.ar...........
.u............
qn............
c.............
b.............
ywvjan........
.....emo......
..............
..............
..............

----------------------------------------------

nemokjahskj
sdjsklakdjs
uqiceasdjnn
sbruakmarli

nemokjahskj
..........s
..........n
......marli

----------------------------------------------

Notes

• The grid will always be a perfect rectangle and will contain only one polyomino tile of nemo, marlin and bruce.
• Your path should not go through bruce or any of the 4 adjacent (up, down, left and right) cells of any cell in the bruce tile.
• It is always guaranteed that there will be at least one valid path from marlin to nemo.
• There is no requirement of a shortest path here, so go nuts!
• Even though you don't have to find the shortest path, any cell in the path (path not including marlin or nemo) cannot be adjacent to more than two other cells in the path.
• The path should not go through the marlin or nemo tiles, as it would then confuse the little fishes in choosing a direction.
• As usual, you may write a program or function, taking input via STDIN (or closest equivalent), command-line argument or function parameter, and producing output via STDOUT (or closest equivalent), return value or function (out) parameter.
• If multi-line input is not possible, then you may assume that the grid is joined by the | character instead of \n. You may also take the input as an array of grid rows.

This is code golf so the shortest entry in bytes wins.

Answer 1

Matlab 560

560 bytes when removing all unnecessary spaces, all semicolons and all comments. Could be golfed much more but I am to tired right now (maybe tomorrow...) Good night everyone.

PS: I assumed that the path must have a 4 neighbourhood ('+') connectedness.

function c(A)
Z = [0,1,0;1,1,1;0,1,0];
Br = q('bruce');
Bn = conv2(Br,ones(3),'s')>0;
Ne = q('nemo');
Ma = q('marlin');
%construct path marlin to nemo
U=Ma>0;M=A*Inf;
M(U)=0;
for k=1:2*sum(size(A))%upper bound for path length
    %expand
    V=imdilate(U,Z);
    V(Bn)=0;
    M(V-U==1)=k;
    U=V;
    %disp(M)
end
%go back from nemo to marlin
Pr=reshape(1:numel(A),size(A));
[i,j]=find(Ne);
m=M(i(1),j(1));%value
P=A*0;%path image
P(i(1),j(1))=1;
for k=m:-1:1
    %find neighbour of (i(1),j(1)) with value m-1
    U=imdilate(P,Z);
    F = M==k;
    G = F&U;
    mask = Pr == min(Pr(F & U));
    P(mask)=1; 
end
A(~P & ~Ma & ~Ne)='.';
disp(A)



    function M = q(s)%find string in matrix, A ascii, M mask
        M = A*0;
        m=numel(s);
        N = M+1;%all neighbours
        for k=1:m;
            M(A==s(k) & N)=k;%only set the ones that were in the neighbourhood of last
            L=M==k;
            N=imdilate(L,Z);
        end
        for k=m:-1:2
            %set all that are not neighbour to next higher highest to zero
            L=M==k;
            N=imdilate(L,Z);
            M(M==k-1 & ~N)=0;
        end
    end


end

Calling function : (newlines not necessary)

c(['oxknvvolacycxg',
'xmliuzsxpdzkpw',
'warukpyhcldlgu',
'tucpzymenmoyhk',
'qnvtbsalyfrlyn',
'cicjrucejhiaeb',
'bzqfnfwqtrzqbp',
'ywvjanjdtzcoyh',
'xsjeyemojwtyhi',
'mcefvugvqabqtt',
'oihfadeihvzakk',
'pjuicqduvnwscv']);

Output:

...n..........
.mli..........
.ar...........
..c...........
..v...........
..c...........
..q...........
..vjan........
.....emo......
..............
..............
..............

How it works

Extracting names

The first part is extracting the names e.g. nemo, which is done by the function q(). The function first marks everything as 0, then the occurences first letter of the name as 1, then the second letter as 2 if there is a 1 in the neighbourhood, then the third and so on. After that there should in the case of nemo be only one 4. From that we go backwards until we found the 1 again and then delete all the other numbers that were greater that, so we get back a nice mask where the letters nemo are masked. We do this for all three names, and can then proceed to finding a path.

Finding the path

We start at Marlins positions and send a shockwave throu the hole 'image' step by step. In each step we increase the distance counter and mark the 'pixels' under the wavefront with the current distance. (As it is usually done with shortest path algorithms.) This wavefront obviously gets blocked by the area of Bruce, therefore it will flow around him. This step is repeated until an upper bound is reached. This (admittedly very loose) upper bound is now the circumference of the 'image' (the shortest paths will be way shorter in any case). In the test case it looks something like this:

 2 1 1  0  1  2  3  4  5  6  7  8  9 10
 1 0 0  0  1  2  3  4  5  6  7  8  9 10
 1 0 0  1  2  3  4  5  6  7  8  9 10 11
 2 1 1  _  _  _  5  6  7  8  9 10 11 12
 3 2 2  _  _  _  _  _  _  9 10 11 12 13
 4 3 3  _  _  _  _  _  _ 10 11 12 13 14
 5 4 4  _  _  _  _  _  _ 11 12 13 14 15
 6 5 5  6  7  8  9 10 11 12 13 14 15 16
 7 6 6  7  8  9 10 11 12 13 14 15 16 17
 8 7 7  8  9 10 11 12 13 14 15 16 17 18
 9 8 8  9 10 11 12 13 14 15 16 17 18 19
10 9 9 10 11 12 13 14 15 16 17 18 19 20

Now start at nemo pixels and decrease the distance counter in each step and add a neighbour with the next lower distance (according to that distance map we calculated earlier) to our path.

Answer 2

Python 2 - 658

Very very inefficient both in time and memory. The function to identify the patterns is the recursive function S, and the function to find the paths is the C, which is basically a horribly inefficient A* implementation.

G=input().split('\n')
R=range
S=lambda g,x,y,s,B:[[(x,y)]+r for a,b in[(-1,0),(0,-1),(0,1),(1,0)]for r in S(g,x+a,y+b,s[1:],B)if B(x,y)and s[0]==g[y][x]]if s else[[]]
C=lambda l,N,B:[i for i in l if i[-1]in N]or C([i+[(i[-1][0]+c,i[-1][1]+d)]for i in l for c,d in [(-1,0),(0,-1),(0,1),(1,0)]if all(1<abs(i[-1][0]+c-a)or 1<abs(i[-1][1]+d-b)for a,b in B)],N,B)
X,Y=len(G[0]),len(G)
N,M,B=[filter(list,[S(G,s,t,e,lambda a,b:0<=a<X and 0<=b<Y and Y*(a-s)+b-t>=0)for s in R(X)for t in R(Y)])[0][0]for e in["nemo","marlin","bruce"]]
print'\n'.join(''.join(G[y][x]if(x,y)in N+M+min([C([[k]],N,B)[0]for k in M],key=lambda i:len(i))else'.'for x in R(X))for y in R(Y))

For testing use this (very slightly) less golfed one (which calculates the path once instead for every tile)

G=input().split('\n')
R=range
S=lambda g,x,y,s,B:[[(x,y)]+r for a,b in[(-1,0),(0,-1),(0,1),(1,0)]for r in S(g,x+a,y+b,s[1:],B)if B(x,y)and s[0]==g[y][x]]if s else[[]]
C=lambda l,N,B:[i for i in l if i[-1]in N]or C([i+[(i[-1][0]+c,i[-1][1]+d)]for i in l for c,d in [(-1,0),(0,-1),(0,1),(1,0)]if all(1<abs(i[-1][0]+c-a)or 1<abs(i[-1][1]+d-b)for a,b in B)],N,B)
X,Y=len(G[0]),len(G)
N,M,B=[filter(list,[S(G,s,t,e,lambda a,b:0<=a<X and 0<=b<Y and Y*(a-s)+b-t>=0)for s in R(X)for t in R(Y)])[0][0]for e in["nemo","marlin","bruce"]]
s=N+M+min([C([[k]],N,B)[0]for k in M],key=lambda i:len(i))
print'\n'.join(''.join(G[y][x]if(x,y)in s else'.'for x in R(X))for y in R(Y))