Dada una matriz que consiste en enteros positivos, genera la ruta con la suma más baja cuando se atraviesa desde el elemento superior izquierdo hasta el inferior derecho. Puede moverse verticalmente, horizontalmente y diagonalmente. Tenga en cuenta que es posible moverse hacia arriba / abajo, derecha / izquierda y diagonalmente a todos los lados.
Ejemplo:
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*
La ruta que da la suma más baja está marcada con asteriscos y da como resultado la siguiente suma: 1 + 4 + 1 + 1 + 1 + 5 + 1 + 9 = 23 .
Casos de prueba:
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 es el código de golf, por lo que gana el código más corto en cada idioma.
code-golf
number
graph-theory
optimization
matrix
Stewie Griffin
fuente
fuente
Respuestas:
JavaScript,
442 412 408358 bytesEsta es mi primera presentación PPCG. Se agradecería cualquier comentario.
Esto toma una matriz multidimensional como entrada.
Explicación
Básicamente, recorra todas las celdas una y otra vez ajustando el costo más bajo conocido para llegar a cada uno de los vecinos. Finalmente, la cuadrícula alcanzará un estado donde el costo total para llegar a la esquina inferior derecha es el costo más bajo para llegar allí.
Manifestación
Editar: Un agradecimiento especial a @ETHproductions por ayudarme a afeitar docenas de sabrosos bytes.
Más gracias a @Stewie Griffin por sus consejos que eliminaron 50 bytes.
fuente
}
cual debería ahorrar algunos bytes. Tampoco necesita declarar sus variables; Creo que eliminar losvar
s debería ahorrarte 24 bytes más en total.m[v][t]
como una variable:t=x+X;v=y+Y;k=m[v][t]
¿será aún más corto ...?Python 3 + numpy + scipy ,
239222186 bytesPruébalo en línea!
fuente
Octave + Paquete de procesamiento de imágenes,
175162157151142139 bytesAhorró 14 bytes gracias a @Luis Mendo y 1 byte gracias a @notjagan
Utiliza el paquete de procesamiento de imágenes, porque ¿por qué no? ¿No es así como todos resuelven los problemas gráficos?
Pruébalo en línea!
Explotó
Explicación
Dada una variedad de pesos:
Inicialice una matriz de costos para que el costo de alcanzar cada elemento sea Infinito, excepto el punto de partida (el elemento superior izquierdo) cuyo costo es igual a su peso.
Esta es la iteración 0. Para cada iteración posterior, el costo para llegar a una celda se establece en el mínimo de:
Después de la primera iteración, el costo de la ruta al elemento (2,2) (usando indexación basada en 1) será
La matriz de costos completa después de la primera iteración sería:
Después de la iteración
k
, cada elemento será el costo más bajo de llegar a ese elemento desde el principio siguiendo la mayoría de losk
pasos. Por ejemplo, el elemento en (3,3) se puede alcanzar en 2 pasos (iteraciones) por un costo de 22:Pero en la cuarta iteración, se encuentra una ruta de 4 pasos con un costo de 20:
Dado que ninguna ruta a través de la matriz mxn puede ser más larga que el número de elementos en la matriz (como un límite superior muy suelto), después de las
m*n
iteraciones, cada elemento contendrá el costo de la ruta más corta para llegar a ese elemento desde el principio.fuente
while
y~
.while
afor
y todavía era capaz de utilizar su punta. ¡Gracias!JavaScript, 197 bytes
Embellecer:
fuente
Mathematica 279 Bytes
La idea básica es crear un gráfico con vértices correspondientes a entradas de matriz y aristas dirigidas entre dos vértices separados por un valor
ChessboardDistance
mayor que cero pero menor o igual que 1. Por cierto, esto se conoce como un gráfico King , ya que corresponde a Los movimientos válidos de un rey en un tablero de ajedrez.FindShortestPath
luego se usa para obtener la ruta mínima. FuncionaEdgeWeight
, noVertexWeight
, por lo que hay un código adicional para definirEdgeWeight
como la entrada de matriz correspondiente al destino de cada borde dirigido.Código:
Tenga en cuenta que el
carácter es el símbolo de transposición. Se pegará en Mathematica tal cual.Uso:
Salida:
Si configura
g=Graph[...,GraphLayout->{"GridEmbedding","Dimension"->d},VertexLabels->Thread[s->m]
yp=FindShortestPath[...
luego el siguiente gráfico mostrará visualmente la solución (la parte superior de la matriz corresponde a la parte inferior del gráfico):fuente
Haskell, 228 bytes
Las posiciones son listas de dos elementos, porque son fáciles de generar
sequence
e igual de fáciles de combinar que las 2 tuplas.Comience
-1,-1
y cuente el costo del campo de destino de cada paso.Primeras dos líneas alternativas: comience en
0,0
, cuente los campos de salida, termine en las coordenadas iguales a las dimensiones de la matriz (tan hacia abajo a la derecha del objetivo, que debe agregarse a la lista de destinos legales), exactamente la misma longitud pero más lenta:El uso de un infijo para
map
no ahorra bytes aquí, pero lo sustituyo tan pronto como no cuesta uno, porque solo puede mejorar con más usos y, a veces, también con otras reestructuraciones que eliminan otro par de paréntesis.Para mejorar: redundante
filter
s. La fusión de / en-alineándolos afilter(flip elem$(s$(\x->[0..x])#m)\\p)
laimport Data.List
de\\
los costos de 3 bytes.Además, muy mal
(fromEnumTo 0)
es 2 bytes más largo que(\x->[0..x])
.sum$concat c
es el costo de todos los campos resumido y, por lo tanto, un límite superior expresable de manera concisa en el costo de la ruta que se le da paraminimum
evitar una lista vacía (mi comprobador de tipos ya ha determinado todo para trabajar enInteger
s, por lo que no hay que codificar el máximo , jeje). No importa cómo restrinja los pasos basados en el anterior realizado (lo que aceleraría mucho el algoritmo, pero también costaría bytes), no puedo evitar los callejones sin salida que hacen necesario este retroceso.Una idea de filtro fue la
((not.e n).zipWith(-)(head r))
extracciónn=s[[-1..1],[-1..1]]
, que requiere agregar,[-1,-1]
a la ruta inicial. El algoritmo evita ir a donde ya podría haber ido en el paso anterior, lo que hace que pisar un campo de borde ortogonalmente a ese borde sea un callejón sin salida.Otro fue
((>=0).sum.z(*)d)
con la extracciónz=zipWith
, que introduce un nuevo argumentod
para la función recursiva que se da como(z(-)p q)
en la recursividad y[1,1]
en el caso inicial. El algoritmo evita pasos sucesivos con un producto escalar negativo (qued
es el paso anterior), lo que significa que no hay vueltas bruscas de 45 °. Esto todavía reduce considerablemente las opciones y evita el callejón sin salida trivial anterior, pero todavía hay caminos que terminan encerrados en campos ya visitados (y posiblemente un 'escape' que, sin embargo, sería un giro brusco).fuente
Python 2,
356320 bytesPruébalo aquí!
-36 bytes gracias a notjagan !
Recibe una lista de listas como entrada y genera el costo más bajo cuando navega por la matriz desde la parte superior izquierda a la parte inferior derecha.
Explicación
Encuentre todas las rutas posibles desde la parte superior izquierda hasta la parte inferior derecha de la matriz, creando una lista de coordenadas x, y para cada ruta. Las rutas no pueden dar marcha atrás, y deben terminar en
(len(s)-1,len(s[0])-1)
.Suma los enteros en cada ruta de coordenadas y devuelve el costo mínimo.
Se
print
puede cambiar fácilmente para generar la lista de coordenadas para la ruta más corta.fuente
or
los condicionales. ¡Gracias!APL (Dyalog Classic) , 33 bytes
Pruébalo en línea!
{ }
funcionar con argumento⍵
+\+⍀⍵
tomar sumas parciales por fila y por columna para establecer un límite superior pesimista en las distancias de ruta( )⍣≡
repetir hasta la convergencia:(⍉3⌊/⊣/,⊢,⊢/)⍣2
min de distancias a los vecinos, es decir, hacer dos veces (( )⍣2
): anteponer la columna más a la izquierda (⊣/,
) a self (⊢
) y agregar las columnas más a la derecha (,⊢/
), encontrar los mínimos en triples horizontales (3⌊/
) y transponer (⍉
)⍵+
agregue el valor de cada nodo a su mínimo de distancias a los vecinos⊢⌊
intenta superar las mejores distancias actuales⊃⌽,
finalmente, devuelve la celda inferior derechafuente