Medio

Particiones en listas de segmentos

PorJosé A. Alonso 27-enero-20153-febrero-2015

Exercitium

Definir la función

   particiones :: Int -> [a] -> [[[a]]]

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

tal que (particiones n xs) es la lista de listas de n elementos cuya concatenación es xs. Por ejemplo,

   ghci> particiones 2 "abc"
   [["","abc"],["a","bc"],["ab","c"],["abc",""]]
   ghci> particiones 3 "abc"
   [["","","abc"],["","a","bc"],["","ab","c"],["","abc",""],
    ["a","","bc"],["a","b","c"],["a","bc",""],["ab","","c"],
    ["ab","c",""],["abc","",""]]
   ghci> length (particiones 4 "abc")
   20

ghci> particiones 2 "abc"

[["","abc"],["a","bc"],["ab","c"],["abc",""]]

ghci> particiones 3 "abc"

[["","","abc"],["","a","bc"],["","ab","c"],["","abc",""],

["a","","bc"],["a","b","c"],["a","bc",""],["ab","","c"],

["ab","c",""],["abc","",""]]

ghci> length (particiones 4 "abc")

Soluciones

particiones :: Int -> [a] -> [[[a]]]
particiones 0 [] = [[]]
particiones 0 xs = []
particiones n xs = [ys:yss | (ys,zs) <- biparticiones xs,
                             yss <- particiones (n-1) zs]

-- (biparticiones xs) es la lista de los pares (xs1,xs2) tales que su
-- concatenación es xs. Por ejemplo, 
--    ghci> biparticiones "abc"
--    [("","abc"),("a","bc"),("ab","c"),("abc","")]
biparticiones :: [a] -> [([a],[a])]
biparticiones []     = [([],[])]
biparticiones (x:xs) = ([],x:xs) :  
                       [(x:xs1,xs2) | (xs1,xs2) <- biparticiones xs]

particiones :: Int -> [a] -> [[[a]]]

particiones 0 [] = [[]]

particiones 0 xs = []

particiones n xs = [ys:yss | (ys,zs) <- biparticiones xs,

yss <- particiones (n-1) zs]

-- (biparticiones xs) es la lista de los pares (xs1,xs2) tales que su

-- concatenación es xs. Por ejemplo,

-- ghci> biparticiones "abc"

-- [("","abc"),("a","bc"),("ab","c"),("abc","")]

biparticiones :: [a] -> [([a],[a])]

biparticiones [] = [([],[])]

biparticiones (x:xs) = ([],x:xs) :

[(x:xs1,xs2) | (xs1,xs2) <- biparticiones xs]

Sustitución de listas

PorJosé A. Alonso 22-enero-201530-noviembre-2015

Definir la función

   sustituye :: Eq a => [a] -> [a] -> [a] -> [a]

1	sustituye :: Eq a => [a] -> [a] -> [a] -> [a]

tal que (sustituye xs ys zs) es la lista obtenida sustituyendo las ocurrencias de la lista no vacía xs en zs por ys. Por ejemplo,

   sustituye "as" "_" "las casaderas"   ==  "l_ c_ader_"
   sustituye "as" "es" "las casaderas"  ==  "les cesaderes"
   sustituye "asa" "a" "las casaderas"  ==  "las caderas"
   sustituye "asd" "a" "las casaderas"  ==  "las casaderas"

sustituye "as" "_" "las casaderas" == "l_ c_ader_"

sustituye "as" "es" "las casaderas" == "les cesaderes"

sustituye "asa" "a" "las casaderas" == "las caderas"

sustituye "asd" "a" "las casaderas" == "las casaderas"

Soluciones

import Data.List (isPrefixOf)

sustituye :: Eq a => [a] -> [a] -> [a] -> [a]
sustituye xs ys [] = []
sustituye xs ys (z:zs) 
    | isPrefixOf xs (z:zs) = ys ++ sustituye xs ys (drop n zs)
    | otherwise            = z : sustituye xs ys zs
    where n = length xs - 1

import Data.List (isPrefixOf)

sustituye :: Eq a => [a] -> [a] -> [a] -> [a]

sustituye xs ys [] = []

sustituye xs ys (z:zs)

| isPrefixOf xs (z:zs) = ys ++ sustituye xs ys (drop n zs)

| otherwise = z : sustituye xs ys zs

where n = length xs - 1

Triparticiones de una lista

PorJosé A. Alonso 21-enero-201530-noviembre-2015

Definir la función

   triparticiones :: [a] -> [([a],[a],[a])]

