Caminho ideal através de uma matriz

19

Dada uma matriz composta por números inteiros positivos, imprima o caminho com a menor soma ao percorrer o elemento superior esquerdo para o canto inferior direito. Você pode se mover verticalmente, horizontalmente e diagonalmente. Observe que é possível mover para cima / para baixo, direita / esquerda e na diagonal para todos os lados.

Exemplo:

 1*   9    7    3   10    2    2
10    4*   1*   1*   1*   7    8
 3    6    3    8    9    5*   7
 8   10    2    5    2    1*   4
 5    1    1    3    6    7    9*

O caminho que dá a soma mais baixa é marcado com asteriscos e resulta na seguinte soma: 1 + 4 + 1 + 1 + 1 + 5 + 1 + 9 = 23 .

Casos de teste:

1   1   1
1   1   1
Output: 3

 7    9    6    6    4
 6    5    9    1    6
10    7   10    4    3
 4    2    2    3    7
 9    2    7    9    4
Output: 28

2  42   6   4   1
3  33   1   1   1
4  21   7  59   1
1   7   6  49   1
1   9   2  39   1
Output: 27 (2+3+4+7+7+1+1+1+1)

 5    6    7    4    4
12   12   25   25   25
 9    4   25    9    5
 7    4   25    1   12
 4    4    4    4    4
Output: 34 (5+12+4+4+4+1+4)

1   1   1   1
9   9   9   1
1   9   9   9
1   9   9   9
1   1   1   1
Output: 15

 2   55    5    3    1    1    4    1
 2   56    1   99   99   99   99    5
 3   57    5    2    2    2   99    1
 3   58    4    2    8    1   99    2
 4   65   66   67   68    3   99    3
 2    5    4    3    3    4   99    5
75   76   77   78   79   80   81    2
 5    4    5    1    1    3    3    2
Output: 67 (2+2+3+3+4+5+4+3+3+3+1+2+2+1+3+1+1+4+5+1+2+3+5+2+2)

Este é o portanto o código mais curto em cada idioma vence.

Stewie Griffin
fonte
Muito semelhante , embora não permita movimento diagonal.
Mego
7
@WheatWizard Eu discordo. Além das diferenças superficiais na maioria das vezes que esse desafio permite o movimento diagonal e todas as posições são alcançáveis, o outro desafio exige o retorno do caminho em si, e não apenas o custo do caminho. A menos que você esteja usando built-ins que retornam ambos, o código não é intercambiável.
copo
@beaker Eu realmente não vejo a diferença. Você tem que encontrar o caminho para saber o seu comprimento. A diferença aqui é uma diferença bastante pequena na produção, na minha opinião, e esse desafio não oferece nada de novo ou interessante que ainda não esteja coberto por esse desafio.
Assistente de trigo
11
@WheatWizard Minha solução aqui não encontra o caminho. Ele pode encontrar o caminho, mas não sem uma matriz e lógica predecessoras separadas para evitar que um nó seja seu próprio predecessor. Sem mencionar a recuperação do caminho no final.
beaker
@beaker A modificação é bastante trivial na minha opinião. Independentemente da questão dos burros, não é se todas as entradas válidas em um desafio podem ser transportadas com o mínimo esforço, é sobre o caso geral. Não apenas acho que a maioria dos esforços aqui pode ser portada, como também não acho que esse desafio ofereça algo novo ou interessante do outro.
Wheat Wizard

Respostas:

8

JavaScript, 442 412 408 358 bytes

Este é o meu primeiro envio de PPCG. O feedback seria apreciado.

(m,h=m.length,w=m[0].length)=>{for(i=0;i<h*w;i++)for(x=0;x<w;x++){for(y=0;y<h;y++){if(m[y][x]%1==0)m[y][x]={c:m[y][x],t:m[y][x]};for(X=-1;X<=1;X++)for(Y=-1;Y<=1;Y++){t=x+X;v=y+Y;if((X==0&&Y==0)||t<0||t>=w||v<0||v>=h)continue;if(m[v][t]%1==0)m[v][t]={c:m[v][t],t:null};c=m[y][x].t+m[v][t].c;if (c<m[v][t].t||m[v][t].t==null)m[v][t].t=c}}}return m[h-1][w-1].t}

