Antiimágenes de funciones crecientes bidimensionales

José A. Alonso

05-04-2021

Una función f de pares de números naturales en números naturales es estrictamente creciente en ambos argumentos si

para x1 < x2, se tiene f(x1,y) < f(x1,y), para todo y y
para y1 < y2, se tiene f(x,y1) < f(x,y2), para todo x.

Por ejemplo, la función f definida por f(x,y) = x^2+3^y escreciente en ambos argumentos.

Las antiimágenes por f de t son los pares (x,y) tales que f(x,y) = t. Por ejemplo, las antimágenes por f(x,y) = x^2+3^y de 82 son los pares (1,4) y (9,0).

Definir la función

   antiimagenes :: Integral a => ((a,a) -> a) -> a -> [(a,a)]

tal que (antiimagenes f t) es la lista de las antiimágenes por f de t, donde se supone que f es una función de pares de números naturales en números naturales que es estrictamente creciente en ambos argumentos. Por ejemplo,

   antiimagenes (\(x,y) -> x^2+3^y) 82        ==  [(1,4),(9,0)]
   antiimagenes (\(x,y) -> x^2+3^y) 387421785 == [(36,18)]

Soluciones

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

antiimagenes :: Integral a => ((a,a) -> a) -> a -> [(a,a)]
antiimagenes f t =
  [(x,y) | x <- [0..t], y <- [0..t ], f (x,y) == t]

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

antiimagenes2 :: Integral a => ((a,a) -> a) -> a -> [(a,a)]
antiimagenes2 f t = antiimagenesEn (0,t)
  where antiimagenesEn (a,b) = [(x,y) | x <- [a..t], y <- [b,b-1..0], f (x,y) == t]

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

antiimagenes3 :: Integral a => ((a,a) -> a) -> a -> [(a,a)]
antiimagenes3 f t = antiimagenesEn (0,t)
  where antiimagenesEn (a,b)
          | a > t || b < 0 = []
          | c < t          = antiimagenesEn (a+1,b)
          | c == t         = (a,b) : antiimagenesEn (a+1,b-1)
          | c > t          = antiimagenesEn (a,b-1)
          where c = f (a,b)

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

antiimagenes4 :: Integral a => ((a,a) -> a) -> a -> [(a,a)]
antiimagenes4 f t = desde (0,p) (q,0) where
  p = menor (-1,t) (\ y -> f (0,y)) t
  q = menor (-1,t) (\ x -> f (x,0)) t
  desde (x1,y1) (x2,y2)
    | x2 < x1 || y1 < y2 = []
    | y1 - y <= x2 - x1  = fila x
    | otherwise          = columna y
    where
      x = menor (x1-1,x2) (\ x -> f (x,r)) t
      y = menor (y2-1,y1) (\ y -> f (c,y)) t
      c = (x1 + x2) `div` 2
      r = (y1 + y2) `div` 2
      fila x
        | z < t  = desde (x1,y1) (x2,r+1)
        | z == t = (x,r) : desde (x1,y1) (x-1,r+1) ++ desde (x+1,r-1) (x2,y2)
        | z > t  = desde (x1,y1) (x-1,r+1) ++ desde (x,r-1) (x2,y2)
        where z = f (x,r)
      columna y
        | z < t  = desde (c+1,y1) (x2,y2)
        | z == t = (c,y) : desde (x1,y1) (c-1,y+1) ++ desde (c+1,y-1) (x2,y2)
        | z > t  = desde (x1,y1) (c-1,y) ++ desde (c+1,y-1) (x2,y2)
        where z = f (c, y)


-- (menor (a,b) f t), suponiendo que t <= f b, es el menor x enel
-- intervalo (a,b] tal que t <= f x.
menor :: Integral a => (a,a) -> (a -> a) -> a -> a
menor (a,b) f t
  | a + 1 == b = b
  | t <= f m   = menor (a, m) f t
  | otherwise  = menor (m, b) f t
  where m = (a + b) `div` 2

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

-- La comparación es
--    λ> antiimagenes (\(x,y) -> x^2+3^y) 2383
--    [(14,7)]
--    (15.63 secs, 26,904,500,208 bytes)
--    λ> antiimagenes2 (\(x,y) -> x^2+3^y) 2383
--    [(14,7)]
--    (16.37 secs, 26,950,312,440 bytes)
--    λ> antiimagenes3 (\(x,y) -> x^2+3^y) 2383
--    [(14,7)]
--    (0.03 secs, 11,892,160 bytes)
--    λ> antiimagenes4 (\(x,y) -> x^2+3^y) 2383
--    [(14,7)]
--    (0.01 secs, 277,696 bytes)
--
--    λ> antiimagenes3 (\(x,y) -> x^2+3^y) 59449
--    [(20,10)]
--    (3.77 secs, 1,329,803,208 bytes)
--    λ> antiimagenes4 (\(x,y) -> x^2+3^y) 59449
--    [(20,10)]
--    (0.03 secs, 400,400 bytes)