11

о нет! Немо, наша маленькая рыба-клоун потерялась в океане ASCII, и его отец Марлин пытается найти его.

Ваша задача - безопасно доставить Марлина в Немо. Но будьте осторожны, у нас на свободе безумный питающий Брюс, так что лучше избегайте его любой ценой!

подробности

Вам дана прямоугольная сетка океана ASCII, содержащая только строчные буквы a-z. Этот океан будет иметь nemo, marlinи bruceвнутри него, в виде непрерывного полиомино, всегда начиная с самой верхней ячейки в первом столбце полиомино. Так, например, из всех возможных тетромино действительные перечислены в приведенном ниже фрагменте

Показать фрагмент кода

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

Expand snippet

Но такие формы недопустимы и не будут присутствовать во входных данных:

omen

ne
mo

nem
o

o
m
en

nem
 o

n
eo
m

Наконец, ваша задача - найти путь от marlinплитки polyomino к плитке nemopolyomino, убедившись, что ни одна ячейка в вашем пути не примыкает к bruceплитке polyomino. Ваш вывод должен заменить все алфавиты, которые не являются частью marlinтайла, nemoтайла и пути, соединяющего их обоих символом из диапазона ASCII для печати (включая пробел), кроме строчных a-z.

пример

Если входной океан выглядит следующим образом:

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

(с 3-мя множителями:

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

)

Тогда правильное решение может выглядеть так:

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

Ниже приведен фрагмент кода:

Показать фрагмент кода

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

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

Expand snippet

Заметки

Сетка всегда будет идеальным прямоугольником и будет содержать только одну плитку полиомино nemo, marlinи bruce.
Ваш путь не должен проходить bruceили через любую из 4 смежных (вверх, вниз, влево и вправо) ячеек любой ячейки в bruceтайле.
Всегда гарантируется, что будет хотя бы один допустимый путь от marlinдо nemo.
Здесь нет требования кратчайшего пути, так что сходите с ума!
Даже если вам не нужно находить кратчайший путь, ни одна ячейка в пути (путь, кроме marlin или nemo) не может быть смежной с более чем двумя другими ячейками в пути.
Путь не должен проходить через плитки marlinили nemo, так как это могло бы сбить с толку маленьких рыб при выборе направления.
Как обычно, вы можете написать программу или функцию, получая ввод через STDIN (или ближайший эквивалент), аргумент командной строки или параметр функции и производя вывод через STDOUT (или ближайший эквивалент), возвращаемое значение или параметр функции (out).
Если многострочный ввод невозможен, вы можете предположить, что сетка соединена |символом, а не \n. Вы также можете принять входные данные как массив строк сетки.

Это код гольф, поэтому выигрывает самая короткая запись в байтах.

code-golf grid path-finding оптимизатор
источник

Может ли путь пройти через марлина (или немо)? будет ли вышеуказанное решение все еще в силе, если kвыше lбудет видно марлин? (прокладывая путь от русских в марлине к немо)

KSab

@KSab Я бы сказал «нет», потому что это смутило бы Марлина :)

Оптимизатор

4

Matlab 560

560 байт при удалении всех ненужных пробелов, всех точек с запятой и всех комментариев. Можно было бы играть в гольф намного больше, но я устал сейчас (может быть, завтра ...) Всем спокойной ночи.

PS: я предположил, что путь должен иметь 4-х окрестность ('+') связности.

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

Вызов функции: (новые строки не нужны)

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

Выход:

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

Как это работает

Извлечение имен

Первая часть извлекает имена, например nemo, что делается функцией q(). Функция сначала помечает все как 0, затем вначале встречается первая буква имени как 1, затем вторая буква, как 2будто есть 1соседство, затем третья и так далее. После этого должен nemoбыть только один 4. От этого мы идем назад, пока не найдем 1снова, а затем удаляем все остальные числа, которые были больше, поэтому мы получаем красивую маску, где маскируются буквы nemo. Мы делаем это для всех трех имен, а затем можем перейти к поиску пути.

Нахождение пути

Мы начинаем с позиций Марлина и шаг за шагом посылаем ударную волну через «изображение» дыры. На каждом шаге мы увеличиваем счетчик расстояний и отмечаем «пиксели» под волновым фронтом текущим расстоянием. (Как это обычно делается с алгоритмами кратчайшего пути.) Этот волновой фронт, очевидно, блокируется областью Брюса, поэтому он будет обтекать его. Этот шаг повторяется до тех пор, пока не будет достигнута верхняя граница. Эта (предположительно очень свободная) верхняя граница теперь является окружностью «изображения» (в любом случае самые короткие пути будут намного короче). В тестовом примере это выглядит примерно так:

 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

Теперь начните с nemoпикселей и уменьшайте счетчик расстояний на каждом шаге и добавляйте соседа со следующим меньшим расстоянием (согласно той карте расстояний, которую мы рассчитали ранее) к нашему пути.

flawr
источник

3

Питон 2 - 658

Очень и очень неэффективно как по времени, так и по памяти. Функция для идентификации шаблонов - это рекурсивная функция S, а функция для поиска путей - это C, которая в основном является ужасно неэффективной реализацией 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))

Для тестирования используйте этот (очень немного) менее гольфовый (который рассчитывает путь один раз вместо каждой плитки)

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
источник

В поисках Поли Немо!

Ответы:

Matlab 560

Как это работает

Извлечение имен

Нахождение пути

Питон 2 - 658