Relación 21

-- I1M 2021-22: Relación 21
-- Programación dinámica.
-- Departamento de Ciencias de la Computación e Inteligencia Artificial
-- Universidad de Sevilla
-- ============================================================================

-- ============================================================================
-- Librerías auxiliares
-- ============================================================================

import qualified Data.Matrix as M
import qualified Data.Array as A
import qualified Data.Vector as V

-- ----------------------------------------------------------------------------
-- Ejercicio 1: Definir la función
--   fib :: Int -> Integer
-- tal que '(fib n)' es el n-ésimo de programación dinámica. Por ejemplo,
--   fib 10                 ==  55
--   fib 100                ==  354224848179261915075
--   fib 1000 `mod` 10^20   ==  76137795166849228875
--   fib 10000 `mod` 10^20  ==  66073310059947366875
-- ----------------------------------------------------------------------------

-- Álvaro Galisteo:

fib :: Int -> Integer
fib n = v A.! n
      where v = A.array (0,n) [(i, f i)| i <- [0..n]]
            f 0 = 0
            f 1 = 1
            f n = v A.! (n-1) + v A.! (n-2) 

-- ----------------------------------------------------------------------------
-- Ejercicio 2: Los números combinatorios se pueden calcular de forma recursiva
-- mediante el uso de la siguiente ecuación en recurrencia:
-- C(n,m) = C(n-1,m-1) + C(n-1,m)
-- Para ello se puede crear esta matriz, llamada triángulo de Tartaglia:
-- 1
-- 1  1
-- 1  2  1
-- 1  3  3  1
-- 1  4  6  4  1
-- 1  5 10 10  5  1
-- ...
-- Que también nos da, para cada fila "i", los coeficientes del binomio de
-- Newton (a+b)^i
-- Crear una función (numerosCombinatorios n m) que devuelva el valor del
-- número combinatorio C(n,m)
-- ----------------------------------------------------------------------------

-- Álvaro Galisteo:

numerosCombinatorios :: Int -> Int -> Integer
numerosCombinatorios n m = (matrizTrianguloTartaglia n m) A.! (n,m)

matrizTrianguloTartaglia :: Int -> Int -> A.Array (Int,Int) Integer
matrizTrianguloTartaglia n m = A.array ((0,0),(n,m)) [((i,j),f i j)| i <- [0..n], j <- [0..m]]
                where f i 0 = 1
                      f i j | i == j = 1
                            | otherwise = (matrizTrianguloTartaglia n m) A.! (i-1,j) + (matrizTrianguloTartaglia n m) A.! (i-1,j-1) 

-- ----------------------------------------------------------------------------
-- Ejercicio 3: Un montón de barriles se construye apilando unos encima de
-- otros por capas, de forma que en cada capa todos los barriles estén apoyados
-- sobre dos de la capa inferior y todos los barriles de una misma capa estén
-- pegados unos a otros. Por ejemplo, los siguientes montones son válidos:
--             _          _   _                   _
--            / \        / \ / \                 / \
--           _\_/_      _\_/_\_/_   _       _   _\_/_   _
--          / \ / \    / \ / \ / \ / \     / \ / \ / \ / \
--          \_/ \_/    \_/ \_/ \_/ \_/     \_/ \_/ \_/ \_/
--
-- y los siguientes no son válidos:
--         _   _          _       _               _   _
--        / \ / \        / \     / \             / \ / \
--        \_/_\_/_      _\_/_   _\_/_       _   _\_/_\_/
--          / \ / \    / \ / \ / \ / \     / \ / \ / \
--          \_/ \_/    \_/ \_/ \_/ \_/     \_/ \_/ \_/
--
-- Se puede comprobar que el número de formas distintas de construir montones
-- con n barriles en la base (M_n) viene dado por la siguiente fórmula:
--
--              (n-1)
--             -------
--              \
--               \
--   M_n = 1 +    )   (n-j) * M_j
--               /
--              /
--             -------
--              j = 1
-- Intente razonar la fórmula anterior.
-- Definir la función
--   montones :: Int -> Integer
-- tal que '(montones base)' es el número de formas distintas de construir
-- montones con 'base' barriles en la base, calculado mediante la técnica de
-- programación dinámica. Por ejemplo,
--   montones 1   ==  1
--   montones 10  ==  4181
--   montones 20  ==  63245986
--   montones 30  ==  956722026041
--   montones 40  ==  14472334024676221
--   montones 50  ==  218922995834555169026
-- ----------------------------------------------------------------------------

