Medio

Sucesiones de números consecutivos con suma dada

PorJosé A. Alonso 29-marzo-20187-abril-2018

El número 15 se puede escribir de 5 formas como suma de números naturales consecutivos:

   15 = 0+1+2+3+4+5 = 1+2+3+4+5 = 4+5+6 = 7+8 = 15.

1	15 = 0+1+2+3+4+5 = 1+2+3+4+5 = 4+5+6 = 7+8 = 15.

Definir las funciones

   sucesionesConSuma        :: Int -> [(Int,Int)]
   graficaSucesionesConSuma :: Int -> IO ()

1 2	sucesionesConSuma :: Int -> [(Int,Int)] graficaSucesionesConSuma :: Int -> IO ()

tales que

(sucesionesConSuma n) es la lista de los pares formados por el primero y por el último elemento de las sucesiones de números naturales consecutivos con suma n. Por ejemplo,

     sucesionesConSuma 15             ==  [(0,5),(1,5),(4,6),(7,8),(15,15)]
     length (sucesionesConSuma 3000)  ==  8

1 2	sucesionesConSuma 15 == [(0,5),(1,5),(4,6),(7,8),(15,15)] length (sucesionesConSuma 3000) == 8

(graficaSucesionesConSuma n) dibuja la gráfica del número de formas de escribir los n primeros números como suma de números naturales consecutivos. Por ejemplo, (graficaSucesionesConSuma 100) dibuja

Soluciones

import Graphics.Gnuplot.Simple

-- 1ª solución
sucesionesConSuma :: Int -> [(Int,Int)]
sucesionesConSuma n =
  [(x,y) | y <- [0..n], x <- [0..y], sum [x..y] == n]

-- 2ª solución
sucesionesConSuma2 :: Int -> [(Int,Int)]
sucesionesConSuma2 n = 
    [(x,y) | y <- [0..n], x <- [0..y], (x+y)*(y-x+1) == 2*n]

-- Comparación de eficiencia
--    λ> sucesionesConSuma 700
--    [(3,37),(16,40),(84,91),(97,103),(138,142),(700,700)]
--    (2.71 secs, 7,894,718,264 bytes)
--    λ> sucesionesConSuma2 700
--    [(3,37),(16,40),(84,91),(97,103),(138,142),(700,700)]
--    (0.22 secs, 118,104,176 bytes)

-- Gráfica
graficaSucesionesConSuma :: Int -> IO ()
graficaSucesionesConSuma n =
  plotList [ Key Nothing
           , PNG "Sucesiones_de_numeros_consecutivos_con_suma_dada.png"]
           [length (sucesionesConSuma2 k) | k <- [0..n]]

import Graphics.Gnuplot.Simple

-- 1ª solución

sucesionesConSuma :: Int -> [(Int,Int)]

sucesionesConSuma n =

[(x,y) | y <- [0..n], x <- [0..y], sum [x..y] == n]

-- 2ª solución

sucesionesConSuma2 :: Int -> [(Int,Int)]

sucesionesConSuma2 n =

[(x,y) | y <- [0..n], x <- [0..y], (x+y)*(y-x+1) == 2*n]

-- Comparación de eficiencia

-- λ> sucesionesConSuma 700

-- [(3,37),(16,40),(84,91),(97,103),(138,142),(700,700)]

-- (2.71 secs, 7,894,718,264 bytes)

-- λ> sucesionesConSuma2 700

-- [(3,37),(16,40),(84,91),(97,103),(138,142),(700,700)]

-- (0.22 secs, 118,104,176 bytes)

-- Gráfica

graficaSucesionesConSuma :: Int -> IO ()

graficaSucesionesConSuma n =

plotList [ Key Nothing

, PNG "Sucesiones_de_numeros_consecutivos_con_suma_dada.png"]

[length (sucesionesConSuma2 k) | k <- [0..n]]

Conjetura de Goldbach

PorJosé A. Alonso 21-marzo-201826-marzo-2022

Una forma de la conjetura de Golbach afirma que todo entero mayor que 1 se puede escribir como la suma de uno, dos o tres números primos.

Si se define el índice de Goldbach de n > 1 como la mínima cantidad de primos necesarios para que su suma sea n, entonces la conjetura de Goldbach afirma que todos los índices de Goldbach de los enteros mayores que 1 son menores que 4.

Definir las siguientes funciones

   indiceGoldbach  :: Int -> Int
   graficaGoldbach :: Int -> IO ()

1 2	indiceGoldbach :: Int -> Int graficaGoldbach :: Int -> IO ()

tales que

(indiceGoldbach n) es el índice de Goldbach de n. Por ejemplo,

     indiceGoldbach 2                        ==  1
     indiceGoldbach 4                        ==  2
     indiceGoldbach 27                       ==  3
     sum (map indiceGoldbach [2..5000])      ==  10619
     maximum (map indiceGoldbach [2..5000])  ==  3

indiceGoldbach 2 == 1

indiceGoldbach 4 == 2

indiceGoldbach 27 == 3

sum (map indiceGoldbach [2..5000]) == 10619

maximum (map indiceGoldbach [2..5000]) == 3

(graficaGoldbach n) dibuja la gráfica de los índices de Goldbach de los números entre 2 y n. Por ejemplo, (graficaGoldbach 150) dibuja

Comprobar con QuickCheck la conjetura de Goldbach anterior.

Soluciones

import Data.Array
import Data.Numbers.Primes
import Graphics.Gnuplot.Simple
import Test.QuickCheck


-- 1ª definición
-- =============

indiceGoldbach :: Int -> Int
indiceGoldbach n =
  minimum (map length (particiones n))

particiones :: Int -> [[Int]]
particiones n = v ! n where
  v = array (0,n) [(i,f i) | i <- [0..n]]
    where f 0 = [[]]
          f m = [x:y | x <- xs, 
                       y <- v ! (m-x), 
                       [x] >= take 1 y]
            where xs = reverse (takeWhile (<= m) primes)

-- 2ª definición
-- =============

indiceGoldbach2 :: Int -> Int
indiceGoldbach2 x =
  head [n | n <- [1..], esSumaDe x n]

-- (esSumaDe x n) se verifica si x se puede escribir como la suma de n
-- primos. Por ejemplo,
--    esSumaDe 2  1  ==  True
--    esSumaDe 4  1  ==  False
--    esSumaDe 4  2  ==  True
--    esSumaDe 27 2  ==  False
--    esSumaDe 27 3  ==  True
esSumaDe :: Int -> Int -> Bool
esSumaDe x 1 = isPrime x
esSumaDe x n = or [esSumaDe (x-p) (n-1) | p <- takeWhile (<= x) primes]

-- 3ª definición
-- =============

indiceGoldbach3 :: Int -> Int
indiceGoldbach3 x =
  head [n | n <- [1..], esSumaDe3 x n]

esSumaDe3 :: Int -> Int -> Bool
esSumaDe3 x n = a ! (x,n) where
  a = array ((2,1),(x,9)) [((i,j),f i j) | i <- [2..x], j <- [1..9]]
  f i 1 = isPrime i
  f i j = or [a!(i-k,j-1) | k <- takeWhile (<= i) primes]

-- 4ª definición
-- =============

indiceGoldbach4 :: Int -> Int
indiceGoldbach4 n = v ! n where
  v = array (2,n) [(i,f i) | i <- [2..n]]
  f i | isPrime i = 1
      | otherwise = 1 + minimum [v!(i-p) | p <- takeWhile (< (i-1)) primes]

-- Comparación de eficiencia
-- =========================

--    λ> sum (map indiceGoldbach [2..80])
--    142
--    (2.66 secs, 1,194,330,496 bytes)
--    λ> sum (map indiceGoldbach2 [2..80])
--    142
--    (0.01 secs, 1,689,944 bytes)
--    λ> sum (map indiceGoldbach3 [2..80])
--    142
--    (0.03 secs, 27,319,296 bytes)
--    λ> sum (map indiceGoldbach4 [2..80])
--    142
--    (0.03 secs, 47,823,656 bytes)
--    
--    λ> sum (map indiceGoldbach2 [2..1000])
--    2030
--    (0.10 secs, 200,140,264 bytes)
--    λ> sum (map indiceGoldbach3 [2..1000])
--    2030
--    (3.10 secs, 4,687,467,664 bytes)

-- Gráfica
-- =======

graficaGoldbach :: Int -> IO ()
graficaGoldbach n =
  plotList [ Key Nothing
           , XRange (2,fromIntegral n)
           , PNG ("Conjetura_de_Goldbach_" ++ show n ++ ".png")
           ]
           [indiceGoldbach2 k | k <- [2..n]]

-- Comprobación de la conjetura de Goldbach
-- ========================================

-- La propiedad es
prop_Goldbach :: Int -> Property
prop_Goldbach x =
  x >= 2 ==> indiceGoldbach2 x < 4

-- La comprobación es
--    λ> quickCheck prop_Goldbach
--    +++ OK, passed 100 tests.

100

101

102

103

104

105

106

107

import Data.Array

import Data.Numbers.Primes

import Graphics.Gnuplot.Simple

import Test.QuickCheck

-- 1ª definición

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

indiceGoldbach :: Int -> Int

indiceGoldbach n =

minimum (map length (particiones n))

particiones :: Int -> [[Int]]

particiones n = v ! n where

v = array (0,n) [(i,f i) | i <- [0..n]]

where f 0 = [[]]

f m = [x:y | x <- xs,

y <- v ! (m-x),

[x] >= take 1 y]

where xs = reverse (takeWhile (<= m) primes)

-- 2ª definición

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

indiceGoldbach2 :: Int -> Int

indiceGoldbach2 x =

head [n | n <- [1..], esSumaDe x n]

-- (esSumaDe x n) se verifica si x se puede escribir como la suma de n

-- primos. Por ejemplo,

-- esSumaDe 2 1 == True

-- esSumaDe 4 1 == False

-- esSumaDe 4 2 == True

