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 código-golfe, portanto o código mais curto em cada idioma vence.
code-golf
number
graph-theory
optimization
matrix
Stewie Griffin
fonte
fonte
Respostas:
JavaScript,
442 412 408358 bytesEste é o meu primeiro envio de PPCG. O feedback seria apreciado.
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
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.
fonte
}
que deve economizar alguns bytes. Você também não precisa declarar suas variáveis; Eu acho que remover osvar
s deve economizar mais 24 bytes no total.m[v][t]
como variável:t=x+X;v=y+Y;k=m[v][t]
será ainda mais curto ...?Python 3 + numpy + scipy ,
239222186 bytesExperimente online!
fonte
Pacote Octave + Processamento de imagem,
175162157151142139 bytesEconomizou 14 bytes graças a @Luis Mendo e 1 byte graças a @notjagan
Usa o pacote Image Processing, porque por que não? Não é assim que todo mundo resolve problemas gráficos?
Experimente online!
Explodido
Explicação
Dada uma variedade de pesos:
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.
Esta é a iteração 0. Para cada iteração subsequente, o custo para atingir uma célula é definido no mínimo de:
Após a primeira iteração, o custo do caminho para o elemento (2,2) (usando a indexação baseada em 1) será
A matriz de custo completo após a primeira iteração seria:
Após a iteração
k
, cada elemento terá o menor custo para alcançá-lo desde o início, executando na maioria dask
etapas. Por exemplo, o elemento em (3,3) pode ser alcançado em 2 etapas (iterações) por um custo de 22:Mas na quarta iteração, um caminho de 4 etapas é encontrado com um custo de 20:
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*n
iterações, cada elemento conterá o custo do caminho mais curto para alcançar esse elemento desde o início.fonte
while
e~
.while
afor
e ainda foi capaz de usar sua dica. Obrigado!JavaScript, 197 bytes
Embelezar:
fonte
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
ChessboardDistance
maior 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 funcionaEdgeWeight
, nãoVertexWeight
, portanto, há algum código extra para definirEdgeWeight
como a entrada da matriz correspondente ao destino de cada aresta direcionada.Código:
Observe que o
caractere é o símbolo de transposição. Ele será colado no Mathematica como está.Uso:
Resultado:
Se você definir
g=Graph[...,GraphLayout->{"GridEmbedding","Dimension"->d},VertexLabels->Thread[s->m]
e, emp=FindShortestPath[...
seguida, o gráfico a seguir exibirá visualmente a solução (a parte superior da matriz corresponde à parte inferior do gráfico):fonte
Haskell, 228 bytes
As posições são listas de dois elementos, porque são fáceis de gerar
sequence
e tão fáceis de combinar como duas tuplas.Comece em
-1,-1
e 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:Usar um infixo para
map
nã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:
filter
s redundantes . Fundindo / em-alinhando-afilter(flip elem$(s$(\x->[0..x])#m)\\p)
com aimport Data.List
de\\
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 aominimum
para evitar uma lista vazia (meu verificador de tipos já determinou tudo para trabalhar emInteger
s, 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çãon=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çãoz=zipWith
, que introduz um novo argumentod
para 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 (d
sendo 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).fonte
Python 2,
356320 bytesExperimente 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
print
pode ser facilmente alterado para a saída da lista de coordenadas para a rota mais curta.fonte
or
para os condicionais. Obrigado!APL (Dyalog Classic) , 33 bytes
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⌊/⊣/,⊢,⊢/)⍣2
min 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 direitafonte