Mayor producto de n números adyacentes en una matriz
Definir la función
|
1 |
mayorProductoAdyacentes :: (Num a, Ord a) => Int -> Matriz a -> [[a]] |
tal que (mayorProductoAdyacentes n p) es la lista de los segmentos formados por n elementos adyacentes en la misma fila, columna o diagonal de la matriz p cuyo productos son máximo. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
ghci> mayorProductoAdyacentes 3 (listArray ((1,1),(3,4)) [1..12]) [[10,11,12]] ghci> mayorProductoAdyacentes 3 (listArray ((1,1),(3,4)) [1,3,4,5, 0,7,2,1, 3,9,2,1]) [[3,7,9]] ghci> mayorProductoAdyacentes 2 (listArray ((1,1),(2,3)) [1,3,4, 0,3,2]) [[3,4],[4,3]] ghci> mayorProductoAdyacentes 2 (listArray ((1,1),(2,3)) [1,2,1, 3,0,3]) [[2,3],[2,3]] ghci> mayorProductoAdyacentes 2 (listArray ((1,1),(2,3)) [1,2,1, 3,4,3]) [[3,4],[4,3]] ghci> mayorProductoAdyacentes 2 (listArray ((1,1),(2,3)) [1,5,1, 3,4,3]) [[5,4]] ghci> mayorProductoAdyacentes 3 (listArray ((1,1),(3,4)) [1,3,4,5, 0,7,2,1, 3,9,2,1]) [[3,7,9]] |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
import Data.Array type Matriz a = Array (Int,Int) a mayorProductoAdyacentes :: (Num a, Ord a) => Int -> Matriz a -> [[a]] mayorProductoAdyacentes n p = [xs | xs <- segmentos, product xs == m] where segmentos = adyacentes n p m = maximum (map product segmentos) -- (adyacentes n p) es la lista de los segmentos de longitud n de las -- líneas de la matriz p. Por ejemplo, -- ghci> adyacentes 3 (listArray ((1,1),(3,4)) [1..12]) -- [[1,2,3],[2,3,4],[5,6,7],[6,7,8],[9,10,11],[10,11,12],[1,5,9], -- [2,6,10],[3,7,11],[4,8,12],[1,6,11],[2,7,12],[3,6,9],[4,7,10]] adyacentes :: Num a => Int -> Matriz a -> [[a]] adyacentes n p = concatMap (segmentos n) (lineas p) -- (lineas p) es la lista de las líneas de la matriz p. Por ejemplo, -- ghci> lineas (listArray ((1,1),(3,4)) [1..12]) -- [[1,2,3,4],[5,6,7,8],[9,10,11,12], -- [1,5,9],[2,6,10],[3,7,11],[4,8,12], -- [9],[5,10],[1,6,11],[2,7,12],[3,8],[4], -- [1],[2,5],[3,6,9],[4,7,10],[8,11],[12]] lineas :: Num a => Matriz a -> [[a]] lineas p = filas p ++ columnas p ++ diagonalesPrincipales p ++ diagonalesSecundarias p -- (filas p) es la lista de las filas de la matriz p. Por ejemplo, -- ghci> filas (listArray ((1,1),(3,4)) [1..12]) -- [[1,2,3,4],[5,6,7,8],[9,10,11,12]] filas :: Num a => Matriz a -> [[a]] filas p = [fila i p | i <- [1..m]] where (_,(m,_)) = bounds p -- (fila i p) es la fila i-ésima de la matriz p. Por ejemplo, -- fila 2 (listArray ((1,1),(3,4)) [1..12]) == [5,6,7,8] fila :: Num a => Int -> Matriz a -> [a] fila i p = [p!(i,j) | j <- [1..n]] where (_,(_,n)) = bounds p -- (columnas p) es la lista de las columnas de la matriz p. Por ejemplo, -- ghci> columnas (listArray ((1,1),(3,4)) [1..12]) -- [[1,5,9],[2,6,10],[3,7,11],[4,8,12]] columnas :: Num a => Matriz a -> [[a]] columnas p = [columna j p | j <- [1..n]] where (_,(_,n)) = bounds p -- (columna j p) es la columna j-ésima de la matriz p. Por ejemplo, -- columna 2 (listArray ((1,1),(3,4)) [1..12]) == [2,6,10] columna :: Num a => Int -> Matriz a -> [a] columna j p = [p!(i,j) | i <- [1..m]] where (_,(m,_)) = bounds p -- (diagonalesPrincipales p) es la lista de las diagonales principales -- de p. Por ejemplo, -- ghci> diagonalesPrincipales (listArray ((1,1),(3,4)) [1..12]) -- [[9],[5,10],[1,6,11],[2,7,12],[3,8],[4]] diagonalesPrincipales :: Matriz a -> [[a]] diagonalesPrincipales p = [[p!ij1 | ij1 <- extension ij] | ij <- iniciales] where (_,(m,n)) = bounds p iniciales = [(i,1) | i <- [m,m-1..2]] ++ [(1,j) | j <- [1..n]] extension (i,j) = [(i+k,j+k) | k <- [0..min (m-i) (n-j)]] -- (diagonalesSecundarias p) es la lista de las diagonales secundarias -- de p. Por ejemplo, -- ghci> diagonalesSecundarias (listArray ((1,1),(3,4)) [1..12]) -- [[1],[2,5],[3,6,9],[4,7,10],[8,11],[12]] diagonalesSecundarias p = [[p!ij1 | ij1 <- extension ij] | ij <- iniciales] where (_,(m,n)) = bounds p iniciales = [(1,j) | j <- [1..n]] ++ [(i,n) | i <- [2..m]] extension (i,j) = [(i+k,j-k) | k <- [0..min (j-1) (m-i)]] -- (segmentos n xs) es la lista de los segmentos de longitud n de la -- lista xs. Por ejemplo, -- segmentos 3 [1..5] == [[1,2,3],[2,3,4],[3,4,5]] segmentos :: Int -> [a] -> [[a]] segmentos n xs | length xs < n = [] | otherwise = take n xs : segmentos n (tail xs) |