-- esSumaDe 27 2 == False

-- esSumaDe 27 3 == True

esSumaDe :: Int -> Int -> Bool

esSumaDe x 1 = isPrime x

esSumaDe x n = or [esSumaDe (x-p) (n-1) | p <- takeWhile (<= x) primes]

-- 3ª definición

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

indiceGoldbach3 :: Int -> Int

indiceGoldbach3 x =

head [n | n <- [1..], esSumaDe3 x n]

esSumaDe3 :: Int -> Int -> Bool

esSumaDe3 x n = a ! (x,n) where

a = array ((2,1),(x,9)) [((i,j),f i j) | i <- [2..x], j <- [1..9]]

f i 1 = isPrime i

f i j = or [a!(i-k,j-1) | k <- takeWhile (<= i) primes]

-- 4ª definición

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

indiceGoldbach4 :: Int -> Int

indiceGoldbach4 n = v ! n where

v = array (2,n) [(i,f i) | i <- [2..n]]

f i | isPrime i = 1

| otherwise = 1 + minimum [v!(i-p) | p <- takeWhile (< (i-1)) primes]

-- Comparación de eficiencia

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

-- λ> sum (map indiceGoldbach [2..80])

-- 142

-- (2.66 secs, 1,194,330,496 bytes)

-- λ> sum (map indiceGoldbach2 [2..80])

-- 142

-- (0.01 secs, 1,689,944 bytes)

-- λ> sum (map indiceGoldbach3 [2..80])

-- 142

-- (0.03 secs, 27,319,296 bytes)

-- λ> sum (map indiceGoldbach4 [2..80])

-- 142

-- (0.03 secs, 47,823,656 bytes)

-- λ> sum (map indiceGoldbach2 [2..1000])

-- 2030

-- (0.10 secs, 200,140,264 bytes)

-- λ> sum (map indiceGoldbach3 [2..1000])

-- 2030

-- (3.10 secs, 4,687,467,664 bytes)

-- Gráfica

-- =======

graficaGoldbach :: Int -> IO ()

graficaGoldbach n =

plotList [ Key Nothing

, XRange (2,fromIntegral n)

, PNG ("Conjetura_de_Goldbach_" ++ show n ++ ".png")

]

[indiceGoldbach2 k | k <- [2..n]]

-- Comprobación de la conjetura de Goldbach

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

-- La propiedad es

prop_Goldbach :: Int -> Property

prop_Goldbach x =

x >= 2 ==> indiceGoldbach2 x < 4

-- La comprobación es

-- λ> quickCheck prop_Goldbach

-- +++ OK, passed 100 tests.

Particiones primas

PorJosé A. Alonso 20-marzo-201828-marzo-2018

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 7 particiones primas ya que

   7 = 7 = 5 + 2 = 3 + 2 + 2

1	7 = 7 = 5 + 2 = 3 + 2 + 2

Definir la función

   particiones :: Int -> [[Int]]

1	particiones :: Int -> [[Int]]

tal que (particiones n) es el comjunto de las particiones primas de n. Por ejemplo,

   particiones 7             ==  [[7],[5,2],[3,2,2]]
   particiones 8             ==  [[5,3],[3,3,2],[2,2,2,2]]
   particiones 9             ==  [[7,2],[5,2,2],[3,3,3],[3,2,2,2]]
   length (particiones 100)  ==  40899

particiones 7 == [[7],[5,2],[3,2,2]]

particiones 8 == [[5,3],[3,3,2],[2,2,2,2]]

particiones 9 == [[7,2],[5,2,2],[3,3,3],[3,2,2,2]]

length (particiones 100) == 40899

Soluciones

import Data.Numbers.Primes (primes)
import Data.Array          (Array, (!), array)

-- 1ª solución
-- ===========

particiones1 :: Int -> [[Int]]
particiones1 0 = [[]]
particiones1 n = [x:y | x <- xs, 
                        y <- particiones1 (n-x), 
                        [x] >= take 1 y]
  where xs = reverse (takeWhile (<= n) primes)

-- 2ª solución (con programación dinámica)
-- =======================================

particiones2 :: Int -> [[Int]]
particiones2 n = (vectorParticiones n) ! n

-- (vectorParticiones n) es el vector con índices de 0 a n tal que el
-- valor del índice k es la lista de las particiones primas de k. Por
-- ejemplo, 
--    λ> mapM_ print (elems (vectorParticiones 9))
--    [[]]
--    []
--    [[2]]
--    [[3]]
--    [[2,2]]
--    [[5],[3,2]]
--    [[3,3],[2,2,2]]
--    [[7],[5,2],[3,2,2]]
--    [[5,3],[3,3,2],[2,2,2,2]]
--    [[7,2],[5,2,2],[3,3,3],[3,2,2,2]]
--    λ> elems (vectorParticiones 9) == map particiones1 [0..9]
--    True
vectorParticiones :: Int -> Array Int [[Int]]
vectorParticiones n = v where
  v = array (0,n) [(i,f i) | i <- [0..n]]
    where f 0 = [[]]
          f m = [x:y | x <- xs, 
                       y <- v ! (m-x), 
                       [x] >= take 1 y]
            where xs = reverse (takeWhile (<= m) primes)

-- Comparación de eficiencia
-- =========================

--    λ> length (particiones1 35)
--    175
--    (5.88 secs, 2,264,266,040 bytes)
--    λ> length (particiones2 35)
--    175
--    (0.02 secs, 1,521,560 bytes)

import Data.Numbers.Primes (primes)

import Data.Array (Array, (!), array)

-- 1ª solución

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

particiones1 :: Int -> [[Int]]

particiones1 0 = [[]]

particiones1 n = [x:y | x <- xs,

y <- particiones1 (n-x),

[x] >= take 1 y]

where xs = reverse (takeWhile (<= n) primes)

-- 2ª solución (con programación dinámica)

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

particiones2 :: Int -> [[Int]]

particiones2 n = (vectorParticiones n) ! n

-- (vectorParticiones n) es el vector con índices de 0 a n tal que el

-- valor del índice k es la lista de las particiones primas de k. Por

-- ejemplo,

-- λ> mapM_ print (elems (vectorParticiones 9))

-- [[]]

-- []

-- [[2]]

-- [[3]]

-- [[2,2]]

-- [[5],[3,2]]

-- [[3,3],[2,2,2]]

-- [[7],[5,2],[3,2,2]]

-- [[5,3],[3,3,2],[2,2,2,2]]

-- [[7,2],[5,2,2],[3,3,3],[3,2,2,2]]

-- λ> elems (vectorParticiones 9) == map particiones1 [0..9]

-- True

vectorParticiones :: Int -> Array Int [[Int]]

vectorParticiones n = v where

v = array (0,n) [(i,f i) | i <- [0..n]]

where f 0 = [[]]

f m = [x:y | x <- xs,

y <- v ! (m-x),

[x] >= take 1 y]

where xs = reverse (takeWhile (<= m) primes)

-- Comparación de eficiencia

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

-- λ> length (particiones1 35)

-- 175

-- (5.88 secs, 2,264,266,040 bytes)

-- λ> length (particiones2 35)

-- 175

-- (0.02 secs, 1,521,560 bytes)

La sucesión de Sylvester

PorJosé A. Alonso 19-marzo-201825-abril-2021

La sucesión de Sylvester es la sucesión que comienza en 2 y sus restantes términos se obtienen multiplicando los anteriores y sumándole 1.

Definir las funciones

   sylvester        :: Integer -> Integer
   graficaSylvester :: Integer -> Integer -> IO ()

1 2	sylvester :: Integer -> Integer graficaSylvester :: Integer -> Integer -> IO ()

tales que

(sylvester n) es el n-ésimo término de la sucesión de Sylvester. Por ejemplo,

     λ> [sylvester n | n <- [0..7]]
     [2,3,7,43,1807,3263443,10650056950807,113423713055421844361000443]
     λ> length (show (sylvester 25))
     6830085

λ> [sylvester n | n <- [0..7]]

[2,3,7,43,1807,3263443,10650056950807,113423713055421844361000443]

λ> length (show (sylvester 25))

6830085

(graficaSylvester d n) dibuja la gráfica de los d últimos dígitos de los n primeros términos de la sucesión de Sylvester. Por ejemplo,
- (graficaSylvester 3 30) dibuja
- (graficaSylvester 4 30) dibuja
- (graficaSylvester 5 30) dibuja

Soluciones

import Data.List               (genericIndex)
import Data.Array              ((!), array)
import Graphics.Gnuplot.Simple (plotList, Attribute (Key, PNG))

-- 1ª solución (por recursión)
-- ===========================

sylvester1 :: Integer -> Integer
sylvester1 0 = 2
sylvester1 n = 1 + product [sylvester1 k | k <- [0..n-1]]

-- 2ª solución (con programación dinámica)
-- =======================================

sylvester2 :: Integer -> Integer
sylvester2 n = v ! n where
  v = array (0,n) [(i,f i) | i <- [0..n]]
  f 0 = 2
  f m = 1 + product [v!k | k <- [0..m-1]]

-- 3ª solución
-- ===========

sylvester3 :: Integer -> Integer
sylvester3 0 = 2
sylvester3 n = 1 + x^2 - x
  where x = sylvester3 (n-1)

-- 4ª solución
-- ===========

sylvester4 :: Integer -> Integer
sylvester4 n = v ! n where
  v = array (0,n) [(i,f i) | i <- [0..n]]
  f 0 = 2
  f m = 1 + x^2 - x
    where x = v ! (m-1)

-- 4ª solución
-- ===========

sylvester5 :: Integer -> Integer
sylvester5 0 = 2
sylvester5 n = 1 + (productosSylvester `genericIndex` (n-1))

sucSylvester5 :: [Integer]
sucSylvester5 = map sylvester5 [0..]

productosSylvester :: [Integer]
productosSylvester = scanl1 (*) sucSylvester5

-- Comparación de eficiencia
-- =========================