-- Álvaro Galisteo:

montones :: Integer -> Integer
montones n = m A.! n
           where m = A.listArray (0,n) [f i| i <-[0..n]]
                 f i | i == 0 = 0
                     | otherwise = 1 + sum [(i-j)*(m A.! j) | j <- [1..(i-1)]]

-- ----------------------------------------------------------------------------
-- Ejercicio 4. Definir la función
--   numeroFactoresPrimos :: Int -> Int
-- tal que '(numeroFactoresPrimos n)' es el número de factores primos
-- (contando repeticiones) de 'n', calculado
-- mediante la técnica de programación dinámica. Por ejemplo,
--   numeroFactoresPrimos 2       ==  1
--   numeroFactoresPrimos 10      ==  2
--   numeroFactoresPrimos 100     ==  4
--   numeroFactoresPrimos 1000    ==  6
--   numeroFactoresPrimos (2*3*5*7*11*13) = 6
-- ----------------------------------------------------------------------------

-- Álvaro Galisteo:

numeroFactoresPrimos :: Integer -> Integer
numeroFactoresPrimos n = m A.! n
                       where m = A.listArray (0,n) [f i| i <- [0..n]]
                             f i | i == 0 = 0
                                 | i == 1 = 1 
                                 | otherwise = 1 + m A.! (div' i (head' [x | x <- (listaPrimos i), mod i x == 0]))

primo :: Integer -> Bool
primo n = and [mod n x /= 0| x <- [2..(n-1)]]

listaPrimos :: Integer -> [Integer]
listaPrimos n = [x | x <- [2..(n-1)], and[mod x y /= 0| y <- [2..(x-1)]]]

head' xs = if xs == [] then 0 else head xs
div' x y = if y == 0 then 0 else div x y

-- ----------------------------------------------------------------------------
-- Ejercicio 5. Problema número 15 de 'Project Euler': Comenzando en la esquina
-- superior izquierda de una rejilla de dimensiones 2x2, y moviéndose sólo
-- hacia la derecha y hacia abajo, hay exactamente 6 caminos distintos que
-- llegan a la esquina inferior derecha.
--
--   ╒═══╤═══╗  ╒═══╗───┐  ╒═══╗───┐  ╓───┬───┐  ╓───┬───┐  ╓───┬───┐
--   │   │   ║  │   ║   │  │   ║   │  ║   │   │  ║   │   │  ║   │   │
--   ├───┼───╢  ├───╚═══╗  ├───║───┤  ╚═══╪═══╗  ╚═══╗───┤  ╟───┼───┤
--   │   │   ║  │   │   ║  │   ║   │  │   │   ║  │   ║   │  ║   │   │
--   └───┴───╜  └───┴───╜  └───╚═══╛  └───┴───╜  └───╚═══╛  ╚═══╧═══╛
--
-- Definir la función:
--   caminos :: Int -> Int -> Integer
-- tal que '(caminos n m)' es el número de caminos que hay en una rejilla de
-- 'n' filas y 'm' columnas, desde la esquina superior izquierda hasta la
-- esquina inferior derecha, moviéndose sólo hacia la derecha y hacia abajo,
-- calculado mediante la técnica de programación dinámica. Por ejemplo,
--   caminos 3 3  ==  6
--   caminos 3 4  ==  10
--   caminos 4 4  ==  20
--   caminos 4 5  ==  35
--   caminos 5 5  ==  70
-- ----------------------------------------------------------------------------

-- Álvaro Galisteo:

caminos :: Int -> Int -> Int
caminos f c = m A.! (f,c)
            where m = A.listArray ((0,0),(f,c)) [g i j| i <- [0..f], j <- [0..c]]
                  g i j | i == 0 || j == 0 = 0 
                        | i == 1 || j == 1 = 1
                        | otherwise =  2 *(m A.! (i-1,j-1)) +  (m A.! (i-2,j)) +  (m A.! (i,j-2)) 

-- ----------------------------------------------------------------------------
-- Ejercicio 6: Problema número 116 de 'Project Euler': En una rejilla de 5
-- cuadros de longitud se pueden colocar de distintas formas piezas rojas de 2
-- cuadros de longitud, piezas verdes de 3 cuadros de longitud o piezas azules
-- de 4 cuadros de longitud.
--
-- En concreto, hay 7 formas distintas de colocar piezas rojas en la rejilla de
-- 5 cuadros:
--   ╔═══════╗───┬───┬───┐   ┌───╔═══════╗───┬───┐   ┌───┬───╔═══════╗───┐
--   ║       ║   │   │   │   │   ║       ║   │   │   │   │   ║       ║   │
--   ╚═══════╝───┴───┴───┘   └───╚═══════╝───┴───┘   └───┴───╚═══════╝───┘
--   ┌───┬───┬───╔═══════╗   ╔═══════╦═══════╗───┐   ╔═══════╗───╔═══════╗
--   │   │   │   ║       ║   ║       ║       ║   │   ║       ║   ║       ║
--   └───┴───┴───╚═══════╝   ╚═══════╩═══════╝───┘   ╚═══════╝───╚═══════╝
--   ┌───╔═══════╦═══════╗
--   │   ║       ║       ║
--   └───╚═══════╩═══════╝
--
-- Hay 3 formas distintas de colocar piezas verdes:
--   ╔═══════════╗───┬───┐   ┌───╔═══════════╗───┐   ┌───┬───╔═══════════╗
--   ║           ║   │   │   │   ║           ║   │   │   │   ║           ║
--   ╚═══════════╝───┴───┘   └───╚═══════════╝───┘   └───┴───╚═══════════╝
--
-- Finalmente, hay 2 formas distintas de colocar piezas azules:
--   ╔═══════════════╗───┐   ┌───╔═══════════════╗
--   ║               ║   │   │   ║               ║
--   ╚═══════════════╝───┘   └───╚═══════════════╝
--
-- Suponiendo que las piezas de colores no se pueden mezclar, hay 12 formas
-- distintas de colocar piezas en una rejilla de 5 cuadros.
--
-- Definir la función
--   combinaciones116 :: Int -> Integer
-- tal que '(combinaciones116 n)' es el número de formas distintas de colocar
-- piezas rojas de 2 cuadros de longitud, piezas verdes de 3 cuadros de
-- longitud o piezas azules de 4 cuadros de longitud, en una rejilla de 'n'
-- cuadros de longitud, sin mezclar piezas de distintos colores y usando al
-- menos una, calculado mediante la técnica de programación dinámica. Por
-- ejemplo,
--   combinaciones116 5   ==  12
--   combinaciones116 10  ==  128
--   combinaciones116 15  ==  1242
--   combinaciones116 20  ==  12566
-- ----------------------------------------------------------------------------

-- Álvaro Galisteo:

combinaciones116 :: Int -> Integer
combinaciones116 n = sum [m A.! (x,n) | x <- [0,1,2]]
                   where m = A.listArray ((0,0),(2,n)) [f i j | i <- [0..2], j <- [0..n]]
                         f i j | j < (i+2) = 0
                               | j == (i+2) = 1
                               | j > (i+2) = (m A.! (i,j-1)) + (m A.! (i,j-(i+2))) + 1  

