Avanzado

Fractal de la curva del dragón

PorJosé A. Alonso 18-diciembre-201427-diciembre-2014

La curva del dragón es un fractal que se construye siguiendo los siguientes pasos:

A partir de un segmento, se construye el triángulo rectángulo e isósceles, como lo muestra las dos primeras figuras. Luego se borra el segmento inicial.
Se repite varias veces el proceso de remplazar un segmento por otros dos para cada línea de la curva, alternando siempre la orientación de los triángulos.

La siguiente figura muestra los trece primeros pasos:

El ejercicio consiste en definir (en CodeWorld) la función

   dragon :: Number -> Picture

1	dragon :: Number -> Picture

tal que dragon(n) es el dibujo correspondiente al paso n de la construcción de la curva del dragón. Por ejemplo, el dibujo de dragon(20) es

Comentarios

La descripción de la curva dragón es la que se encuentra en el artículo de la Wikipedia.
Una definición análoga es la del fractal de la curva de Koch.

Soluciones

main = pictureOf(translate(dragon(20), 1, -2))

dragon :: Number -> Picture
dragon(0) = line[(-6, 0), (6, 0)]
dragon(n) = translate(rotate(sub, 45),  -3, 3) &
            translate(rotate(sub, 135), 3, 3)
  where sub = scale(dragon(n-1), 1 / sqrt(2), 1 / sqrt(2))

main = pictureOf(translate(dragon(20), 1, -2))

dragon :: Number -> Picture

dragon(0) = line[(-6, 0), (6, 0)]

dragon(n) = translate(rotate(sub, 45), -3, 3) &

translate(rotate(sub, 135), 3, 3)

where sub = scale(dragon(n-1), 1 / sqrt(2), 1 / sqrt(2))

Juego de bloques con letras

PorJosé A. Alonso 12-diciembre-201425-abril-2021

Introducción

Para el juego de los bloques se dispone de un conjunto de bloques con una letra en cada una de sus dos caras. El objetivo del juego consiste en formar palabras sin que se pueda usar un bloque más de una vez y sin diferenciar mayúsculas de minúsculas. Por ejemplo, si se tiene tres bloques de forma que el 1º tiene las letras A y B, el 2ª la N y la O y el 3º la O y la A entonces se puede obtener la palabra ANA de dos formas: una con los bloques 1, 2 y 3 y otra con los 3, 2 y 1.

Enunciado

-- Definir la función 
--    soluciones :: [String] -> String -> [[String]]
-- tal que (soluciones bs cs) es la lista de las soluciones del juego de
-- los bloque usando los bloques bs (cada bloque es una cadena de dos
-- letras mayúsculas) para formar la palabra cs. Por ejemplo,
--    ghci> soluciones ["AB","NO","OA"] "ANA"
--    [["AB","NO","OA"],["OA","NO","AB"]]
--    ghci> soluciones ["AB","NE","OA"] "Bea"
--    [["AB","NE","OA"]]
--    ghci> soluciones ["AB","NE","OA"] "EvA"
--    []
--    ghci> soluciones ["AB","NO","OA","NC"] "ANA"
--    [["AB","NO","OA"],["AB","NC","OA"],["OA","NO","AB"],["OA","NC","AB"]]
--    ghci> soluciones ["AB","NO","OA","NC"] "Anca"
--    [["AB","NO","NC","OA"],["OA","NO","NC","AB"]]

-- Definir la función

-- soluciones :: [String] -> String -> [[String]]

-- tal que (soluciones bs cs) es la lista de las soluciones del juego de

-- los bloque usando los bloques bs (cada bloque es una cadena de dos

-- letras mayúsculas) para formar la palabra cs. Por ejemplo,

-- ghci> soluciones ["AB","NO","OA"] "ANA"

-- [["AB","NO","OA"],["OA","NO","AB"]]

-- ghci> soluciones ["AB","NE","OA"] "Bea"

-- [["AB","NE","OA"]]

-- ghci> soluciones ["AB","NE","OA"] "EvA"

-- []

-- ghci> soluciones ["AB","NO","OA","NC"] "ANA"

-- [["AB","NO","OA"],["AB","NC","OA"],["OA","NO","AB"],["OA","NC","AB"]]

-- ghci> soluciones ["AB","NO","OA","NC"] "Anca"

-- [["AB","NO","NC","OA"],["OA","NO","NC","AB"]]

Soluciones

import Data.List (delete)
import Data.Char (toUpper)

soluciones :: [String] -> String -> [[String]]
soluciones _ []      = [[]]
soluciones bs (c:cs) = [b:rs | b <- bs, 
                               toUpper c `elem` b,
                               rs <- soluciones (delete b bs) cs]

import Data.List (delete)

import Data.Char (toUpper)