--    λ> length (show (sylvester1 20))
--    213441
--    (3.40 secs, 519,249,840 bytes)
--    λ> length (show (sylvester2 20))
--    213441
--    (0.10 secs, 13,716,024 bytes)
--    λ> length (show (sylvester3 20))
--    213441
--    (0.16 secs, 13,646,472 bytes)
--    λ> length (show (sylvester4 20))
--    213441
--    (0.18 secs, 13,654,064 bytes)
--    λ> length (show (sylvester5 20))
--    213441
--    (0.12 secs, 13,497,192 bytes)

graficaSylvester :: Integer -> Integer -> IO ()
graficaSylvester d n =
  plotList [ Key Nothing
           , PNG ("La_sucesion_de_Sylvester_" ++ show (d,n) ++ ".png")
           ]
           [sylvester5 k `mod` (10^d) | k <- [0..n]]

import Data.List (genericIndex)

import Data.Array ((!), array)

import Graphics.Gnuplot.Simple (plotList, Attribute (Key, PNG))

-- 1ª solución (por recursión)

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

sylvester1 :: Integer -> Integer

sylvester1 0 = 2

sylvester1 n = 1 + product [sylvester1 k | k <- [0..n-1]]

-- 2ª solución (con programación dinámica)

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

sylvester2 :: Integer -> Integer

sylvester2 n = v ! n where

v = array (0,n) [(i,f i) | i <- [0..n]]

f 0 = 2

f m = 1 + product [v!k | k <- [0..m-1]]

-- 3ª solución

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

sylvester3 :: Integer -> Integer

sylvester3 0 = 2

sylvester3 n = 1 + x^2 - x

where x = sylvester3 (n-1)

-- 4ª solución

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

sylvester4 :: Integer -> Integer

sylvester4 n = v ! n where

v = array (0,n) [(i,f i) | i <- [0..n]]

f 0 = 2

f m = 1 + x^2 - x

where x = v ! (m-1)

-- 4ª solución

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

sylvester5 :: Integer -> Integer

sylvester5 0 = 2

sylvester5 n = 1 + (productosSylvester `genericIndex` (n-1))

sucSylvester5 :: [Integer]

sucSylvester5 = map sylvester5 [0..]

productosSylvester :: [Integer]

productosSylvester = scanl1 (*) sucSylvester5

-- Comparación de eficiencia

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

-- λ> length (show (sylvester1 20))

-- 213441

-- (3.40 secs, 519,249,840 bytes)

-- λ> length (show (sylvester2 20))

-- 213441

-- (0.10 secs, 13,716,024 bytes)

-- λ> length (show (sylvester3 20))

-- 213441

-- (0.16 secs, 13,646,472 bytes)

-- λ> length (show (sylvester4 20))

-- 213441

-- (0.18 secs, 13,654,064 bytes)

-- λ> length (show (sylvester5 20))

-- 213441

-- (0.12 secs, 13,497,192 bytes)

graficaSylvester :: Integer -> Integer -> IO ()

graficaSylvester d n =

plotList [ Key Nothing

, PNG ("La_sucesion_de_Sylvester_" ++ show (d,n) ++ ".png")

]

[sylvester5 k `mod` (10^d) | k <- [0..n]]

Camino de máxima suma en una matriz

PorJosé A. Alonso 16-marzo-201825-abril-2021

Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz

   (  1  6 11  2 )
   (  7 12  3  8 )
   (  3  8  4  9 )

( 1 6 11 2 )

( 7 12 3 8 )

( 3 8 4 9 )

moviéndose en cada paso una casilla hacia abajo o hacia la derecha, son los siguientes:

   1, 7,  3, 8, 4, 9
   1, 7, 12, 8, 4, 9
   1, 7, 12, 3, 4, 9
   1, 7, 12, 3, 8, 9
   1, 6, 12, 8, 4, 9
   1, 6, 12, 3, 4, 9
   1, 6, 12, 3, 8, 9
   1, 6, 11, 3, 4, 9
   1, 6, 11, 3, 8, 9
   1, 6, 11, 2, 8, 9

1, 7, 3, 8, 4, 9

1, 7, 12, 8, 4, 9

1, 7, 12, 3, 4, 9

1, 7, 12, 3, 8, 9

1, 6, 12, 8, 4, 9

1, 6, 12, 3, 4, 9

1, 6, 12, 3, 8, 9

1, 6, 11, 3, 4, 9

1, 6, 11, 3, 8, 9

1, 6, 11, 2, 8, 9

Las sumas de los caminos son 32, 41, 36, 40, 40, 35, 39, 34, 38 y 37, respectivamente. El camino de máxima suma es el segundo (1, 7, 12, 8, 4, 9) que tiene una suma de 41.

Definir la función

   caminoMaxSuma :: Matrix Int -> [Int]

1	caminoMaxSuma :: Matrix Int -> [Int]

tal que (caminoMaxSuma m) es un camino de máxima suma en la matriz m desde el extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia abajo o hacia la derecha. Por ejemplo,

   λ> caminoMaxSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
   [1,7,12,8,4,9]
   λ> sum (caminoMaxSuma (fromList 500 500 [1..]))
   187001249

λ> caminoMaxSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])

[1,7,12,8,4,9]

λ> sum (caminoMaxSuma (fromList 500 500 [1..]))

187001249

Soluciones

import Data.Matrix

-- 1ª definición
-- =============

caminoMaxSuma1 :: Matrix Int -> [Int]
caminoMaxSuma1 m =
  head [c | c <- cs, sum c == k] 
  where cs = caminos1 m
        k  = maximum (map sum cs)

caminos1 :: Matrix Int -> [[Int]]
caminos1 m =
  map reverse (caminos1Aux m (nf,nc))
  where nf = nrows m
        nc = ncols m

-- (caminos1Aux p x) es la lista de los caminos invertidos en la matriz p
-- desde la posición (1,1) hasta la posición x. Por ejemplo,
caminos1Aux :: Matrix Int -> (Int,Int) -> [[Int]]
caminos1Aux m (1,1) = [[m!(1,1)]]
caminos1Aux m (1,j) = [[m!(1,k) | k <- [j,j-1..1]]]
caminos1Aux m (i,1) = [[m!(k,1) | k <- [i,i-1..1]]]
caminos1Aux m (i,j) = [m!(i,j) : xs
                      | xs <- caminos1Aux m (i,j-1) ++
                              caminos1Aux m (i-1,j)]

-- 2ª definición
-- =============

caminoMaxSuma2 :: Matrix Int -> [Int]
caminoMaxSuma2 m =
  head [c | c <- cs, sum c == k] 
  where cs = caminos2 m
        k  = maximum (map sum cs)

caminos2 :: Matrix Int -> [[Int]]
caminos2 m =
  map reverse (matrizCaminos m ! (nrows m, ncols m))

matrizCaminos :: Matrix Int -> Matrix [[Int]]
matrizCaminos m = q
  where
    q = matrix (nrows m) (ncols m) f
    f (1,y) = [[m!(1,z) | z <- [y,y-1..1]]]
    f (x,1) = [[m!(z,1) | z <- [x,x-1..1]]]
    f (x,y) = [m!(x,y) : cs | cs <- q!(x-1,y) ++ q!(x,y-1)]  

-- 3ª definición (con programación dinámica)
-- =========================================

caminoMaxSuma3 :: Matrix Int -> [Int]
caminoMaxSuma3 m = reverse (snd (q ! (nf,nc)))
  where nf = nrows m
        nc = ncols m
        q  = caminoMaxSumaAux m

caminoMaxSumaAux :: Matrix Int -> Matrix (Int,[Int])
caminoMaxSumaAux m = q 
  where
    nf = nrows m
    nc = ncols m
    q  = matrix nf nc f
      where
        f (1,1) = (m!(1,1),[m!(1,1)])
        f (1,j) = (k + m!(1,j), m!(1,j):xs)
          where (k,xs) = q!(1,j-1)
        f (i,1) = (k + m!(i,1), m!(i,1):xs)
          where (k,xs) = q!(i-1,1)        
        f (i,j) | k1 > k2   = (k1 + m!(i,j), m!(i,j):xs)
                | otherwise = (k2 + m!(i,j), m!(i,j):ys)
          where (k1,xs) = q!(i,j-1)
                (k2,ys) = q!(i-1,j)

-- Comparación de eficiencia
-- -------------------------

--    λ> length (caminoMaxSuma1 (fromList 11 11 [1..]))
--    21
--    (10.00 secs, 1,510,120,328 bytes)
--    λ> length (caminoMaxSuma2 (fromList 11 11 [1..]))
--    21
--    (3.84 secs, 745,918,544 bytes)
--    λ> length (caminoMaxSuma3 (fromList 11 11 [1..]))
--    21
--    (0.01 secs, 0 bytes)

import Data.Matrix

-- 1ª definición

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

caminoMaxSuma1 :: Matrix Int -> [Int]

caminoMaxSuma1 m =

head [c | c <- cs, sum c == k]

where cs = caminos1 m

k = maximum (map sum cs)

caminos1 :: Matrix Int -> [[Int]]

caminos1 m =

map reverse (caminos1Aux m (nf,nc))

where nf = nrows m

nc = ncols m

-- (caminos1Aux p x) es la lista de los caminos invertidos en la matriz p

-- desde la posición (1,1) hasta la posición x. Por ejemplo,

caminos1Aux :: Matrix Int -> (Int,Int) -> [[Int]]

caminos1Aux m (1,1) = [[m!(1,1)]]

caminos1Aux m (1,j) = [[m!(1,k) | k <- [j,j-1..1]]]

caminos1Aux m (i,1) = [[m!(k,1) | k <- [i,i-1..1]]]

caminos1Aux m (i,j) = [m!(i,j) : xs

| xs <- caminos1Aux m (i,j-1) ++

caminos1Aux m (i-1,j)]

-- 2ª definición

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

