Mayor número de atracciones visitables
En el siguiente gráfico se representa en una cuadrícula el plano de Manhattan. Cada línea es una opción a seguir; el número representa las atracciones que se pueden visitar si se elige esa opción.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
3 2 4 0 * ------- * ------- * ------- * ------- * | | | | | |1 |0 |2 |4 |3 | 3 | 2 | 4 | 2 | * ------- * ------- * ------- * ------- * | | | | | |4 |6 |5 |2 |1 | 0 | 7 | 3 | 4 | * ------- * ------- * ------- * ------- * | | | | | |4 |4 |5 |2 |1 | 3 | 3 | 0 | 2 | * ------- * ------- * ------- * ------- * | | | | | |5 |6 |8 |5 |3 | 1 | 3 | 2 | 2 | * ------- * ------- * ------- * ------- * |
El turista entra por el extremo superior izquierda y sale por el extremo inferior derecha. Sólo puede moverse en las direcciones Sur y Este (es decir, hacia abajo o hacia la derecha).
Representamos el mapa mediante una matriz p tal que p(i,j) = (a,b), donde a = nº de atracciones si se va hacia el sur y b = nº de atracciones si se va al este. Además, ponemos un 0 en el valor del número de atracciones por un camino que no se puede elegir. De esta forma, el mapa anterior se representa por la matriz siguiente:
|
1 2 3 4 5 |
( (1,3) (0,2) (2,4) (4,0) (3,0) ) ( (4,3) (6,2) (5,4) (2,2) (1,0) ) ( (4,0) (4,7) (5,3) (2,4) (1,0) ) ( (5,3) (6,3) (8,0) (5,2) (3,0) ) ( (0,1) (0,3) (0,2) (0,2) (0,0) ) |
En este caso, si se hace el recorrido
|
1 |
[S, E, S, E, S, S, E, E], |
el número de atracciones es
|
1 |
1 3 6 7 5 8 2 2 |
cuya suma es 34.
Definir la función
|
1 |
mayorNumeroV:: M.Matrix (Int,Int) -> Int |
tal que (mayorNumeroV p) es el máximo número de atracciones que se pueden visitar en el plano representado por la matriz p. Por ejemplo, si se define la matriz anterior por
|
1 2 3 4 5 6 |
ejMapa :: M.Matrix (Int,Int) ejMapa = M.fromLists [[(1,3),(0,2),(2,4),(4,0),(3,0)], [(4,3),(6,2),(5,4),(2,2),(1,0)], [(4,0),(4,7),(5,3),(2,4),(1,0)], [(5,3),(6,3),(8,0),(5,2),(3,0)], [(0,1),(0,3),(0,2),(0,2),(0,0)]] |
entonces
|
1 2 3 |
mayorNumeroV ejMapa == 34 mayorNumeroV (fromLists [[(1,3),(0,0)],[(0,3),(0,0)]]) == 4 mayorNumeroV (fromLists [[(1,3),(6,0)],[(0,3),(0,0)]]) == 9 |
Para los siguientes ejemplos se define un generador de mapas
|
1 2 3 |
genMapa :: Int -> Matrix (Int,Int) genMapa n = extendTo (0,0) n n (fromList (n-1) (n-1) [(k,k+1) | k <- [1..]]) |
Entonces,
|
1 2 |
mayorNumeroV (genMapa 10) == 962 mayorNumeroV (genMapa 500) == 185880992 |
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 |
import Data.Matrix ejMapa :: Matrix (Int,Int) ejMapa = fromLists [[(1,3),(0,2),(2,4),(4,0),(3,0)], [(4,3),(6,2),(5,4),(2,2),(1,0)], [(4,0),(4,7),(5,3),(2,4),(1,0)], [(5,3),(6,3),(8,0),(5,2),(3,0)], [(0,1),(0,3),(0,2),(0,2),(0,0)]] genMapa :: Int -> Matrix (Int,Int) genMapa n = extendTo (0,0) n n (fromList (n-1) (n-1) [(k,k+1) | k <- [1..]]) -- 1ª definición (por recursión) -- ============================= mayorNumeroV1 :: Matrix (Int,Int) -> Int mayorNumeroV1 p = aux m n where m = nrows p n = ncols p aux 1 1 = 0 aux 1 j = sum [snd (p !(1,k)) | k <- [1..j-1]] aux i 1 = sum [fst (p !(k,1)) | k <- [1..i-1]] aux i j = max ((aux (i-1) j) + fst (p !(i-1,j))) ((aux i (j-1)) + snd (p !(i,j-1))) -- 2ª solución (con programación dinámica) -- ======================================= mayorNumeroV2 :: Matrix (Int,Int) -> Int mayorNumeroV2 p = (matrizNumeroV p) ! (m,n) where m = nrows p n = ncols p matrizNumeroV :: Matrix (Int,Int) -> Matrix Int matrizNumeroV p = q where m = nrows p n = ncols p q = matrix m n f f (1,1) = 0 f (1,j) = snd (p!(1,j-1)) + q!(1,j-1) f (i,1) = fst (p!(i-1,1)) + q!(i-1,1) f (i,j) = max (fst (p!(i-1,j)) + q!(i-1,j)) (snd (p!(i,j-1)) + q!(i,j-1)) -- 3ª solución (con programación dinámica) -- ======================================= mayorNumeroV3 :: Matrix (Int, Int) -> Int mayorNumeroV3 mapa = m ! (1,1) where m = matrix r c f r = nrows mapa c = ncols mapa f (i,j) | i == r && j == c = 0 | i == r = e + m !(r,j+1) | j == c = s + m !(i+1,c) | otherwise = max (e + m !(i, j+1)) (s + m !(i+1, j)) where (s,e) = mapa ! (i,j) -- Comparación de eficiencia -- ========================= -- λ> mayorNumeroV1 (genMapa 11) -- 1334 -- (2.07 secs, 352,208,752 bytes) -- λ> mayorNumeroV2 (genMapa 11) -- 1334 -- (0.01 secs, 319,792 bytes) -- λ> mayorNumeroV3 (genMapa 11) -- 1334 -- (0.01 secs, 299,936 bytes) -- -- λ> mayorNumeroV2 (genMapa 500) -- 185880992 -- (2.26 secs, 374,557,416 bytes) -- λ> mayorNumeroV3 (genMapa 500) -- 185880992 -- (3.15 secs, 401,098,336 bytes) |