1	triparticiones :: [a] -> [([a],[a],[a])]

tal que (triparticiones xs) es la lista de las ternas (xs1,xs2,xs3) tales que su concatenación es xs. Por ejemplo,

   ghci> triparticiones "abc"
   [("","","abc"),("","a","bc"),("","ab","c"),("","abc",""),
    ("a","","bc"),("a","b","c"),("a","bc",""),("ab","","c"),
    ("ab","c",""),("abc","","")]

ghci> triparticiones "abc"

[("","","abc"),("","a","bc"),("","ab","c"),("","abc",""),

("a","","bc"),("a","b","c"),("a","bc",""),("ab","","c"),

("ab","c",""),("abc","","")]

Comprobar con QuickCheck que, suponiendo que xs es una lista de elementos comparables por igualdad, entonces para cada terna de (triparticiones xs) se cumple que la concatenación de sus elementos es xs.

Soluciones

import Test.QuickCheck

triparticiones :: [a] -> [([a],[a],[a])]
triparticiones xs = [(xs1,xs2,xs3) | (xs1,ys)  <- biparticiones xs,
                                     (xs2,xs3) <- biparticiones ys]

-- (biparticiones xs) es la lista de los pares (xs1,xs2) tales que su
-- concatenación es xs. Por ejemplo, 
--    ghci> biparticiones "abc"
--    [("","abc"),("a","bc"),("ab","c"),("abc","")]
biparticiones :: [a] -> [([a],[a])]
biparticiones []     = [([],[])]
biparticiones (x:xs) = ([],x:xs) :
                       [(x:xs1,xs2) | (xs1,xs2) <- biparticiones xs]

-- La propiedad es
prop_triparticiones :: Eq a => [a] -> Bool
prop_triparticiones xs =
    all (\(xs1,xs2,xs3) -> xs1 ++ xs2 ++ xs3 == xs) (triparticiones xs)

-- La comprobación es 
--    ghci> quickCheck prop_triparticiones
--    +++ OK, passed 100 tests.

import Test.QuickCheck

triparticiones :: [a] -> [([a],[a],[a])]

triparticiones xs = [(xs1,xs2,xs3) | (xs1,ys) <- biparticiones xs,

(xs2,xs3) <- biparticiones ys]

-- (biparticiones xs) es la lista de los pares (xs1,xs2) tales que su

-- concatenación es xs. Por ejemplo,

-- ghci> biparticiones "abc"

-- [("","abc"),("a","bc"),("ab","c"),("abc","")]

biparticiones :: [a] -> [([a],[a])]

biparticiones [] = [([],[])]

biparticiones (x:xs) = ([],x:xs) :

[(x:xs1,xs2) | (xs1,xs2) <- biparticiones xs]

-- La propiedad es

prop_triparticiones :: Eq a => [a] -> Bool

prop_triparticiones xs =

all (\(xs1,xs2,xs3) -> xs1 ++ xs2 ++ xs3 == xs) (triparticiones xs)

-- La comprobación es

-- ghci> quickCheck prop_triparticiones

-- +++ OK, passed 100 tests.

Listas con suma dada

PorJosé A. Alonso 20-enero-201530-noviembre-2015

Definir la función

   conSuma :: (Eq a, Num a) => [a] -> [[a]] -> [[[a]]]

1	conSuma :: (Eq a, Num a) => [a] -> [[a]] -> [[[a]]]

tal que (conSuma xs yss) es la lista de los vectores de xss cuya suma vectorial es xs. Por ejemplo,

   ghci> conSuma [9,10,12] [[4,7,3],[3,1,4],[5,3,9],[2,2,5]] 
   [[[4,7,3],[5,3,9]],[[4,7,3],[3,1,4],[2,2,5]]]
   ghci> conSuma [9,11,12] [[4,7,3],[3,1,4],[5,3,9],[2,2,5]] 
   []

ghci> conSuma [9,10,12] [[4,7,3],[3,1,4],[5,3,9],[2,2,5]]

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

ghci> conSuma [9,11,12] [[4,7,3],[3,1,4],[5,3,9],[2,2,5]]

[]

Soluciones

import Data.List (subsequences, transpose)

conSuma :: (Eq a, Num a) => [a] -> [[a]] -> [[[a]]]
conSuma xs yss = [zss | zss <- subsequences yss, suma zss == xs]

-- (suma xss) es la suma de las listas xs. Por ejemplo,
--    suma [[4,7,3],[3,1,4],[2,2,5]]  ==  [9,10,12]
suma :: Num a => [[a]] -> [a]
suma = map sum . transpose