caminoMaxSuma2 :: Matrix Int -> [Int]

caminoMaxSuma2 m =

head [c | c <- cs, sum c == k]

where cs = caminos2 m

k = maximum (map sum cs)

caminos2 :: Matrix Int -> [[Int]]

caminos2 m =

map reverse (matrizCaminos m ! (nrows m, ncols m))

matrizCaminos :: Matrix Int -> Matrix [[Int]]

matrizCaminos m = q

where

q = matrix (nrows m) (ncols m) f

f (1,y) = [[m!(1,z) | z <- [y,y-1..1]]]

f (x,1) = [[m!(z,1) | z <- [x,x-1..1]]]

f (x,y) = [m!(x,y) : cs | cs <- q!(x-1,y) ++ q!(x,y-1)]

-- 3ª definición (con programación dinámica)

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

caminoMaxSuma3 :: Matrix Int -> [Int]

caminoMaxSuma3 m = reverse (snd (q ! (nf,nc)))

where nf = nrows m

nc = ncols m

q = caminoMaxSumaAux m

caminoMaxSumaAux :: Matrix Int -> Matrix (Int,[Int])

caminoMaxSumaAux m = q

where

nf = nrows m

nc = ncols m

q = matrix nf nc f

where

f (1,1) = (m!(1,1),[m!(1,1)])

f (1,j) = (k + m!(1,j), m!(1,j):xs)

where (k,xs) = q!(1,j-1)

f (i,1) = (k + m!(i,1), m!(i,1):xs)

where (k,xs) = q!(i-1,1)

f (i,j) | k1 > k2 = (k1 + m!(i,j), m!(i,j):xs)

| otherwise = (k2 + m!(i,j), m!(i,j):ys)

where (k1,xs) = q!(i,j-1)

(k2,ys) = q!(i-1,j)

-- Comparación de eficiencia

-- -------------------------

-- λ> length (caminoMaxSuma1 (fromList 11 11 [1..]))

-- 21

-- (10.00 secs, 1,510,120,328 bytes)

-- λ> length (caminoMaxSuma2 (fromList 11 11 [1..]))

-- 21

-- (3.84 secs, 745,918,544 bytes)

-- λ> length (caminoMaxSuma3 (fromList 11 11 [1..]))

-- 21

-- (0.01 secs, 0 bytes)

Máximo de las sumas de los caminos en una matriz

PorJosé A. Alonso 15-marzo-201825-abril-2021

Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz

   (  1  6 11  2 )
   (  7 12  3  8 )
   (  3  8  4  9 )

( 1 6 11 2 )

( 7 12 3 8 )

( 3 8 4 9 )

moviéndose en cada paso una casilla hacia abajo o hacia la derecha, son los siguientes:

   1, 7,  3, 8, 4, 9
   1, 7, 12, 8, 4, 9
   1, 7, 12, 3, 4, 9
   1, 7, 12, 3, 8, 9
   1, 6, 12, 8, 4, 9
   1, 6, 12, 3, 4, 9
   1, 6, 12, 3, 8, 9
   1, 6, 11, 3, 4, 9
   1, 6, 11, 3, 8, 9
   1, 6, 11, 2, 8, 9

1, 7, 3, 8, 4, 9

1, 7, 12, 8, 4, 9

1, 7, 12, 3, 4, 9

1, 7, 12, 3, 8, 9

1, 6, 12, 8, 4, 9

1, 6, 12, 3, 4, 9

1, 6, 12, 3, 8, 9

1, 6, 11, 3, 4, 9

1, 6, 11, 3, 8, 9

1, 6, 11, 2, 8, 9

Las sumas de los caminos son 32, 41, 36, 40, 40, 35, 39, 34, 38 y 37, respectivamente. El máximo de las suma de los caminos es 41.

Definir la función

   maximaSuma :: Matrix Int -> Int

1	maximaSuma :: Matrix Int -> Int

tal que (maximaSuma m) es el máximo de las sumas de los caminos en la matriz m desde el extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia abajo o hacia la derecha. Por ejemplo,

   λ> maximaSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
   41
   λ> maximaSuma (fromList 800 800 [1..])
   766721999

λ> maximaSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])

λ> maximaSuma (fromList 800 800 [1..])

766721999

Soluciones

import Data.Matrix

-- 1ª definición
-- =============

maximaSuma1 :: Matrix Int -> Int
maximaSuma1 =
  maximum . map sum . caminos1

caminos1 :: Matrix Int -> [[Int]]
caminos1 m =
  map reverse (caminos1Aux m (nf,nc))
  where nf = nrows m
        nc = ncols m

-- (caminos1Aux p x) es la lista de los caminos invertidos en la matriz p
-- desde la posición (1,1) hasta la posición x. Por ejemplo,
caminos1Aux :: Matrix Int -> (Int,Int) -> [[Int]]
caminos1Aux m (1,1) = [[m!(1,1)]]
caminos1Aux m (1,j) = [[m!(1,k) | k <- [j,j-1..1]]]
caminos1Aux m (i,1) = [[m!(k,1) | k <- [i,i-1..1]]]
caminos1Aux m (i,j) = [m!(i,j) : xs
                      | xs <- caminos1Aux m (i,j-1) ++
                              caminos1Aux m (i-1,j)]

-- 2ª definición
-- =============

maximaSuma2 :: Matrix Int -> Int
maximaSuma2 =
  maximum . map sum . caminos2

caminos2 :: Matrix Int -> [[Int]]
caminos2 m =
  map reverse (matrizCaminos m ! (nrows m, ncols m))

matrizCaminos :: Matrix Int -> Matrix [[Int]]
matrizCaminos m = q
  where
    q = matrix (nrows m) (ncols m) f
    f (1,y) = [[m!(1,z) | z <- [y,y-1..1]]]
    f (x,1) = [[m!(z,1) | z <- [x,x-1..1]]]
    f (x,y) = [m!(x,y) : cs | cs <- q!(x-1,y) ++ q!(x,y-1)]  

-- 3ª definicion (por recursión, sin calcular el camino)
-- =====================================================

maximaSuma3 :: Matrix Int -> Int
maximaSuma3 m = maximaSuma3Aux m (nf,nc)
  where nf = nrows m
        nc = ncols m

-- (maximaSuma3Aux m p) calcula la suma máxima de un camino hasta la
-- posición p. Por ejemplo,
--    λ> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (3,4)
--    41
--    λ> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (3,3)
--    32
--    λ> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (2,4)
--    31
maximaSuma3Aux :: Matrix Int -> (Int,Int) -> Int
maximaSuma3Aux m (1,1) = m ! (1,1)
maximaSuma3Aux m (1,j) = maximaSuma3Aux m (1,j-1) + m ! (1,j)
maximaSuma3Aux m (i,1) = maximaSuma3Aux m (i-1,1) + m ! (i,1)
maximaSuma3Aux m (i,j) =
  max (maximaSuma3Aux m (i,j-1)) (maximaSuma3Aux m (i-1,j)) + m ! (i,j)

-- 4ª solución (mediante programación dinámica)
-- ============================================

maximaSuma4 :: Matrix Int -> Int
maximaSuma4 m = q ! (nf,nc)
  where nf = nrows m
        nc = ncols m
        q  = matrizMaximaSuma m

-- (matrizMaximaSuma m) es la matriz donde en cada posición p se
-- encuentra el máxima de las sumas de los caminos desde (1,1) a p en la
-- matriz m. Por ejemplo,   
--    λ> matrizMaximaSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) 
--    (  1  7 18 20 )
--    (  8 20 23 31 )
--    ( 11 28 32 41 )
matrizMaximaSuma :: Matrix Int -> Matrix Int
matrizMaximaSuma m = q 
  where nf = nrows m
        nc = ncols m
        q  = matrix nf nc f
          where  f (1,1) = m ! (1,1)
                 f (1,j) = q ! (1,j-1) + m ! (1,j)
                 f (i,1) = q ! (i-1,1) + m ! (i,1)
                 f (i,j) = max (q ! (i,j-1)) (q ! (i-1,j)) + m ! (i,j)

-- Comparación de eficiencia
-- =========================

--    λ> maximaSuma1 (fromList 8 8 [1..])
--    659
--    (0.11 secs, 31,853,136 bytes)
--    λ> maximaSuma1a (fromList 8 8 [1..])
--    659
--    (0.09 secs, 19,952,640 bytes)
-- 
--    λ> maximaSuma1 (fromList 10 10 [1..])
--    1324
--    (2.25 secs, 349,722,744 bytes)
--    λ> maximaSuma2 (fromList 10 10 [1..])
--    1324
--    (0.76 secs, 151,019,296 bytes)
--    
--    λ> maximaSuma2 (fromList 11 11 [1..])
--    1781
--    (3.02 secs, 545,659,632 bytes)
--    λ> maximaSuma3 (fromList 11 11 [1..])
--    1781
--    (1.57 secs, 210,124,912 bytes)
--    
--    λ> maximaSuma3 (fromList 12 12 [1..])
--    2333
--    (5.60 secs, 810,739,032 bytes)
--    λ> maximaSuma4 (fromList 12 12 [1..])
--    2333
--    (0.01 secs, 23,154,776 bytes)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

import Data.Matrix

-- 1ª definición

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

maximaSuma1 :: Matrix Int -> Int

maximaSuma1 =

maximum . map sum . caminos1

caminos1 :: Matrix Int -> [[Int]]

caminos1 m =

map reverse (caminos1Aux m (nf,nc))

where nf = nrows m

nc = ncols m

-- (caminos1Aux p x) es la lista de los caminos invertidos en la matriz p

-- desde la posición (1,1) hasta la posición x. Por ejemplo,

caminos1Aux :: Matrix Int -> (Int,Int) -> [[Int]]

caminos1Aux m (1,1) = [[m!(1,1)]]

caminos1Aux m (1,j) = [[m!(1,k) | k <- [j,j-1..1]]]