soluciones :: [String] -> String -> [[String]]

soluciones _ [] = [[]]

soluciones bs (c:cs) = [b:rs | b <- bs,

toUpper c `elem` b,

rs <- soluciones (delete b bs) cs]

Normalización de expresiones aritméticas

PorJosé A. Alonso 10-diciembre-201425-abril-2021

Enunciado

-- El siguiente tipo de dato representa expresiones construidas con
-- variables, sumas y productos
--    data Expr = V String
--              | S Expr Expr
--              | P Expr Expr
--              deriving (Eq, Show)
-- Por ejemplo, x*(y+z) se representa por (P (V "x") (S (V "y") (V "z"))) 
-- 
-- Una expresión es un término si es un producto de variables. Por
-- ejemplo, x*(y*z) es un término pero x+(y*z) ni x*(y+z) lo son.
--
-- Una expresión está en forma normal si es una suma de términos. Por
-- ejemplo, x*(y*z) y x+(y*z) está en forma normal; pero x*(y+z) y
-- (x+y)*(x+z) no lo están. 
-- 
-- Definir la función 
--    normal :: Expr -> Expr
-- tal que (normal e) es la forma normal de la expresión e obtenida
-- aplicando, mientras que sea posible, las propiedades distributivas:
--    (a+b)*c = a*c+b*c
--    c*(a+b) = c*a+c*b
-- Por ejemplo,
--    ghci> normal (P (S (V "x") (V "y")) (V "z"))
--    S (P (V "x") (V "z")) (P (V "y") (V "z"))
--    ghci> normal (P (V "z") (S (V "x") (V "y")))
--    S (P (V "z") (V "x")) (P (V "z") (V "y"))
--    ghci> normal (P (S (V "x") (V "y")) (S (V "u") (V "v")))
--    S (S (P (V "x") (V "u")) (P (V "x") (V "v"))) 
--      (S (P (V "y") (V "u")) (P (V "y") (V "v")))
--    ghci> normal (S (P (V "x") (V "y")) (V "z"))
--    S (P (V "x") (V "y")) (V "z")
--    ghci> normal (V "x")
--    V "x"
--
-- Comprobar con QuickCheck (usando la función esNormal del ejercicio
-- del 2 de diciembre) que para cualquier expresión e, (normal e) está en
-- forma normal y que (normal (normal e)) es igual a (normal e).
--
-- Nota. Para la comprobación se usará el siguiente generador de
-- expresiones aritméticas:
--    instance Arbitrary Expr where
--        arbitrary = sized arb 
--            where
--              arb 0          =  liftM V arbitrary
--              arb n | n > 0  =  oneof [liftM V arbitrary,
--                                       liftM2 S sub sub, 
--                                       liftM2 P sub sub] 
--                    where sub = arb (n `div` 2)

-- El siguiente tipo de dato representa expresiones construidas con

-- variables, sumas y productos

-- data Expr = V String

-- | S Expr Expr

-- | P Expr Expr

-- deriving (Eq, Show)

-- Por ejemplo, x*(y+z) se representa por (P (V "x") (S (V "y") (V "z")))

-- Una expresión es un término si es un producto de variables. Por

-- ejemplo, x*(y*z) es un término pero x+(y*z) ni x*(y+z) lo son.

-- Una expresión está en forma normal si es una suma de términos. Por

-- ejemplo, x*(y*z) y x+(y*z) está en forma normal; pero x*(y+z) y

-- (x+y)*(x+z) no lo están.

-- Definir la función

-- normal :: Expr -> Expr

-- tal que (normal e) es la forma normal de la expresión e obtenida

-- aplicando, mientras que sea posible, las propiedades distributivas:

-- (a+b)*c = a*c+b*c

-- c*(a+b) = c*a+c*b

-- Por ejemplo,

-- ghci> normal (P (S (V "x") (V "y")) (V "z"))

-- S (P (V "x") (V "z")) (P (V "y") (V "z"))

-- ghci> normal (P (V "z") (S (V "x") (V "y")))

-- S (P (V "z") (V "x")) (P (V "z") (V "y"))

-- ghci> normal (P (S (V "x") (V "y")) (S (V "u") (V "v")))

-- S (S (P (V "x") (V "u")) (P (V "x") (V "v")))

-- (S (P (V "y") (V "u")) (P (V "y") (V "v")))

-- ghci> normal (S (P (V "x") (V "y")) (V "z"))

-- S (P (V "x") (V "y")) (V "z")

-- ghci> normal (V "x")

-- V "x"

-- Comprobar con QuickCheck (usando la función esNormal del ejercicio

-- del 2 de diciembre) que para cualquier expresión e, (normal e) está en

-- forma normal y que (normal (normal e)) es igual a (normal e).