import Data.List (subsequences, transpose)

conSuma :: (Eq a, Num a) => [a] -> [[a]] -> [[[a]]]

conSuma xs yss = [zss | zss <- subsequences yss, suma zss == xs]

-- (suma xss) es la suma de las listas xs. Por ejemplo,

-- suma [[4,7,3],[3,1,4],[2,2,5]] == [9,10,12]

suma :: Num a => [[a]] -> [a]

suma = map sum . transpose

Ordenación según una función

PorJosé A. Alonso 16-enero-201526-abril-2015

Definir la función

   ordenaSegun :: Ord b => (a -> b) -> [a] -> [a]

1	ordenaSegun :: Ord b => (a -> b) -> [a] -> [a]

tal que (ordenaSegun f xs) es la lista obtenida ordenando los elementos de xs según sus valores mediante la función f. Por ejemplo,

   ordenaSegun abs [-3,2,5,-2]                           ==  [2,-2,-3,5]
   ordenaSegun abs [-3,-2,5,2]                           ==  [-2,2,-3,5]
   ordenaSegun length ["pq","x","mn"]                    ==  ["x","pq","mn"]
   [g 0 | g <- ordenaSegun (\f -> f 4) [(+5),(+2),(+3)]] == [2,3,5]

ordenaSegun abs [-3,2,5,-2] == [2,-2,-3,5]

ordenaSegun abs [-3,-2,5,2] == [-2,2,-3,5]

ordenaSegun length ["pq","x","mn"] == ["x","pq","mn"]

[g 0 | g <- ordenaSegun (\f -> f 4) [(+5),(+2),(+3)]] == [2,3,5]

Comprobar con QuickCheck que (ordenaSegun id) es equivalente a sort.

Soluciones

import Data.List (sort, sortBy)
import Data.Ord (comparing)
import Test.QuickCheck

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

ordenaSegun :: Ord b => (a -> b) -> [a] -> [a]
ordenaSegun _ []  = []
ordenaSegun f (x:xs) = insertaSegun f x (ordenaSegun f xs)

insertaSegun :: Ord b => (a -> b) -> a -> [a] -> [a]
insertaSegun _ x [] = [x]
insertaSegun f x (y:ys) | f x <= f y = x : y : ys
                        | otherwise  = y : insertaSegun f x ys

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

ordenaSegun2 :: Ord b => (a -> b) -> [a] -> [a]
ordenaSegun2 f xs = [xs!!i | (_,i) <- sort (zip [f x | x <- xs] [0..])]

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

ordenaSegun3 :: Ord b => (a -> b) -> [a] -> [a]
ordenaSegun3 f xs = map ((xs!!) . snd) (sort (zip (map f xs) [0..]))

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

ordenaSegun4 :: Ord b => (a -> b) -> [a] -> [a]
ordenaSegun4 = sortBy . comparing

-- La propiedad es
prop_ordenaSegun :: Ord a => [a] -> Bool
prop_ordenaSegun xs =
    ordenaSegun id xs == sort xs

-- La comprobación es
--    ghci> quickCheck prop_ordenaSegun
--    +++ OK, passed 100 tests.

import Data.List (sort, sortBy)

import Data.Ord (comparing)

import Test.QuickCheck

-- 1ª definición

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

ordenaSegun :: Ord b => (a -> b) -> [a] -> [a]

ordenaSegun _ [] = []

ordenaSegun f (x:xs) = insertaSegun f x (ordenaSegun f xs)

insertaSegun :: Ord b => (a -> b) -> a -> [a] -> [a]

insertaSegun _ x [] = [x]

insertaSegun f x (y:ys) | f x <= f y = x : y : ys

| otherwise = y : insertaSegun f x ys

-- 2ª definición

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

ordenaSegun2 :: Ord b => (a -> b) -> [a] -> [a]

ordenaSegun2 f xs = [xs!!i | (_,i) <- sort (zip [f x | x <- xs] [0..])]

-- 3ª definición

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

ordenaSegun3 :: Ord b => (a -> b) -> [a] -> [a]

ordenaSegun3 f xs = map ((xs!!) . snd) (sort (zip (map f xs) [0..]))

-- 4ª definición

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

ordenaSegun4 :: Ord b => (a -> b) -> [a] -> [a]

ordenaSegun4 = sortBy . comparing

-- La propiedad es

prop_ordenaSegun :: Ord a => [a] -> Bool

prop_ordenaSegun xs =