caminos1Aux m (i,1) = [[m!(k,1) | k <- [i,i-1..1]]]

caminos1Aux m (i,j) = [m!(i,j) : xs

| xs <- caminos1Aux m (i,j-1) ++

caminos1Aux m (i-1,j)]

-- 2ª definición

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

maximaSuma2 :: Matrix Int -> Int

maximaSuma2 =

maximum . map sum . caminos2

caminos2 :: Matrix Int -> [[Int]]

caminos2 m =

map reverse (matrizCaminos m ! (nrows m, ncols m))

matrizCaminos :: Matrix Int -> Matrix [[Int]]

matrizCaminos m = q

where

q = matrix (nrows m) (ncols m) f

f (1,y) = [[m!(1,z) | z <- [y,y-1..1]]]

f (x,1) = [[m!(z,1) | z <- [x,x-1..1]]]

f (x,y) = [m!(x,y) : cs | cs <- q!(x-1,y) ++ q!(x,y-1)]

-- 3ª definicion (por recursión, sin calcular el camino)

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

maximaSuma3 :: Matrix Int -> Int

maximaSuma3 m = maximaSuma3Aux m (nf,nc)

where nf = nrows m

nc = ncols m

-- (maximaSuma3Aux m p) calcula la suma máxima de un camino hasta la

-- posición p. Por ejemplo,

-- λ> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (3,4)

-- 41

-- λ> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (3,3)

-- 32

-- λ> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (2,4)

-- 31

maximaSuma3Aux :: Matrix Int -> (Int,Int) -> Int

maximaSuma3Aux m (1,1) = m ! (1,1)

maximaSuma3Aux m (1,j) = maximaSuma3Aux m (1,j-1) + m ! (1,j)

maximaSuma3Aux m (i,1) = maximaSuma3Aux m (i-1,1) + m ! (i,1)

maximaSuma3Aux m (i,j) =

max (maximaSuma3Aux m (i,j-1)) (maximaSuma3Aux m (i-1,j)) + m ! (i,j)

-- 4ª solución (mediante programación dinámica)

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

maximaSuma4 :: Matrix Int -> Int

maximaSuma4 m = q ! (nf,nc)

where nf = nrows m

nc = ncols m

q = matrizMaximaSuma m

-- (matrizMaximaSuma m) es la matriz donde en cada posición p se

-- encuentra el máxima de las sumas de los caminos desde (1,1) a p en la

-- matriz m. Por ejemplo,

-- λ> matrizMaximaSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])

-- ( 1 7 18 20 )

-- ( 8 20 23 31 )

-- ( 11 28 32 41 )

matrizMaximaSuma :: Matrix Int -> Matrix Int

matrizMaximaSuma m = q

where nf = nrows m

nc = ncols m

q = matrix nf nc f

where f (1,1) = m ! (1,1)

f (1,j) = q ! (1,j-1) + m ! (1,j)

f (i,1) = q ! (i-1,1) + m ! (i,1)

f (i,j) = max (q ! (i,j-1)) (q ! (i-1,j)) + m ! (i,j)

-- Comparación de eficiencia

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

-- λ> maximaSuma1 (fromList 8 8 [1..])

-- 659

-- (0.11 secs, 31,853,136 bytes)

-- λ> maximaSuma1a (fromList 8 8 [1..])

-- 659

-- (0.09 secs, 19,952,640 bytes)

-- λ> maximaSuma1 (fromList 10 10 [1..])

-- 1324

-- (2.25 secs, 349,722,744 bytes)

-- λ> maximaSuma2 (fromList 10 10 [1..])

-- 1324

-- (0.76 secs, 151,019,296 bytes)

-- λ> maximaSuma2 (fromList 11 11 [1..])

-- 1781

-- (3.02 secs, 545,659,632 bytes)

-- λ> maximaSuma3 (fromList 11 11 [1..])

-- 1781

-- (1.57 secs, 210,124,912 bytes)

-- λ> maximaSuma3 (fromList 12 12 [1..])

-- 2333

-- (5.60 secs, 810,739,032 bytes)

-- λ> maximaSuma4 (fromList 12 12 [1..])

-- 2333

-- (0.01 secs, 23,154,776 bytes)

Caminos en una matriz

PorJosé A. Alonso 14-marzo-201825-abril-2021

Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz

   (  1  6 11  2 )
   (  7 12  3  8 )
   (  3  8  4  9 )

( 1 6 11 2 )

( 7 12 3 8 )

( 3 8 4 9 )

moviéndose en cada paso una casilla hacia abajo o hacia la derecha, son los siguientes:

   1, 7,  3, 8, 4, 9
   1, 7, 12, 8, 4, 9
   1, 7, 12, 3, 4, 9
   1, 7, 12, 3, 8, 9
   1, 6, 12, 8, 4, 9
   1, 6, 12, 3, 4, 9
   1, 6, 12, 3, 8, 9
   1, 6, 11, 3, 4, 9
   1, 6, 11, 3, 8, 9
   1, 6, 11, 2, 8, 9

1, 7, 3, 8, 4, 9

1, 7, 12, 8, 4, 9

1, 7, 12, 3, 4, 9

1, 7, 12, 3, 8, 9

1, 6, 12, 8, 4, 9

1, 6, 12, 3, 4, 9

1, 6, 12, 3, 8, 9

1, 6, 11, 3, 4, 9

1, 6, 11, 3, 8, 9

1, 6, 11, 2, 8, 9

Definir la función

   caminos :: Matrix Int -> [[Int]]

1	caminos :: Matrix Int -> [[Int]]

tal que (caminos m) es la lista de los caminos en la matriz m desde el extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia abajo o hacia la derecha. Por ejemplo,

   λ> caminos (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
   [[1,7, 3,8,4,9],
    [1,7,12,8,4,9],
    [1,7,12,3,4,9],
    [1,7,12,3,8,9],
    [1,6,12,8,4,9],
    [1,6,12,3,4,9],
    [1,6,12,3,8,9],
    [1,6,11,3,4,9],
    [1,6,11,3,8,9],
    [1,6,11,2,8,9]]
   λ> length (caminos (fromList 12 13 [1..]))
   1352078

λ> caminos (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])

[[1,7, 3,8,4,9],

[1,7,12,8,4,9],

[1,7,12,3,4,9],

[1,7,12,3,8,9],

[1,6,12,8,4,9],

[1,6,12,3,4,9],

[1,6,12,3,8,9],

[1,6,11,3,4,9],

[1,6,11,3,8,9],

[1,6,11,2,8,9]]

λ> length (caminos (fromList 12 13 [1..]))

1352078

Soluciones

import Data.Matrix

-- 1ª definición de caminos (por recursión)
-- ----------------------------------------

caminos1 :: Matrix Int -> [[Int]]
caminos1 a = aux (1,1)
  where
    aux (i,j)
      | i == m           = [[a!(i,k) | k <- [j..n]]]
      | j == n           = [[a!(k,j) | k <- [i..m]]]
      | otherwise        = [a!(i,j) : cs | cs <- aux (i+1,j) ++ aux (i,j+1)]
      where m = nrows a
            n = ncols a

-- 2ª solución (mediante programación dinámica)
-- --------------------------------------------

caminos2 :: Matrix Int -> [[Int]]
caminos2 a = q ! (1,1)
  where
    q = matrix m n f
    m = nrows a
    n = ncols a
    f (i,j) | i == m    = [[a!(i,k) | k <- [j..n]]]
            | j == n    = [[a!(k,j) | k <- [i..m]]]
            | otherwise = [a!(i,j) : cs | cs <- q!(i+1,j) ++ q!(i,j+1)]  

-- 3ª solución
-- ===========

caminos3 :: Matrix Int -> [[Int]]
caminos3 a
  | m == 1 || n == 1 = [toList a]
  | otherwise = map (a ! (1,1):) (caminos3 (submatrix 2 m 1 n a) ++
                                  caminos3 (submatrix 1 m 2 n a)) 
  where m = nrows a
        n = ncols a

-- Comparación de eficiencia
-- -------------------------

--    λ> length (caminos1 (fromList 11 11 [1..]))
--    184756
--    (4.15 secs, 738,764,712 bytes)
--    λ> length (caminos2 (fromList 11 11 [1..]))
--    184756
--    (0.74 secs, 115,904,952 bytes)
--    λ> length (caminos3 (fromList 11 11 [1..]))
--    184756
--    (2.22 secs, 614,472,136 bytes)

import Data.Matrix

-- 1ª definición de caminos (por recursión)

-- ----------------------------------------

caminos1 :: Matrix Int -> [[Int]]

caminos1 a = aux (1,1)

where

aux (i,j)

| i == m = [[a!(i,k) | k <- [j..n]]]

| j == n = [[a!(k,j) | k <- [i..m]]]

| otherwise = [a!(i,j) : cs | cs <- aux (i+1,j) ++ aux (i,j+1)]

where m = nrows a

n = ncols a

-- 2ª solución (mediante programación dinámica)

-- --------------------------------------------

caminos2 :: Matrix Int -> [[Int]]

caminos2 a = q ! (1,1)

where

q = matrix m n f

m = nrows a

n = ncols a

f (i,j) | i == m = [[a!(i,k) | k <- [j..n]]]

| j == n = [[a!(k,j) | k <- [i..m]]]

| otherwise = [a!(i,j) : cs | cs <- q!(i+1,j) ++ q!(i,j+1)]

-- 3ª solución

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

caminos3 :: Matrix Int -> [[Int]]

caminos3 a

| m == 1 || n == 1 = [toList a]

| otherwise = map (a ! (1,1):) (caminos3 (submatrix 2 m 1 n a) ++

caminos3 (submatrix 1 m 2 n a))

where m = nrows a

n = ncols a

-- Comparación de eficiencia

-- -------------------------

-- λ> length (caminos1 (fromList 11 11 [1..]))

-- 184756

-- (4.15 secs, 738,764,712 bytes)

-- λ> length (caminos2 (fromList 11 11 [1..]))