-- Nota. Para la comprobación se usará el siguiente generador de

-- expresiones aritméticas:

-- instance Arbitrary Expr where

-- arbitrary = sized arb

-- where

-- arb 0 = liftM V arbitrary

-- arb n | n > 0 = oneof [liftM V arbitrary,

-- liftM2 S sub sub,

-- liftM2 P sub sub]

-- where sub = arb (n `div` 2)

Soluciones

import Test.QuickCheck
import Control.Monad

data Expr = V String
          | S Expr Expr
          | P Expr Expr
          deriving (Eq, Show)

esTermino :: Expr -> Bool
esTermino (V _)   = True
esTermino (S _ _) = False
esTermino (P a b) = esTermino a && esTermino b

esNormal :: Expr -> Bool
esNormal (S a b) = esNormal a && esNormal b
esNormal a       = esTermino a

normal :: Expr -> Expr
normal (V v)   = V v
normal (S a b) = S (normal a) (normal b)
normal (P a b) = p (normal a) (normal b)
    where p (S a b) c = S (p a c) (p b c)
          p a (S b c) = S (p a b) (p a c)
          p a b       = P a b

prop_normal :: Expr -> Bool
prop_normal e = 
    esNormal (normal e) && normal (normal e) == normal e

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

instance Arbitrary Expr where
    arbitrary = sized arb 
        where
          arb 0          =  liftM V arbitrary
          arb n | n > 0  =  oneof [liftM V arbitrary,
                                   liftM2 S sub sub, 
                                   liftM2 P sub sub] 
                where sub = arb (n `div` 2)

import Test.QuickCheck

import Control.Monad

data Expr = V String

| S Expr Expr

| P Expr Expr

deriving (Eq, Show)

esTermino :: Expr -> Bool

esTermino (V _) = True

esTermino (S _ _) = False

esTermino (P a b) = esTermino a && esTermino b

esNormal :: Expr -> Bool

esNormal (S a b) = esNormal a && esNormal b

esNormal a = esTermino a

normal :: Expr -> Expr

normal (V v) = V v

normal (S a b) = S (normal a) (normal b)

normal (P a b) = p (normal a) (normal b)

where p (S a b) c = S (p a c) (p b c)

p a (S b c) = S (p a b) (p a c)

p a b = P a b

prop_normal :: Expr -> Bool

prop_normal e =

esNormal (normal e) && normal (normal e) == normal e

-- La comprobación es

-- ghci> quickCheck prop_normal

-- +++ OK, passed 100 tests.

instance Arbitrary Expr where

arbitrary = sized arb

where

arb 0 = liftM V arbitrary

arb n | n > 0 = oneof [liftM V arbitrary,

liftM2 S sub sub,

liftM2 P sub sub]

where sub = arb (n `div` 2)

Particiones de longitud fija

PorJosé A. Alonso 28-noviembre-201425-abril-2021

Enunciado

-- Definir la función 
--    particionesFijas :: Int -> Int -> [[Int]]
-- tal que (particionesFijas n k) es la lista de listas de k números
-- naturales no crecientes cuya suma es n. Por ejemplo,
--    ghci> particionesFijas 8 3
--    [[3,3,2],[4,2,2],[4,3,1],[5,2,1],[6,1,1]]

-- Definir la función

-- particionesFijas :: Int -> Int -> [[Int]]

-- tal que (particionesFijas n k) es la lista de listas de k números

-- naturales no crecientes cuya suma es n. Por ejemplo,

-- ghci> particionesFijas 8 3

-- [[3,3,2],[4,2,2],[4,3,1],[5,2,1],[6,1,1]]

Soluciones

-- 1ª definición
particionesFijas :: Int -> Int -> [[Int]]
particionesFijas n 1 = [[n]]
particionesFijas n k 
    | k < 1     = []
    | otherwise = [x:y:ys | x <- [1..n-1], 
                            (y:ys) <- particionesFijas (n-x) (k-1),
                            x >= y]

-- 2ª definición
particionesFijas2 :: Int -> Int -> [[Int]]
particionesFijas2 n k
    | k <= 0    = []
    | k == 1    = [[n]]
    | k == n    = [replicate k 1]
    | k > n     = []
    | otherwise = [xs ++ [1] | xs <- particionesFijas2 (n-1) (k-1)] ++
                  [[x+1 | x <- xs] | xs <- particionesFijas2 (n-k) k]

-- Comparación:
--    ghci> length (particionesFijas 800 3)
--    53333
--    (1.01 secs, 97696476 bytes)
--    
--    ghci> length (particionesFijas2 800 3)
--    53333
--    (4.52 secs, 693969028 bytes)

-- 1ª definición

particionesFijas :: Int -> Int -> [[Int]]

particionesFijas n 1 = [[n]]