ordenaSegun id xs == sort xs

-- La comprobación es

-- ghci> quickCheck prop_ordenaSegun

-- +++ OK, passed 100 tests.

Máxima suma de los segmentos

PorJosé A. Alonso 13-enero-201525-abril-2021

Un segmento de una lista xs es una sublista de xs formada por elementos consecutivos en la lista. El problema de la máxima suma de segmentos consiste en dada una lista de números enteros calcular el máximo de las sumas de todos los segmentos de la lista. Por ejemplo, para la lista [-1,2,-3,5,-2,1,3,-2,-2,-3,6] la máxima suma de segmentos es 7 que es la suma del segmento [5,-2,1,3] y para la lista [-1,-2,-3] es 0 que es la suma de la lista vacía.

Definir la función

   mss :: [Integer] -> Integer

1	mss :: [Integer] -> Integer

tal que (mss xs) es la máxima suma de los segmentos de xs. Por ejemplo,

   mss [-1,2,-3,5,-2,1,3,-2,-2,-3,6]  ==  7
   mss [-1,-2,-3]                     ==  0
   mss [1..500]                       ==  125250
   mss [1..1000]                      ==  500500
   mss [-500..3]                      ==  6
   mss [-1000..3]                     ==  6

mss [-1,2,-3,5,-2,1,3,-2,-2,-3,6] == 7

mss [-1,-2,-3] == 0

mss [1..500] == 125250

mss [1..1000] == 500500

mss [-500..3] == 6

mss [-1000..3] == 6

Soluciones

import Data.List (inits,tails)

-- 1ª solución
mss :: [Integer] -> Integer
mss = maximum . map sum . segmentos

-- (segmentos xs) es la lista de los segmentos de xs. Por ejemplo,
--    ghci> segmentos "abc"
--    ["","a","ab","abc","","b","bc","","c",""]
segmentos :: [a] -> [[a]]
segmentos = concat . map inits . tails

-- 2ª definición:
mss2 :: [Integer] -> Integer
mss2 = maximum . map (maximum . scanl (+) 0) . tails

-- 3ª definición:
mss3 :: [Integer] -> Integer
mss3 = maximum . map sum . concatMap tails . inits 

-- 4ª definición
mss4 :: [Integer] -> Integer
mss4  = fst . foldr (\x (b,a) -> (max (a+x) b, max 0 (a+x))) (0,0) 

-- 5ª definición (con scanl):
mss5 :: [Integer] -> Integer
mss5 = maximum . scanl (\a x -> max 0 a + x) 0

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

--    ghci> mss [1..500]
--    125250
--    (7.52 secs, 2022130824 bytes)
--    
--    ghci> mss2 [1..500]
--    125250
--    (0.01 secs, 10474956 bytes)
--    
--    ghci> mss3 [1..500]
--    125250
--    (0.98 secs, 841862016 bytes)
--    
--    ghci> mss4 [1..500]
--    125250
--    (0.01 secs, 552252 bytes)
--    
--    ghci> mss2 [1..1000]
--    500500
--    (0.06 secs, 54575712 bytes)
--    
--    ghci> mss3 [1..1000]
--    500500
--    (7.87 secs, 7061347900 bytes)
--
--    ghci> mss4 [1..1000]
--    500500
--    (0.01 secs, 549700 bytes)
--    
--    ghci> mss2 [1..2000]
--    2001000
--    (0.29 secs, 216424336 bytes)
--    
--    ghci> mss2 [1..5000]
--    12502500
--    (2.37 secs, 1356384840 bytes)
--    
--    ghci> mss4 [1..5000]
--    12502500
--    (0.02 secs, 1913548 bytes)
--
--    ghci> mss5 [1..5000]
--    12502500
--    (0.01 secs, 2886360 bytes)

import Data.List (inits,tails)

-- 1ª solución

mss :: [Integer] -> Integer

mss = maximum . map sum . segmentos

-- (segmentos xs) es la lista de los segmentos de xs. Por ejemplo,

-- ghci> segmentos "abc"

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

segmentos :: [a] -> [[a]]

segmentos = concat . map inits . tails

-- 2ª definición:

mss2 :: [Integer] -> Integer

mss2 = maximum . map (maximum . scanl (+) 0) . tails

-- 3ª definición:

mss3 :: [Integer] -> Integer

mss3 = maximum . map sum . concatMap tails . inits

-- 4ª definición

mss4 :: [Integer] -> Integer

mss4 = fst . foldr (\x (b,a) -> (max (a+x) b, max 0 (a+x))) (0,0)