-- 184756

-- (0.74 secs, 115,904,952 bytes)

-- λ> length (caminos3 (fromList 11 11 [1..]))

-- 184756

-- (2.22 secs, 614,472,136 bytes)

Suma de las sumas de los cuadrados de los divisores

PorJosé A. Alonso 7-marzo-201814-marzo-2018

La suma de las sumas de los cuadrados de los divisores de los 6 primeros números enteros positivos es

     1² + (1²+2²) + (1²+3²) + (1²+2²+4²) + (1²+5²) + (1²+2²+3²+6²)
   = 1  + 5       + 10      + 21         + 26      + 50
   = 113

1² + (1²+2²) + (1²+3²) + (1²+2²+4²) + (1²+5²) + (1²+2²+3²+6²)

= 1 + 5 + 10 + 21 + 26 + 50

= 113

Definir la función

   sumaSumasCuadradosDivisores :: Integer -> Integer

1	sumaSumasCuadradosDivisores :: Integer -> Integer

tal que (sumaSumasCuadradosDivisores n) es la suma de las sumas de los cuadrados de los divisores de los n primeros números enteros positivos. Por ejemplo,

   sumaSumasCuadradosDivisores 6       ==  113
   sumaSumasCuadradosDivisores (10^6)  ==  400686363385965077

1 2	sumaSumasCuadradosDivisores 6 == 113 sumaSumasCuadradosDivisores (10^6) == 400686363385965077

Soluciones

import Data.List (genericIndex)

-- 1ª solución
-- ===========

sumaSumasCuadradosDivisores :: Integer -> Integer
sumaSumasCuadradosDivisores n =
  sum [sumaCuadradosDivisores k | k <- [1..n]]

-- (sumaCuadradosDivisores n) es la suma de los cuadrados de los
-- divisores de n. Por ejemplo,
--    sumaCuadradosDivisores 6  ==  50
sumaCuadradosDivisores :: Integer -> Integer
sumaCuadradosDivisores n = sum (map (^2) (divisores n))

-- (divisores n) es la lista de los divisores de n. Por ejemplo, 
--    divisores 6  ==  [1,6,2,3]
divisores :: Integer -> [Integer]
divisores 1 = [1]
divisores n = 1 : n : [x | x <- [2..n `div` 2], n `mod` x == 0]

-- 2ª solución
-- ===========

sumaSumasCuadradosDivisores2 :: Integer -> Integer
sumaSumasCuadradosDivisores2 n =
  sumasSumasCuadradosDivisores `genericIndex` (n-1)

-- sumasSumasCuadradosDivisores es la sucesión cuyo n-ésimo término es
-- la suma de las sumas de los cuadrados de los divisores de n. Por
-- ejemplo, 
--    take 6 sumasSumasCuadradosDivisores  ==  [1,6,16,37,63,113]
sumasSumasCuadradosDivisores :: [Integer]
sumasSumasCuadradosDivisores = 1 : sig 1 2
  where sig m n = y : sig y (n+1)
          where y = m + sumaCuadradosDivisores n

-- 3ª solución
-- ===========

sumaSumasCuadradosDivisores3 :: Integer -> Integer
sumaSumasCuadradosDivisores3 n =
  last (sumasSumasCuadradosDivisores3 n)

-- (sumasSumasCuadradosDivisores3 n) es la sucesión cuyo k-ésimo término
-- es la suma de las sumas de los cuadrados de los divisores de k, para
-- k entre 0 y n. Por ejemplo, 
--    sumasSumasCuadradosDivisores3 6  ==  [0,6,18,36,52,77,113]
sumasSumasCuadradosDivisores3 :: Integer -> [Integer]
sumasSumasCuadradosDivisores3 n = scanl f 0 [1..n]
  where f x k = x + k^2 * (n `div` k)

-- 4ª solución
-- ===========

sumaSumasCuadradosDivisores4 :: Integer -> Integer
sumaSumasCuadradosDivisores4 n =
  last (sumasSumasCuadradosDivisores4 n)

-- (sumasSumasCuadradosDivisores4 n) es la sucesión cuyo k-ésimo término
-- es la suma de las sumas de los cuadrados de los divisores de k, para
-- k entre 0 y n. Por ejemplo, 
--    sumasSumasCuadradosDivisores4 6  ==  [0,6,18,36,52,77,113]
sumasSumasCuadradosDivisores4 :: Integer -> [Integer]
sumasSumasCuadradosDivisores4 n = scanl1 f [0,1..n]
  where f x k = x + k^2 * (n `div` k)

-- 5ª solución
-- ===========

sumaSumasCuadradosDivisores5 :: Integer -> Integer
sumaSumasCuadradosDivisores5 n =
  last (sumasSumasCuadradosDivisores5 n)

-- (sumasSumasCuadradosDivisores5 n) es la sucesión cuyo k-ésimo término
-- es la suma de las sumas de los cuadrados de los divisores de k, para
-- k entre 0 y n. Por ejemplo, 
--    sumasSumasCuadradosDivisores5 6  ==  [0,6,18,36,52,77,113]
sumasSumasCuadradosDivisores5 :: Integer -> [Integer]
sumasSumasCuadradosDivisores5 n = scanl1 f [0,1..n]
  where f x k = x + k * (n - (n `mod` k))

-- 6ª solución
-- ===========

-- Cada elemento k de [1..n], al cuadrado, aparece tantas veces como la
-- parte entera de n/k; luego,
--    sumaSumasCuadradosDivisores n =
--       1^2*n + 2^2*(n `div` 2) + 3^2*(n `div` 3) + ... + n^2*1

sumaSumasCuadradosDivisores6 :: Integer -> Integer
sumaSumasCuadradosDivisores6 n = sum (zipWith (*) ds vs)
  where ds = map (^2) [1..n]
        vs = [n `div` k | k <- [1..n]]

-- Comparación de eficiencia:
-- =========================

--    λ> sumaSumasCuadradosDivisores (3*10^3)
--    10825397502
--    (3.29 secs, 468,721,192 bytes)
--    λ> sumaSumasCuadradosDivisores2 (3*10^3)
--    10825397502
--    (3.25 secs, 469,462,600 bytes)
--    λ> sumaSumasCuadradosDivisores3 (3*10^3)
--    10825397502
--    (0.03 secs, 2,788,752 bytes)
--    λ> sumaSumasCuadradosDivisores4 (3*10^3)
--    10825397502
--    (0.03 secs, 2,813,304 bytes)
--    λ> sumaSumasCuadradosDivisores5 (3*10^3)
--    10825397502
--    (0.03 secs, 1,467,056 bytes)
--    λ> sumaSumasCuadradosDivisores6 (3*10^3)
--    10825397502
--    (0.03 secs, 3,291,664 bytes)
--    
--    λ> sumaSumasCuadradosDivisores3 (5*10^5)
--    50085873311988831
--    (2.34 secs, 440,961,640 bytes)
--    λ> sumaSumasCuadradosDivisores4 (5*10^5)
--    50085873311988831
--    (2.29 secs, 444,962,904 bytes)
--    λ> sumaSumasCuadradosDivisores5 (5*10^5)
--    50085873311988831
--    (1.23 secs, 220,960,152 bytes)
--    λ> sumaSumasCuadradosDivisores6 (5*10^5)
--    50085873311988831
--    (2.76 secs, 524,962,464 bytes)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

import Data.List (genericIndex)

-- 1ª solución

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

sumaSumasCuadradosDivisores :: Integer -> Integer

sumaSumasCuadradosDivisores n =

sum [sumaCuadradosDivisores k | k <- [1..n]]

-- (sumaCuadradosDivisores n) es la suma de los cuadrados de los

-- divisores de n. Por ejemplo,

-- sumaCuadradosDivisores 6 == 50

sumaCuadradosDivisores :: Integer -> Integer

sumaCuadradosDivisores n = sum (map (^2) (divisores n))

-- (divisores n) es la lista de los divisores de n. Por ejemplo,

-- divisores 6 == [1,6,2,3]

divisores :: Integer -> [Integer]

divisores 1 = [1]

divisores n = 1 : n : [x | x <- [2..n `div` 2], n `mod` x == 0]

-- 2ª solución

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

sumaSumasCuadradosDivisores2 :: Integer -> Integer

sumaSumasCuadradosDivisores2 n =

sumasSumasCuadradosDivisores `genericIndex` (n-1)

-- sumasSumasCuadradosDivisores es la sucesión cuyo n-ésimo término es

-- la suma de las sumas de los cuadrados de los divisores de n. Por

-- ejemplo,

-- take 6 sumasSumasCuadradosDivisores == [1,6,16,37,63,113]

sumasSumasCuadradosDivisores :: [Integer]

sumasSumasCuadradosDivisores = 1 : sig 1 2

where sig m n = y : sig y (n+1)

where y = m + sumaCuadradosDivisores n

-- 3ª solución

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

sumaSumasCuadradosDivisores3 :: Integer -> Integer

sumaSumasCuadradosDivisores3 n =

last (sumasSumasCuadradosDivisores3 n)

-- (sumasSumasCuadradosDivisores3 n) es la sucesión cuyo k-ésimo término

-- es la suma de las sumas de los cuadrados de los divisores de k, para

-- k entre 0 y n. Por ejemplo,

-- sumasSumasCuadradosDivisores3 6 == [0,6,18,36,52,77,113]

sumasSumasCuadradosDivisores3 :: Integer -> [Integer]

sumasSumasCuadradosDivisores3 n = scanl f 0 [1..n]

where f x k = x + k^2 * (n `div` k)

-- 4ª solución

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

sumaSumasCuadradosDivisores4 :: Integer -> Integer

sumaSumasCuadradosDivisores4 n =

last (sumasSumasCuadradosDivisores4 n)

-- (sumasSumasCuadradosDivisores4 n) es la sucesión cuyo k-ésimo término

-- es la suma de las sumas de los cuadrados de los divisores de k, para