-- ----------------------------------------------------------------------------
-- Ejercicio 7: Problema número 117 de 'Project Euler': En una rejilla de 5
-- cuadros de longitud se pueden colocar de distintas formas piezas rojas de 2
-- cuadros de longitud, piezas verdes de 3 cuadros de longitud y piezas azules
-- de 4 cuadros de longitud.
--
-- Hay 15 formas distintas de colocar las piezas:
--
--   ┌───┬───┬───┬───┬───┐   ╔═══════╗───┬───┬───┐   ┌───╔═══════╗───┬───┐
--   │   │   │   │   │   │   ║       ║   │   │   │   │   ║       ║   │   │
--   └───┴───┴───┴───┴───┘   ╚═══════╝───┴───┴───┘   └───╚═══════╝───┴───┘
--   ┌───┬───╔═══════╗───┐   ┌───┬───┬───╔═══════╗   ╔═══════╦═══════╗───┐
--   │   │   ║       ║   │   │   │   │   ║       ║   ║       ║       ║   │
--   └───┴───╚═══════╝───┘   └───┴───┴───╚═══════╝   ╚═══════╩═══════╝───┘
--   ╔═══════╗───╔═══════╗   ┌───╔═══════╦═══════╗   ╔═══════════╗───┬───┐
--   ║       ║   ║       ║   │   ║       ║       ║   ║           ║   │   │
--   ╚═══════╝───╚═══════╝   └───╚═══════╩═══════╝   ╚═══════════╝───┴───┘
--   ┌───╔═══════════╗───┐   ┌───┬───╔═══════════╗   ╔═══════╦═══════════╗
--   │   ║           ║   │   │   │   ║           ║   ║       ║           ║
--   └───╚═══════════╝───┘   └───┴───╚═══════════╝   ╚═══════╩═══════════╝
--   ╔═══════════╦═══════╗   ╔═══════════════╗───┐   ┌───╔═══════════════╗
--   ║           ║       ║   ║               ║   │   │   ║               ║
--   ╚═══════════╩═══════╝   ╚═══════════════╝───┘   └───╚═══════════════╝
--
-- Definir la función
--   combinaciones117 :: Int -> Integer
-- tal que '(combinaciones117 n)' es el número de formas distintas de colocar
-- piezas rojas de 2 cuadros de longitud, piezas verdes de 3 cuadros de
-- longitud y piezas azules de 4 cuadros de longitud, en una rejilla de 'n'
-- cuadros de longitud, calculado mediante la técnica de programación
-- dinámica. Por ejemplo,
--   combinaciones117 5   ==  15
--   combinaciones117 10  ==  401
--   combinaciones117 15  ==  10671
--   combinaciones117 20  ==  283953
-- ----------------------------------------------------------------------------

-- Álvaro Galisteo:

combinaciones117 :: Int -> Integer
combinaciones117 n = sum [m A.! (x,n) | x <- [0,1,2]] + (w A.! n) + 1
                   where m = A.listArray ((0,0),(2,n)) [f i j | i <- [0..2], j <- [0..n]]
                         f i j | j < (i+2) = 0
                               | j == (i+2) = 1
                               | j > (i+2) = (m A.! (i,j-1)) + (m A.! (i,j-(i+2))) + 1
                         w = A.listArray (0,n) [g i| i <- [0..n]]
                         g i | i < 5 = 0
                             | i >= 5 = sum [w A.! (i-x) | x <- [1,2,3,4]] + (sum [m A.! (0,i-x) | x <- [3,4]]) + (sum [m A.! (1,i-x) | x <- [2,4]]) + (sum [m A.! (2,i-x) | x <- [2,3]])