-- 5ª definición (con scanl):

mss5 :: [Integer] -> Integer

mss5 = maximum . scanl (\a x -> max 0 a + x) 0

-- Comparación de eficiencia

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

-- ghci> mss [1..500]

-- 125250

-- (7.52 secs, 2022130824 bytes)

-- ghci> mss2 [1..500]

-- 125250

-- (0.01 secs, 10474956 bytes)

-- ghci> mss3 [1..500]

-- 125250

-- (0.98 secs, 841862016 bytes)

-- ghci> mss4 [1..500]

-- 125250

-- (0.01 secs, 552252 bytes)

-- ghci> mss2 [1..1000]

-- 500500

-- (0.06 secs, 54575712 bytes)

-- ghci> mss3 [1..1000]

-- 500500

-- (7.87 secs, 7061347900 bytes)

-- ghci> mss4 [1..1000]

-- 500500

-- (0.01 secs, 549700 bytes)

-- ghci> mss2 [1..2000]

-- 2001000

-- (0.29 secs, 216424336 bytes)

-- ghci> mss2 [1..5000]

-- 12502500

-- (2.37 secs, 1356384840 bytes)

-- ghci> mss4 [1..5000]

-- 12502500

-- (0.02 secs, 1913548 bytes)

-- ghci> mss5 [1..5000]

-- 12502500

-- (0.01 secs, 2886360 bytes)

Referencias

El ejercicio está basado en la función mss del libro de Bird Thinking functionally with Haskell (página 127).
Las soluciones 3ª y 4ª las publicó josejuan aquí

2015 y los números pitagóricos

PorJosé A. Alonso 8-enero-201530-noviembre-2015

Un número pitagórico es un número natural cuyo cuadrado se puede escribir como la suma de los cuadrados de dos números naturales no nulos; es decir, el número natural a es pitagórico si existen dos números naturales b y c distintos de cero tales que a² = b²+c². Por ejemplo, 5 es un número pitagórico ya que 5² = 3²+4² y también lo es 2015 ya que 2015² = 1612²+1209².

Definir la sucesión

    pitagoricos :: [Integer]

1	pitagoricos :: [Integer]

cuyos elementos son los números pitagóricos. Por ejemplo,

   ghci> take 20 pitagoricos
   [5,10,13,15,17,20,25,26,29,30,34,35,37,39,40,41,45,50,51,52]

1 2	ghci> take 20 pitagoricos [5,10,13,15,17,20,25,26,29,30,34,35,37,39,40,41,45,50,51,52]

Calcular la posición de 2015 en la sucesión.

Soluciones

import Test.QuickCheck

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

pitagoricos :: [Integer]
pitagoricos = [n | n <- [1..], esPitagorico n]

-- (esPitagorico n) se verifica si n es pitagórico. Por ejemplo,
--    esPitagorico 5  ==  True
--    esPitagorico 6  ==  False
esPitagorico :: Integer -> Bool
esPitagorico n = not (null (ternasPitagoricas n))

-- (ternasPitagoricas n) es la lista de las ternas (n,a,b) tales que 
-- n² = a²+b² con b < a < n. Por ejemplo,
--    ghci> ternasPitagoricas 5
--    [(5,4,3)]
--    ghci> ternasPitagoricas 2015
--    [(2015,1612,1209),(2015,1736,1023),(2015,1860,775),(2015,1953,496)]
ternasPitagoricas :: Integer -> [(Integer,Integer,Integer)]
ternasPitagoricas n = 
    [(n,a,b) | a <- [1..n-1],
               let b2 = n^2-a^2,
               let b = round (sqrt (fromIntegral b2)),
               b < a,     
               b^2 == b2]

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

pitagoricos2 :: [Integer]
pitagoricos2 = [round (sqrt (fromIntegral a)) | 
                a <- cuadrados,
                let xs = takeWhile (< a) cuadrados,
                any (\b -> a-b `elem` xs) xs]

-- cuadrados es la lista de los cuadrados de los números naturales. Por
-- ejemplo, 
--    take 10 cuadrados  ==  [1,4,9,16,25,36,49,64,81,100]
cuadrados :: [Integer]
cuadrados = [n*n | n <- [1..]]

-- El cálculo de la posición de 2015 es
--    ghci> length (takeWhile (< 2015) pitagoricos)
--    1195

import Test.QuickCheck

-- 1ª definición

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

pitagoricos :: [Integer]

pitagoricos = [n | n <- [1..], esPitagorico n]

