Medio

Pares a distancia dada

PorJosé A. Alonso 8-mayo-201715-mayo-2017

Definir la función

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

1	pares :: [Int] -> Int -> [(Int,Int)]

tal que (pares xs k) es la lista de pares de elementos de xs que están a distancia k (se supone que los elementos de xs son distintos). Por ejemplo,

   pares [1,5,3,4,2,8] 2       ==  [(1,3),(3,5),(2,4)]
   pares [1,2,7,9,6,5] 2       ==  [(5,7),(7,9)]
   length (pares [1..10^6] 3)  ==  999997

pares [1,5,3,4,2,8] 2 == [(1,3),(3,5),(2,4)]

pares [1,2,7,9,6,5] 2 == [(5,7),(7,9)]

length (pares [1..10^6] 3) == 999997

Soluciones

import Data.List (sort, tails)
import Data.Set 

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

pares1 :: [Int] -> Int -> [(Int,Int)]
pares1 xs k =
  [(x,y) | x <- xs, y <- xs, y - x == k]

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

pares2 :: [Int] -> Int -> [(Int,Int)]
pares2 xs k =
  [(y,y+k) | (y:ys) <- init (tails (sort xs))
           , (y+k) `pertenece` ys]

pertenece :: Int -> [Int] -> Bool
pertenece _ [] = False
pertenece x (y:ys) | x < y     = False
                   | x == y    = True
                   | otherwise = pertenece x ys

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

pares3 :: [Int] -> Int -> [(Int,Int)]
pares3 xs k =
  [(x,x+k) | x <- xs
           , (x+k) `member` c]
  where c = fromList xs

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

--    λ> length (pares1 [1..2000] 3)
--    1997
--    (4.26 secs, 471,640,672 bytes)
--    λ> length (pares2 [1..2000] 3)
--    1997
--    (0.02 secs, 0 bytes)
--    λ> length (pares3 [1..2000] 3)
--    1997
--    (0.01 secs, 0 bytes)
--    
--    λ> length (pares2 [1..10^6] 3)
--    999997
--    (6.00 secs, 855,807,112 bytes)
--    λ> length (pares3 [1..10^6] 3)
--    999997
--    (3.67 secs, 390,934,904 bytes)

import Data.List (sort, tails)

import Data.Set

-- 1ª definición

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

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

pares1 xs k =

[(x,y) | x <- xs, y <- xs, y - x == k]

-- 2ª definición

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

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

pares2 xs k =

[(y,y+k) | (y:ys) <- init (tails (sort xs))

, (y+k) `pertenece` ys]

pertenece :: Int -> [Int] -> Bool

pertenece _ [] = False

pertenece x (y:ys) | x < y = False

| x == y = True

| otherwise = pertenece x ys

-- 3ª definición

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

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

pares3 xs k =

[(x,x+k) | x <- xs

, (x+k) `member` c]

where c = fromList xs

-- Comparación de eficiencia

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

-- λ> length (pares1 [1..2000] 3)

-- 1997

-- (4.26 secs, 471,640,672 bytes)

-- λ> length (pares2 [1..2000] 3)

-- 1997

-- (0.02 secs, 0 bytes)

-- λ> length (pares3 [1..2000] 3)

-- 1997

-- (0.01 secs, 0 bytes)

-- λ> length (pares2 [1..10^6] 3)

-- 999997

-- (6.00 secs, 855,807,112 bytes)

-- λ> length (pares3 [1..10^6] 3)

-- 999997

-- (3.67 secs, 390,934,904 bytes)

Suma de árboles por niveles

PorJosé A. Alonso 27-abril-201711-mayo-2017

Los árboles binarios con valores enteros se pueden representar con el de tipo de dato algebraico

   data Arbol = H
              | N a Arbol Arbol

1 2	data Arbol = H \| N a Arbol Arbol

Por ejemplo, los árboles

       3                7     
      / \              / \    
     2   4            5   8   
    / \   \          / \   \  
   1   3   5        6   4   10
                       /   /
                      9   1

3 7

/ \ / \

2 4 5 8

/ \ \ / \ \

1 3 5 6 4 10

/ /

9 1

se representan por

   ej1, ej2 :: Arbol 
   ej1 = N 3 (N 2 (N 1 H H) (N 3 H H)) (N 4 H (N 5 H H))
   ej2 = N 7 (N 5 (N 6 H H) (N 4 (N 9 H H) H)) (N 8 H (N 10 (N 1 H H) H))

