p
es una función (tipo polimórfico de clase) que toma una permutación como una lista de Int
s, y una lista anidada que representa una matriz multidimensional de Int
s.
Llame como p [2,1] [[10,20,30],[40,50,60]]
, sin embargo, si el valor predeterminado de tipo no tiene éxito, es posible que tenga que agregar una anotación de tipo como :: [[Int]]
(anidada adecuadamente) dando el tipo del resultado.
import Data.List
class P a where p::[Int]->[a]->[a]
instance P Int where p _=id
instance P a=>P[a]where p(x:r)m|n<-p r<$>m,y:z<-sort r=last$n:[p(x:z)<$>transpose n|x>y]
Pruébalo en línea!
Los desafíos de golf con matrices anidadas de profundidad arbitraria son un poco incómodos en Haskell, porque la escritura estática tiende a interferir. Si bien las listas de Haskell (con la misma sintaxis exacta que en la descripción del desafío) se pueden anidar perfectamente, las listas de diferentes profundidades de anidación son de tipos incompatibles. Además, las funciones de análisis estándar de Haskell requieren conocer el tipo del valor que está intentando analizar.
Como resultado, parece inevitable que el programa necesite incluir declaraciones relacionadas con el tipo, que son relativamente detalladas. Para la parte de golf, decidí definir una clase de tipo P
, tal que p
pueda ser polimórfica sobre el tipo de matriz.
Mientras tanto, el arnés de prueba del TIO muestra una forma de sortear el problema del análisis.
Cómo funciona
Para resumir la esencia de este algoritmo: realiza una clasificación de burbujas en la lista de permutación, transponiendo dimensiones vecinas cuando se intercambian los índices de permutación correspondientes.
Como lo indica la class P a
declaración, en cualquier caso, p
toma dos argumentos, una permutación (siempre de tipo [Int]
) y una matriz.
- La permutación se puede dar en la forma en la descripción del desafío, aunque la forma en que funciona el algoritmo, la elección de los índices es arbitraria, excepto por su orden relativo. (Así que tanto el trabajo basado en 0 como en el 1).
- La base
instance P Int
maneja matrices de dimensión 1, que p
simplemente regresa sin cambios, ya que la única dimensión solo se puede asignar a sí misma.
- El otro
instance P a => P [a]
se define de forma recursiva, llamando p
con dimensión n submatrices con el fin de definir para la dimensión n + 1 arrays.
p(x:r)m
primeras llamadas de forma p r
recursiva en cada elemento de m
, dando una matriz de resultados n
en la que todas las dimensiones, excepto la primera, se han permutado correctamente entre sí.
- La permutación restante que debe realizarse
n
está dada por x:y:z = x:sort r
.
- Si
x<y
entonces, la primera dimensión de n
ya está colocada correctamente, y n
simplemente se devuelve.
- Si
x>y
, entonces la primera y segunda dimensión de n
necesidad de intercambiarse, que se hace con la transpose
función. Finalmente, p(x:z)
se aplica de forma recursiva a cada elemento del resultado, asegurando que la primera dimensión original se transponga a la posición correcta.
exec
(guardar dos bytes) , ya que es una declaración en Python 2.z(p) for
.map(z,l)
,s%j
yprint
para 301 bytes - Pruébelo en línea!Python 2 ,
4125 bytesPruébalo en línea!
El vector de permutación
p
se da como una cadena de letras. Entonces[2,3,1]
se puede dar como'bca'
.¡Gracias a @EriktheOutgolfer ahorró 16 bytes!
fuente
JavaScript (ES6),
136132 bytes0 indexado. Explicación:
g
itera recursivamente sobre la matriza
creando una matrizv
de índices reordenados usando la permutaciónp
. Una vez quep
se agota,h
inserta recursivamente el elemento en la matriz de resultadosr
utilizando los índices permutados.fuente