-- (esPitagorico n) se verifica si n es pitagórico. Por ejemplo,

-- esPitagorico 5 == True

-- esPitagorico 6 == False

esPitagorico :: Integer -> Bool

esPitagorico n = not (null (ternasPitagoricas n))

-- (ternasPitagoricas n) es la lista de las ternas (n,a,b) tales que

-- n² = a²+b² con b < a < n. Por ejemplo,

-- ghci> ternasPitagoricas 5

-- [(5,4,3)]

-- ghci> ternasPitagoricas 2015

-- [(2015,1612,1209),(2015,1736,1023),(2015,1860,775),(2015,1953,496)]

ternasPitagoricas :: Integer -> [(Integer,Integer,Integer)]

ternasPitagoricas n =

[(n,a,b) | a <- [1..n-1],

let b2 = n^2-a^2,

let b = round (sqrt (fromIntegral b2)),

b < a,

b^2 == b2]

-- 2ª definición

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

pitagoricos2 :: [Integer]

pitagoricos2 = [round (sqrt (fromIntegral a)) |

a <- cuadrados,

let xs = takeWhile (< a) cuadrados,

any (\b -> a-b `elem` xs) xs]

-- cuadrados es la lista de los cuadrados de los números naturales. Por

-- ejemplo,

-- take 10 cuadrados == [1,4,9,16,25,36,49,64,81,100]

cuadrados :: [Integer]

cuadrados = [n*n | n <- [1..]]

-- El cálculo de la posición de 2015 es

-- ghci> length (takeWhile (< 2015) pitagoricos)

-- 1195

Varios cuadrados encajados

PorJosé A. Alonso 6-enero-201513-enero-2015

Enunciado

Definir la función

   cuadrados :: Int -> Picture

1	cuadrados :: Int -> Picture

tal que (cuadrados n) dibuje n cuadrados encajados como se muestra en las siguientes figuras:

para n=2
para n=4
para n=10

Nota: Escribir las soluciones usando la siguiente plantilla

import Graphics.Gloss
import System.IO
    
main :: IO ()
main = do
  hSetBuffering stdout NoBuffering
  putStr "Introduce el numero de cuadrados [1..10]: "
  n <- readLn
  display (InWindow (show n ++ " cuadrados encajados" ) 
                    (600,600) (20,20)) white (cuadrados n)
    
cuadrados :: Int -> Picture
cuadrados n = undefined

import Graphics.Gloss

import System.IO

main :: IO ()

main = do

hSetBuffering stdout NoBuffering

putStr "Introduce el numero de cuadrados [1..10]: "

n <- readLn

display (InWindow (show n ++ " cuadrados encajados" )

(600,600) (20,20)) white (cuadrados n)

cuadrados :: Int -> Picture

cuadrados n = undefined

Soluciones

import Graphics.Gloss
import System.IO
    
main :: IO ()
main = do
  hSetBuffering stdout NoBuffering
  putStr "Introduce el numero de cuadrados [1..10]: "
  n <- readLn
  display (InWindow (show n ++ " cuadrados encajados" ) 
                    (600,600) (20,20)) white (cuadrados n)
    
-- 1ª solución (por comprensión):    
cuadrados :: Int -> Picture
cuadrados n = 
    pictures [scale (r^n) (r^n) $ rotate (g n) $ cuadrado | n <- [0..n-1]]
    where cuadrado        = rectangleWire 500 500
          g n | even n    = 0
              | otherwise = 45
          r               = 1 / sqrt 2

-- 2ª solución (por recursión):    
cuadrados2 :: Int -> Picture
cuadrados2 1 = rectangleWire 500 500
cuadrados2 n = 
    pictures [rectangleWire 500 500,
              rotate 45 $ scale (1/sqrt 2) (1/sqrt 2) (cuadrados2 (n-1))]

import Graphics.Gloss

import System.IO

main :: IO ()

main = do

hSetBuffering stdout NoBuffering

putStr "Introduce el numero de cuadrados [1..10]: "

n <- readLn

display (InWindow (show n ++ " cuadrados encajados" )

(600,600) (20,20)) white (cuadrados n)

-- 1ª solución (por comprensión):

cuadrados :: Int -> Picture

cuadrados n =

pictures [scale (r^n) (r^n) $ rotate (g n) $ cuadrado | n <- [0..n-1]]

where cuadrado = rectangleWire 500 500

g n | even n = 0

| otherwise = 45

r = 1 / sqrt 2

-- 2ª solución (por recursión):