Isso leva uma matriz multidimensional como entrada.

Explicação

Basicamente, percorra todas as células repetidamente, ajustando o menor custo conhecido para chegar a cada um dos vizinhos. Eventualmente, a grade alcançará um estado em que o custo total para chegar ao canto inferior direito é o menor custo para chegar lá.

Demo

f=(m,h=m.length,w=m[0].length)=>{for(i=0;i<h*w;i++)for(x=0;x<w;x++){for(y=0;y<h;y++){if(m[y][x]%1==0)m[y][x]={c:m[y][x],t:m[y][x]};for(X=-1;X<=1;X++)for(Y=-1;Y<=1;Y++){t=x+X;v=y+Y;if((X==0&&Y==0)||t<0||t>=w||v<0||v>=h)continue;if(m[v][t]%1==0)m[v][t]={c:m[v][t],t:null};c=m[y][x].t+m[v][t].c;if (c<m[v][t].t||m[v][t].t==null)m[v][t].t=c}}}return m[h-1][w-1].t}

//Tests
console.log(f([[1,1,1],[1,1,1]])===3);
console.log(f([[7,9,6,6,4],[6,5,9,1,6],[10,7,10,4,3],[4,2,2,3,7],[9,2,7,9,4]])===28);
console.log(f([[2,42,6,4,1],[3,33,1,1,1],[4,21,7,59,1],[1,7,6,49,1],[1,9,2,39,1]])===27);
console.log(f([[5,6,7,4,4],[12,12,25,25,25],[9,4,25,9,5],[7,4,25,1,12],[4,4,4,4,4]])===34); 
console.log(f([[1,1,1,1],[9,9,9,1],[1,9,9,9],[1,9,9,9],[1,1,1,1]])===15)
console.log(f([[2,55,5,3,1,1,4,1],[2,56,1,99,99,99,99,5],[3,57,5,2,2,2,99,1],[3,58,4,2,8,1,99,2],[4,65,66,67,68,3,99,3],[2,5,4,3,3,4,99,5],[75,76,77,78,79,80,81,2],[5,4,5,1,1,3,3,2]])===67);

Edit: Um agradecimento especial ao @ETHproductions por me ajudar a fazer a barba de dezenas de bytes saborosos.

Mais obrigado a @Stewie Griffin por suas dicas que interromperam 50 bytes.

Benjamin Cuningham
fonte
3
Bem-vindo ao PPCG! Existem alguns espaços extras que você pode remover no final (conto 5 no total), e você não precisa de nenhum ponto e vírgula diretamente antes de um, o }que deve economizar alguns bytes. Você também não precisa declarar suas variáveis; Eu acho que remover os vars deve economizar mais 24 bytes no total.
ETHproductions
2
Bem-vindo ao PPCG =) Estou feliz que você tenha escolhido um dos meus desafios como ponto de partida. Meu único comentário: adoro explicações. É opcional, portanto, você não precisa adicioná-lo, a menos que queira. :)
Stewie Griffin
Acho que talvez armazenar m[v][t]como variável: t=x+X;v=y+Y;k=m[v][t]será ainda mais curto ...?
Stewie Griffin
7

Python 3 + numpy + scipy , 239 222 186 bytes