-- ----------------------------------------------------------------------------
-- Ejercicio 8. Problema número 114 de 'Project Euler': En una fila de 7
-- cuadros de longitud se pueden colocar de distintas formas piezas de longitud
-- mayor o igual que 3, de forma que haya al menos un cuadro de separación
-- entre cada dos de ellas consecutivas. Hay exactamente 17 formas de hacerlo:
--
--     ┌───┬───┬───┬───┬───┬───┬───┐       ╔═══════════╗───┬───┬───┬───┐
--     │   │   │   │   │   │   │   │       ║           ║   │   │   │   │
--     └───┴───┴───┴───┴───┴───┴───┘       ╚═══════════╝───┴───┴───┴───┘
--     ┌───╔═══════════╗───┬───┬───┐       ┌───┬───╔═══════════╗───┬───┐
--     │   ║           ║   │   │   │       │   │   ║           ║   │   │
--     └───╚═══════════╝───┴───┴───┘       └───┴───╚═══════════╝───┴───┘
--     ┌───┬───┬───╔═══════════╗───┐       ┌───┬───┬───┬───╔═══════════╗
--     │   │   │   ║           ║   │       │   │   │   │   ║           ║
--     └───┴───┴───╚═══════════╝───┘       └───┴───┴───┴───╚═══════════╝
--     ╔═══════════╗───╔═══════════╗       ╔═══════════════╗───┬───┬───┐
--     ║           ║   ║           ║       ║               ║   │   │   │
--     ╚═══════════╝───╚═══════════╝       ╚═══════════════╝───┴───┴───┘
--     ┌───╔═══════════════╗───┬───┐       ┌───┬───╔═══════════════╗───┐
--     │   ║               ║   │   │       │   │   ║               ║   │
--     └───╚═══════════════╝───┴───┘       └───┴───╚═══════════════╝───┘
--     ┌───┬───┬───╔═══════════════╗       ╔═══════════════════╗───┬───┐
--     │   │   │   ║               ║       ║                   ║   │   │
--     └───┴───┴───╚═══════════════╝       ╚═══════════════════╝───┴───┘
--     ┌───╔═══════════════════╗───┐       ┌───┬───╔═══════════════════╗
--     │   ║                   ║   │       │   │   ║                   ║
--     └───╚═══════════════════╝───┘       └───┴───╚═══════════════════╝
--     ╔═══════════════════════╗───┐       ┌───╔═══════════════════════╗
--     ║                       ║   │       │   ║                       ║
--     ╚═══════════════════════╝───┘       └───╚═══════════════════════╝
--     ╔═══════════════════════════╗
--     ║                           ║
--     ╚═══════════════════════════╝
--
-- Aunque no se de el caso en el ejemplo anterior, es posible utilizar piezas
-- de distinta longitud.
--
-- Definir la función
--   combinaciones114 :: Int -> Integer
-- tal que '(combinaciones114 n)' es el número de formas distintas de colocar
-- piezas de longitud mayor o igual que 3 en una fila de 'n' cuadros de
-- longitud, de forma que haya al menos un cuadro de separación entre cada dos
-- de ellas consecutivas, calculado mediante la técnica de programación
-- dinámica. Por ejemplo,
--   combinaciones114 7   ==  17
--   combinaciones114 10  ==  72
--   combinaciones114 15  ==  798
--   combinaciones114 20  ==  8855
-- ----------------------------------------------------------------------------

combinaciones114 :: Int -> Integer
combinaciones114 = undefined
                 
-- ----------------------------------------------------------------------------
-- Ejercicio 9. Problema número 18 de 'Project Euler': Comenzando desde el
-- extremo superior del siguiente triángulo de números y desplazándose siempre
-- hacia los números adyacentes de la fila inferior, se pueden describir un
-- total de 8 caminos que llevan hasta la última fila.
--
--                             3
--                            7 4
--                           2 4 6
--                          8 5 9 3
--
-- Si para cada camino calculamos la suma de los números por los que pasa,
-- se tendrá que el valor máximo es 3 + 7 + 4 + 9 = 23.
--
-- Definir la función
--   sumaMaxima :: [Int] -> Int
-- tal que '(sumaMaxima xs)' calcula el valor máximo de la suma de los números
-- de los caminos que van desde el extremo superior hasta un número de la
-- última fila en un triángulo de números formado por los elementos de la lista
-- 'xs', calculado mediante la técnica de programación dinámica. Por ejemplo,
--   sumaMaxima [3,7,4,2,4,6,8,5,9,3]  ==  23
--
-- Calcular el valor máximo de la suma de los números de los caminos que van
-- desde el extremo superior hasta un número de la última fila en el siguiente
-- triángulo de números:
--
--                                   75
--                                 95  64
--                               17  47  82
--                             18  35  87  10
--                           20  04  82  47  65
--                         19  01  23  75  03  34
--                       88  02  77  73  07  63  67
--                     99  65  04  28  06  16  70  92
--                   41  41  26  56  83  40  80  70  33
--                 41  48  72  33  47  32  37  16  94  29
--               53  71  44  65  25  43  91  52  97  51  14
--             70  11  33  28  77  73  17  78  39  68  17  57
--           91  71  52  38  17  14  91  43  58  50  27  29  48
--         63  66  04  68  89  53  67  30  73  16  69  87  40  31
--       04  62  98  27  23  09  70  98  73  93  38  53  60  04  23
--
-- sumaMaxima numeros18 == 1074
-- Aplicar la función 'sumaMaxima' para resolver también el problema número 67
-- del proyecto Euler.
-- ----------------------------------------------------------------------------