particionesFijas n k

| k < 1 = []

| otherwise = [x:y:ys | x <- [1..n-1],

(y:ys) <- particionesFijas (n-x) (k-1),

x >= y]

-- 2ª definición

particionesFijas2 :: Int -> Int -> [[Int]]

particionesFijas2 n k

| k <= 0 = []

| k == 1 = [[n]]

| k == n = [replicate k 1]

| k > n = []

| otherwise = [xs ++ [1] | xs <- particionesFijas2 (n-1) (k-1)] ++

[[x+1 | x <- xs] | xs <- particionesFijas2 (n-k) k]

-- Comparación:

-- ghci> length (particionesFijas 800 3)

-- 53333

-- (1.01 secs, 97696476 bytes)

-- ghci> length (particionesFijas2 800 3)

-- 53333

-- (4.52 secs, 693969028 bytes)

Máximo de una función

PorJosé A. Alonso 4-noviembre-201427-diciembre-2014

Enunciado

-- Se considera la siguiente función
--    g :: Integer -> Integer
--    g n = if n < 10 then n*n else n
-- 
-- Definir la función 
--    max_g :: Integer -> Integer
-- tal que (max_g n) es el punto i del intervalo [0,n] donde g alcanza
-- el máximo de sus valores, si n es positivo y 0 en caso contrario. Por
-- ejemplo,
--    max_g (-7)  ==  0
--    max_g 7     ==  7
--    max_g 14    ==  9
--    max_g 84    ==  84
-- 
-- Comprobar con QuickCheck que la función max_g es equivalente a la
-- función f definida por  
--    f :: Integer -> Integer
--    f n | n < 0             = 0
--        | n >= 10 && n < 81 = 9
--        | otherwise         = n
--
-- Nota: Se piden dos definiciones de max_g, una por comprensión y otra
-- por recursión.

-- Se considera la siguiente función

-- g :: Integer -> Integer

-- g n = if n < 10 then n*n else n

-- Definir la función

-- max_g :: Integer -> Integer

-- tal que (max_g n) es el punto i del intervalo [0,n] donde g alcanza

-- el máximo de sus valores, si n es positivo y 0 en caso contrario. Por

-- ejemplo,

-- max_g (-7) == 0

-- max_g 7 == 7

-- max_g 14 == 9

-- max_g 84 == 84

-- Comprobar con QuickCheck que la función max_g es equivalente a la

-- función f definida por

-- f :: Integer -> Integer

-- f n | n < 0 = 0

-- | n >= 10 && n < 81 = 9

-- | otherwise = n

-- Nota: Se piden dos definiciones de max_g, una por comprensión y otra

-- por recursión.

Soluciones

import Test.QuickCheck

g :: Integer -> Integer
g n = if n < 10 then n*n else n

-- 1ª definición (por comprensión):
max_gC :: Integer -> Integer
max_gC n | n < 0     = 0 
         | otherwise = snd (maximum [(g i,i) | i <- [0..n]])

-- 2ª definición (por recursión):
max_gR :: Integer -> Integer
max_gR n | n < 0      = 0
         | g m > g n  = m 
         | otherwise  = n
         where m = max_gR (n - 1)

f :: Integer -> Integer
f n | n < 0             = 0
    | n >= 10 && n < 81 = 9
    | otherwise         = n

-- La propiedad con max_gR es
prop_max_gR n = max_gR n == f n

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

-- La propiedad con max_gC es
prop_max_gC n = max_gC n == f n

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

import Test.QuickCheck

g :: Integer -> Integer

g n = if n < 10 then n*n else n

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

max_gC :: Integer -> Integer

max_gC n | n < 0 = 0

| otherwise = snd (maximum [(g i,i) | i <- [0..n]])

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

max_gR :: Integer -> Integer

max_gR n | n < 0 = 0

| g m > g n = m

| otherwise = n

where m = max_gR (n - 1)

f :: Integer -> Integer

f n | n < 0 = 0

| n >= 10 && n < 81 = 9

| otherwise = n

-- La propiedad con max_gR es

prop_max_gR n = max_gR n == f n

-- La comprobación es

-- ghci> quickCheck prop_max_gR

-- +++ OK, passed 100 tests.

-- La propiedad con max_gC es

prop_max_gC n = max_gC n == f n

-- La comprobación es

-- ghci> quickCheck prop_max_gC

-- +++ OK, passed 100 tests.

Fractal de la curva del dragón

Comentarios

Soluciones

Juego de bloques con letras

Introducción

Enunciado

Soluciones

Normalización de expresiones aritméticas

Enunciado

Soluciones

Particiones de longitud fija

Enunciado

Soluciones

Máximo de una función

Enunciado

Soluciones

Entradas recientes

Buscar

Correo electrónico