cuadrados2 :: Int -> Picture

cuadrados2 1 = rectangleWire 500 500

cuadrados2 n =

pictures [rectangleWire 500 500,

rotate 45 $ scale (1/sqrt 2) (1/sqrt 2) (cuadrados2 (n-1))]

2015 y los números con factorización capicúa

PorJosé A. Alonso 1-enero-20151-mayo-2016

Un número tiene factorización capicúa si puede escribir como un producto de números primos tal que la concatenación de sus dígitos forma un número capicúa. Por ejemplo, el 2015 tiene factorización capicúa ya que 2015 = 13·5·31, los factores son primos y su concatenación es 13531 que es capicúa.

Definir la sucesión

   conFactorizacionesCapicuas :: [Int]

1	conFactorizacionesCapicuas :: [Int]

formada por los números que tienen factorización capicúa. Por ejemplo,

   ghci> take 20 conFactorizacionesCapicuas
   [1,2,3,4,5,7,8,9,11,12,16,18,20,25,27,28,32,36,39,44]

1 2	ghci> take 20 conFactorizacionesCapicuas [1,2,3,4,5,7,8,9,11,12,16,18,20,25,27,28,32,36,39,44]

Usando conFactorizacionesCapicuas escribir expresiones cuyos valores sean las respuestas a las siguientes preguntas y calcularlas

¿Qué lugar ocupa el 2015 en la sucesión?
¿Cuál fue el anterior año con factorización capicúa?
¿Cuál será el siguiente año con factorización capicúa?

Soluciones

import Data.List (permutations)

conFactorizacionesCapicuas :: [Int]
conFactorizacionesCapicuas =
    [n | n <- [1..], not (null (factorizacionesCapicua n))]

-- (factorizacionesCapicua n) es la lista de las factorizaciones
-- capicúas de n. Por ejemplo,
--    factorizacionesCapicua 2015  ==  [[13,5,31],[31,5,13]]
factorizacionesCapicua :: Int -> [[Int]]
factorizacionesCapicua n =
    [xs | xs <- permutations (factorizacion n),
          esCapicuaConcatenacion xs]

-- (factorizacion n) es la lista de todos los factores primos de n; es
-- decir, es una lista de números primos cuyo producto es n. Por ejemplo,
--    factorizacion 300  ==  [2,2,3,5,5]
factorizacion :: Int -> [Int]
factorizacion n | n == 1    = []
                | otherwise = x : factorizacion (div n x)
    where x = menorFactor n

-- (menorFactor n) es el menor factor primo de n. Por ejemplo,
--    menorFactor 15  ==  3
--    menorFactor 16  ==  2
--    menorFactor 17  == 17
menorFactor :: Int -> Int
menorFactor n = head [x | x <- [2..], rem n x == 0]

-- (esCapicuaConcatenacion xs) se verifica si la concatenación de los
-- números de xs es capicúa. Por ejemplo,
--    esCapicuaConcatenacion [13,5,31]   ==  True
--    esCapicuaConcatenacion [135,31]    ==  True
--    esCapicuaConcatenacion [135,21]    ==  False
esCapicuaConcatenacion :: [Int] -> Bool
esCapicuaConcatenacion xs = ys == reverse ys
    where ys = concat (map show xs)

-- El cálculo de la 1ª respuesta es
--    ghci> length (takeWhile (<= 2015) conFactorizacionesCapicuas)
--    265

-- El cálculo de la 2ª respuesta es
--    ghci> last (takeWhile (<2015) conFactorizacionesCapicuas)
--    2001

-- El cálculo de la 3ª respuesta es
--    ghci> head (dropWhile (<=2015) conFactorizacionesCapicuas)
--    2023

import Data.List (permutations)

conFactorizacionesCapicuas :: [Int]

conFactorizacionesCapicuas =

[n | n <- [1..], not (null (factorizacionesCapicua n))]

-- (factorizacionesCapicua n) es la lista de las factorizaciones

-- capicúas de n. Por ejemplo,

-- factorizacionesCapicua 2015 == [[13,5,31],[31,5,13]]

factorizacionesCapicua :: Int -> [[Int]]

factorizacionesCapicua n =

[xs | xs <- permutations (factorizacion n),

esCapicuaConcatenacion xs]

-- (factorizacion n) es la lista de todos los factores primos de n; es

-- decir, es una lista de números primos cuyo producto es n. Por ejemplo,

-- factorizacion 300 == [2,2,3,5,5]

factorizacion :: Int -> [Int]