from numpy import*
from scipy.sparse.csgraph import*
def f(M):m,n=s=M.shape;x,y=indices(s);return dijkstra([(M*(abs(i//n-x)<2)*(abs(i%n-y)<2)).flatten()for i in range(m*n)])[0,-1]+M[0,0]

Experimente online!

notjagan
fonte
6

Pacote Octave + Processamento de imagem, 175 162 157 151 142 139 bytes

Economizou 14 bytes graças a @Luis Mendo e 1 byte graças a @notjagan

function P(G)A=inf(z=size(G));A(1)=G(1);for k=G(:)'B=im2col(padarray(A,[1,1],inf),[3,3])+G(:)';B(5,:)-=G(:)';A=reshape(min(B),z);end,A(end)

Usa o pacote Image Processing, porque por que não? Não é assim que todo mundo resolve problemas gráficos?

Experimente online!

Explodido

function P(G)
   A=inf(z=size(G));         % Initialize distance array to all Inf
   A(1)=G(1);                % Make A(1) = cost of start cell
   for k=G(:)'               % For a really long time...
      B=im2col(padarray(A,[1,1],inf),[3,3])+G(:)';
       %  B=padarray(A,[1,1],inf);     % Add border of Inf around distance array
       %  B=im2col(B,[3,3]);           % Turn each 3x3 neighborhood into a column
       %  B=B+G(:)';                   % Add the weights to each row
      B(5,:)-=G(:)';         % Subtract the weights from center of neighborhood
      A=reshape(min(B),z);   % Take minimum columnwise and reshape to original
   end
   A(end)                    % Display cost of getting to last cell

Explicação

Dada uma variedade de pesos:

7   12    6    2    4
5   13    3   11    1
4    7    2    9    3
4    2   12   13    4
9    2    7    9    4

Inicialize uma matriz de custos para que o custo para alcançar cada elemento seja Infinito, exceto o ponto inicial (o elemento superior esquerdo) cujo custo é igual ao seu peso.

  7   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf

Esta é a iteração 0. Para cada iteração subsequente, o custo para atingir uma célula é definido no mínimo de:

  • o custo atual para alcançar esse elemento e
  • o custo atual para alcançar os vizinhos do elemento + o peso do elemento

Após a primeira iteração, o custo do caminho para o elemento (2,2) (usando a indexação baseada em 1) será

minimum([  7   Inf   Inf]   [13  13  13]) = 20
        [Inf   Inf   Inf] + [13   0  13]
        [Inf   Inf   Inf]   [13  13  13]

A matriz de custo completo após a primeira iteração seria:

  7    19   Inf   Inf   Inf
 12    20   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf

Após a iteração k, cada elemento terá o menor custo para alcançá-lo desde o início, executando na maioria das ketapas. Por exemplo, o elemento em (3,3) pode ser alcançado em 2 etapas (iterações) por um custo de 22:

  7    19    25   Inf   Inf
 12    20    22   Inf   Inf
 16    19    22   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf

Mas na quarta iteração, um caminho de 4 etapas é encontrado com um custo de 20:

 7   19   25   24   28
12   20   22   32   25
16   19   20   30   34
20   18   30   34   35
27   20   25   40   39

Como nenhum caminho através da matriz mxn pode ser maior que o número de elementos na matriz (como um limite superior muito frouxo), após as m*niterações, cada elemento conterá o custo do caminho mais curto para alcançar esse elemento desde o início.

taça
fonte
-1 byte removendo o espaço entre whilee ~.
precisa saber é o seguinte
@notjagan Troquei de whilea fore ainda foi capaz de usar sua dica. Obrigado!
copo
5

JavaScript, 197 bytes

a=>(v=a.map(x=>x.map(_=>1/0)),v[0][0]=a[0][0],q=[...(a+'')].map(_=>v=v.map((l,y)=>l.map((c,x)=>Math.min(c,...[...'012345678'].map(c=>a[y][x]+((v[y+(c/3|0)-1]||[])[x+c%3-1]||1/0)))))),v.pop().pop())

Embelezar:

a=>(
  // v is a matrix holds minimal distance to the left top
  v=a.map(x=>x.map(_=>1/0)),
  v[0][0]=a[0][0],
  q=[
     // iterate more than width * height times to ensure the answer is correct
    ...(a+'')
  ].map(_=>
    v=v.map((l,y)=>
      l.map((c,x)=>
        // update each cell
        Math.min(c,...[...'012345678'].map(
          c=>a[y][x]+((v[y+(c/3|0)-1]||[])[x+c%3-1]||1/0)
        ))
      )
    )
  ),
  // get result at right bottom
  v.pop().pop()
)
tsh
fonte
4

Mathematica 279 bytes

A idéia básica é criar um gráfico com vértices correspondentes às entradas da matriz e arestas direcionadas entre quaisquer dois vértices separados por um ChessboardDistancemaior que zero, mas menor que ou igual a 1. Aliás, isso é conhecido como gráfico de King , pois corresponde a os movimentos válidos de um rei em um tabuleiro de xadrez.

FindShortestPathé então usado para obter o caminho mínimo. Como funciona EdgeWeight, não VertexWeight, portanto, há algum código extra para definir EdgeWeightcomo a entrada da matriz correspondente ao destino de cada aresta direcionada.

Código:

(m=Flatten[#];d=Dimensions@#;s=Range[Times@@d];e=Select[Tuples[s,2],0<ChessboardDistance@@(#/.Thread[s->({Ceiling[#/d[[1]]],Mod[#,d[[1]],1]}&/@s)])≤1&];Tr[FindShortestPath[Graph[s,#[[1]]->#[[2]]&/@e,EdgeWeight->(Last@#&/@Map[Extract[m,#]&,e,{2}])],1,Last@s]/.Thread[s->m]])&

Observe que o caractere é o símbolo de transposição. Ele será colado no Mathematica como está.

Uso:

%@{{2, 55, 5, 3, 1, 1, 4, 1},
  {2, 56, 1, 99, 99, 99, 99, 5},
  {3, 57, 5, 2, 2, 2, 99, 1},
  {3, 58, 4, 2, 8, 1, 99, 2},
  {4, 65, 66, 67, 68, 3, 99, 3},
  {2, 5, 4, 3, 3, 4, 99, 5},
  {75, 76, 77, 78, 79, 80, 81, 2},
  {5, 4, 5, 1, 1, 3, 3, 2}}

Resultado:

67

Se você definir g=Graph[...,GraphLayout->{"GridEmbedding","Dimension"->d},VertexLabels->Thread[s->m]e, em p=FindShortestPath[...seguida, o gráfico a seguir exibirá visualmente a solução (a parte superior da matriz corresponde à parte inferior do gráfico):

HighlightGraph[g,PathGraph[p,Thread[Most@p->Rest@p]]]

insira a descrição da imagem aqui

Kelly Lowder
fonte
3

Haskell, 228 bytes

As posições são listas de dois elementos, porque são fáceis de gerar sequencee tão fáceis de combinar como duas tuplas.

h=g[[-1,-1]]
g t@(p:r)c|p==m=0|1<2=minimum$(sum$concat c):(\q@[a,b]->c!!a!!b+g(q:t)c)#(f(e$s$(\x->[0..x])#m)$f(not.e t)$zipWith(+)p#s[[-1..1],[-1..1]])where m=[l(c)-1,l(head c)-1]
(#)=map
f=filter
e=flip elem
s=sequence
l=length

Comece em -1,-1e conte o custo de cada campo de destino das etapas.

Primeiras duas linhas alternativas: comece em 0,0, conte os campos de partida, termine nas coordenadas iguais às dimensões da matriz (tão abaixo da meta, que precisa ser adicionada à lista de destinos legais) - exatamente o mesmo comprimento, mas mais lento:

j=i[[0,0]]
i t@(p@[a,b]:r)c|p==m=0|1<2=c!!a!!b+(minimum$(sum$concat c):(\q->i(q:t)c)#(f(e$m:(s$(\x->[0..x-1])#m))$f(not.e t)$zipWith(+)p#s[[-1..1],[-1..1]]))where m=[l c,l$head c]

Usar um infixo para mapnão salva bytes aqui, mas eu o substituo assim que não custa um, porque só pode melhorar com mais usos e, às vezes, com outras reestruturações que reduzem outro par parênteses.

Para ser melhorado: filters redundantes . Fundindo / em-alinhando-a filter(flip elem$(s$(\x->[0..x])#m)\\p)com a import Data.Listde \\custos de três bytes.

Além disso, muito ruim (fromEnumTo 0)é 2 bytes mais longo que (\x->[0..x]).

sum$concat cé o custo de todos os campos resumido e, portanto, um limite superior concisamente expressável no custo do caminho que é atribuído ao minimumpara evitar uma lista vazia (meu verificador de tipos já determinou tudo para trabalhar em Integers, portanto, não é necessário codificar o máximo , ele Ele). Não importa como eu restrinja as etapas com base na anterior executada (o que aceleraria muito o algoritmo, mas também custaria bytes), não posso evitar os becos sem saída que tornam esse fallback necessário.

  • Uma ideia de filtro era ((not.e n).zipWith(-)(head r))com a extração n=s[[-1..1],[-1..1]], o que requer adição ,[-1,-1]ao caminho inicial. O algoritmo evita ir aonde ele já poderia ter ido na etapa anterior, o que torna o passo em um campo de borda ortogonalmente para essa borda um beco sem saída.

  • Outra foi ((>=0).sum.z(*)d)a extração z=zipWith, que introduz um novo argumento dpara a função recursiva que é dada como (z(-)p q)na recursão e [1,1]no caso inicial. O algoritmo evita etapas sucessivas com um produto escalar negativo ( dsendo a etapa anterior), o que significa que não há curvas acentuadas de 45 °. Isso ainda reduz consideravelmente as opções e evita o beco sem saída trivial anterior, mas ainda existem caminhos que acabam fechados em campos já visitados (e possivelmente uma 'fuga' que, no entanto, seria uma curva acentuada).

Leif Willerts
fonte
3

Python 2, 356 320 bytes

s=input()
r=lambda x:[x-1,x,x+1][-x-2:]
w=lambda z:[z+[(x,y)]for x in r(z[-1][0])for y in r(z[-1][1])if x<len(s)>0==((x,y)in z)<len(s[0])>y]
l=len(s)-1,len(s[0])-1
f=lambda x:all(l in y for y in x)and x or f([a for b in[l in z and[z]or w(z)for z in x]for a in b])
print min(sum(s[a][b]for(a,b)in x)for x in f([[(0,0)]]))

Experimente aqui!

-36 bytes graças a notjagan !

Recebe uma lista de listas como entrada e gera o menor custo ao navegar na matriz do canto superior esquerdo para o canto inferior direito.

Explicação

Encontre todas as rotas possíveis da parte superior esquerda para a parte inferior direita da matriz, criando uma lista de coordenadas x, y para cada rota. As rotas não podem voltar atrás e devem terminar em (len(s)-1,len(s[0])-1).

Soma os números inteiros em cada caminho de coordenadas e retorne o custo mínimo.

O printpode ser facilmente alterado para a saída da lista de coordenadas para a rota mais curta.

Solvação
fonte
-36 bytes com algumas alterações diversas.
precisa saber é
@notjagan Grandes mudanças, especialmente o uso de orpara os condicionais. Obrigado!
Solvation
1

APL (Dyalog Classic) , 33 bytes

{⊃⌽,(⊢⌊⍵+(⍉3⌊/⊣/,⊢,⊢/)⍣2)⍣≡+\+⍀⍵}

Experimente online!

{ } função com argumento

+\+⍀⍵ tome somas parciais por linha e por coluna para estabelecer um limite superior pessimista nas distâncias do caminho

( )⍣≡ repita até a convergência:

  • (⍉3⌊/⊣/,⊢,⊢/)⍣2min de distâncias para os vizinhos, ou seja, faça duas vezes ( ( )⍣2): acrescente a coluna da esquerda ( ⊣/,) a si mesmo ( ) e adicione a coluna da direita ( ,⊢/), encontre os mínimos em triplos horizontais ( 3⌊/) e transponha ( )

  • ⍵+ adicione o valor de cada nó ao seu min de distâncias aos vizinhos

  • ⊢⌊ tente vencer as melhores distâncias atuais

⊃⌽, finalmente, retorne a célula inferior direita

ngn
fonte