-- k entre 0 y n. Por ejemplo,

-- sumasSumasCuadradosDivisores4 6 == [0,6,18,36,52,77,113]

sumasSumasCuadradosDivisores4 :: Integer -> [Integer]

sumasSumasCuadradosDivisores4 n = scanl1 f [0,1..n]

where f x k = x + k^2 * (n `div` k)

-- 5ª solución

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

sumaSumasCuadradosDivisores5 :: Integer -> Integer

sumaSumasCuadradosDivisores5 n =

last (sumasSumasCuadradosDivisores5 n)

-- (sumasSumasCuadradosDivisores5 n) es la sucesión cuyo k-ésimo término

-- es la suma de las sumas de los cuadrados de los divisores de k, para

-- k entre 0 y n. Por ejemplo,

-- sumasSumasCuadradosDivisores5 6 == [0,6,18,36,52,77,113]

sumasSumasCuadradosDivisores5 :: Integer -> [Integer]

sumasSumasCuadradosDivisores5 n = scanl1 f [0,1..n]

where f x k = x + k * (n - (n `mod` k))

-- 6ª solución

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

-- Cada elemento k de [1..n], al cuadrado, aparece tantas veces como la

-- parte entera de n/k; luego,

-- sumaSumasCuadradosDivisores n =

-- 1^2*n + 2^2*(n `div` 2) + 3^2*(n `div` 3) + ... + n^2*1

sumaSumasCuadradosDivisores6 :: Integer -> Integer

sumaSumasCuadradosDivisores6 n = sum (zipWith (*) ds vs)

where ds = map (^2) [1..n]

vs = [n `div` k | k <- [1..n]]

-- Comparación de eficiencia:

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

-- λ> sumaSumasCuadradosDivisores (3*10^3)

-- 10825397502

-- (3.29 secs, 468,721,192 bytes)

-- λ> sumaSumasCuadradosDivisores2 (3*10^3)

-- 10825397502

-- (3.25 secs, 469,462,600 bytes)

-- λ> sumaSumasCuadradosDivisores3 (3*10^3)

-- 10825397502

-- (0.03 secs, 2,788,752 bytes)

-- λ> sumaSumasCuadradosDivisores4 (3*10^3)

-- 10825397502

-- (0.03 secs, 2,813,304 bytes)

-- λ> sumaSumasCuadradosDivisores5 (3*10^3)

-- 10825397502

-- (0.03 secs, 1,467,056 bytes)

-- λ> sumaSumasCuadradosDivisores6 (3*10^3)

-- 10825397502

-- (0.03 secs, 3,291,664 bytes)

-- λ> sumaSumasCuadradosDivisores3 (5*10^5)

-- 50085873311988831

-- (2.34 secs, 440,961,640 bytes)

-- λ> sumaSumasCuadradosDivisores4 (5*10^5)

-- 50085873311988831

-- (2.29 secs, 444,962,904 bytes)

-- λ> sumaSumasCuadradosDivisores5 (5*10^5)

-- 50085873311988831

-- (1.23 secs, 220,960,152 bytes)

-- λ> sumaSumasCuadradosDivisores6 (5*10^5)

-- 50085873311988831

-- (2.76 secs, 524,962,464 bytes)

Suma de los dígitos de las repeticiones de un número

PorJosé A. Alonso 6-marzo-201814-marzo-2018

Dados dos números naturales n y x, su suma reducida se obtiene a partir del número obtenido repitiendo n veces el x sumando sus dígitos hasta obtener un número con sólo un dígito. Por ejemplo, si n es 3 y x es 24 las transformaciones son

   242424 ==> 18 ==> 9

1	242424 ==> 18 ==> 9

Análogamente, si n es 4 y x es 7988 las transformaciones son

   7988798879887988 ==> 128 ==> 11 ==> 2

1	7988798879887988 ==> 128 ==> 11 ==> 2

Definir las funciones

   sumaReducidaDigitosRepeticiones :: Integer -> Integer -> Integer
   grafica                         :: Integer -> IO ()

1 2	sumaReducidaDigitosRepeticiones :: Integer -> Integer -> Integer grafica :: Integer -> IO ()

tales que

(sumaReducidaDigitosRepeticiones n x) es la suma reducida de n repeticiones de x. Por ejemplo

     sumaReducidaDigitosRepeticiones 3 24                    ==  9
     sumaReducidaDigitosRepeticiones 4 7988                  == 2
     sumaReducidaDigitosRepeticiones (12^(10^7)) (12^(10^7)) == 9

sumaReducidaDigitosRepeticiones 3 24 == 9

sumaReducidaDigitosRepeticiones 4 7988 == 2

sumaReducidaDigitosRepeticiones (12^(10^7)) (12^(10^7)) == 9

(grafica n) dibuja la gráfica de los n primeros elementos de la sucesión cuyo elementos k-ésimo es (sumaReducidaDigitosRepeticiones k k). Por ejemplo, (grafica 50) dibuja

Soluciones

import Data.List (genericReplicate)
import Graphics.Gnuplot.Simple
import Test.QuickCheck

-- 1ª solución
-- ===========

sumaReducidaDigitosRepeticiones :: Integer -> Integer -> Integer
sumaReducidaDigitosRepeticiones n x =
  sumaReducidaDigitos (repeticiones n x) 

-- (repeticiones n x) es el número obtenido repitiendo n veces el x. Por
-- ejemplo, 
--    repeticiones 3 24   ==  242424
--    repeticiones 4 325  ==  325325325325
repeticiones :: Integer -> Integer -> Integer
repeticiones n x = read (concat (genericReplicate n (show x)))

-- (sumaDigitos x) es la suma de los dígitos de x. Por ejemplo,
--    sumaDigitos 325  ==  10
sumaDigitos :: Integer -> Integer
sumaDigitos x | x < 10    = x
              | otherwise = b + sumaDigitos a
  where (a,b) = divMod x 10

-- (sumaReducidaDigitos x) es el número obtenido a partir de x
-- reiterando la suma de los dígitos hasta obtener un número con sólo un
-- dígito. Por ejemplo,
--    sumaReducidaDigitos 24   ==  6
--    sumaReducidaDigitos 325  ==  1
sumaReducidaDigitos :: Integer -> Integer
sumaReducidaDigitos x | x < 10    = x
                      | otherwise = sumaReducidaDigitos (sumaDigitos x)

-- 2ª solución
-- ===========

sumaReducidaDigitosRepeticiones2 :: Integer -> Integer -> Integer
sumaReducidaDigitosRepeticiones2 n x =
  sumaReducidaDigitos2 (n * sumaReducidaDigitos2 x) 

sumaReducidaDigitos2 :: Integer -> Integer
sumaReducidaDigitos2 0 = 0
sumaReducidaDigitos2 x | y == 0    = 9
                       | otherwise = y
  where y = x `mod` 9

-- Equivalencia de las definiciones
-- ================================

-- La propiedad es
prop_equiv :: Positive Integer -> Positive Integer -> Bool
prop_equiv (Positive n) (Positive x) =
  sumaReducidaDigitosRepeticiones n x == sumaReducidaDigitosRepeticiones2 n x 

-- La comprobación es
--    λ> quickCheck prop_equiv
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

--    λ> sumaReducidaDigitosRepeticiones (10^4) (10^4)
--    1
--    (2.00 secs, 574,667,384 bytes)
--    λ> sumaReducidaDigitosRepeticiones2 (10^4) (10^4)
--    1
--    (0.03 secs, 141,120 bytes)
  
-- Gráfica
-- =======
                      
grafica :: Integer -> IO ()
grafica n =
  plotList [Key Nothing]
           [sumaReducidaDigitosRepeticiones2 k k | k <- [1..n]]

import Data.List (genericReplicate)

import Graphics.Gnuplot.Simple

import Test.QuickCheck

-- 1ª solución

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

sumaReducidaDigitosRepeticiones :: Integer -> Integer -> Integer

sumaReducidaDigitosRepeticiones n x =

sumaReducidaDigitos (repeticiones n x)

-- (repeticiones n x) es el número obtenido repitiendo n veces el x. Por

-- ejemplo,

-- repeticiones 3 24 == 242424

-- repeticiones 4 325 == 325325325325

repeticiones :: Integer -> Integer -> Integer

repeticiones n x = read (concat (genericReplicate n (show x)))

-- (sumaDigitos x) es la suma de los dígitos de x. Por ejemplo,

-- sumaDigitos 325 == 10

sumaDigitos :: Integer -> Integer

sumaDigitos x | x < 10 = x

| otherwise = b + sumaDigitos a

where (a,b) = divMod x 10

-- (sumaReducidaDigitos x) es el número obtenido a partir de x

-- reiterando la suma de los dígitos hasta obtener un número con sólo un

-- dígito. Por ejemplo,

-- sumaReducidaDigitos 24 == 6

-- sumaReducidaDigitos 325 == 1

sumaReducidaDigitos :: Integer -> Integer

sumaReducidaDigitos x | x < 10 = x

| otherwise = sumaReducidaDigitos (sumaDigitos x)

-- 2ª solución

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

sumaReducidaDigitosRepeticiones2 :: Integer -> Integer -> Integer

sumaReducidaDigitosRepeticiones2 n x =

sumaReducidaDigitos2 (n * sumaReducidaDigitos2 x)

sumaReducidaDigitos2 :: Integer -> Integer

sumaReducidaDigitos2 0 = 0

sumaReducidaDigitos2 x | y == 0 = 9

| otherwise = y

where y = x `mod` 9

-- Equivalencia de las definiciones

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

-- La propiedad es

prop_equiv :: Positive Integer -> Positive Integer -> Bool

prop_equiv (Positive n) (Positive x) =

sumaReducidaDigitosRepeticiones n x == sumaReducidaDigitosRepeticiones2 n x

-- La comprobación es

-- λ> quickCheck prop_equiv

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- λ> sumaReducidaDigitosRepeticiones (10^4) (10^4)