numerosEjemplo :: [Int]
numerosEjemplo = [03,00,00,00,
                  07,04,00,00,
                  02,04,06,00,
                  08,05,09,03]

numeros18 :: [Int]
numeros18 = [75,00,00,00,00,00,00,00,00,00,00,00,00,00,00,
             95,64,00,00,00,00,00,00,00,00,00,00,00,00,00 ,
             17,47,82,00,00,00,00,00,00,00,00,00,00,00,00,
             18,35,87,10,00,00,00,00,00,00,00,00,00,00,00,
             20,04,82,47,65,00,00,00,00,00,00,00,00,00,00,
             19,01,23,75,03,34,00,00,00,00,00,00,00,00,00,
             88,02,77,73,07,63,67,00,00,00,00,00,00,00,00,
             99,65,04,28,06,16,70,92,00,00,00,00,00,00,00,
             41,41,26,56,83,40,80,70,33,00,00,00,00,00,00,
             41,48,72,33,47,32,37,16,94,29,00,00,00,00,00,
             53,71,44,65,25,43,91,52,97,51,14,00,00,00,00,
             70,11,33,28,77,73,17,78,39,68,17,57,00,00,00,
             91,71,52,38,17,14,91,43,58,50,27,29,48,00,00,
             63,66,04,68,89,53,67,30,73,16,69,87,40,31,00,
             04,62,98,27,23,09,70,98,73,93,38,53,60,04,23]


-- Álvaro Galisteo:

sumaMaxima :: [Int] -> Int
sumaMaxima xs = maximum [w A.! (x,y) | y <- [0..x]]
              where m = A.listArray ((0,0),(x,x)) xs
                    x = (round (sqrt(sum [1 | x <- xs]))) - 1
                    w = A.listArray ((0,0),(x,x)) [f i j | i <- [0..x], j <- [0..x]]
                    f i j | i == 0 && j == 0 = m A.! (0,0)
                          | j > i = 0 
                          | j == 0 = m A.! (i,j) + w A.! (i-1,j)
                          | otherwise = m A.! (i,j) + max (w A.! (i-1,j)) (w A.! (i-1,j-1))
                    
                    

