Znalezienie Poly Nemo!

11

O nie! Nemo, nasza mała ryba klauna zaginęła w tym oceanie ASCII, a jego tata Marlin próbuje go znaleźć.

Twoim zadaniem jest bezpieczne doprowadzenie Marlina do Nemo. Ale uwaga, mamy na wolności szalonego Bruce'a, więc lepiej go unikać za wszelką cenę!

Detale

Otrzymujesz prostokątną siatkę oceaniczną ASCII zawierającą tylko małe litery a-z. Ten ocean będzie miał nemo, marlina brucewewnątrz niego w postaci ciągłego poliomino, zawsze zaczynając od najwyższej komórki w pierwszej kolumnie poliomino. Na przykład spośród wszystkich możliwych tetrominów prawidłowe są wymienione w poniższym fragmencie

Pokaż fragment kodu

Ale takie formularze są nieprawidłowe i nie będą obecne w danych wejściowych:

omen

ne
mo

nem
o

o
m
en

nem
 o

n
eo
m

Wreszcie, Twoim zadaniem jest znalezienie ścieżki od marlinpłytki poliomino do płytki nemopoliomino, upewniając się, że żadna komórka na Twojej ścieżce nie sąsiaduje z brucepłytką poliomino. Twój wynik powinien zastąpić wszystkie alfabety, które nie są częścią marlinkafelka, nemokafelka i ścieżki łączącej oba znaki znakiem z drukowanego zakresu ASCII (w tym spacją) innym niż małe litery a-z.

Przykład

Jeśli ocean wejściowy jest następujący:

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

(przy czym 3 poliaminy to:

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

)

W takim przypadku prawidłowe rozwiązanie może wyglądać następująco:

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

Poniżej fragment zawiera kilka innych przykładów:

Pokaż fragment kodu

Notatki

  • Siatka zawsze będzie idealny prostokąt i będzie zawierać tylko jeden Polyomino płytki z nemo, marlini bruce.
  • Twoja ścieżka nie powinna przechodzić przez bruceżadną z 4 sąsiadujących (w górę, w dół, w lewo i w prawo) komórek żadnej komórki na brucekafelku.
  • Zawsze gwarantuje się, że będzie co najmniej jedna poprawna ścieżka od marlindo nemo.
  • Nie ma tu wymogu najkrótszej ścieżki, więc zwariuj!
  • Nawet jeśli nie musisz znajdować najkrótszej ścieżki, żadna komórka na ścieżce (ścieżka nie włączając marlina ani nemo) nie może przylegać do więcej niż dwóch innych komórek na ścieżce.
  • Ścieżka nie powinna przechodzić przez kafelki marlinlub nemo, ponieważ wówczas mylą małe ryby przy wyborze kierunku.
  • Jak zwykle, możesz napisać program lub funkcję, pobierając dane wejściowe przez STDIN (lub najbliższy odpowiednik), argument wiersza poleceń lub parametr funkcji i generując dane wyjściowe przez STDOUT (lub najbliższy odpowiednik), zwracaną wartość lub parametr funkcji (wyjściowej).
  • Jeśli wprowadzanie wielu wierszy nie jest możliwe, możesz założyć, że do siatki dołącza |znak zamiast \n. Możesz również wziąć dane wejściowe jako tablicę wierszy siatki.

To jest kod golfowy, więc wygrywa najkrótszy wpis w bajtach.

code-golf grid path-finding Optymalizator
źródło
Czy ścieżka może przejść przez marlin (lub nemo)? czy powyższe rozwiązanie byłoby nadal aktualne, gdyby widoczny był kpowyższy lmarlin? (droga od
mar
@KSab Powiedziałbym „nie”, ponieważ wprowadziłoby to zamieszanie w marlinie :)
Optymalizator

Odpowiedzi:

4

Matlab 560

560 bajtów podczas usuwania wszystkich niepotrzebnych spacji, wszystkich średników i wszystkich komentarzy. Można grać w golfa o wiele więcej, ale jestem teraz zmęczony (może jutro ...) Dobranoc wszystkim.

PS: Zakładałem, że ścieżka musi mieć 4 sąsiedztwo („+”).

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

Funkcja wywoływania: (nowe linie nie są konieczne)

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

Wynik:

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

Jak to działa

Wyodrębnianie nazw

Pierwszą częścią jest wyodrębnienie nazw np. nemo, Które wykonuje funkcja q(). Funkcja najpierw oznacza wszystko jako 0, następnie występuje pierwsza litera nazwy jako 1, a następnie druga litera, 2jakby 1w sąsiedztwie była, a następnie trzecia i tak dalej. Potem powinno nemobyć tylko jedno 4. Od tego cofamy się, aż odnajdujemy 1ponownie, a następnie usuwamy wszystkie inne liczby, które były większe, więc otrzymujemy ładną maskę, w której litery nemosą zamaskowane. Robimy to dla wszystkich trzech nazw, a następnie możemy przejść do znalezienia ścieżki.

Znalezienie ścieżki

Zaczynamy od pozycji Marlinsa i krok po kroku wysyłamy falę uderzeniową przez „obraz” dziury. Na każdym kroku zwiększamy licznik odległości i zaznaczamy „piksele” pod falą bieżącą odległością. (Jak to zwykle się dzieje z algorytmami najkrótszej ścieżki.) Ten front fali oczywiście zostaje zablokowany przez obszar Bruce'a, dlatego będzie go otaczał. Ten krok powtarza się, aż zostanie osiągnięta górna granica. Ta (co prawda bardzo luźna) górna granica stanowi teraz obwód „obrazu” (w każdym razie najkrótsze ścieżki będą o wiele krótsze). W przypadku testowym wygląda to tak:

 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

Teraz zacznij od nemopikseli i zmniejszaj licznik odległości na każdym kroku i dodaj do ścieżki sąsiada o następnej niższej odległości (zgodnie z obliczoną wcześniej mapą odległości).

wada
źródło
3

Python 2 - 658

Bardzo bardzo nieefektywny zarówno pod względem czasu, jak i pamięci. Funkcją identyfikującą wzorce jest funkcja rekurencyjna S, a funkcją znajdowania ścieżek jest C, co jest w zasadzie strasznie nieefektywną implementacją A *.

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

Do testowania użyj tego (bardzo nieznacznie) mniej golfowego (który zamiast tego oblicza ścieżkę raz dla każdego kafelka)

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
źródło