ej1, ej2 :: Arbol

ej1 = N 3 (N 2 (N 1 H H) (N 3 H H)) (N 4 H (N 5 H H))

ej2 = N 7 (N 5 (N 6 H H) (N 4 (N 9 H H) H)) (N 8 H (N 10 (N 1 H H) H))

Definir la función

   suma :: Arbol -> Int

1	suma :: Arbol -> Int

tal que (suma a) es la suma de todos los nodos a una distancia par de la raíz del árbol a menos la suma de todos los nodos a una distancia impar de la raíz. Por ejemplo,

   suma ej1  ==  6
   suma ej2  ==  4

1 2	suma ej1 == 6 suma ej2 == 4

ya que

    (3 + 1+3+5) - (2+4)        = 6
    (7 + 6+4+10) - (5+8 + 9+1) = 4

1 2	(3 + 1+3+5) - (2+4) = 6 (7 + 6+4+10) - (5+8 + 9+1) = 4

Soluciones

data Arbol = H
           | N Int Arbol Arbol

ej1, ej2 :: Arbol 
ej1 = N 3 (N 2 (N 1 H H) (N 3 H H)) (N 4 H (N 5 H H))
ej2 = N 7 (N 5 (N 6 H H) (N 4 (N 9 H H) H)) (N 8 H (N 10 (N 1 H H) H))

suma :: Arbol -> Int
suma H         = 0
suma (N x i d) = x - suma i - suma d

data Arbol = H

| N Int Arbol Arbol

ej1, ej2 :: Arbol

ej1 = N 3 (N 2 (N 1 H H) (N 3 H H)) (N 4 H (N 5 H H))

ej2 = N 7 (N 5 (N 6 H H) (N 4 (N 9 H H) H)) (N 8 H (N 10 (N 1 H H) H))

suma :: Arbol -> Int

suma H = 0

suma (N x i d) = x - suma i - suma d

Recorrido en ZigZag

PorJosé A. Alonso 25-abril-201725-abril-2021

El recorrido en ZigZag de una matriz consiste en pasar de la primera fila hasta la última, de izquierda a derecha en las filas impares y de derecha a izquierda en las filas pares, como se indica en la figura.

         /             \
         | 1 -> 2 -> 3 |
         |           | |
         |           v |
         | 4 <- 5 <- 6 |   =>  Recorrido ZigZag: [1,2,3,6,5,4,7,8,9]
         | |           |
         | v           |
         | 7 -> 8 -> 9 |
         \             /

/ \

| 1 -> 2 -> 3 |

| | |

| v |

| 4 <- 5 <- 6 | => Recorrido ZigZag: [1,2,3,6,5,4,7,8,9]

| | |

| v |

| 7 -> 8 -> 9 |

\ /

Definir la función

   recorridoZigZag :: Matrix a -> [a]

1	recorridoZigZag :: Matrix a -> [a]

tal que (recorridoZigZag m) es la lista con los elementos de la matriz m cuando se recorre esta en ZigZag. Por ejemplo,

   λ> recorridoZigZag (fromLists [[1,2,3],[4,5,6],[7,8,9]])
   [1,2,3,6,5,4,7,8,9]
   λ> recorridoZigZag (fromLists [[1,2],[3,4],[5,6],[7,8]])
   [1,2,4,3,5,6,8,7]
   λ> recorridoZigZag (fromLists [[1,2,3,4],[5,6,7,8],[9,10,11,12]])
   [1,2,3,4,8,7,6,5,9,10,11,12]
   λ> recorridoZigZag (fromList 5 4 "Cada paso es la meta")
   "Cadasap o es al meta"
   λ> recorridoZigZag (fromList 4 5 "Cada paso es la meta")
   "Cada  osapes laatem "
   λ> recorridoZigZag (fromList 10 2 "Cada paso es la meta")
   "Caad psao se l ameat"
   λ> recorridoZigZag (fromList 2 10 "Cada paso es la meta")
   "Cada paso atem al se"

λ> recorridoZigZag (fromLists [[1,2,3],[4,5,6],[7,8,9]])

[1,2,3,6,5,4,7,8,9]

λ> recorridoZigZag (fromLists [[1,2],[3,4],[5,6],[7,8]])

[1,2,4,3,5,6,8,7]

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