-- ----------------------------------------------------------------------------
-- Ejercicio 10. Para multiplicar una matriz de orden AxB por otra de orden BxC
-- se necesitan realizar un total de A*B*C multiplicaciones de elementos. El
-- problema del producto de cadenas de matrices consiste en determinar la mejor
-- forma de multiplicar una secuencia de matrices (con las dimensiones
-- adecuadas) minimizando el número de multiplicaciones de elementos.
--
-- Por ejemplo, si tenemos cuatro matrices A(30x1), B(1x40), C(40x10) y
-- D(10x25), los productos necesarios en las posibles asociaciones de la cadena
-- de multiplicaciones de matrices A*B*C*D son:
--     ((A*B)*C)*D :  30x1x40 + 30x40x10 + 30x10x25 = 20700
--     A*(B*(C*D)) : 40x10x25 +  1x40x25 +  30x1x25 = 11750
--     (A*B)*(C*D) :  30x1x40 + 40x10x25 + 30x40x25 = 41200
--     A*((B*C)*D) :  1x40x10 +  1x10x25 +  30x1x25 = 1400
--     (A*(B*C))*D :  1x40x10 +  30x1x10 + 30x10x25 = 8200
--
-- De forma general, consideremos un total de n matrices A1, A2, A3, ..., An
-- tales que tienen dimensiones coherentes para realizar la multiplicación
-- A1*A2*A3*...*An, y la lista de sus dimensiones es [d0,d1,d2,...,dn], es
-- decir la dimensión de A1 es d0xd1, la dimensión de A2 es d1xd2, la dimensión
-- de A3 es d2xd3, ... Si cij es el mínimo número de operaciones necesarias
-- para multiplicar las matrices desde la i-ésima hasta la j-ésima entonces se
-- tiene:
-- - cii = 0, para todo i = 1..n
-- - cij = minimo { cik + c(k+1)j + d(i-1)*dk*dj | i <= k < j }
-- - c1n es la solución del problema
--
-- Definir la función
--   pcm :: [Int] -> Int
-- tal que '(pcm ds)' es el menor número de operaciones necesarias para
-- multiplicar matrices de las dimensiones indicadas en 'ds', calculado
-- mediante la técnica de programación dinámica. Por ejemplo,
--   pcm [30,1,40,10,25]  ==  1400
-- ----------------------------------------------------------------------------

-- Álvaro Galisteo:

pcm :: [Int] -> Int
pcm ds = c A.! (1,n)
       where n = (length ds) - 1 
             d = A.listArray (0,n) ds
             c = A.listArray ((1,1),(n,n)) [f i j | i <- [1..n], j <- [1..n]]
             f i j | i == j = 0
                   | otherwise = minimum [c A.! (i,k) + c A.! (k+1,j) + (d A.! (i-1)) * (d A.! k) * (d A.! j) | k <- [i..j-1]]


-- ----------------------------------------------------------------------------
-- Ejercicio 11. Una triangulación de un polígono es una división del área en
-- un conjunto de triángulos, de forma que la unión de todos ellos es igual al
-- polígono original, y cualquier par de triángulos es disjunto o comparte
-- únicamente un vértice o un lado. En el caso de polígonos convexos, la
-- cantidad de triangulaciones posibles depende únicamente del número de
-- vértices del polígono.
--
-- Si llamamos T(n) al número de triangulaciones de un polígono de n vértices,
-- se verifica la siguiente relación de recurrencia:
--     T(2) = 1
--     T(n) = T(2)*T(n-1) + T(3)*T(n-2) + ... + T(n-1)*T(2)
--
-- Definir la función
--   numeroTriangulaciones :: Integer -> Integer
-- tal que '(numeroTriangulaciones n)' es el número de triangulaciones de un
-- polígono convexo de n vértices, calculado mediante la técnica de
-- programación dinámica. Por ejemplo,
--   numeroTriangulaciones 3    ==  1
--   numeroTriangulaciones 5    ==  5
--   numeroTriangulaciones 6    ==  14
--   numeroTriangulaciones 7    ==  42
--   numeroTriangulaciones 50   ==  131327898242169365477991900
--   numeroTriangulaciones 100  ==
--     57743358069601357782187700608042856334020731624756611000
-- ----------------------------------------------------------------------------

-- Álvaro Galisteo:

numeroTriangulaciones :: Int -> Integer
numeroTriangulaciones n = m A.! n
                        where m = A.listArray (2,n) [f i | i <- [2..n]]
                              f i | i == 2 = 1
                                  | otherwise = sum [(m A.! x)*(m A.! (i-(x-1)))| x <- [2..(i-1)]]