factorizacion n | n == 1 = []

| otherwise = x : factorizacion (div n x)

where x = menorFactor n

-- (menorFactor n) es el menor factor primo de n. Por ejemplo,

-- menorFactor 15 == 3

-- menorFactor 16 == 2

-- menorFactor 17 == 17

menorFactor :: Int -> Int

menorFactor n = head [x | x <- [2..], rem n x == 0]

-- (esCapicuaConcatenacion xs) se verifica si la concatenación de los

-- números de xs es capicúa. Por ejemplo,

-- esCapicuaConcatenacion [13,5,31] == True

-- esCapicuaConcatenacion [135,31] == True

-- esCapicuaConcatenacion [135,21] == False

esCapicuaConcatenacion :: [Int] -> Bool

esCapicuaConcatenacion xs = ys == reverse ys

where ys = concat (map show xs)

-- El cálculo de la 1ª respuesta es

-- ghci> length (takeWhile (<= 2015) conFactorizacionesCapicuas)

-- 265

-- El cálculo de la 2ª respuesta es

-- ghci> last (takeWhile (<2015) conFactorizacionesCapicuas)

-- 2001

-- El cálculo de la 3ª respuesta es

-- ghci> head (dropWhile (<=2015) conFactorizacionesCapicuas)

-- 2023

Enumeración de los pares de números naturales

PorJosé A. Alonso 29-diciembre-201425-marzo-2022

Los pares de los números naturales se pueden ordenar por la suma de sus componentes y entre los pares con la misma suma elegir antes al que tiene mayos su primera componente.

Definir la función

   pares :: [(Int,Int)]

1	pares :: [(Int,Int)]

tal que pares es la lista de los pares de números naturales con el orden anterior. por ejemplo,

   ghci> take 10 pares
   [(0,0),(1,0),(0,1),(2,0),(1,1),(0,2),(3,0),(2,1),(1,2),(0,3)]

1 2	ghci> take 10 pares [(0,0),(1,0),(0,1),(2,0),(1,1),(0,2),(3,0),(2,1),(1,2),(0,3)]

Usando la definición de pares, definir la función

   posicion :: (Int,Int) -> Int

1	posicion :: (Int,Int) -> Int

tal que (posicion p) es la posición del par p en la lista pares. Por ejemplo,

   posicion (0,0)  ==  0
   posicion (2,0)  ==  3

1 2	posicion (0,0) == 0 posicion (2,0) == 3

Finalmente, comprobar con QuickCheck que para cualquier par (x,y) de números naturales, la (posicion (x,y)) es igual a (y + (x+y+1)*(x+y) div 2).

Nota. En la comprobación usar

   quickCheckWith (stdArgs {maxSize=7}) prop_posicion

1	quickCheckWith (stdArgs {maxSize=7}) prop_posicion

Soluciones

import Test.QuickCheck

pares :: [(Int,Int)]
pares = [(n-y,y) | n <- [0..], y <- [0..n]] 

posicion :: (Int,Int) -> Int
posicion p = length (takeWhile (/=p) pares)

-- La propiedad es
prop_posicion :: (Int,Int) -> Property
prop_posicion (x,y) =
    x >= 0 && y >= 0 ==> 
    posicion (x,y) == y + (x+y+1)*(x+y) `div` 2

-- La comprobación es
--    ghci> quickCheckWith (stdArgs {maxSize=7}) prop_posicion
--    +++ OK, passed 100 tests.

import Test.QuickCheck

pares :: [(Int,Int)]

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

posicion :: (Int,Int) -> Int

posicion p = length (takeWhile (/=p) pares)

-- La propiedad es

prop_posicion :: (Int,Int) -> Property

prop_posicion (x,y) =

x >= 0 && y >= 0 ==>

posicion (x,y) == y + (x+y+1)*(x+y) `div` 2

-- La comprobación es

-- ghci> quickCheckWith (stdArgs {maxSize=7}) prop_posicion

-- +++ OK, passed 100 tests.

Particiones en listas de segmentos

Exercitium

Soluciones

Sustitución de listas

Soluciones

Triparticiones de una lista

Soluciones

Listas con suma dada

Soluciones

Ordenación según una función

Soluciones

Máxima suma de los segmentos

Soluciones

Referencias

2015 y los números pitagóricos

Soluciones

Varios cuadrados encajados

Enunciado

Soluciones

2015 y los números con factorización capicúa

Soluciones

Enumeración de los pares de números naturales

Soluciones

Entradas recientes

Buscar

Correo electrónico