Encontrar Poly Nemo!

11

¡Oh no! Nemo, nuestro pequeño pez payaso se pierde en este océano ASCII y su padre Marlin está tratando de encontrarlo.

Su tarea es llevar a Marlin a Nemo con seguridad. Pero cuidado, tenemos un frenesí de alimentación Bruce suelto, ¡así que mejor evítalo a toda costa!

Detalles

Se le proporciona una cuadrícula oceánica rectangular ASCII que contiene solo alfabetos en minúsculas a-z. Este océano tendrá nemo, marliny brucedentro de él, en forma de un poliomino continuo, siempre comenzando desde la celda más alta en la primera columna de poliomino. Entonces, por ejemplo, de todos los tetrominos posibles, los válidos se enumeran en el fragmento a continuación

Mostrar fragmento de código

Pero formas como estas no son válidas y no estarán presentes en la entrada:

omen

ne
mo

nem
o

o
m
en

nem
 o

n
eo
m

Finalmente, su tarea es encontrar una ruta desde el marlinmosaico poliomino al mosaico nemopoliomino asegurándose de que ninguna celda en su ruta no sea adyacente al brucemosaico poliomino. Su salida debe reemplazar todos los alfabetos que no son parte del marlinmosaico, el nemomosaico y la ruta que los conecta a ambos con un carácter del rango ASCII imprimible (incluido el espacio) que no sea minúscula a-z.

Ejemplo

Si el océano de entrada es el siguiente:

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

(siendo los 3 poliominos:

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

)

Entonces una solución válida puede verse así:

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

El siguiente fragmento contiene algunos ejemplos más:

Mostrar fragmento de código

Notas

  • La cuadrícula siempre será un rectángulo perfecto y contendrá solo un mosaico poliomino de nemo, marliny bruce.
  • Su ruta no debe atravesar bruceni ninguna de las 4 celdas adyacentes (arriba, abajo, izquierda y derecha) de ninguna celda en el brucemosaico.
  • Siempre se garantiza que habrá al menos una ruta válida desde marlinhasta nemo.
  • No hay requisito de un camino más corto aquí, ¡así que enloquece!
  • Aunque no tiene que encontrar la ruta más corta, ninguna celda en la ruta (ruta que no incluye marlin o nemo) no puede estar adyacente a más de otras dos células en la ruta.
  • El camino no debe atravesar las baldosas marlino nemo, ya que confundiría a los pequeños peces al elegir una dirección.
  • Como de costumbre, puede escribir un programa o función, tomando la entrada a través de STDIN (o equivalente más cercano), argumento de línea de comando o parámetro de función, y produciendo salida a través de STDOUT (o equivalente más cercano), valor de retorno o parámetro de función (out).
  • Si no es posible la entrada de varias líneas, puede suponer que la cuadrícula está unida por el |carácter en lugar de \n. También puede tomar la entrada como una matriz de filas de cuadrícula.

Este es el código de golf, por lo que gana la entrada más corta en bytes.

code-golf grid path-finding Optimizador
fuente
¿Puede el camino atravesar marlin (o nemo)? ¿la solución anterior seguiría siendo válida si la kanterior len marlin fuera visible? (haciendo el camino de la n en marlin a nemo)
KSab
@KSab Yo diría que no, ya que confundiría a marlin :)
Optimizer

Respuestas:

4

Matlab 560

560 bytes al eliminar todos los espacios innecesarios, todos los puntos y comas y todos los comentarios. Podría jugar al golf mucho más, pero ahora estoy cansado (tal vez mañana ...) Buenas noches a todos.

PD: Supuse que la ruta debe tener una conexión de 4 vecindades ('+').

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

Función de llamada: (no se necesitan líneas nuevas)

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

Salida:

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

Cómo funciona

Extrayendo nombres

La primera parte es extraer los nombres nemo, por ejemplo , lo que hace la función q(). La función primero marca todo como 0, luego ocurre la primera letra del nombre como 1, luego la segunda letra como 2si hubiera una 1en el vecindario, luego la tercera y así sucesivamente. Después de eso, en el caso de nemoser solo uno 4. A partir de ahí, retrocedemos hasta encontrar el 1nuevo y luego eliminamos todos los otros números que eran mayores que, de modo que obtenemos una bonita máscara donde nemose enmascaran las letras . Hacemos esto para los tres nombres, y luego podemos proceder a encontrar una ruta.

Encontrar el camino

Comenzamos en las posiciones de Marlins y enviamos una onda de choque a través de la 'imagen' del agujero paso a paso. En cada paso aumentamos el contador de distancia y marcamos los 'píxeles' debajo del frente de onda con la distancia actual. (Como generalmente se hace con algoritmos de ruta más corta). Este frente de onda obviamente es bloqueado por el área de Bruce, por lo tanto, fluirá a su alrededor. Este paso se repite hasta que se alcanza un límite superior. Este límite superior (ciertamente muy suelto) es ahora la circunferencia de la 'imagen' (los caminos más cortos serán mucho más cortos en cualquier caso). En el caso de prueba se ve así:

 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

Ahora comience en nemopíxeles y disminuya el contador de distancia en cada paso y agregue un vecino con la siguiente distancia más baja (de acuerdo con ese mapa de distancia que calculamos anteriormente) a nuestra ruta.

falla
fuente
3

Python 2 - 658

Muy muy ineficiente tanto en tiempo como en memoria. La función para identificar los patrones es la función recursiva S, y la función para encontrar las rutas es la C, que es básicamente una implementación A * horriblemente ineficiente.

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

Para las pruebas, use este (muy ligeramente) menos golfizado (que calcula la ruta una vez para cada ficha)

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))
KSab
fuente