-- ----------------------------------------------------------------------------
-- Ejercicio 12. 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.
--
--     * ---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 izquierdo y sale por el extremo
-- inferior derecho. 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 hacia el 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
-- siguiente matriz:
--
--   ( (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
--   [S, E, S, E, S, S, E, E],
-- el número de atracciones es
--    1  3  6  7  5  8  2  2
-- cuya suma es 34.
--
-- Definir la función
--   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', calculado mediante la
-- técnica de programación dinámica. Por ejemplo, si se define la matriz
-- anterior por
--   ej1b :: M.Matrix (Int,Int)
--   ej1b = 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
--   mayorNumeroV ej1b == 34
--   mayorNumeroV (M.fromLists [[(1,3),(0,0)],
--                              [(0,3),(0,0)]]) == 4
--   mayorNumeroV (M.fromLists [[(1,3),(0,2),(2,0)],
--                              [(4,3),(6,2),(5,0)],
--                              [(0,0),(0,7),(0,0)]]) == 17
-- ----------------------------------------------------------------------------

ej1b :: M.Matrix (Int,Int)
ej1b = 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)]]


-- Álvaro Galisteo:

mayorNumeroV :: M.Matrix (Int,Int) -> Int
mayorNumeroV p = (\ (x,y) -> max x y) (m M.! (x,y))
               where x = M.nrows p
                     y = M.ncols p
                     m = M.matrix x y f
                     mejorCamino i j = max (snd(m M.! (i, j-1))) (fst(m M.! (i-1,j)))
                     f (i,j) | i == 1 && j == 1 = p M.! (1,1)
                             | i == 1 = (\ (x,y) -> (snd(m M.! (1,j-1)) + x, snd(m M.! (1,j-1)) + y)) (p M.! (1,j))
                             | j == 1 = (\ (x,y) -> (fst(m M.! (i-1,1)) + x, fst(m M.! (i-1,1)) + y)) (p M.! (i,1))
                             | otherwise = (\ (x,y) -> ((mejorCamino i j) + x, (mejorCamino i j) + y)) (p M.! (i,j))

-- ----------------------------------------------------------------------------
-- Ejercicio 13. Una partición prima de un número natural n es un conjunto de
-- primos cuya suma es n. Por ejemplo, el número 7 tiene 3 particiones primas
-- ya que
--    7 = 7 = 5 + 2 = 3 + 2 + 2
--
-- Definir la función
--   particiones :: Int -> Integer
-- tal que '(particiones n)' es el número de particiones primas del número
-- natural 'n', calculado mediante la técnica de programación dinámica. Por
-- ejemplo,
--   particiones 7     ==  3
--   particiones 8     ==  3
--   particiones 9     ==  47
--   particiones 90    ==  20636
--   particiones 100   ==  40899
--   particiones 500   ==  414270104287
--   particiones 1000  ==  48278613741845757
-- ----------------------------------------------------------------------------

particiones :: Int -> Integer
particiones = undefined

primos :: Integer -> [Integer]
primos n = [x | x <- [2..n], and[mod x y /= 0| y <- [2..(x-1)]]]

-- ============================================================================

data Mat = Mat [[String]] Int

instance Show Mat where
  show (Mat x m) = "/ " ++ (showRow (x !! 0) m) ++ "\\\n" ++
                   (showIntermediateRows x 1 m) ++
                   "\\ " ++ (showRow (x !! (length x - 1)) m) ++ "/"

showRow :: [String] -> Int -> String
showRow [] m = []
showRow (x:xs) m = (replicate (m - (length x)) ' ') ++ x ++ " " ++ (showRow xs m)

showIntermediateRows :: [[String]] -> Int -> Int -> String
showIntermediateRows xxs i m | i >= length xxs - 1 = []
                             | otherwise = "| " ++ showRow (xxs !! i) m ++ "|\n" ++
                               showIntermediateRows xxs (i+1) m

printMatrix :: Show a => M.Matrix a -> Mat
printMatrix m = Mat (M.toLists nm) mx
  where nm = (M.mapPos (\ (i,j) e -> show e) m)
        mx = maximum (map (length) (M.toList nm))