Trouver Poly Nemo!

11

Oh non! Nemo, notre petit poisson clown est perdu dans cet océan ASCII et son père Marlin essaie de le retrouver.

Votre tâche consiste à amener Marlin à Nemo en toute sécurité. Mais attention, nous avons une frénésie d'alimentation Bruce en liberté, alors mieux vaut l'éviter à tout prix!

Détails

Vous obtenez une grille océanique ASCII rectangulaire contenant uniquement des alphabets en minuscules a-z. Cet océan aura nemo, marlinet à l' bruceintérieur sous la forme d'un polyomino continu, toujours à partir de la cellule la plus haute de la première colonne de polyomino. Ainsi, par exemple, parmi tous les tétrominos possibles, ceux valides sont répertoriés dans l'extrait ci-dessous

Afficher l'extrait de code

Mais des formulaires comme ceux-ci ne sont pas valides et ne seront pas présents dans l'entrée:

omen

ne
mo

nem
o

o
m
en

nem
 o

n
eo
m

Enfin, votre tâche consiste à trouver un chemin entre la marlintuile polyomino et la nemotuile polyomino en vous assurant qu'aucune cellule de votre chemin n'est adjacente à la brucetuile polyomino. Votre sortie doit remplacer tous les alphabets qui ne font pas partie de la marlintuile, de la nemotuile et du chemin les reliant tous les deux par un caractère de la plage ASCII imprimable (y compris l'espace) autre que les minuscules a-z.

Exemple

Si l'océan d'entrée est le suivant:

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

(les 3 polyominos étant:

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

)

Une solution valide peut alors ressembler à:

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

L'extrait ci-dessous contient quelques autres exemples:

Afficher l'extrait de code

Remarques

  • La grille sera toujours un rectangle parfait et ne contiendra qu'une seule tuile polyomino de nemo, marlinet bruce.
  • Votre chemin ne doit pas traverser bruceou l'une des 4 cellules adjacentes (haut, bas, gauche et droite) d'une cellule de la brucetuile.
  • Il est toujours garanti qu'il y aura au moins un chemin valide de marlinà nemo.
  • Il n'y a aucune exigence de chemin le plus court ici, alors allez-y!
  • Même si vous n'avez pas besoin de trouver le chemin le plus court, aucune cellule du chemin (chemin n'incluant pas le marlin ou le nemo) ne peut être adjacente à plus de deux autres cellules du chemin.
  • Le chemin ne doit pas passer par le marlinou les nemotuiles, car cela dérouterait alors les petits poissons dans le choix d'une direction.
  • Comme d'habitude, vous pouvez écrire un programme ou une fonction, en prenant une entrée via STDIN (ou son équivalent le plus proche), un argument de ligne de commande ou un paramètre de fonction, et en produisant une sortie via STDOUT (ou son équivalent le plus proche), une valeur de retour ou un paramètre de fonction (out).
  • Si la saisie sur plusieurs lignes n'est pas possible, vous pouvez supposer que la grille est jointe par le |caractère au lieu de \n. Vous pouvez également prendre l'entrée comme un tableau de lignes de grille.

Il s'agit du code golf, donc l'entrée la plus courte en octets l'emporte.

code-golf grid path-finding Optimiseur
la source
Le chemin peut-il passer par le marlin (ou nemo)? la solution ci-dessus serait-elle toujours valable si ce qui kprécède le lmarlin était visible? (faisant le chemin du n à marlin vers nemo)
KSab
@KSab Je dirais non car cela confondrait alors marlin :)
Optimizer

Réponses:

4

Matlab 560

560 octets lors de la suppression de tous les espaces inutiles, de tous les points-virgules et de tous les commentaires. Pourrait être joué au golf beaucoup plus mais je suis fatigué en ce moment (peut-être demain ...) Bonne nuit à tous.

PS: J'ai supposé que le chemin devait avoir une connectivité à 4 quartiers ('+').

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

Fonction d'appel: (les nouvelles lignes ne sont pas nécessaires)

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

Production:

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

Comment ça fonctionne

Extraire des noms

La première partie est d'extraire les noms par exemple nemo, ce qui est fait par la fonction q(). La fonction marque d'abord tout comme 0, puis les occurrences première lettre du nom comme 1, puis la deuxième lettre comme 2s'il y a un 1dans le voisinage, puis la troisième et ainsi de suite. Après cela, il ne devrait y en nemoavoir qu'un 4. De là, nous revenons en arrière jusqu'à ce que nous retrouvions le 1, puis supprimons tous les autres nombres qui étaient supérieurs à cela, nous récupérons donc un joli masque où les lettres nemosont masquées. Nous faisons cela pour les trois noms et pouvons ensuite rechercher un chemin.

Trouver le chemin

Nous partons des positions de Marlins et envoyons une onde de choc à travers l'image du trou pas à pas. À chaque étape, nous augmentons le compteur de distance et marquons les «pixels» sous le front d'onde avec la distance actuelle. (Comme cela se fait généralement avec les algorithmes de chemin le plus court.) Ce front d'onde est évidemment bloqué par la zone de Bruce, donc il circulera autour de lui. Cette étape est répétée jusqu'à ce qu'une limite supérieure soit atteinte. Cette limite supérieure (certes très lâche) est maintenant la circonférence de «l'image» (les chemins les plus courts seront de toute façon beaucoup plus courts). Dans le cas de test, cela ressemble à ceci:

 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

Commencez maintenant par les nemopixels et diminuez le compteur de distance à chaque étape et ajoutez un voisin avec la distance inférieure suivante (selon la carte de distance que nous avons calculée plus tôt) à notre chemin.

flawr
la source
3

Python 2 - 658

Très très inefficace en temps et en mémoire. La fonction pour identifier les motifs est la fonction récursive S, et la fonction pour trouver les chemins est le C, qui est fondamentalement une implémentation A * horriblement inefficace.

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

Pour les tests, utilisez celui-ci (très légèrement) moins golfé (qui calcule le chemin une fois pour chaque tuile)

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
la source