-- 1

-- (2.00 secs, 574,667,384 bytes)

-- λ> sumaReducidaDigitosRepeticiones2 (10^4) (10^4)

-- 1

-- (0.03 secs, 141,120 bytes)

-- Gráfica

-- =======

grafica :: Integer -> IO ()

grafica n =

plotList [Key Nothing]

[sumaReducidaDigitosRepeticiones2 k k | k <- [1..n]]

Nodos con máxima suma de hijos

PorJosé A. Alonso 1-marzo-201830-marzo-2020

Los árboles se pueden representar mediante el siguiente tipo de datos

   data Arbol a = N a [Arbol a]
                  deriving Show

1 2	data Arbol a = N a [Arbol a] deriving Show

Por ejemplo, los árboles

     1               3      
    / \             /|\     
   2   3           / | \    
       |          5  4  7   
       4          |    /|\  
                  6   2 8 6

1 3

/ \ /|\

2 3 / | \

| 5 4 7

4 | /|\

6 2 8 6

se representan por

   ej1, ej2 :: Arbol Int
   ej1 = N 1 [N 2 [], N 3 [N 4 []]]
   ej2 = N 3 [N 5 [N 6 []], 
              N 4 [], 
              N 7 [N 2 [], N 8 [], N 6 []]]

ej1, ej2 :: Arbol Int

ej1 = N 1 [N 2 [], N 3 [N 4 []]]

ej2 = N 3 [N 5 [N 6 []],

N 4 [],

N 7 [N 2 [], N 8 [], N 6 []]]

Definir la función

   nodosSumaMaxima :: (Num t, Ord t) => Arbol t -> [t]

1	nodosSumaMaxima :: (Num t, Ord t) => Arbol t -> [t]

tal que (nodosSumaMaxima a) es la lista de los nodos del árbol a cuyos hijos tienen máxima suma. Por ejemplo,

   nodosSumaMaxima ej1  ==  [1]
   nodosSumaMaxima ej2  ==  [7,3]

1 2	nodosSumaMaxima ej1 == [1] nodosSumaMaxima ej2 == [7,3]

Soluciones

import Data.List     (groupBy, sort)
import Data.Function (on)

data Arbol a = N a [Arbol a]
  deriving Show

ej1, ej2 :: Arbol Int
ej1 = N 1 [N 2 [], N 3 [N 4 []]]
ej2 = N 3 [N 5 [N 6 []], 
           N 4 [], 
           N 7 [N 2 [], N 8 [], N 6 []]]

-- 1ª solución
-- ===========

nodosSumaMaxima :: (Num t, Ord t) => Arbol t -> [t]
nodosSumaMaxima a =
  [x | (s,x) <- ns, s == m]
  where ns = reverse (sort (nodosSumas a))
        m  = fst (head ns)

-- (nodosSumas x) es la lista de los pares (s,n) donde n es un nodo del
-- árbol x y s es la suma de sus hijos. Por ejemplo,  
--    λ> nodosSumas ej1
--    [(5,1),(0,2),(4,3),(0,4)]
--    λ> nodosSumas ej2
--    [(16,3),(6,5),(0,6),(0,4),(16,7),(0,2),(0,8),(0,6)]
nodosSumas :: Num t => Arbol t -> [(t,t)]
nodosSumas (N x []) = [(0,x)]
nodosSumas (N x as) = (sum (raices as),x) : concatMap nodosSumas as

-- (raices b) es la lista de las raíces del bosque b. Por ejemplo,
--    raices [ej1,ej2]  ==  [1,3]
raices :: [Arbol t] -> [t]
raices = map raiz

-- (raiz a) es la raíz del árbol a. Por ejemplo,
--    raiz ej1  ==  1
--    raiz ej2  ==  3
raiz :: Arbol t -> t
raiz (N x _) = x

-- 2ª solución
-- ===========

nodosSumaMaxima2 :: (Num t, Ord t) => Arbol t -> [t]
nodosSumaMaxima2 a =
  [x | (s,x) <- ns, s == m]
  where ns = sort (nodosOpSumas a)
        m  = fst (head ns)

-- (nodosOpSumas x) es la lista de los pares (s,n) donde n es un nodo del
-- árbol x y s es el opuesto de la suma de sus hijos. Por ejemplo,  
--    λ> nodosOpSumas ej1
--    [(-5,1),(0,2),(-4,3),(0,4)]
--    λ> nodosOpSumas ej2
--    [(-16,3),(-6,5),(0,6),(0,4),(-16,7),(0,2),(0,8),(0,6)]
nodosOpSumas :: Num t => Arbol t -> [(t,t)]
nodosOpSumas (N x []) = [(0,x)]
nodosOpSumas (N x as) = (-sum (raices as),x) : concatMap nodosOpSumas as


-- 3ª solución
-- ===========

nodosSumaMaxima3 :: (Num t, Ord t) => Arbol t -> [t]
nodosSumaMaxima3 a =
  [x | (s,x) <- ns, s == m]
  where ns = sort (nodosOpSumas a)
        m  = fst (head ns)

-- 4ª solución
-- ===========

nodosSumaMaxima4 :: (Num t, Ord t) => Arbol t -> [t]
nodosSumaMaxima4 a =
  map snd (head (groupBy (\p q -> fst p == fst q)
                         (sort (nodosOpSumas a))))

-- 5ª solución
-- ===========

nodosSumaMaxima5 :: (Num t, Ord t) => Arbol t -> [t]
nodosSumaMaxima5 a =
  map snd (head (groupBy ((==) `on` fst)
                         (sort (nodosOpSumas a))))

-- 6ª solución
-- ===========

nodosSumaMaxima6 :: (Num t, Ord t) => Arbol t -> [t]
nodosSumaMaxima6 =
  map snd
  . head
  . groupBy ((==) `on` fst)
  . sort
  . nodosOpSumas

import Data.List (groupBy, sort)

import Data.Function (on)

data Arbol a = N a [Arbol a]

deriving Show

ej1, ej2 :: Arbol Int

ej1 = N 1 [N 2 [], N 3 [N 4 []]]

ej2 = N 3 [N 5 [N 6 []],

N 4 [],

N 7 [N 2 [], N 8 [], N 6 []]]

-- 1ª solución

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

nodosSumaMaxima :: (Num t, Ord t) => Arbol t -> [t]

nodosSumaMaxima a =

[x | (s,x) <- ns, s == m]

where ns = reverse (sort (nodosSumas a))

m = fst (head ns)

-- (nodosSumas x) es la lista de los pares (s,n) donde n es un nodo del

-- árbol x y s es la suma de sus hijos. Por ejemplo,

-- λ> nodosSumas ej1

-- [(5,1),(0,2),(4,3),(0,4)]

-- λ> nodosSumas ej2

-- [(16,3),(6,5),(0,6),(0,4),(16,7),(0,2),(0,8),(0,6)]

nodosSumas :: Num t => Arbol t -> [(t,t)]

nodosSumas (N x []) = [(0,x)]

nodosSumas (N x as) = (sum (raices as),x) : concatMap nodosSumas as

-- (raices b) es la lista de las raíces del bosque b. Por ejemplo,

-- raices [ej1,ej2] == [1,3]

raices :: [Arbol t] -> [t]

raices = map raiz

-- (raiz a) es la raíz del árbol a. Por ejemplo,

-- raiz ej1 == 1

-- raiz ej2 == 3

raiz :: Arbol t -> t

raiz (N x _) = x

-- 2ª solución

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

nodosSumaMaxima2 :: (Num t, Ord t) => Arbol t -> [t]

nodosSumaMaxima2 a =

[x | (s,x) <- ns, s == m]

where ns = sort (nodosOpSumas a)

m = fst (head ns)

-- (nodosOpSumas x) es la lista de los pares (s,n) donde n es un nodo del

-- árbol x y s es el opuesto de la suma de sus hijos. Por ejemplo,

-- λ> nodosOpSumas ej1

-- [(-5,1),(0,2),(-4,3),(0,4)]

-- λ> nodosOpSumas ej2

-- [(-16,3),(-6,5),(0,6),(0,4),(-16,7),(0,2),(0,8),(0,6)]

nodosOpSumas :: Num t => Arbol t -> [(t,t)]

nodosOpSumas (N x []) = [(0,x)]

nodosOpSumas (N x as) = (-sum (raices as),x) : concatMap nodosOpSumas as

-- 3ª solución

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

nodosSumaMaxima3 :: (Num t, Ord t) => Arbol t -> [t]

nodosSumaMaxima3 a =

[x | (s,x) <- ns, s == m]

where ns = sort (nodosOpSumas a)

m = fst (head ns)

-- 4ª solución

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

nodosSumaMaxima4 :: (Num t, Ord t) => Arbol t -> [t]

nodosSumaMaxima4 a =

map snd (head (groupBy (\p q -> fst p == fst q)

(sort (nodosOpSumas a))))

-- 5ª solución

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

nodosSumaMaxima5 :: (Num t, Ord t) => Arbol t -> [t]

nodosSumaMaxima5 a =

map snd (head (groupBy ((==) `on` fst)

(sort (nodosOpSumas a))))

-- 6ª solución

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

nodosSumaMaxima6 :: (Num t, Ord t) => Arbol t -> [t]

nodosSumaMaxima6 =

map snd

. head

. groupBy ((==) `on` fst)

. sort

. nodosOpSumas

Sucesiones de números consecutivos con suma dada

Soluciones

Conjetura de Goldbach

Soluciones

Particiones primas

Soluciones

La sucesión de Sylvester

Soluciones

Camino de máxima suma en una matriz

Soluciones

Máximo de las sumas de los caminos en una matriz

Soluciones

Caminos en una matriz

Soluciones

Suma de las sumas de los cuadrados de los divisores

Soluciones

Suma de los dígitos de las repeticiones de un número

Soluciones

Nodos con máxima suma de hijos

Soluciones

Entradas recientes

Buscar

Correo electrónico