[1,2,3,4,8,7,6,5,9,10,11,12]

λ> recorridoZigZag (fromList 5 4 "Cada paso es la meta")

"Cadasap o es al meta"

λ> recorridoZigZag (fromList 4 5 "Cada paso es la meta")

"Cada osapes laatem "

λ> recorridoZigZag (fromList 10 2 "Cada paso es la meta")

"Caad psao se l ameat"

λ> recorridoZigZag (fromList 2 10 "Cada paso es la meta")

"Cada paso atem al se"

Soluciones

import Data.Matrix (Matrix, toLists, fromLists, fromList)

recorridoZigZag :: Matrix a -> [a]
recorridoZigZag m =
  concat [f xs | (f,xs) <- zip (cycle [id,reverse]) (toLists m)]

import Data.Matrix (Matrix, toLists, fromLists, fromList)

recorridoZigZag :: Matrix a -> [a]

recorridoZigZag m =

concat [f xs | (f,xs) <- zip (cycle [id,reverse]) (toLists m)]

Subnúmeros pares

PorJosé A. Alonso 18-abril-201725-abril-2017

Los subnúmeros de un número x son los números que se pueden formar con dígitos de x en posiciones consecutivas. Por ejemplo, el número 254 tiene 6 subnúmeros: 2, 5, 4, 25, 54 y 254.

Definir las funciones

   subnumeros       :: Integer -> [Integer]
   nSubnumerosPares :: Integer -> Integer

1 2	subnumeros :: Integer -> [Integer] nSubnumerosPares :: Integer -> Integer

tales que

(subnumerosPares x) es la lista de los subnúmeros pares de x. Por ejemplo,

     subnumerosPares 254   ==  [2,254,54,4]
     subnumerosPares 154   ==  [154,54,4]
     subnumerosPares 15    ==  []

subnumerosPares 254 == [2,254,54,4]

subnumerosPares 154 == [154,54,4]

subnumerosPares 15 == []

(nSubnumerosPares x) es la cantidad de subnúmeros pares de x. Por ejemplo,

     nSubnumerosPares 254   ==  4
     nSubnumerosPares2 (4^(10^6))  ==  90625258498

1 2	nSubnumerosPares 254 == 4 nSubnumerosPares2 (4^(10^6)) == 90625258498

Soluciones

import Data.List ( genericLength
                 , inits
                 , tails
                 )

subnumerosPares :: Integer -> [Integer]
subnumerosPares n =
  filter even (subnumeros n)

-- (subnumeros n) es la lista de los subnúmeros de n. Por ejemplo,
--    subnumeros 254  ==  [2,25,5,254,54,4]
subnumeros :: Integer -> [Integer]
subnumeros n =
  [read x | x <- sublistas (show n)]

-- (sublistas xs) es la lista de las sublistas de xs. Por ejemplo, 
--    sublistas "abc"  ==  ["a","ab","b","abc","bc","c"]
sublistas :: [a] -> [[a]]
sublistas xs =
  concat [init (tails ys) | ys <- tail (inits xs)]

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

nSubnumerosPares :: Integer -> Integer
nSubnumerosPares =
  genericLength . subnumerosPares

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

nSubnumerosPares2 :: Integer -> Integer
nSubnumerosPares2 =
  sum . posicionesDigitosPares 

-- (posicionesDigitosPares x) es la lista de las posiciones de los
-- dígitos pares de x. Por ejemplo,
--    posicionesDigitosPares 254  ==  [1,3]
posicionesDigitosPares :: Integer -> [Integer]
posicionesDigitosPares x =
  [n | (n,y) <- zip [1..] (show x)
     , y `elem` "02468"]

-- Comparación de eficiencia
--    λ> nSubnumerosPares (2^(10^3))
--    22934
--    (2.83 secs, 3,413,414,872 bytes)
--    λ> nSubnumerosPares2 (2^(10^3))
--    22934
--    (0.01 secs, 0 bytes)

import Data.List ( genericLength

, inits

, tails

)

subnumerosPares :: Integer -> [Integer]

subnumerosPares n =

filter even (subnumeros n)

-- (subnumeros n) es la lista de los subnúmeros de n. Por ejemplo,

-- subnumeros 254 == [2,25,5,254,54,4]

subnumeros :: Integer -> [Integer]

subnumeros n =

[read x | x <- sublistas (show n)]

