Menu Close

Conjuntos de puntos enteros en regiones rectangulares

Los puntos de una cuadrícula se puede representar mediante pares de números enteros

   type Punto = (Int,Int)

y las regiones rectangulares mediante el siguiente tipo de dato

   data Region = Rectangulo Punto  Punto 
               | Union      Region Region
               | Diferencia Region Region
               deriving (Eq, Show)

donde

  • (Rectangulo p1 p2) es la región formada por un rectángulo cuyo vértice superior izquierdo es p1 y su vértice inferior derecho es p2.
  • (Union r1 r2) es la región cuyos puntos pertenecen a alguna de las regiones r1 y r2.
  • (Diferencia r1 r2) es la región cuyos puntos pertenecen a la región r1 pero no pertenecen a la r2.

Definir la función

   puntos :: Region -> [Punto]

tal que (puntos r) es la lista de puntos de la región r. Por ejemplo, usando las regiones definidas por

   r0021, r3051, r4162 :: Region
   r0021 = Rectangulo (0,0) (2,1)
   r3051 = Rectangulo (3,0) (5,1)
   r4162 = Rectangulo (4,1) (6,2)

se tiene

   ghci> puntos r0021
   [(0,0),(0,1),(1,0),(1,1),(2,0),(2,1)]
   ghci> puntos r3051
   [(3,0),(3,1),(4,0),(4,1),(5,0),(5,1)]
   ghci> puntos r4162
   [(4,1),(4,2),(5,1),(5,2),(6,1),(6,2)]
   ghci> puntos (Union r0021 r3051)
   [(0,0),(0,1),(1,0),(1,1),(2,0),(2,1),(3,0),(3,1),(4,0),(4,1),(5,0),(5,1)]
   ghci> puntos (Diferencia r3051 r4162)
   [(3,0),(3,1),(4,0),(5,0)]
   ghci> puntos (Union (Diferencia r3051 r4162) r4162)
   [(3,0),(3,1),(4,0),(5,0),(4,1),(4,2),(5,1),(5,2),(6,1),(6,2)]

Comprobar con QuickCheck, usando la función enRegion definida en el ejercicio [Puntos en regiones rectangulares](Puntos en regiones rectangulares) que (enRegion p r) es equivalente a (p elem puntos r).

Nota: Escribir las soluciones usando la siguiente plantilla que contiene un generador de regiones

import Test.QuickCheck
import Control.Monad
 
type Punto = (Int,Int)
 
data Region = Rectangulo Punto  Punto
            | Union      Region Region
            | Diferencia Region Region
            deriving (Eq, Show)
 
r0021, r3051, r4162 :: Region
r0021 = Rectangulo (0,0) (2,1)
r3051 = Rectangulo (3,0) (5,1)
r4162 = Rectangulo (4,1) (6,2)
 
puntos :: Region -> [Punto]
puntos = undefined
 
-- La propiedad es
prop_puntos :: Punto -> Region -> Bool
prop_puntos p r = undefined
 
-- La comprobación es
--    ghci> quickCheckWith (stdArgs {maxSize=7}) prop_puntos
--    +++ OK, passed 100 tests.
 
enRegion :: Punto -> Region -> Bool
enRegion (x,y) (Rectangulo (x1,y1) (x2,y2)) =
    x1 <= x && x <= x2 && y1 <= y && y <= y2
enRegion p (Union r1 r2)      = enRegion p r1 || enRegion p r2
enRegion p (Diferencia r1 r2) = enRegion p r1 && not (enRegion p r2)
 
-- Generador de regiones:
instance Arbitrary Region where
    arbitrary = sized arb where
        arb 0         = liftM2 Rectangulo arbitrary arbitrary
        arb n | n > 0 = oneof [liftM2 Rectangulo arbitrary arbitrary,
                               liftM2 Union sub sub, 
                               liftM2 Diferencia sub sub] 
              where sub = arb (n `div` 2)

Soluciones

import Data.List 
import Test.QuickCheck
import Control.Monad
 
type Punto = (Int,Int)
 
data Region = Rectangulo Punto  Punto
            | Union      Region Region
            | Diferencia Region Region
            deriving (Eq, Show)
 
r0021, r3051, r4162 :: Region
r0021 = Rectangulo (0,0) (2,1)
r3051 = Rectangulo (3,0) (5,1)
r4162 = Rectangulo (4,1) (6,2)
 
puntos :: Region -> [Punto]
puntos (Rectangulo (x1,y1) (x2,y2)) = 
    [(x,y) | x <- [x1..x2], y <- [y1..y2]]
puntos (Union r1 r2)      = puntos r1 `union` puntos r2
puntos (Diferencia r1 r2) = puntos r1 \\ puntos r2
 
-- La propiedad es
prop_puntos :: Punto -> Region -> Bool
prop_puntos p r =
    enRegion p r == (p `elem` puntos r)
 
-- La comprobación es
--    ghci> quickCheckWith (stdArgs {maxSize=7}) prop_puntos
--    +++ OK, passed 100 tests.
 
enRegion :: Punto -> Region -> Bool
enRegion (x,y) (Rectangulo (x1,y1) (x2,y2)) =
    x1 <= x && x <= x2 && y1 <= y && y <= y2
enRegion p (Union r1 r2)      = enRegion p r1 || enRegion p r2
enRegion p (Diferencia r1 r2) = enRegion p r1 && not (enRegion p r2)
 
-- Generador de regiones:
instance Arbitrary Region where
    arbitrary = sized arb where
        arb 0         = liftM2 Rectangulo arbitrary arbitrary
        arb n | n > 0 = oneof [liftM2 Rectangulo arbitrary arbitrary,
                               liftM2 Union sub sub, 
                               liftM2 Diferencia sub sub] 
              where sub = arb (n `div` 2)

2 soluciones de “Conjuntos de puntos enteros en regiones rectangulares

  1. Rafael González
    puntos :: Region -> [Punto]
    puntos (Rectangulo (x1,y1) (x2,y2)) = 
        [p | s <- [y1..y2], p <- zip [x1..x2] (repeat s)] 
    puntos (Union r1 r2) = 
        puntos r1 ++ [p | p <- puntos r2, enRegion p (Diferencia r2 r1)] 
    puntos (Diferencia r1 r2) = 
        [x | x <- puntos r1, enRegion x (Diferencia r1 r2)] 
     
    -- La propiedad es
    prop_puntos :: Punto -> Region -> Bool
    prop_puntos p r = enRegion p r == elem p (puntos r)
  2. M Miranda
    puntos :: Region -> [Punto]
    puntos (Rectangulo p1 p2) = [(x,y)|x<-[a..c],y<-[b..d]]
        where (a,b) = p1
              (c,d) = p2                              
    puntos (Union r1 r2)      = union (puntos r1) (puntos r2)
    puntos (Diferencia r1 r2) = puntos r1 \ puntos r2
     
    -- La propiedad es
    prop_puntos :: Punto -> Region -> Bool
    prop_puntos p r = elem p (puntos r) ==> enRegion p r

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.