Encontrando Poly Nemo!

11

Ah não! Nemo, nosso pequeno peixe-palhaço está perdido neste oceano ASCII e seu pai Marlin está tentando encontrá-lo.

Sua tarefa é levar Marlin a Nemo com segurança. Mas cuidado, temos um frenesi de Bruce à solta, então é melhor evitá-lo a todo custo!

Detalhes

Você recebe uma grade oceânica ASCII retangular contendo apenas alfabetos em minúsculas a-z. Este oceano terá nemo, marline brucedentro dele, na forma de um poliomaino contínuo, sempre começando da célula superior na primeira coluna do poliomaino. Assim, por exemplo, de todos os tetrominos possíveis, os válidos estão listados no trecho abaixo

Mostrar snippet de código

Mas formulários como estes são inválidos e não estarão presentes na entrada:

omen

ne
mo

nem
o

o
m
en

nem
 o

n
eo
m

Por fim, sua tarefa é encontrar um caminho do marlinbloco de poliomino para o nemobloco de poliomino, certificando-se de que qualquer célula em seu caminho não seja adjacente ao brucebloco de poliomino. Sua saída deve substituir todos os alfabetos que não fazem parte do marlinbloco, nemobloco e o caminho que os conecta com um caractere do intervalo ASCII imprimível (incluindo espaço) que não seja minúsculo a-z.

Exemplo

Se o oceano de entrada for o seguinte:

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

(com os 3 poliomanos sendo:

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

)

Em seguida, uma solução válida pode se parecer com:

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

O snippet abaixo contém mais alguns exemplos:

Mostrar snippet de código

Notas

  • A grade sempre será um retângulo perfeito e conterá apenas um bloco de poliomino de nemo, marline bruce.
  • Seu caminho não deve passar por brucenenhuma das quatro células adjacentes (para cima, para baixo, esquerda e direita) de nenhuma célula do brucebloco.
  • É sempre garantido que haverá pelo menos um caminho válido de marlinpara nemo.
  • Não há necessidade de um caminho mais curto aqui, então enlouqueça!
  • Mesmo que você não precise encontrar o caminho mais curto, qualquer célula do caminho (caminho que não inclua marlin ou nemo) não pode ser adjacente a mais de duas outras células no caminho.
  • O caminho não deve passar pelos marlinou nemoazulejos, pois confundiria os peixinhos na escolha de uma direção.
  • Como de costume, você pode escrever um programa ou função, recebendo entrada via STDIN (ou equivalente mais próximo), argumento da linha de comando ou parâmetro de função e produzindo saída via STDOUT (ou equivalente mais próximo), valor de retorno ou parâmetro de função (saída).
  • Se a entrada de várias linhas não for possível, você poderá assumir que a grade é unida pelo |caractere em vez de \n. Você também pode receber a entrada como uma matriz de linhas da grade.

Este é o código golf, pelo que ganha a menor entrada em bytes.

code-golf grid path-finding Optimizer
fonte
O caminho pode passar pelo marlin (ou nemo)? a solução acima ainda seria válida se o kacima do lmarlin fosse visível? (fazendo com que o caminho desde o terminal N em Marlin para nemo)
KSab
@KSab eu diria que não, pois seria então marlin confundir :)
Optimizer

Respostas:

4

Matlab 560

560 bytes ao remover todos os espaços desnecessários, todos os pontos e vírgulas e todos os comentários. Poderia jogar muito mais, mas estou cansado agora (talvez amanhã ...) Boa noite a todos.

PS: Eu assumi que o caminho deve ter uma conexão de 4 vizinhanças ('+').

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

Função de chamada: (novas linhas não são necessárias)

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

Resultado:

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

Como funciona

Extraindo nomes

A primeira parte é extrair os nomes nemo, por exemplo , o que é feito pela função q(). A função primeiro marca tudo como 0, depois a primeira letra do nome como 1, depois a segunda letra como 2se houvesse um 1na vizinhança, depois a terceira e assim por diante. Depois disso, no caso de nemohaver apenas um 4. A partir disso, vamos para trás até encontrarmos 1novamente e, em seguida, excluímos todos os outros números que eram maiores que isso, de modo que obtemos uma boa máscara em que as letras nemoestão mascaradas. Fazemos isso para todos os três nomes e podemos prosseguir para encontrar um caminho.

Encontrando o caminho

Começamos nas posições de Marlins e enviamos uma onda de choque através da 'imagem' do buraco, passo a passo. Em cada etapa, aumentamos o contador de distâncias e marcamos os 'pixels' sob a frente da onda com a distância atual. (Como geralmente é feito com algoritmos de caminho mais curto.) Essa frente de onda obviamente fica bloqueada pela área de Bruce, portanto flui ao seu redor. Esta etapa é repetida até que um limite superior seja atingido. Esse limite superior (reconhecidamente muito flexível) agora é a circunferência da 'imagem' (os caminhos mais curtos serão bem mais curtos em qualquer caso). No caso de teste, é algo parecido com isto:

 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

Agora comece com nemopixels e diminua o contador de distâncias em cada etapa e adicione um vizinho com a próxima distância mais baixa (de acordo com o mapa de distância que calculamos anteriormente) ao nosso caminho.

flawr
fonte
3

Python 2-658

Muito, muito ineficiente no tempo e na memória. A função para identificar os padrões é a função recursiva S, e a função para encontrar os caminhos é o C, que é basicamente uma implementação A * terrivelmente 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 testar, use este (muito ligeiramente) menos golfe (que calcula o caminho uma vez para cada bloco)

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
fonte