-- (sublistas xs) es la lista de las sublistas de xs. Por ejemplo,

-- sublistas "abc" == ["a","ab","b","abc","bc","c"]

sublistas :: [a] -> [[a]]

sublistas xs =

concat [init (tails ys) | ys <- tail (inits xs)]

-- 1ª definición

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

nSubnumerosPares :: Integer -> Integer

nSubnumerosPares =

genericLength . subnumerosPares

-- 2ª definición

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

nSubnumerosPares2 :: Integer -> Integer

nSubnumerosPares2 =

sum . posicionesDigitosPares

-- (posicionesDigitosPares x) es la lista de las posiciones de los

-- dígitos pares de x. Por ejemplo,

-- posicionesDigitosPares 254 == [1,3]

posicionesDigitosPares :: Integer -> [Integer]

posicionesDigitosPares x =

[n | (n,y) <- zip [1..] (show x)

, y `elem` "02468"]

-- Comparación de eficiencia

-- λ> nSubnumerosPares (2^(10^3))

-- 22934

-- (2.83 secs, 3,413,414,872 bytes)

-- λ> nSubnumerosPares2 (2^(10^3))

-- 22934

-- (0.01 secs, 0 bytes)

Ampliación de una matriz

PorJosé A. Alonso 12-abril-201720-abril-2017

Definir, usando Data.Matrix, la función

   ampliaMatriz :: Matrix a -> Int -> Int -> Matrix a

1	ampliaMatriz :: Matrix a -> Int -> Int -> Matrix a

tal que (ampliaMatriz p f c) es la matriz obtenida a partir de p repitiendo cada fila f veces y cada columna c veces. Por ejemplo, si ej1 es la matriz definida por

   ej1 :: Matrix Char
   ej1 = fromLists [" x ",
                    "x x",
                    " x "]

ej1 :: Matrix Char

ej1 = fromLists [" x ",

"x x",

" x "]

entonces

   λ> ampliaMatriz ej1 1 2
   ( ' ' ' ' 'x' 'x' ' ' ' ' )
   ( 'x' 'x' ' ' ' ' 'x' 'x' )
   ( ' ' ' ' 'x' 'x' ' ' ' ' )
   
   λ> (putStr . unlines . toLists) (ampliaMatriz ej1 1 2)
     xx  
   xx  xx
     xx  
   λ> (putStr . unlines . toLists) (ampliaMatriz ej1 2 1)
    x 
    x 
   x x
   x x
    x 
    x 
   λ> (putStr . unlines . toLists) (ampliaMatriz ej1 2 2)
     xx  
     xx  
   xx  xx
   xx  xx
     xx  
     xx  
   λ> (putStr . unlines . toLists) (ampliaMatriz ej1 2 3)
      xxx   
      xxx   
   xxx   xxx
   xxx   xxx
      xxx   
      xxx

λ> ampliaMatriz ej1 1 2

( ' ' ' ' 'x' 'x' ' ' ' ' )

( 'x' 'x' ' ' ' ' 'x' 'x' )

( ' ' ' ' 'x' 'x' ' ' ' ' )

λ> (putStr . unlines . toLists) (ampliaMatriz ej1 1 2)

xx xx

λ> (putStr . unlines . toLists) (ampliaMatriz ej1 2 1)

x x

λ> (putStr . unlines . toLists) (ampliaMatriz ej1 2 2)

xx xx

λ> (putStr . unlines . toLists) (ampliaMatriz ej1 2 3)

xxx

xxx xxx

xxx

Nota: Este ejercicio está basado en el problema Skener de Kattis.

Soluciones

import Data.Matrix

ej1 :: Matrix Char
ej1 = fromLists [" x ",
                 "x x",
                 " x "]

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

ampliaMatriz :: Matrix a -> Int -> Int -> Matrix a
ampliaMatriz p f c =
  ampliaColumnas (ampliaFilas p f) c

ampliaFilas :: Matrix a -> Int -> Matrix a
ampliaFilas p f =
  matrix (f*m) n (\(i,j) -> p!(1 + (i-1) `div` f, j))
  where m = nrows p
        n = ncols p

ampliaColumnas :: Matrix a -> Int -> Matrix a
ampliaColumnas p c =
  matrix m (c*n) (\(i,j) -> p!(i,1 + (j-1) `div` c))
  where m = nrows p
        n = ncols p

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

ampliaMatriz2 :: Matrix a -> Int -> Int -> Matrix a
ampliaMatriz2 p f c =
  ampliaColumnas2 (ampliaFilas2 p f) c

ampliaFilas2 :: Matrix a -> Int -> Matrix a
ampliaFilas2 p f =
  fromLists (concatMap (replicate f) (toLists p))

ampliaColumnas2 :: Matrix a -> Int -> Matrix a
ampliaColumnas2 p c =
  fromLists (map (concatMap (replicate c)) (toLists p))

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

ampliaMatriz3 :: Matrix a -> Int -> Int -> Matrix a
ampliaMatriz3 p f c =
  ( fromLists
  . concatMap (map (concatMap (replicate c)) . replicate f)
  . toLists) p

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

ejemplo :: Int -> Matrix Int
ejemplo n = fromList n n [1..]

--    λ> maximum (ampliaMatriz (ejemplo 10) 100 200)
--    100
--    (6.64 secs, 1,026,559,296 bytes)
--    λ> maximum (ampliaMatriz2 (ejemplo 10) 100 200)
--    100
--    (1.90 secs, 513,211,144 bytes)
--    λ> maximum (ampliaMatriz3 (ejemplo 10) 100 200)
--    100
--    (1.89 secs, 644,928,024 bytes)
--    λ> maximum (ampliaMatriz2 (ejemplo 10) 200 200)
--    100
--    (5.13 secs, 1,248,173,384 bytes)
--    λ> maximum (ampliaMatriz3 (ejemplo 10) 200 200)
--    100
--    (4.67 secs, 1,431,540,344 bytes)

import Data.Matrix

ej1 :: Matrix Char

ej1 = fromLists [" x ",

"x x",

" x "]

-- 1ª definición

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

ampliaMatriz :: Matrix a -> Int -> Int -> Matrix a

ampliaMatriz p f c =

ampliaColumnas (ampliaFilas p f) c

ampliaFilas :: Matrix a -> Int -> Matrix a

ampliaFilas p f =

matrix (f*m) n (\(i,j) -> p!(1 + (i-1) `div` f, j))

where m = nrows p

n = ncols p

ampliaColumnas :: Matrix a -> Int -> Matrix a

ampliaColumnas p c =

matrix m (c*n) (\(i,j) -> p!(i,1 + (j-1) `div` c))

where m = nrows p

n = ncols p

-- 2ª definición

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

ampliaMatriz2 :: Matrix a -> Int -> Int -> Matrix a

ampliaMatriz2 p f c =

ampliaColumnas2 (ampliaFilas2 p f) c

ampliaFilas2 :: Matrix a -> Int -> Matrix a

ampliaFilas2 p f =

fromLists (concatMap (replicate f) (toLists p))

ampliaColumnas2 :: Matrix a -> Int -> Matrix a

ampliaColumnas2 p c =

fromLists (map (concatMap (replicate c)) (toLists p))

-- 3ª definición

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

ampliaMatriz3 :: Matrix a -> Int -> Int -> Matrix a

ampliaMatriz3 p f c =

( fromLists

. concatMap (map (concatMap (replicate c)) . replicate f)

. toLists) p

-- Comparación de eficiencia

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

ejemplo :: Int -> Matrix Int

ejemplo n = fromList n n [1..]

-- λ> maximum (ampliaMatriz (ejemplo 10) 100 200)

-- 100

-- (6.64 secs, 1,026,559,296 bytes)

-- λ> maximum (ampliaMatriz2 (ejemplo 10) 100 200)

-- 100

-- (1.90 secs, 513,211,144 bytes)

-- λ> maximum (ampliaMatriz3 (ejemplo 10) 100 200)

-- 100

-- (1.89 secs, 644,928,024 bytes)

-- λ> maximum (ampliaMatriz2 (ejemplo 10) 200 200)

-- 100

-- (5.13 secs, 1,248,173,384 bytes)

-- λ> maximum (ampliaMatriz3 (ejemplo 10) 200 200)

-- 100

-- (4.67 secs, 1,431,540,344 bytes)

Pares a distancia dada

Soluciones

Suma de árboles por niveles

Soluciones

Recorrido en ZigZag

Soluciones

Subnúmeros pares

Soluciones

Ampliación de una matriz

Soluciones

Entradas recientes

Buscar

Correo electrónico